Explaining metaheuristic performance through iterative experimentation

Abstract

For many years metaheuristics have been successfully applied to solve computationally challenging optimisation problems. These general solutions procedures are most commonly evaluated by running them on standard benchmark problems and comparing performance results with other state-of-the-art methods. The objective is to be better than the competition. A detailed investigation of the metaheuristic elements responsible for the superior performance is rarely performed. Understanding how all the elements impact performance and how they interact with the specific problem instance to be solved is, nevertheless, relevant to gain insight into both metaheuristic and optimisation problem. In this research, the focus is on gaining a better understanding of heuristic algorithm performance. We investigate the performance difference between two configurations of a large neighbourhood search algorithm applied on instances of the vehicle routing problem with time windows and are able to substantially reduce the performance gap after a detailed analysis of the destroy and repair process. We observed that when reinserting customers in the solution, the most isolated ones should be prioritised.