Analysing metaheuristic algorithms for the vehicle routing problem with time windows

Abstract

A large number of heuristic procedures have been developed to solve vehicle routing problems. These methods operate according to the setting of various parameters. This is often done by trial-and-error, by testing on a limited sample of benchmark instances, or simply quoting values from literature without any rigorous examination of their suitability in the used context. A configuration is rarely obtained through the use of some rigorous statistical procedure, but is usually based on personal experience and rules of thumb, often involving monotonous and time consuming experiments. Furthermore, such an approach limits any conclusions made to the specific problems considered in the used benchmark set. No statements can be made for unseen problem instances. A more rigorous parameter tuning can be obtained through the use of established experiment designs and the proper statistical tools.

We propose a new methodological framework that applies a multilevel regression perspective with the aim of gaining complete insights over the full range of algorithmic parameter values and problem characteristics. The regression analysis will allow us to identify the impact each parameter value and heuristic component has on performance, which parameter and component combinations achieve better results and what influence the problem characteristics have. Are any perceived gains in (meta)heuristic performance statistically significant or are they simply due to chance? A first multilevel regression analysis is performed on a set of artificially generated VRPTW instances that are solved using a simplified version of the Adaptive Large Neighbourhood Search metaheuristic.