A method for simultaneous minimal-cost supply node location and network design in pipelined infrastructure.

Designing low-cost infrastructure networks for transport of hydrogen represents a key step in the adoption and penetration of hydrogen technology in a low-carbon energy future.

For hydrogen distribution, network design amounts to creating pipeline systems in which supply is matched to demand through a transportation system that respects multiple constraints (technical, social, environmental) and minimizes cost. This can equate to recycling pre-existing pipelines or building new ones, but also involves the placement of carefully chosen supply nodes.

In a multi-level distribution network, supply nodes may assume many roles from large-capacity geological storage facilities, to local relay nodes addressing the end customers.

Finding minimum-cost pipeline network designs in which supply node locations are already chosen is itself a well-studied combinatorial optimization problem (Cayley’s formula predicts  possible spanning trees for  nodes) for which multiple heuristic and exact methods are known [1].

Allowing the supply node to take any position within the network renders the problem significantly more complex as the minimum-cost network topology (the specific connections to between nodes) will potentially change for each new supply node position.

We propose a heuristic algorithm that finds good solutions in a reasonable amount of time based on a back-and-forth between:

- Repositioning optimally the supply node, while maintaining the same connections to the supply node (reduces cost)

- Optimizing the network topology, assuming a fixed supply node position (also reduces cost)

The algorithm stops once no further cost reductions for the network design are found. The algorithm output is found to be sensitive to the initial guess of the supply node position, the initial guess of the connections to the supply node, and to the specific “path” of the back-and-forth taken to reach the given local minimum. As such, a good initial guess for a “housing polygon”, i.e. the nodes to which supply node is directly connected to, is crucial in finding the minimum-cost solution, and in the shortest time possible. We attempt to make this initial guess with a machine learning algorithm, with features describing the geometrical distribution of node capacity, as well as elementary network concepts.

Finally, an example is provided on a model hydrogen network comprised of typical elements and realistic cost-functions.

 

[1]: Brimberg J, Hansen P, Lin K, Mladenovi N, Breton M, Brimberg, J (2003) An oil pipeline design problem. Operations Research, 51(2):228–239. https://doi.org/10.1287/opre.51.2.228.12786