# Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows

**Authors:** Christoph Kerscher, Stefan Minner  
**arXiv:** [2402.00041](https://arxiv.org/abs/2402.00041)  
**Date:** 2024-01-20  
**Summary page:** https://www.summarizepaper.com/en/paper/2402.00041v1/

## Key points

- Authors Christoph Kerscher and Stefan Minner introduce a novel approach to solving large-scale instances of the Vehicle Routing Problem (VRP) using Machine Learning techniques.
- They propose a Decompose-Route-Improve (DRI) framework that utilizes clustering techniques to group customers based on spatial, temporal, and demand characteristics.
- The DRI framework breaks down the routing problem into sub-problems that can be independently solved using various algorithms, offering flexibility and efficiency.
- An innovation introduced by Kerscher and Minner is the application of pruned Local Search between solved subproblems to optimize the overall solution.
- In a computational study, the DRI framework outperformed Hybrid Genetic Search in terms of solution quality and efficiency.
- The newly introduced similarity metric enables better segmentation of sub-VRPs and enhances decision-making during the improvement phase.
- The DRI framework shows promise in scaling existing metaheuristics for large-scale VRPs while maintaining high-quality solutions within shorter time frames.
- The approach can be easily adapted to accommodate different solution methods and VRP characteristics, making it a versatile tool for efficiently addressing a wide range of routing problems.

## Summary

In their paper titled "Spatial-temporal-demand clustering for solving large-scale vehicle routing problems with time windows," authors Christoph Kerscher and Stefan Minner introduce a novel approach to tackling the challenges of solving large-scale instances of the Vehicle Routing Problem (VRP). The traditional use of metaheuristics in decomposition and pruning strategies has relied on simple rules specific to the problem domain. However, with the increasing availability of data and advancements in computer hardware, there is a growing interest in leveraging Machine Learning (ML) techniques to enhance scalability. The authors propose a Decompose-Route-Improve (DRI) framework that utilizes clustering techniques to group customers based on their spatial, temporal, and demand characteristics. The similarity metric used aligns with the objective function and constraints of the VRP. By breaking down the routing problem into sub-problems that can be independently solved using various algorithms, the DRI framework offers a flexible and efficient approach. One key innovation introduced by Kerscher and Minner is the application of pruned Local Search (LS) between solved subproblems to optimize the overall solution. This pruning process is guided by customer similarity information obtained during decomposition, allowing for more targeted improvements in subsequent iterations. In a computational study, the authors compare their DRI framework against Hybrid Genetic Search (HGS) proposed by Vidal et al. (2013), demonstrating superior performance in terms of solution quality and efficiency. The results indicate that the data-driven approach presented by Kerscher and Minner outperforms traditional cluster-first, route-second methods that solely rely on spatial information. The newly introduced similarity metric enables better segmentation of sub-VRPs and enhances decision-making during the improvement phase. Overall, the DRI framework shows promise in scaling existing metaheuristics for large-scale VRPs while maintaining high-quality solutions within shorter time frames. Furthermore, Kerscher and Minner highlight that their approach can be easily adapted to accommodate different solution methods and VRP characteristics such as customer distribution patterns, depot locations, and varying time window scenarios. This generalizability makes the DRI framework a versatile tool for efficiently addressing a wide range of routing problems.