Journal article
A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in R-d
Journal of heuristics, Vol.17(4), pp.353-372
08/01/2011
DOI: 10.1007/s10732-010-9137-z
Abstract
We present a heuristic for the Euclidean Steiner tree problem in R-d for d >= 2. The algorithm utilizes the Delaunay triangulation to generate candidate Steiner points for insertion, the minimum spanning tree to identify the Steiner points to remove, and second-order cone programming to optimize the location of the remaining Steiner points. Unlike other ESTP heuristics relying upon Delaunay triangulation, we insert Steiner points probabilistically into Delaunay triangles to achieve different subtrees on subsets of terminal points. We govern this neighbor generation procedure with a local search framework that extends effectively into higher dimensions. We present computational results on benchmark test problems in R-d for 2 <= d <= 5.
Details
- Title: Subtitle
- A randomized Delaunay triangulation heuristic for the Euclidean Steiner tree problem in R-d
- Creators
- Jon W. Van Laarhoven - University of IowaJeffrey W. Ohlmann - University of Iowa
- Resource Type
- Journal article
- Publication Details
- Journal of heuristics, Vol.17(4), pp.353-372
- Publisher
- Springer Nature
- DOI
- 10.1007/s10732-010-9137-z
- ISSN
- 1381-1231
- eISSN
- 1572-9397
- Number of pages
- 20
- Language
- English
- Date published
- 08/01/2011
- Academic Unit
- Business Analytics
- Record Identifier
- 9984380398702771
Metrics
2 Record Views