Decompose-route-improve framework for solving large-scale vehicle routing problems with time windows

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 to improve scalability of solution algorithms. We propose a decompose-route-improve (DRI) framework, which first partitions the customers of the VRP with time windows (VRPTW) using clustering. Its dissimilarity metric incorporates customers’ spatial, temporal, and demand data and is formulated to reflect the problem’s objective function and constraints. Second, the resulting sub-routing problems are solved independently using any suitable algorithm. Lastly, 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 a state-of-the-art solver on large VRPTW instances and very large-scale instances with up to 30,000 customers, which are introduced in this study. Results show that our data-based approach outperforms classic and recent cluster-first, route-second approaches as well as decomposition strategies that are solely based on customers’ spatial information. The newly introduced dissimilarity metric forms separate sub-VRPTWs and improves the selection of LS moves in the improvement phase. Thus, the DRI scales existing metaheuristics to achieve high-quality solutions faster for very large-scale VRPTWs by efficiently reducing complexity. Further, the DRI can be adapted to various solution methods and problem characteristics, such as the distribution of customer locations and demands, the depot location, and different time window scenarios, making it a generalizable approach to solving large- and very large-scale practical routing problems.