Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions

Iterated local search algorithms for the Euclidean Steiner tree problem in n dimensions

0.00 Avg rating0 Votes
Article ID: iaor20162907
Volume: 23
Issue: 6
Start Page Number: 1185
End Page Number: 1199
Publication Date: Nov 2016
Journal: International Transactions in Operational Research
Authors: , , ,
Keywords: search, heuristics: local search, programming: branch and bound
Abstract:

We propose algorithmic frameworks based on the iterated local search (ILS) metaheuristic to obtain good‐quality solutions for the Euclidean Steiner tree problem (ESTP) in n dimensions. This problem consists in finding a tree with minimal total length that spans p points given in an n‐dimensional Euclidean space and, eventually, also some additional points whose insertion contributes to reduce the total length of the tree. These ILS approaches make use of both the tree enumeration structure, called topology‐describing vector, and the exact minimization step of a well‐known branch‐and‐bound method for the ESTP. Computational results are provided.

Reviews

Required fields are marked *. Your email address will not be published.