A methodological framework to optimize and compare VRP algorithms

Abstract

Vehicle Routing Problems (VRP) are an extensively studied class of combinatorial optimization problems, with a wide spectrum of real-life applications. An impressive number of heuristic procedures have been proposed for VRP problems. However, no common, agreed-upon methodology is used to compare heuristic performance on vehicle routing problems. In VRP literature, (meta-)heuristics are rarely compared by means of statistical techniques. In this paper a methodological framework is proposed to optimize and compare heuristic algorithms. The optimization of algorithms relates both to setting the optimal algorithmic parameter values and testing the effects of various components of an algorithm. The methodological framework is demonstrated by analyzing the performance of the ALNS algorithm (Pisinger and Ropke, 2007) for the vehicle routing problem with time windows. Based on a thorough and reliable understanding of the relationship between algorithm performance, problem characteristics and algorithm properties, one can determine the optimal parameter setting and construct rules stating which heuristic elements should be activated for a particular instance. Alternatively, the statistical insight also provides robust parameter and algorithmic components settings, resulting in an optimized algorithm independent of the specific environment and variability in the data, because it is designed to handle a general situation.