Local Search for the Steiner Tree Problem in the Euclidean Plane

Research output: Contribution to journalArticlepeer-review

19 Citations (Scopus)


Most heuristics for the Steiner tree problem in the Euclidean plane perform a series of iterative improvements using the minimum spanning tree as an initial solution. We may therefore characterize them as local search heuristics. In this paper, we first give a survey of existing heuristic approaches from a local search perspective, by setting up solution spaces and neighbourhood structures. Secondly, we present a new general local search approach which is based on a list of full Steiner trees constructed in a preprocessing phase. This list defines a solution space on which three neighbourhood structures are proposed and evaluated. Computational results show that this new approach is very competitive from a cost–benefit point of view. Furthermore, it has the advantage of being easy to apply to the Steiner tree problem in other metric spaces and to obstacle avoiding variants.
Original languageEnglish
Pages (from-to)282-300
Number of pages19
JournalEuropean Journal of Operational Research
Issue number2
Publication statusPublished - 1999


  • heuristics
  • survey
  • local search
  • Steiner trees


Dive into the research topics of 'Local Search for the Steiner Tree Problem in the Euclidean Plane'. Together they form a unique fingerprint.

Cite this