Journal Article

A construction heuristic for the capacitated Steiner tree problem

Van den Eynde, Simon, Audenaert, Pieter, Pickavet, Mario, Colle, Didier

2022

Overview

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.

• Publisher: Public Library of Science,Public Library of Science (PLoS)
• Subject: Algorithms / Analysis / Biology and Life Sciences / Computer and Information Sciences / Cost accounting / Costs / Datasets / Deep learning / Engineering and Technology / Engineering research / Experiments / Fiber optic cables / Graphs / Heuristic / Houses / Integers / Linear programming / Mathematical models / Methods / Nodes / Physical Sciences / Problem solving / Process costing / Research and Analysis Methods / Shortest-path problems / Telecommunication systems / Telecommunications / Trees (Graph theory)