Adaptive Large Neighborhood Search for Rich and Real-World Vehicle Routing Problems

Abstract

In optimization, many variants of the Vehicle Routing Problem exists with all sorts of restrictions and characteristics. Heuristics that find near-optimal solutions are known and tested on in the literature, such as heuristics that escape local minima with the use of large neighborhoods. An example is Adaptive Large Neighborhood Search, which can be used to find near-optimal solutions for rich Vehicle Routing Problems. In order to understand the differences between this heuristic and other heuristics that use large neighborhoods, an overview of the most related minima-escaping heuristics is provided in this thesis. Unfortunately, studies that involve real-world data are limited. Therefore, this thesis involves a study on how to configure the components of Adaptive Large Neighborhood Search, such that it can be used on real-world data. This study is carried out at ORTEC, a company that provides optimization software and analytical solutions to all sorts of companies, and customer cases are used for testing. Most of the time, an initial solution is required as input for the minima-escaping heuristics and the importance of the quality of this solution is not specified. Therefore, the influence of the construction method for an initial feasible solution on the performance of Adaptive Large Neighborhood Search will be investigated as well. It turns out that this influence is case and configuration specific. To intensify the search and explore smaller neighborhoods as well, local search methods are added to Adaptive Large Neighborhood Search, which will improve the solutions that are found. The research concludes with an Adaptive Large Neighborhood Search that is tuned for the real-world cases that are investigated at ORTEC. Because the computing time that is available for real-world cases is usually limited, a simplified version of the heuristic will be provided as well.