Evaluation and optimization of metaheuristic algorithms for the vehicle routing problem with time windows

Abstract

The vehicle routing problem with time windows (VRPTW) is an extension to the traditional vehicle routing problem. Finding an optimal solution for the NP-hard VRPTW is difficult. Therefore, a large number of heuristic procedures have been proposed for VRP problems.

There is, however, no agreed-upon methodology used for comparing heuristic performance on these problems. In VRP literature, heuristic performance is traditionally studied by evaluating the performance of a specific heuristic on a set of standard test problems, but any conclusions made are limited to the benchmark set and often not robust. To obtain statistical meaningful conclusions experimental design should be applied on the different levels of the various algorithmic parameters and the results compared by appropriate techniques. This need for more scientific rigour in the operations research and heuristics community was already called for many years ago by several researchers. Nonetheless, few papers have made notion of using either design of experiment techniques or statistical tools for exploring data and testing hypotheses. In other research fields these are prerequisites for performing scientific work. Current VRP research can therefore make a significant methodological progress by applying a statistical approach to obtain a more rigorous evaluation and gain a more complete insight in and understanding of the different results. This research aims at developing such a methodological framework.