First-improvement or best-improvement? An in-depth local search computational study to elucidate a dominance claim

Daniel Aloise, Robin Moine, Celso C. Ribeiro and Jonathan Jalbert

European Journal of Operational Research, 2025, vol. 326, issue 3, 413-426

Abstract: Local search methods start from a feasible solution and improve it by successive minor modifications until a solution that cannot be further improved is encountered. They are a common component of most metaheuristics. Two fundamental local search strategies exist: first-improvement and best-improvement. In this work, we perform an in-depth computational study using consistent performance metrics and rigorous statistical tests on several classes of test problems considering different initialization strategies and neighborhood structures to evaluate whether one strategy is dominant over the other. The numerical results show that computational experiments previously reported in the literature claiming the dominance of one strategy over the other for the TSP given an initialization method (random or greedy) cannot be extrapolated to other problems. Still, our results highlight the need for thorough experimentation and stress the importance of examining instance feature spaces and optimization landscapes to choose the best strategy for each problem and context, as no rule of thumb seems to exist for identifying the best local search strategy in the general case.

Keywords: Local search; Heuristics; First-improvement; Best-improvement; Combinatorial optimization (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221725002693
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:326:y:2025:i:3:p:413-426

DOI: 10.1016/j.ejor.2025.04.019

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().