A method for designing minimum-cost multisource multisink network layouts

Abstract

Systems engineers are equipped to design complex networked systems such as infrastructures. A key goal is cost minimization over a vast solution space. However, finding a minimum-cost system while comprehensively satisfying different stakeholders is challenging and lacks proper methodological support. Stakeholders often employ their own expert estimations for lack of suitable decision-support methods. In these settings, systems engineers typically require mid-fidelity, easy-to-use methods. We present a rigorous method that quickly finds minimum-cost solutions for networks with multiple sources and sinks, focusing on pipeline topology, length, and capacity. It can serve as a discussion tool in multiactor design processes, to demarcate the design space, indicate sources of uncertainty, and provoke further analyses, different designs, or contractual negotiations. It is applicable to a wide variety of cases, including many prominent infrastructures needed to mitigate CO₂. We prove that the optimal layout is a minimum-cost Gilbert tree, and develop a heuristic based on the Gilbert-Melzak method. We demonstrate the method's efficacy for a case set regarding solution quality, computational time, and scalability. We also show its efficiency and usefulness for systems engineers in real-world settings. Systems engineers can use the generated cost-optimal system designs to benchmark any design changes in real-world negotiation processes.