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.
Figures & tables
Paper
Cap.
Time Windows
PDP
Problem Size
DMC
TW1
TW2
TW3
<100
<1000
>1000
AM, 2019 [ 18 ]
+
-
-
-
-
+
-
-
-
JAMPR, 2020 [ 10 ]
+
+
+
+
-
+
-
-
-
L2I, 2020 [ 21 ]
+
-
-
-
-
+
-
-
-
W. Kool, 2021 [ 17 ]
-
+
+
-
-
+
-
-
- ⋆
L. Xin, 2021 [ 40 ]
+
+
-
-
+
+
+
-
-
Table 1: List of papers, where RL neuroheuristics were applied to constrained VRP problems. Time windows constraints are considered of three types: hard (TW1), medium (TW2) and soft (TW3). The last column (DMC) means Distance Matrix Changes. ”+” against method denotes the presence of a constraint in the corresponding paper, minus denotes its absence or unsatisfactory result.
Figure 1: Deep RL transformer architectures for VRP problems with different constraints. Top row: AM (left), JAMPR (right). Bottom row: JAMPR+ (left), JAMPR+/L2D (right).
Figure 2: Solver performance over runtime: curves show the mean GAP (%, lower is better) versus time limit, where GAP is computed relative to the best solution observed (BSO) across all methods and all time points (global best across curves). Top panels represent generated Solomon distribution. Bottom panels represent real-world ORTEC data. Left upper panel: JAMPR+ best basic solver across all heuristic models for CPDPTW with size 50. Right upper: JAMPR+/L2D outperform heuristic without finetuning for larger problem size on known distance matrix distribution for CPDPTW with size 200. Left bottom: tuned mask of JAMPR+/L2D gains best solution for unseen distance matrix distribution over all heuristics for CPDPTW with size 200. Right bottom: JAMPR+/L2D outperforms all heuristic on weaker constraints without retraining for VRPTW with size 200. Proposed JAMPR+/L2D model is the best algorithm for solving route optimization problems with sizes 50 and 200 and VRPTW and CPDPTW constraints.
Figure 3: GAPs(%) for JAMPR+/L2D and HGS on CVRPLib test instances relative to best-known solutions (BKS). JAMPR+/L2D outperforms HGS on CVRP (left panel) and VRPTW (central panel) constraints and on problem sizes from 200 to 1000 (right panel). See text for details.
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
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.
Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1
Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow
Latent recursion repeatedly processes internal representations through the same neural network. Recent work has shown this approach to be effective on structured reasoning tasks such as Sudoku and maze solving. However, whether latent recursion can support neural routing remains unclear. We introduce RELAGRAM (Recursive Latent Graph Model), a novel approach that brings latent recursion to graph combinatorial optimization. RELAGRAM encodes a capacitated vehicle routing problem (CVRP) instance as edge tokens; a compact transformer recurrently updates the latent representations of these tokens. An output head maps the answer state to an edge heatmap, from which an autoregressive decoder constructs a feasible solution. On CVRP-100 instances, the 0.53M-parameter RELAGRAM achieves gaps to a PyVRP reference of 13.4%, 9.8%, and 8.3% under greedy decoding, eightfold symmetry augmentation, and 256-candidate search, respectively. Trained only on CVRP-100, RELAGRAM generalizes zero-shot to CVRP-500 and CVRP-1000, achieving gaps of 15.6% and 21.7% under 256-candidate search. Together, these results demonstrate that latent recursion is a promising approach to neural routing.