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.
|Title of host publication||Modern Heuristic Search Methods|
|Place of Publication||Chichester|
|Number of pages||13|
|Publication status||Published - 1996|