Computationally efficient topology design of district heating networks by price-collecting Steiner trees

The expansion of district heating infrastructure is an important pillar in the decarbonization of municipal energy systems. However, designing piping networks for district heating is complex and time-consuming. This paper introduces a computationally efficient approach for automated, near-optimal design of district heating piping networks utilizing the price-collecting Steiner tree (PCST) problem formulation from graph theory. Based on an initial graph, PCST algorithms aim to identify the subgraph with the highest profit by balancing edge and vertex weights, where selected vertices increase the profit while edges decrease the profit by their weights. This work presents the application of PCSTs to network topology design by selecting the weights to represent the district heating application, discussing needed assumptions and introducing post-processing for heat flow and pipe diameter calculation. A benchmark study on a small German city shows that the PCST approach outperforms state-of-the-art approaches regarding computational efficiency, offering millisecond-range computation times. The computational efficiency comes at the cost of optimality with an optimality gap around 5%. However, effects of parameter uncertainties in network design exceed the effect of suboptimality by the PCST approach, making the approach promising for comprehensive parameter studies and integration with other planning aspects of municipal energy systems.