TL;DR
This paper introduces TuneNSearch, a novel approach that combines transfer learning and local search to solve various Vehicle Routing Problems (VRPs). By pre-training on complex multi-depot VRPs and then fine-tuning, TuneNSearch achieves strong generalization across different VRP variants with significantly less training time than existing methods, while also improving solution quality through an integrated local search.
What Problem Does This Paper Address?
Vehicle Routing Problems (VRPs) are a fundamental class of optimization problems with numerous real-world applications in logistics and transportation. However, solving these problems, especially for large-scale instances with complex constraints, is computationally challenging. Existing neural network-based approaches often excel at specific VRP variants but struggle to generalize across different problem types, requiring extensive retraining for each new variant. This lack of adaptability is a significant bottleneck for practical applications where dynamic routing needs are common. Furthermore, many current neural methods overlook the complexity of multi-depot VRPs (MDVRPs), which are more representative of real-world scenarios. The paper aims to bridge this gap by developing a single, adaptable model that can efficiently solve diverse VRPs with high performance and strong generalization capabilities.
Methods
TuneNSearch employs a two-stage approach:
- Pre-training and Fine-tuning:
- Pre-training: A reinforcement learning model, based on the POMO architecture, is first pre-trained on MDVRP instances. This leverages the inherent complexity of MDVRPs to learn richer, more transferable node representations compared to training on simpler problems like TSP.
- Fine-tuning: The pre-trained model is then fine-tuned for specific VRP variants (e.g., CVRP, VRPTW) using a shorter training phase. This approach is more efficient than training from scratch for each variant.
- Model Architecture:
- Encoder: An Edge-Graph Attention Network (E-GAT) is integrated into the encoder. This E-GAT captures not only node features but also edge distances and residual connections, leading to a more precise encoding of the VRP's graph structure.
- Decoder: A Transformer-based decoder, similar to POMO, is used to construct solutions.
- Local Search Integration: After the neural model generates an initial solution (inference), an efficient local search algorithm is applied to further refine the solution. This hybrid approach combines the speed of neural methods with the optimization power of traditional search techniques. The local search employs various operators (e.g., (X, M)-exchange, 2-OPT, RELOCATE*, SWAP*) and a selective route exchange crossover (SREX) for generating offspring.
Datasets
The paper utilizes several datasets for training and evaluation:
- MDVRP: Used for pre-training the core model.
- CVRPLIB and TSPLIB: Standard benchmark datasets for various VRP variants (CVRP, TSP, VRPL, OVRP, VRPTW).
- Cordeau's dataset: A benchmark dataset specifically for MDVRP.
- INCOM2024 benchmark instances: A dataset of large-scale MDVRP instances (up to 1000 nodes) introduced by the Supply Chain AI Lab at the University of Cambridge.
- Randomly generated instances: Used extensively for evaluating performance across different VRP variants and problem sizes.
Key Insights and Ideas
- MDVRP as a superior pre-training task: Pre-training on the more complex MDVRP, rather than simpler problems like TSP or CVRP, leads to richer node representations and better generalization across a wider range of VRP variants, including single-depot ones. This is a key differentiator from prior transfer learning approaches.
- E-GAT enhances encoding: Integrating an edge-aware graph attention mechanism (E-GAT) into the encoder significantly improves the model's ability to capture spatial relationships and edge information, leading to more accurate VRP feature encoding.
- Hybrid approach for optimal balance: Combining a fast neural inference stage with a powerful local search refinement stage strikes an effective balance between computational efficiency and solution quality, outperforming purely neural or purely local search methods.
- Fine-tuning is efficient and effective: The fine-tuning phase requires significantly fewer epochs than training from scratch, demonstrating the value of transfer learning for adapting to new VRP variants.
Key Results
- Generalization: TuneNSearch demonstrates strong generalization capabilities across different VRP variants, problem sizes, and instance distributions.
- Performance: It achieves performance comparable to or better than state-of-the-art models, often with significantly lower relative percentage deviations from best-known solutions (e.g., less than 3% on benchmark datasets).
- Efficiency: TuneNSearch requires substantially less training time (e.g., one-fifth of the epochs compared to POMO) and inference time compared to many baseline methods, especially when considering the computational budget. For instance, it can solve problems in a fraction of the time taken by PyVRP and OR-Tools.
- MDVRP superiority: When compared to a model pre-trained on CVRP, TuneNSearch shows significantly better performance on multi-depot variants, while maintaining comparable performance on single-depot variants.
- Local Search Impact: The integrated local search algorithm provides substantial performance gains with minimal additional computational overhead.
Limitations and Future Work
- Limited to traditional VRPs: The current TuneNSearch is designed for traditional VRPs with specific constraints. Extending it to other combinatorial problems (e.g., orienteering, prize collecting TSP) or problems with dynamic objectives would require manual architectural adjustments.
- Fixed objective function: The model assumes a fixed objective function (minimizing total distance). Adapting to different objectives during fine-tuning might require re-optimization of learned parameters.
- Future Work:
- Extend TuneNSearch to scheduling problems.
- Further enhance solution quality and explore decomposition approaches for VRPs.
- Investigate clustering training instances to train specialized local models for improved generalization.
Summary updated