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 neighbourhood 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 problem 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 |
| Editors | V.J. Rayward-Smith, C.R. Reeves, G.D. Smith |
| Place of Publication | Chichester |
| Publisher | Wiley |
| Pages | 117-129 |
| ISBN (Print) | 0-471-96280-5 |
| Publication status | Published - 1996 |