cs.LGAug 14, 2026

Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints

Authors: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Organizations: Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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.

Figures & tables

Figure 1: An original image of JAMPR architecture. Source: Figure 1 from [ 5 ]
 Problem sizeEpochTraining time (hours)
Small50103
723163
Medium1002347
2002193
Large40025188
100010336
Table 1: Table with the time spent on training all the presented models for the CPDPTW task.
Figure 2: Model performance on small-size (50) CVRPTW proplem. Dotted and dashed lines show JAMPR solution after 10 and more than 700 epochs of training, respectivelly. Well trained JAMPR model beat the heuristic solution in cost. JAMPR model after 10 epochs of taining provide fast suboptimal solution. Figure has two scales: total cost (right) and gap with respect to final baseline solution (left).
Figure 3: Model performance on medium problem sizes (100 — top, 200 — bottom panel). JAMPR gives fast suboptimal result; OR-Tools and JAMPR performance are close around 70 seconds of optimization. Each figure has two scales: total cost (right) and gap with respect to final baseline solution (left).
Figure 4: Performance of the model at large graph sizes (400 — top, 1000 — bottom, respectively) looks similar to the behavior seen previously on problems of smaller size. For optimization time less than few minutes JAMPR provide a much more accurate suboptimal solution than OR-Tools baseline (note that at small optimization time OR-Tools is not able to give any solution at all). Each figure has two scales: total cost (right) and gap with respect to final baseline solution (left).
Figure 5: The dependence of the number of unsolved problems on the size of the problem for different time limits. For all sizes except a thousand, 100 instances of the task were tested, for a thousand this number is 10.
Figure 6: Robustness of the model on different percentage of unknown distribution.
More in this topic

Vehicle Routing

Vehicle routing studies how to assign and sequence trips for fleets while meeting capacity, time, energy, and service constraints.

See all 130 papers

Explore similar work

CardsList

  1. JAMPR+/L2D: scalable neural heuristic for constrained vehicle routing problems in dynamic environment

    Aug 14, 2026Andrew Soroka, Alex MeshcheryakovVehicle RoutingNeural Combinatorial Optimization

    Moscow State University, Moscow, Russian Federation · Space Research Institute of RAS, Moscow, Russia

  2. Cluster-Aware Attention-Based Deep Reinforcement Learning for Pickup and Delivery Problems

    Mar 9, 2026Wentao Wang, Lifeng Han, Guangyu ZouVehicle RoutingRL for Combinatorial Optimization

    Leicester International Institute, Dalian University of Technology, Panjin, 124221, Liaoning, China. · Department of Electronic and Information Technology, Dalian University of Technology, Panjin, 124221, Liaoning, China.

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

    Aug 14, 2026Andrew Soroka, German Mikhelson, Alexander Mescheryakov +1Vehicle RoutingMetaheuristic Optimization

    Moscow State University, Faculty of Computational Mathematics and Cybernetics, Moscow · Space Research Institute of RAS, Moscow