A construction heuristic for the capacitated Steiner tree problem.
PLoS One
; 17(6): e0270147, 2022.
Article
em En
| MEDLINE
| ID: mdl-35709229
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.
Texto completo:
1
Coleções:
01-internacional
Base de dados:
MEDLINE
Assunto principal:
Telecomunicações
Idioma:
En
Revista:
PLoS One
Assunto da revista:
CIENCIA
/
MEDICINA
Ano de publicação:
2022
Tipo de documento:
Article
País de afiliação:
Bélgica