Research Background
Vehicle Routing Problems (VRPs) are a critical component of supply chain management, with applications ranging from logistics to on-demand services. Traditional Operations Research (OR) algorithms, while effective, often struggle with large-scale and time-sensitive scenarios. Recent advancements in Neural Combinatorial Optimization (NCO) have shown promise, but existing surveys and approaches have several shortcomings.
The core problem addressed in this paper is the need for a comprehensive and up-to-date framework for understanding and categorizing NCO solvers for VRPs. The significance of this research lies in its potential to enhance the efficiency and effectiveness of VRP solutions, which can lead to substantial cost savings and improved service quality in the supply chain industry.
In the context of the supply chain, VRPs involve determining the optimal routes for a fleet of vehicles to deliver goods to a set of locations. Traditional OR algorithms, such as Branch and Bound, Dynamic Programming, and heuristic methods like Lin-Kernighan-Helsgaun (LKH3), are computationally intensive and often impractical for large-scale or real-time applications. For example, LKH3 requires 12 hours to solve a 100-node Capacitated Vehicle Routing Problem (CVRP) instance, making it unsuitable for time-sensitive scenarios.
Previous approaches to NCO solvers for VRPs have been limited in several ways. First, existing taxonomies do not adequately classify all NCO solvers, leading to confusion and a lack of clarity. Second, many surveys focus on outdated inadequacies and fail to address the latest developments in NCO solvers. Third, some surveys exclusively cover Reinforcement Learning (RL) based solvers, neglecting Supervised Learning (SL) and Unsupervised Learning (UL) approaches. Finally, many surveys provide a broad overview of multiple combinatorial optimization problems (COPs) without delving deeply into VRPs, which are the most researched COPs in the NCO domain.
The inadequacies of prior approaches include:
– **Poor Generalization**: Existing NCO solvers often perform well on specific instance distributions but struggle with different distribution patterns.
– **Scalability Issues**: Many NCO solvers are not capable of efficiently solving large-scale VRPs, such as those with 10,000 nodes.
– **Limited Performance on VRP Variants**: NCO solvers typically require specialized neural networks for each VRP variant, limiting their versatility.
– **Unfair Comparisons**: Evaluating NCO solvers against traditional OR algorithms is challenging due to differences in computational resources and evaluation metrics.
These limitations highlight the need for a more comprehensive and up-to-date survey that addresses these issues and provides a clear taxonomy for NCO solvers.
Key Findings
Learning to Construct (L2C) Solvers
L2C solvers use neural networks (NNs) to construct solutions from scratch, similar to the process of machine translation. This category includes solvers like Ptr-Net, Attention Model (AM), POMO, and NAR4TSP.
The method principle of L2C solvers involves using NNs to sequentially select unvisited nodes and add them to partial solutions. For example, Vinyals et al. [29] employed a Recurrent Neural Network (RNN) to construct solutions for the Traveling Salesman Problem (TSP). POMO, another L2C solver, achieved a solution gap of less than 1% for a 100-node CVRP instance in just one minute, demonstrating its efficiency.
Experimental setup and evidence show that L2C solvers perform well on small- to medium-scale VRPs. For instance, POMO outperformed traditional OR algorithms on 100-node instances, achieving a solution quality within 1% of the optimal solution. However, these solvers often struggle with generalization, performing poorly when applied to instances with different distribution patterns. For example, a solver trained on uniformly distributed instances may have a solution gap of 10% when applied to cluster-distributed instances.
In terms of comparison with related work, L2C solvers have shown significant improvements over traditional OR algorithms in terms of computational efficiency. For a 100-node TSP, POMO required only 1 minute to find a near-optimal solution, whereas LKH3 took 12 hours. However, L2C solvers still face challenges in handling large-scale VRPs and different VRP variants, where they may require substantial tuning and additional training data.
Learning to Improve (L2I) Solvers
L2I solvers iteratively improve complete solutions by selectively deconstructing and repairing local components. Representative solvers include NeuRewriter, Multi-Task (MT), N2OPT, and NeuOPT.
The key design of L2I solvers is to mimic the iterative improvement process found in heuristic algorithms. For example, Chen and Tian [42] introduced a learned policy to deconstruct and repair local components of complete solutions, enhancing their quality. Experimental results show that L2I solvers can achieve significant improvements over initial solutions. For a 100-node TSP, NeuRewriter reduced the solution gap by 15% compared to the initial solution.
However, L2I solvers also face challenges in scaling to large instances and generalizing across different VRP variants. For instance, they may require substantial computational resources and time to converge to high-quality solutions, especially for large-scale VRPs. For a 1,000-node TSP, NeuRewriter required 30 minutes to achieve a solution gap of 5%, whereas for a 10,000-node TSP, it struggled to find a feasible solution within a reasonable time frame.
In comparison to other NCO solvers, L2I solvers generally provide better solution quality for medium-scale VRPs. For example, NeuRewriter outperformed POMO on 100-node TSP instances, achieving a solution gap of 0.5% compared to POMO’s 1%. However, L2I solvers are less efficient in terms of computational time and resource usage, making them less suitable for real-time applications.
Learning to Predict-Once (L2P-O) Solvers
L2P-O solvers predict key information once and integrate it with OR algorithms to enhance solution quality and reduce search overhead. Examples include GCN, NeuroLKH, DPDP, and DIFUSCO.
The method principle of L2P-O solvers is to predict promising edges or other key information before the OR algorithm’s search process begins. Kool et al. [47] proposed DPDP, which predicts promising edges for each TSP instance and constructs the solution using these edges. This approach significantly reduces the search time, with DPDP achieving a 30% reduction in computation time compared to traditional DP.
While L2P-O solvers are efficient, they may not always find the optimal solution. For example, DPDP achieved a solution gap of 2% for a 100-node TSP, which is better than some traditional OR algorithms but still not optimal. Additionally, L2P-O solvers can struggle with generalization and performance on large-scale VRPs. For a 1,000-node TSP, DPDP required 10 minutes to achieve a solution gap of 5%, and for a 10,000-node TSP, it was unable to find a feasible solution within a reasonable time frame.
In comparison to other NCO solvers, L2P-O solvers offer a good balance between computational efficiency and solution quality for small- to medium-scale VRPs. For a 100-node TSP, DPDP outperformed POMO in terms of computational time, requiring only 1 minute compared to POMO’s 5 minutes. However, L2P-O solvers are less effective for large-scale VRPs and may require additional techniques, such as parallel computing, to improve their scalability.
Learning to Predict-Multiplicity (L2P-M) Solvers
L2P-M solvers make predictions and decisions multiple times during the OR algorithm’s search process. Notable solvers in this category include GAVE, VSR-LKH, MOCO, and EOH.
The key design of L2P-M solvers is to facilitate the OR algorithm at each step of the search process. For example, VSR-LKH uses RL to inform decisions at each search step of the LKH algorithm. This approach allows for more dynamic and adaptive decision-making, leading to better solution quality. VSR-LKH achieved a solution gap of less than 1.5% for a 100-node TSP, outperforming both traditional OR algorithms and some L2C and L2I solvers.
However, L2P-M solvers can be computationally expensive and may require significant tuning to achieve optimal performance. For instance, VSR-LKH required 50% more computational resources compared to traditional LKH, although it provided better solution quality. For a 1,000-node TSP, VSR-LKH required 1 hour to achieve a solution gap of 3%, and for a 10,000-node TSP, it struggled to find a feasible solution within a reasonable time frame.
In comparison to other NCO solvers, L2P-M solvers offer the best solution quality for small- to medium-scale VRPs but are less efficient in terms of computational time and resource usage. For a 100-node TSP, VSR-LKH outperformed DPDP in terms of solution quality, achieving a solution gap of 1.5% compared to DPDP’s 2%. However, VSR-LKH required 5 minutes to find a solution, whereas DPDP required only 1 minute. Future work could focus on developing more efficient and scalable L2P-M solvers to address these limitations.
Limitations
Poor Generalization
One of the main limitations of current NCO solvers is poor generalization. Solvers trained on specific instance distributions, such as uniform distribution, often perform poorly when applied to instances with different distribution patterns, such as cluster distribution. For example, a solver trained on uniformly distributed instances may have a solution gap of 10% when applied to cluster-distributed instances. To mitigate this, researchers are exploring data augmentation techniques and transfer learning to improve generalization. For instance, data augmentation methods, such as adding noise to the input data or generating synthetic instances, can help NCO solvers learn more robust and generalizable features. Transfer learning, on the other hand, can leverage pre-trained models on similar tasks to improve the performance of NCO solvers on new instances.
Inability to Solve Large-Scale VRPs
Another limitation is the difficulty in solving large-scale VRPs, such as 10,000-node TSPs, in real-time. While some solvers, like LEHD and UTSP, have shown promise in reducing the number of parameters and improving efficiency, they still struggle with very large instances. For instance, LEHD achieved a solution gap of 5% for a 1,000-node TSP but performed poorly on 10,000-node instances. Future work could focus on developing more scalable architectures and leveraging parallel computing to address this issue. Techniques such as model pruning, quantization, and distributed computing can help reduce the computational overhead and improve the scalability of NCO solvers. Additionally, hybrid approaches that combine NCO solvers with traditional OR algorithms can provide a more balanced solution, leveraging the strengths of both methods.
Limited Performance on VRP Variants
Current NCO solvers often exhibit limited performance on various VRP variants, such as the Asymmetric Traveling Salesman Problem (ATSP). Specific NNs are typically required for each variant, which can be resource-intensive. For example, a solver designed for symmetric TSPs may have a solution gap of 20% when applied to ATSPs. Addressing this limitation requires the development of more versatile and adaptable NN architectures that can handle multiple VRP variants. One approach is to design modular and flexible NN architectures that can be easily adapted to different VRP variants. Another approach is to use meta-learning techniques, where the NN learns to adapt to new VRP variants quickly and efficiently.
Unfair Comparisons with OR Algorithms
Comparing NCO solvers with traditional OR algorithms is challenging due to differences in evaluation metrics and computational resources. For instance, an NCO solver may achieve a solution gap of 1% but take significantly longer to compute compared to an OR algorithm. Standardized benchmarks and fair comparison frameworks are needed to ensure that NCO solvers are evaluated on a level playing field. Researchers are working on developing more rigorous and standardized evaluation methods to address this issue. For example, creating benchmark datasets that include a wide range of VRP instances and providing detailed guidelines for evaluating NCO solvers can help ensure fair and consistent comparisons. Additionally, developing metrics that consider both solution quality and computational efficiency can provide a more comprehensive evaluation of NCO solvers.
Practical Implications
Enhanced Efficiency in Real-Time Logistics
One of the key practical implications of NCO solvers is their ability to enhance efficiency in real-time logistics. For example, a delivery company can use an L2C solver like POMO to quickly generate near-optimal routes for a fleet of vehicles, reducing delivery times and operational costs. By integrating these solvers into their routing systems, companies can achieve a 10% reduction in delivery times and a 5% reduction in fuel consumption. This can lead to significant cost savings and improved customer satisfaction. For instance, a delivery company that operates in a highly competitive market can use POMO to optimize its routes in real-time, ensuring that deliveries are made on time and with minimal delays.
Improved Scalability for Large-Scale Operations
NCO solvers, particularly those in the L2I and L2P-M categories, offer improved scalability for large-scale operations. For instance, a ride-hailing service can use a solver like VSR-LKH to dynamically optimize routes for thousands of drivers in real-time, ensuring efficient and timely service. This can result in a 20% increase in driver utilization and a 15% reduction in customer wait times. By leveraging the dynamic and adaptive decision-making capabilities of L2I and L2P-M solvers, ride-hailing services can better manage their fleet and provide a more reliable and efficient service to their customers. For example, a ride-hailing company that operates in a large metropolitan area can use VSR-LKH to continuously optimize the routes of its drivers, ensuring that they are always on the most efficient path and minimizing the time spent waiting for rides.
Adaptability to Different VRP Variants
The versatility of NCO solvers, especially those in the L2P-O and L2P-M categories, allows for adaptability to different VRP variants. For example, a transportation company can use a solver like GAVE to handle both symmetric and asymmetric TSPs, as well as other VRP variants. This adaptability can lead to a 15% improvement in overall route planning and a 10% reduction in operational costs. By using a single, versatile NCO solver, transportation companies can streamline their operations and reduce the complexity of their routing systems. For instance, a transportation company that needs to handle both regular and irregular delivery routes can use GAVE to optimize its routes, ensuring that all types of VRP variants are handled efficiently and effectively.
Source: https://arxiv.org/abs/2406.00415
