The problem of route optimization with realistic constraints is becoming extremely relevant in the face of global urban population growth. While we are aware of approaches that theoretically provide an exact optimal solution, their application becomes challenging as the problem size increases because of exponential complexity. We investigate the Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) and compare solutions obtaining by exact solver SCIP with heuristic algorithms such as LKH, 2-OPT, 3-OPT, the ORTools framework, and the deep learning model JAMPR. We demonstrate that for problem of size 50 deep learning and classical heuristic solutions became close to SCIP exact solution but requires less time. Additionally for problems with size 100, SCIP exact methods around 13 times slower that neural and classical heuristics with the same route cost and on around 50% worse for the first feasible solution on the same time. To conduct experiments, we developed the Smart Routes platform for solving route optimization problems, which includes exact, heuristic, and deep learning models, and facilitates convenient integration of custom algorithms and datasets.
Figures & tables
Рис. 1: The JAMPR deep RL architecture modified to solve CPDPTW problems. Added block M+ of learnable masks applied to output of decoder (policy πθ ).
Рис. 2: Smart Routes System architecture. Three main blocks: 1) Dataset module is an entry point for all data manipulations, also stores prepared datasets and allows loading third-party data in a specified format; 2) Algorithm module responsible for train and evaluate all available algorithms on prepaired datasets. There is possibility to add user algorithm via special interfaces; 3) Solution module produces metrics, visualizes them and offers web interface for communication with system.
Algorithm Type
Framework
SCIP
Gurobi
OR-Tools
Smart Routes
Exact Approaches
+
+
+
+
Heuristic Approaches
+
+
+
+
Deep Reinforcement Approaches
—
—
—
+
Visualization of Results
—
—
—
+
Adding Custom Algorithms
—
—
—
+
Table 3
Рис. 3: Summary result of classical approaches, where each dot denotes the result of a specific algorithm on a given problem size. The horizontal line indicates the time required for the algorithm to achieve the best cost of the path, the vertical line indicates the best cost achievable by the algorithm. The orange line shows the applicability limit of exact approaches: on the left there is not enough time for the algorithm to provide a solution, the zone on the right is an area favorable for choosing exact approaches.
Рис. 4: Performance of the considered models on the CVRPTW with 50 points. Solid lines represent the results of approximate heuristic approaches. Dotted line represents the results of SCIP - the best cost achieved with the longest time. Dashed line represents JAMPR after 700 epochs of training - a fast suboptimal solution with subsequent asymptotic approximation to the heuristic. The figure has two scales: total cost (on the right) and the gap compared to the final best solution (on the left).
Рис. 5: Performance of the considered models on the CVRPTW with 100 points. Solid lines represent the results of approximate heuristic approaches. Dotted line represents the results of SCIP. Dashed line represents JAMPR after 23 epochs of training - a fast suboptimal solution with subsequent asymptotic approximation to the heuristic. Despite the considerable optimization time, SCIP failed to achieve the accuracy of JAMPR. The figure has two scales: total cost (on the right) and the gap compared to the final best solution (on the left).
The vehicle routing problems with real-world constraints (we consider vehicles capacity limits, time windows constrains, pickup-and-delivery multi-depo --- CPDPTW) pose significant computational challenges. While classical exact and heuristic methods remain effective to solve problems of small/medium size (N≲100), they often lack adaptability and scalability for larger logistics tasks. In this work, we show how JAMPR+/L2D RL deep learning model, proposed in to solve large CPDPTW problems can be adopted in the case of substantial changes of graph distance matrix. We test performance of JAMPR+/L2D model for medium-sized CVRP and VRPTW problems on CVRPLIB benchmarks: JAMPR+/L2D outperforms the state-of-the-art heuristic HGS in over 85% of instances, achieving improvement in objective gap. We show that the JAMPR+/L2D model trained on CPDPTW problem, generalizes well for tasks with simpler constraints (CVRP, VRPTW), for different problem sizes and for moderate changes in distance matrixes. For more substantial changes in distance matrixes, we propose here to make fast finetuning of JAMPR+: on ORTEC data (for CPDPTW) the proposed strategy remarkably reduces the objective gap without full model retraining, what will give both accuracy and rapid inference of the model in the practical routing scenarios with distance matrix changes.
Andrew Soroka, Alex Meshcheryakov
Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia
The task of constructing vehicles optimal routes for pickup and delivery of goods is one of most promising tasks in the context of global urban population growth. Although this kind of problems with small size can be solved by various classical approaches, a fast (or realtime) route optimizer under the constraints of the real world (such as capacity and time windows constraints) for medium-large size problems still remains a highly challenging task. In this work we, for the first time, successfully applied a deep Reinforcing Learning approach (modified JAMPR model) to solve Pickup and Delivery problem with Capacity and Time Window constraints (CPDPTW). We obtained a robust model that gives a fast optimal solution for problems of small and medium size, and gives fast suboptimal solution for problems of larger (> 200) size.
Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov
Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia
Routing problems, like the Traveling Salesman Problem (TSP) and the Capacitated Vehicle Routing Problem (CVRP), are NP-hard and slow to solve for large instances. Diffusion-based solvers can be trained in a supervised way using sets of optimal solutions, and then quickly solve new test instances. However, for large instances, optimal solutions are hard to find, and diffusion models fail to generalize to instance sizes outside their training distribution. Here we describe ResizeCO, a label free size-generalization approach that addresses both the change in statistical properties of larger instances, and the computational challenge of solving them quickly. It uses reinforcement learning on large-scale instances to adapt a diffusion model trained on small instances. Specifically, we adapt GRPO to this problem, using route length as the training signal. ResizeCO also formulates k-opt as a tree search, solved by a beam search on the GPU. In size-generalization experiments on TSP and CVRP instances with up to 10000 nodes, ResizeCO achieves a Pareto front over route quality and time that dominates learned solvers, and also outperforms other solvers at short run times, setting a new state of the art.
Barak Itzchak Davidovitch, Eli Meirom, Ethan Fetaya +1