Local search for Steiner tree problems in graphs

M.G.A. Verhoeven, M.E.M. Severens, E.H.L. Aarts

Research output: Chapter in Book/Report/Conference proceedingChapterScientificpeer-review


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 languageEnglish
Title of host publicationModern Heuristic Search Methods
Place of PublicationChichester
Number of pages13
ISBN (Print)0-471-96280-5
Publication statusPublished - 1996
Externally publishedYes

Cite this