Source-linked AI summary
Deep Reinforcement Learning solution for pickup and delivery routing problems with time window and capacity constraints
Andrew Soroka, Alex Meshcheryakov, Sergey Gerasimov
TL;DR
CPDPTW routing combines pickup-and-delivery order, vehicle-capacity, and time-window constraints, but existing solutions do not address large-dimensional instances with all these constraints. The paper modifies JAMPR with deep reinforcement learning and reports fast suboptimal solutions across sizes, with solutions close to OR-Tools for 50–200-customer problems and zero failure rates across tested instances.
Problem
Existing routing tools do not provide solutions for large-dimensional pickup-and-delivery problems incorporating capacity and time-window constraints.
Method
The paper modifies JAMPR’s policy model and feasibility masks to enforce pickup-delivery order alongside capacity and time-window constraints.
Results
Fast suboptimal solutions arrive within tenths of seconds for all sizes; for 50–200 customers, final solutions are close to OR-Tools with lower optimization time, while failure rates remain zero.
Takeaways & Limitations
Deep reinforcement learning with JAMPR is a promising approach for high-dimensional route optimization under time-window and capacity constraints.
Takeaways & Limitations
For high-dimensional problems, training takes too long, and the fully optimized JAMPR solution loses about 20% of path cost to the metaheuristic.
Abstract
from arXiv · showhide
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.
1 Introduction
The introduction frames CPDPTW as a practically important, NP-hard extension of vehicle routing with pickup, delivery, capacity, and time-window constraints. It motivates a fast neural solver because existing tools remain limited in problem size, supported constraints, or feasibility.
- Problem background: VRP is a combinatorial optimization and integer programming problem that generalizes TSP, and both problems are NP-hard.
- Real-world constraints: Real-world routing adds pickup-and-delivery requirements, nonzero cargo, vehicle-capacity limits, and customer-availability constraints.
- Applications and gap: CPDPTW applies to courier delivery, taxi operation, and logistics between warehouses and points of sale, but no proposed solution covers large-dimensional routing with all important real-world constraints.
- Limitations of existing approaches: Existing methods struggle with realistic constraints: HGS supports only classical CVRP, while OR-Tools may fail to produce feasible solutions even for small problems.
- Motivation and approach: The work aims to develop a fast neural solver for high-dimensional problems involving time windows, limited vehicle volume, and multiple depots using reinforcement learning based on JAMPR.
2 Related work
Related work spans classical routing optimization through heuristics and metaheuristics, followed by deep-learning and reinforcement-learning approaches for constrained vehicle-routing problems. Neural methods progressed from Pointer Networks and attention-based models to JAMPR and iterative local-heuristic selection.
- Classical approaches: Classical routing approaches comprise mixed-integer programming and heuristics.Mixed-integer programming specifies routing domains through inequalities over real and/or integer variables, while heuristics are commonly used for such problems.
- Heuristics: Constructive heuristics rapidly build feasible routes but provide no optimality or solution-quality guarantees.Nearest neighbor constructs routes step by step by choosing the nearest available location from the depot.
- Metaheuristics: Metaheuristics improve routes through repeated neighborhood search, including local search, genetic algorithms, and ant colony methods.Examples include move, exchange, and 2-opt heuristics; LKH-3 uses Lin-Kernighan, while HGS CVRP combines a hybrid genetic algorithm with local search for instances up to 1000.
- Deep-learning methods: Deep-learning routing began with Nazari et al.’s Pointer Network adaptation for CVRP and advanced to Kool et al.’s self-attention transformer architecture.Nazari et al. replaced the recurrent encoder component with a shared-parameter linear embedding layer, while Kool et al. introduced an adapted transformer model.
- Reinforcement-learning methods: JAMPR extended attention-based routing with embeddings for truck paths and positions, enabling successful solution of CVRP-TW problems.Chen and Tian additionally proposed reinforcement learning that selects graph regions and applies established local heuristics iteratively.
3 Model
The model uses JAMPR’s encoder-decoder reinforcement-learning architecture to construct routes sequentially while representing route, vehicle, and problem context. It extends feasibility masking to enforce pickup-and-delivery ordering and supports parallel route construction for restrictive problems.
- Architecture: JAMPR models route optimization as a sequential decision problem formulated as a Markov decision process and solved with reinforcement learning.Routes are constructed incrementally by adding one node at a time.
- Architecture: The encoder embeds node features, while the decoder scores candidate nodes using context such as the depot, last selected node, and remaining bandwidth.Node features include coordinates, demands, and time windows.
- Architecture: JAMPR extends the Attention Model with route and vehicle encoders that enrich the context for vehicle-routing problems with time windows.The extended representation aggregates embeddings of each constructed route with additional fully connected neural networks.
- Parallel routing: Parallel construction of a fixed number κ of routes produces an extended action space while feasibility() filters nodes that would violate restrictions.The number of simultaneously planned routes is fixed by κ.
- Pickup-and-delivery constraints: The modified feasible() function adds a truck-specific mask that limits customers according to the specified pickup-and-delivery order.This mask operates similarly to time-window and visited-customer masks.
4 Data
The study selects CPDPTW instances from an R201-based distribution and specifies truck volumes and time horizons for problem sizes from 50 to 1000 points.
- Instance selection and parameters: Instances are selected from the R201 statistic in Solomon’s reference set, with truck volumes Q50 = 750, Q100 = 1000, Q200 = 3500, Q400 = 6000, and Q1000 = 12000.The corresponding problem sizes are 50, 100, 200, 400, and 1000 points.
- Instance selection and parameters: The time horizon starts at a0 = 0 for every instance, while b0 = 1000 for 50- and 100-point problems, 2000 for 200- and 400-point problems, and 4000 for 1000-point problems.The right boundary increases with task size.
5 Experiments
Experiments across low-, medium-, and high-dimensional CPDPTW instances show that JAMPR provides fast solutions and solves all tested instances, but training time and final solution quality degrade as problem size increases. The model also retains useful performance under distribution and distance-measure changes.
- Experimental setup: JAMPR was evaluated on 50-point, 100- and 200-point, and 400- and 1000-point CPDPTW problems, using 100 test instances per dimension except 10 for 1000 points.Models were trained with early stopping based on no decrease in path cost over 10 optimization steps.
- Low-dimensional problems: 3% reduction in route cost was achieved in the first seconds on low-dimensional problems, while 160 hours versus 3 hours of training changed final results by no more than 0.3%.The well-trained model reached a fast optimal solution, whereas the short-trained model provided a fast suboptimal solution.
- Medium-sized problems: 2 and 4 days of training were used for 100- and 200-point problems, where JAMPR produced fast suboptimal solutions that initially outperformed metaheuristics.JAMPR reached a plateau but delivered useful solutions within the first seconds of optimization.
- High-dimensional problems: 20% of path cost separated final JAMPR results from metaheuristics on high-dimensional problems, despite JAMPR producing fast approximate solutions.Training was especially limiting: early stopping occurred on day 7 for 400 points, while the 1000-point model completed only 10 training epochs within two weeks.
- Robustness: All instances received solutions from JAMPR, while OR-Tools increasingly failed to find a satisfying solution as task size increased, including within 200 seconds.This supports the reported robustness of the neural RL solver across problem sizes.
- Robustness: 25% or less extraneous data from a centered normal distribution still enabled JAMPR to outperform OR-Tools with a fast suboptimal solution, while Manhattan distances produced exactly the same results.Performance worsened as the share of normally distributed data increased, whereas OR-Tools retained its predictive ability.
6 Conclusions
The modified JAMPR deep reinforcement learning model solves CPDPTW robustly and quickly, providing optimal solutions for small and medium problems and suboptimal solutions for larger problems. It remains robust across instances and distribution changes, supporting its promise for high-dimensional constrained route optimization.
- Conclusions: The modified JAMPR model successfully applies deep reinforcement learning to CPDPTW with capacity and time-window constraints.The model adapts JAMPR to handle the additional constraints.
- Conclusions: 50-200 problems receive fast optimal solutions, while larger problems receive fast suboptimal solutions.The reported size range covers small and medium problems; larger problems exceed 200.
- Conclusions: For all problem sizes, JAMPR produces a fast suboptimal solution in the first tenths of seconds and approaches the OR-Tools baseline faster on 50-200 problems.Additional training can improve JAMPR performance, but large problems require too much computational time on one GPU.
- Conclusions: JAMPR has zero failure rate even with small optimization time and large problem sizes, whereas OR-Tools metaheuristics failure rate increases with problem size.The comparison concerns existence of solutions for all instances from the same distribution under fixed optimization time.
- Conclusions: JAMPR preserves fast suboptimal behavior when up to ∼25% of data comes from a normal radially symmetrical distribution.This demonstrates robustness to changing data distributions.
- Conclusions: Deep reinforcement learning algorithms like JAMPR are promising for high-dimensional route optimization with time-window and capacity constraints.This is the paper’s concluding assessment of the model’s applicability.
7 Future work
Future work focuses on improving solvers across problem scales: heuristic optimization combined with trained reinforcement learning performs strongly on low-dimensional problems, while high-dimensional tasks benefit from learned partitioning. Combining reinforcement learning with mixed-integer programming is proposed for CPDPTW problems because MIP is exact on low-dimensional instances but too slow for medium-sized ones.
- Low-dimensional solvers: Heuristics combined with a trained reinforcement model achieve state-of-the-art results for low-dimensional routing problems.These approaches perform best on low-dimensional problems but are difficult to extend with rules supporting new constraints.
- Low-dimensional solvers: Mixed-integer programming gives exact solutions for low-dimensional problems but is impractical for medium-sized problems because optimization requires substantial time.The paper identifies combining reinforcement learning algorithms and MIP solvers for CPDPTW as an interesting research direction.
- High-dimensional solvers: High-dimensional tasks can be split into subtasks solved with classical methods, while learned partitioning policies based on neural networks currently show the best results.Li et al. use a Transformer architecture to train a classifier/regressor for subproblem selection.