A construction heuristic for the capacitated Steiner tree problem

PLoS One. 2022 Jun 16;17(6):e0270147. doi: 10.1371/journal.pone.0270147. eCollection 2022.

Abstract

Many real-life problems boil down to a variant of the Minimum Steiner Tree Problem (STP). In telecommunications, Fiber-To-The-Home (FTTH) houses are clustered so they can be connected with fiber as cost-efficiently as possible. The cost calculation of a fiber installment can be formulated as a capacitated STP. Often, STP variants are solved with integer linear programs, which provide excellent solutions, though the running time costs increase quickly with graph size. Some geographical areas require graphs of over 20000 nodes-typically unattainable for integer linear programs. This paper presents an alternative approach. It extends the shortest path heuristic for the STP to a new heuristic that can construct solutions for the capacitated STP: the Capacitated Shortest Path Heuristic (CSPH). It is straightforward to implement, allowing many extensions. In experiments on realistic telecommunications datasets, CSPH finds solutions on average in time O(|V|2), quadratic in the number of nodes, making it possible to solve 50000 node graphs in under a minute.

Publication types

  • Research Support, Non-U.S. Gov't

MeSH terms

  • Algorithms
  • Telecommunications*

Grants and funding

This research was partly funded by the Ghent University IOP project “Modelling Uncertainty in Hub Location Planning through Interdisciplinary Research”, by the VLAIO project “Comsof Autonomous Planning Agent” and by the UGent-project BOF/STA/202009/039. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.