Abstract
We present a local search algorithm for the Steiner tree problem in graphs, which uses a neighbourhood in which paths in a steiner tree are exchanged. The exchange function of this neigbourhood is based on multiple-source shortest path algorithm. We present computational results for a known benchmark set of generated Steiner tree problem instances and for a set of instances derived from the real-world travelling salesman probelm instances containing up to 18512 vertices. The results show that good quality solutions can be obtained in moderate running times.
| Original language | English |
|---|---|
| Title of host publication | Modern Heuristic Search Methods |
| Place of Publication | Chichester |
| Publisher | Wiley |
| Pages | 117-129 |
| Number of pages | 13 |
| ISBN (Print) | 0-471-96280-5 |
| Publication status | Published - 1996 |
| Externally published | Yes |