A quantitative comparison of generalized fast construction heuristics for the vehicle routing problem with time windows

In this Master Thesis, we explore construction heuristics for the Vehicle Routing Problem with Time Windows (VRPTW). The VRPTW is an important problem that is encountered in many logistic processes. In this problem, a set of geographically dispersed customers needs to be routed from a central depot, within certain time constraints. The problem is further constrained by capacity of vehicles and earliest start and latest end times of routes. Many heuristics have already been proposed to solve this problem. In this thesis, we specifically look into construction heuristics (without improvement steps) and propose a generalized framework that distinguishes three building blocks of construction heuristics: heuristic frameworks, seed selection methods and search function components. In our computational experiments we vary the elements selected for the three building blocks, thus creating a wide range of different composite heuristics. In total, we tested thousands of composite heuristics on a wide range of benchmark problems. In the analysis of the results, we identified which elements contributed most to solution quality, measured in different ways. We did this analysis not only for the aggregate results, but also in relation to problem characteristics. We also explored issues such as flexibility with respect to incorporating additional problem constraints, and scalability. In the end, we provide a recommendation when and how to use the different heuristics (elements) most effectively