🤖 machine learning

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

This paper presents a novel deep reinforcement learning approach, based on a modified JAMPR model, that effectively solves medium-sized Pickup and Delivery problems with capacity and time window constraints (CPDPTW) in real-time and provides fast suboptimal solutions for large-scale instances exceeding 200 nodes.

Original authors: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Published 2026-08-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are the captain of a fleet of delivery trucks in a bustling, ever-growing city. Your job is to drop off packages and pick up returns for hundreds of customers, but you have a strict set of rules: your trucks can only carry so much cargo, and every customer has a specific window of time when they are home to receive a package. If you arrive too early or too late, or if you try to stuff too many boxes into the back of a van, the plan fails. This is the "Pickup and Delivery Problem," a massive puzzle that gets harder the more people you add to the mix.

For decades, computers have tried to solve this by acting like super-fast calculators, testing millions of possible routes one by one to find the perfect path. But as cities grow and the number of stops explodes, these calculators get stuck. They take hours to figure out a route that a human could sketch in minutes, or worse, they give up entirely and say, "I can't solve this." This is where a new kind of computer brain steps in: Deep Reinforcement Learning. Think of this not as a calculator, but as a video game character that learns by playing. Instead of calculating every single possibility, it plays the delivery game thousands of times, getting faster and smarter with every round, learning to spot the best moves without needing to check every single option.

In this paper, Andrew Soroka and his team at Moscow State University and the Space Research Institute of RAS decided to teach this "video game brain" how to handle the messy, real-world rules of delivery: limited truck space and strict time windows. They took an existing smart model called JAMPR and gave it a special upgrade to understand the "pickup and delivery" rules, where a truck might need to grab a package at one stop and drop it off at another, all while juggling capacity limits.

The researchers found that their upgraded model is a speed demon for small to medium-sized cities (with 50 to 200 stops). In these scenarios, the AI can spit out a nearly perfect route in the first few seconds, beating the traditional "calculator" methods that take much longer to even start. It's like having a delivery driver who knows the city so well they can instantly shout out the best route, while the old-school computer is still trying to read the map.

However, the story gets a bit more complicated when the city gets huge (400 to 1,000 stops). Here, the AI still wins the race for speed, offering a "good enough" solution almost instantly, while the traditional methods struggle to find any valid route in the first minute. But, the AI isn't perfect yet. To get the absolute best route for these giant cities, the AI needs to "train" for days, which is a long time. Even after training, for the largest problems, the AI's final route is still about 20% more expensive (in terms of distance) than the very best solution a traditional method could eventually find if given unlimited time. In fact, once the optimization time passes just a few minutes, the traditional methods actually overtake the AI, finding better routes that the AI cannot match without significantly more training.

The team also tested how tough their AI is when the rules change. They found that the AI is incredibly reliable within the specific test conditions used: it never failed to give some solution, even when the traditional computer gave up and said "impossible" for the same distribution of problems. However, if the city layout changes drastically—say, from a random spread of houses to a pattern where everyone lives in a tight circle—the AI's performance dips a bit, though it still manages to beat the traditional methods for the first hour of solving.

In short, the paper suggests that this deep learning approach is a powerful new tool for real-time logistics. It doesn't replace the old methods entirely, especially for the biggest, most complex puzzles where the absolute perfect answer is needed. But for situations where you need a fast, reliable answer right now—like a courier service reacting to traffic or a sudden surge in orders—this AI is a game-changer, offering a robust, fast solution where traditional tools often stall or fail.

Technical Summary: Deep Reinforcement Learning for CPDPTW

Problem Definition

The paper addresses the Pickup and Delivery Problem with Capacity and Time Window constraints (CPDPTW). This is a combinatorial optimization problem where a fleet of vehicles must transport goods from specific pickup locations to delivery locations. The problem is characterized by three primary real-world constraints:

Capacity: Vehicles have a maximum volume limit ( $Q$ ).
Time Windows: Clients are only available during specific time slots.
Pickup and Delivery (PDP): Unlike standard Vehicle Routing Problems (VRP), goods may be picked up from a depot or a client and delivered to another client, requiring strict sequencing (pickup before delivery).

The authors note that while classical approaches (Mixed-Integer Programming, heuristics) exist, they struggle with large-scale instances (e.g., >200 nodes) under real-world constraints, often suffering from high computational loads, lack of flexibility in handling new constraints, or failure to find feasible solutions within reasonable timeframes.

Methodology

The authors propose a Deep Reinforcement Learning (DRL) approach based on a modified JAMPR (Joint Attention Model for Pickup and Routing) architecture.

Model Architecture

Base: The model builds upon the JAMPR framework, which extends the Attention Model (AM) and Pointer Networks. It utilizes an encoder-decoder structure with self-attention mechanisms.
State Representation: The problem is modeled as a Markov Decision Process (MDP).
- Encoder: Encodes node features (coordinates, demands, time windows) into hidden embedding vectors.
- Context ( $C(t)$ ): Includes the problem graph embedding, depot index, the last node added, and remaining vehicle capacity.
- Extended Context: To handle PDP and time windows, the model incorporates specific embeddings for constructed routes and vehicle characteristics (residual capacity, current node, current time) into fully connected neural networks. This allows for the parallel construction of multiple routes.
Action Space: The action is defined as a pair $(r, i)$ , representing the selection of a node $i$ to be added to an active route $r$ . A feasibility mask is applied to ensure constraints (capacity, time windows, and PDP order) are not violated.
Policy: The decoder computes attention scores for feasible nodes. These scores are used for greedy selection or sampled via a softmax distribution during training.

Modifications for CPDPTW

The authors introduced specific modifications to the standard JAMPR model to address the PDP nature of the problem:

PDP Masking: An additional mask was added to the feasible() function to enforce delivery order constraints (a pickup must occur before its corresponding delivery).
Soft Constraint Handling: Recognizing that finding a 100% feasible solution for all clients is sometimes impossible in hard formulations, the authors adopted a SOFT setting. The final cost function is a linear combination of the total distance traveled and the number of missed clients (weighted 13:10, respectively). This ensures the model always produces a solution, even if partial.

Training and Data

Data Generation: Instances were generated based on the Solomon R201 distribution. Problem sizes ranged from 50 to 1000 nodes. Truck capacities and time horizons were scaled according to problem size.
Training: Models were trained using reinforcement learning with early stopping criteria (no cost reduction over 10 steps). Training times varied significantly by problem size, ranging from 3 hours for 50-node problems to over 336 hours for 1000-node problems.
Baseline: The proposed model was compared against Google OR-Tools, a standard heuristic solver used in real-world applications.

Key Results

The performance was evaluated across three problem size categories:

1. Small Size (50 nodes)

Performance: The trained JAMPR model provided a fast optimal solution, beating the heuristic solution in cost during the first few seconds of optimization.
Cost: As optimization time increased, the results of the JAMPR model gradually approached those of OR-Tools. After extensive training (723 epochs), the final results differed from the OR-Tools baseline by no more than 0.3%.
Feasibility: JAMPR solved 100% of instances, whereas OR-Tools failed to find solutions for an increasing number of instances as the problem complexity grew.

2. Medium Size (100–200 nodes)

Performance: The model provided fast suboptimal solutions that were superior to metaheuristics in the initial seconds of optimization (15–200% better cost than OR-Tools).
Convergence: While the model's performance plateaued quickly, it consistently outperformed OR-Tools in speed. OR-Tools required significantly longer optimization times to approach similar cost levels.
Feasibility: JAMPR maintained a 0% failure rate, solving all instances, while OR-Tools failed to find feasible solutions for a growing percentage of instances as size increased.

3. Large Size (400–1000 nodes)

Performance: For high-dimensional problems, the neural model still provided a fast suboptimal solution that was significantly better than OR-Tools in the first 60 seconds (where OR-Tools often found no solution at all).
Limitations: As optimization time increased, metaheuristics (OR-Tools) eventually overtook the neural model. The final result of JAMPR with maximum optimization time lost about 20% of the path cost compared to the metaheuristic.
Training Cost: Training for large instances was computationally expensive (e.g., 336 hours for 1000 nodes), limiting the ability to fully optimize the model within reasonable timeframes on single GPUs.

Robustness Analysis

Distribution Shift: The model demonstrated robustness to changes in data distribution. When tested with a mix of uniform and normal distributions, the model maintained its ability to provide fast suboptimal solutions even with up to 25% of data from the new distribution.
Metric Invariance: The model's performance remained consistent when distance calculations were switched from Euclidean to Manhattan metrics.

Significance and Claims

The paper claims to be the first successful application of a deep reinforcement learning approach (specifically a modified JAMPR model) to solve the CPDPTW problem.

The authors highlight three main contributions:

Speed vs. Quality Trade-off: The model offers a fast suboptimal solution (in tenths of a second) that is often superior to classical heuristics in the early stages of optimization. This is particularly valuable for dynamic systems with strict time limits.
Robustness and Feasibility: Unlike traditional metaheuristics which may fail to find any feasible solution for large or complex instances, the neural model guarantees a solution (even if partial, under the SOFT setting where missed clients are penalized) for all problem instances, regardless of size.
Scalability of Solution Existence: The failure rate of the neural model remains zero across all tested sizes, whereas the failure rate of OR-Tools increases with problem size.

The authors conclude that while deep RL models currently require significant training time for large-scale problems and may not yet match the final optimality of metaheuristics for very large instances, they represent a promising direction for real-time routing optimization where speed and solution existence are critical. They suggest future work could involve combining these RL models with Mixed-Integer Programming (MIP) solvers or using learned partitioning policies to handle high-dimensional problems more effectively.