Smart routes: a system for development and comparison of algorithms for solving vehicle routing problems with realistic constraints

Technical Summary: Smart Routes – A System for Development and Comparison of Algorithms for Solving Vehicle Routing Problems with Realistic Constraints

Problem Statement
The paper addresses the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW), a critical challenge in transport logistics involving the optimization of routes for a fleet of vehicles to serve customers with specific capacity limits and delivery time windows. The authors highlight that while exact mathematical approaches theoretically yield optimal solutions, their application is severely limited by exponential complexity as problem dimensions increase. Consequently, there is a need to balance solution quality against search time, particularly for real-world scenarios involving growing urban populations and complex constraints. Furthermore, the authors identify a lack of unified platforms that allow researchers to seamlessly integrate, compare, and visualize diverse algorithmic approaches (exact, heuristic, and deep learning) without altering system architecture.

Methodology
The study employs a comparative analysis of three distinct classes of algorithms applied to CVRPTW instances:

1. Exact Methods: The authors utilize the SCIP optimization suite, which employs Branch&Bound, Cutting Plane, and Branch&Cut algorithms to find optimal solutions.
2. Classical Heuristics: The study evaluates constructive and metaheuristic approaches, specifically the Lin-Kernighan (LKH) heuristic, 2-OPT, and 3-OPT local search methods, as well as Google's OR-Tools framework.
3. Deep Reinforcement Learning (DRL): The authors utilize a modified version of the JAMPR (Joint Attention Model for Pickup and Delivery with Time Windows) model. This architecture adapts the Attention Model (AM) by adding trainable matrices ($M+$) to the decoder output to handle specific constraints. The model treats route construction as a sequential decision-making process (Markov Decision Process), where the state includes the current route and unvisited nodes, and actions involve selecting the next node.

To facilitate these comparisons, the authors developed Smart Routes, a custom software platform. This system features:

• Modular Architecture: Comprising a Dataset module (for data generation and loading), an Algorithm module (for training and evaluation of user-defined or built-in models), and a Solution module (for metric generation and visualization).
• Extensibility: Users can integrate custom algorithms by inheriting from base classes, allowing for the testing of new ideas without modifying the core system.
• Visualization: The platform provides interactive web interfaces to visualize routes and generate performance graphs comparing route costs over time.

Experimental Setup
Experiments were conducted on artificial datasets generated based on the Solomon R201 benchmark set, focusing on problem sizes of 50 and 100 nodes.

• Constraints: The problem was solved in "soft" settings, allowing for the skipping of unvisited clients with a penalty cost.
• Hardware: Tests were run on a server equipped with an NVIDIA Tesla A40 GPU and an Intel Xeon Gold CPU.
• Time Limits: Heuristic and DRL methods were given 100s (for 50 nodes) and 200s (for 100 nodes). Exact methods (SCIP) were allocated significantly longer times (1000s and 2000s, respectively) to attempt finding optimal solutions.

Key Results
The comparative analysis yielded the following findings:

• 50-Node Instances: Both classical heuristics (LKH, OR-Tools) and the deep reinforcement model (JAMPR) rapidly produced suboptimal solutions. Within the first 10 seconds, SCIP's solution quality was inferior to these methods. While SCIP eventually surpassed them after approximately 100 seconds, the final gap between the DRL model and the exact solution remained less than 5%.
• 100-Node Instances: The limitations of exact methods became pronounced. SCIP required approximately 13 times longer than heuristic and DRL methods to achieve the same route cost. Furthermore, within the allocated time, SCIP failed to find an optimal solution, and its first feasible solution was approximately 50% more costly than those provided by OR-Tools and JAMPR.
• Scalability: As problem dimensionality doubled, the time required for SCIP to find a solution increased roughly 14-fold, whereas the performance of heuristic and neural approaches remained relatively stable, suggesting that exact methods become infeasible for problems of 100 nodes or larger.

Significance and Claims
The paper claims two primary contributions:

1. The Smart Routes Platform: A unified, extensible environment that integrates exact, heuristic, and deep learning approaches for VRP. The authors argue this system offers a significant advantage over existing frameworks (like OR-Tools, Gurobi, and SCIP) by supporting deep reinforcement learning, providing built-in visualization, and allowing easy integration of custom algorithms.
2. Empirical Validation of Approaches: The study provides a comprehensive comparison demonstrating that for problems of moderate size (50 nodes), classical heuristics and deep reinforcement learning offer a superior trade-off between solution quality and computation time compared to exact solvers. For larger instances (100 nodes), the paper concludes that exact methods are practically infeasible due to exponential time growth, while deep reinforcement learning and advanced heuristics provide fast, high-quality suboptimal solutions.

The authors position their work as a step toward more efficient route optimization in the face of global urban growth, emphasizing that their platform facilitates the rapid testing and comparison of new algorithmic ideas in logistics.