Authors: Hansen, Pierre
Mladenović, Nenad 
Title: First vs. best improvement: An empirical study
Journal: Discrete Applied Mathematics
Volume: 154
Issue: 5 SPEC. ISS.
First page: 802
Last page: 817
Issue Date: 1-Apr-2006
Rank: M22
ISSN: 0166-218X
DOI: 10.1016/j.dam.2005.05.020
When applying the 2-opt heuristic to the travelling salesman problem, selecting the best improvement at each iteration gives worse results on average than selecting the first improvement, if the initial solution is chosen at random. However, starting with 'greedy' or 'nearest neighbor' constructive heuristics, the best improvement is better and faster on average. Reasons for this behavior are investigated. It appears to be better to use exchanges introducing into the solution a very small edge and fairly large one, which can easily be removed later, than two small ones which are much harder to remove.
Keywords: Heuristic | Metaheuristic | Travelling salesman | Variable neighborhood search
Publisher: Elsevier

Show full item record


checked on May 18, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.