Project R-5208

Engineering and optimizing metaheuristic algorithms: a step ahead in VRP research. (Research)

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 already been proposed, but a common, agreed-upon methodology to analyze and compare heuristic performance on VRP problems is still missing. Recently, the research community started to recognize the need for such a methodological framework, resulting in a few research publications that apply statistical techniques to evaluate heuristics. However, all of these publications suggest an ANOVA approach that only considers a limited set of heuristic variants. This has its limitations because the number of heuristic variants is often infinite due to e.g. continuous parameters. In this research, we follow a different path and apply a regression rather than ANOVA approach. One of the objectives is to create a statistical methodological framework to analyze (meta-)heuristics, which provides a better understanding of the interaction between problem characteristics, algorithm properties and the overall performance. We further argue that this framework is useful during various phases of the algorithm engineering cycle, i.e. the design and experimentation phase. To provide a proof of concept for the framework in general and evidence of the framework's added value during these two phases, the framework will be applied on two classes of VRP problems, i.e. VRP with time windows and multi-trip VRP.

01 January 2014 - 31 December 2017