Spatial-temporal-demand clustering for solving large-scale vehicle
  routing problems with time windows
Christoph Kerscher Stefan Minner
Several metaheuristics use decomposition and pruning strategies to solve
large-scale instances of the vehicle routing problem (VRP). Those complexity
reduction techniques often rely on simple, problem-specific rules. However, the
growth in available data and advances in computer hardware enable data-based
approaches that use machine learning (ML) to improve scalability of solution
algorithms. We propose a decompose-route-improve (DRI) framework that groups
customers using clustering. Its similarity metric incorporates customers'
spatial, temporal, and demand data and is formulated to reflect the problem's
objective function and constraints. The resulting sub-routing problems can
independently be solved using any suitable algorithm. We apply pruned local
search (LS) between solved subproblems to improve the overall solution. Pruning
is based on customers' similarity information obtained in the decomposition
phase. In a computational study, we parameterize and compare existing
clustering algorithms and benchmark the DRI against the Hybrid Genetic Search
(HGS) of Vidal et al. (2013). Results show that our data-based approach
outperforms classic cluster-first, route-second approaches solely based on
customers' spatial information. The newly introduced similarity metric forms
separate sub-VRPs and improves the selection of LS moves in the improvement
phase. Thus, the DRI scales existing metaheuristics to achieve high-quality
solutions faster for large-scale VRPs by efficiently reducing complexity.
Further, the DRI can be easily adapted to various solution methods and VRP
characteristics, such as distribution of customer locations and demands, depot
location, and different time window scenarios, making it a generalizable
approach to solving routing problems.