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

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.