A novel graph-based optimization method for district heating network design: Benchmarking against MILP

• Graph-based method using Steiner Tree and heuristics for heating network design. • Integrates energy hub design and network optimization in a unified framework. • Develops marginal benefit pruning and simulated annealing for scalable solutions. • Benchmarks graph-based methods against full MILP for quality and efficiency. • Enables large-scale heating network planning under practical computational limits. In the optimization of urban district heating networks and energy hubs with complex computational scales, Mixed-Integer Linear Programming (MILP) methods can provide globally optimal solutions but are often constrained by high computational complexity and long solution times. This paper proposes a novel graph-based optimization framework, combining Steiner Tree formulations with two heuristic approaches: a marginal benefit-based method that iteratively selects buildings according to their contribution to network efficiency, and a metaheuristic method using Simulated Annealing (SA) to explore building combinations. By decomposing the problem into heating network generation and energy hub optimization, the proposed framework significantly reduces computational costs while maintaining acceptable solution quality. Both MILP and graph-based methods are integrated with geographic information system data to incorporate realistic geographical constraints. Comparative experiments show that the best marginal benefit solution deviates by only 5 % from the MILP benchmark while reducing computation time from 656 s to 28 s. The SA method achieves a 19 % deviation with an average computation time of 248 s. Notably, in scenarios with increased spatial or temporal complexity, where MILP may become computationally intractable, the proposed heuristics remain applicable, underscoring their robustness and practical potential for large-scale district heating network planning. While promising, the performance of the heuristics may vary in other urban contexts, depending on the spatial layout and demand distribution, and further validation across diverse cases is encouraged.