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

In plain words

Delivery vehicles often pick goods up at one place and drop them off at another. They must stay within a load limit and reach each stop inside its time slot. Finding good routes under these rules is hard once there are hundreds of stops, and classic solvers can take a long time to produce a route at all.

The authors take an existing neural route builder, JAMPR. It learns by trial and error to add one stop at a time to several routes built in parallel. They change it so that a delivery can only be scheduled after its pickup. They also make a missed stop cost a penalty instead of making the whole plan fail. Once trained, the network answers within seconds, but training takes hours to about two weeks on one GPU.

Compared with Google's OR-Tools heuristic, the authors report better early answers at every size they tested. Their model comes close to OR-Tools' final quality only up to 200 stops. For 400 and 1000 stops, the final neural answer stays about 20% behind the heuristic at the longest time tested.

TL;DR

• Adapts JAMPR, an attention-based reinforcement-learning route builder, to pickup-and-delivery routing with capacity and time windows (CPDPTW) §3.
• Changes: a pickup-order mask, and a soft penalty of 13 per unit of distance plus 10 per missed client §3.
• Author-reported: better early solutions than OR-Tools at every tested size; final quality close to OR-Tools only up to 200 customers §5, §6.
• Training costs 3 to 336 hours per model on one NVIDIA A40 tab. 1. No official code was found.
• The "optimal" wording for small and medium sizes is not checked against an exact solver §5.1, §6.

Problem

Classic exact methods (mixed-integer programming) are precise but too slow even for small instances. Heuristics handle extra constraints better, but OR-Tools can fail to find a feasible plan even for small problems. Strong heuristics such as LKH-3 and HGS need heavy manual tuning and long runs, and HGS handles only the basic capacitated problem. No deep-learning method had been studied for high-dimensional CPDPTW §1, §2.1, §2.2. The paper sets aside the hard version, in which a single missed client means no solution, and uses a soft version instead §3.

Method

The base model is JAMPR §3, §2.2. JAMPR extends the Attention Model of Kool et al. §2.2 with encoders for each route and vehicle. The paper treats routing as a sequential decision process and solves it with reinforcement learning §3. The paper's own changes are the pickup-order mask and the soft cost §3.

1. Node encoding. An encoder maps each node's features (coordinates, demand, time window and similar) to an embedding of dimension d_emb §3. The value of d_emb is not stated.
2. Decoding step. At step t, a decoder computes an attention query for each node against a context C^(t). The scores are used either greedily (highest score) or by sampling from a softmax §3. The policy is written π(i^(t+1) | C^(t), x; θ) §3, unnumbered.
3. Context. The context holds the embedding of the problem graph, the depot index, the last node added to a route and the remaining capacity §3.
4. Route and vehicle encoders (from JAMPR). Each route r is embedded from its node embeddings and from vehicle state φ_r: residual capacity, current node and current time. Fully connected networks aggregate these into the context §3.
5. Parallel routes. κ routes are built at the same time, which fixes the action set to feasible (route, node) pairs §3. The value of κ is not stated.
6. Pickup-delivery mask (added by the authors). A mask removes customers that a truck may not visit yet under the delivery order. It sits beside the time-window and visited-customer masks §3.
7. Soft constraints (added by the authors). Missed clients are allowed. The route cost is a linear combination of the distance travelled (coefficient 13) and the number of missed clients (coefficient 10), used both in training and at inference. The authors chose the coefficients empirically §3.
8. Training. The authors generate task instances on the fly from the distribution in §4. Training stops when the path cost does not decrease over 10 optimization steps §5, §5.2. The training algorithm and its baseline are not named.
9. Evaluation. Each trained model is evaluated on test sets of fixed size, and cost is plotted against the time allowed for optimization §5.

The decoding loop below is reconstructed from the text. The paper contains no algorithm block.

# Building one solution  [§3, reconstructed from the text; no alg. block]
# Input:  instance (nodes with coordinates, demand, time window, service)
# Output: routes; cost = 13 * distance + 10 * missed clients  [§3]

def build_solution(instance, policy, kappa):
    # Encode every node once, with the depot index in the context  [§3]
    node_embeddings = encoder(instance.node_features)
    # Open kappa routes that grow in parallel; kappa is not stated  [§3]
    routes = [start_route(instance.depot) for _ in range(kappa)]
    while unvisited_nodes_remain(routes, instance):
        # Feasible (route, node) pairs under capacity, time window,
        # visited and pickup-delivery order masks  [§3]
        actions = feasible_actions(routes, instance)
        # Route and vehicle embeddings (residual capacity, node, time)  [§3]
        context = build_context(routes, node_embeddings, instance.depot)
        # Score actions; greedy or sampled decoding is not stated  [§3]
        scores = policy(actions, context)
        chosen_route, chosen_node = select(actions, scores)
        append_node(routes[chosen_route], chosen_node)
    # Clients left unvisited are scored as missed, at weight 10  [§3]
    return routes

Key notation, unnumbered in the paper:

A = \{(r, i) \in \mathrm{feasible}(R^{(t)}_{\kappa} \times N)\} §3

Here R^(t)_κ are the active routes, N the clients, and feasible() keeps only the pairs that violate no restriction §3.

Hyperparameters

Results

Author-reported. Setup: CPDPTW instances from the §4 distribution, JAMPR model per size, OR-Tools baseline, one A40 GPU §5. The gap numbers below come from the text. The plotted curves fig. 2–fig. 6 are not given as tables.

Paper vs code

No official code.

Searched: the arXiv metadata and the LaTeX source (no code link in the abstract, the metadata or the TeX files); GitHub repository search for "CPDPTW", "jampr", "JAMPR pickup" and "vehicle routing reinforcement learning time windows capacity"; GitHub user search for the three author names. No repository belonging to the authors was found. Two third-party repositories turned up and were not used: jokofa/JAMPR (MIT), the original JAMPR code from another group, and himloul/primal (a CPDPTW solver with no license, based on simulated annealing and Prins' algorithm).

Pitfalls

• "Optimal" is not checked. The abstract and the conclusions call the small and medium solutions "optimal". The only reference is OR-Tools, and no exact solver is reported §5.1, §6. Read the claim as "close to OR-Tools", not as verified optimality.
• Averages use different instance sets. For n=50 and n=100/200, the metric averages only the instances the method solved §5.1, §5.2. JAMPR solves all instances, while OR-Tools fails on more of them as n grows §5.4. Averages for the two methods therefore cover different sets of instances at large n.
• Reference budgets change with size. Each size has its own OR-Tools reference (100, 200, 400 s; 70 s is mentioned as a usable window). Gaps are not comparable across sizes §5.1–§5.3.
• Gap formula missing. The paper calls the metric a "percentage deviation" from OR-Tools' best result, but writes no formula. The cost unit is also not stated.
• Penalty scale depends on units. The soft cost is 13 × distance + 10 × missed clients. The relative weight only means something once the coordinate scale and distance unit are fixed. §4 does not state them. Changing the scale changes the trade-off, and the coefficients were chosen empirically §3.
• Route closure and depot return are not stated. The paper does not say whether routes must return to the depot, or how open routes are scored beyond the missed-client penalty §3.
• Pickup-delivery mask is underspecified. The paper says only that the mask follows the delivery order. It does not say how each delivery is linked to its pickup, or how deliveries are assigned to depots beyond an even split §3, §4.
• Time-window sampling is not described. The instances follow a distribution "based on the R201 statistic", but the method for sampling windows is not given §4.
• Units of "epoch" and "step" are undefined. The early-stopping rule counts "optimization steps", and the table counts "epochs". The number of instances per epoch and the batch size are not stated §5, tab. 1.
• Numerical slips. §5.1 says two orders of magnitude more training time, but 163 h / 3 h ≈ 54×. The Figure 2 caption says "CVRPTW", but the task is CPDPTW fig. 2.
• Hyperparameters come from elsewhere. The paper builds on JAMPR without restating its settings (κ, d_emb, optimizer, learning rate, batch size). Any value taken from the original JAMPR paper is not confirmed by this paper's text. Mark it as such in an implementation.
• Test-time decoding is unspecified. The paper describes greedy and sampled decoding, but does not say which one produced the reported numbers §3.
• Small test sets. 100 instances per size, and only 10 for n=1000 §5, §5.3. The n=1000 curves rest on 10 instances.
• "Robust" is narrow. The paper uses the word for two things only: a solution always exists, and the model keeps working under a normal-distribution shift §5.4. It does not test other shifts.
• Manhattan result has no numbers. The claim that the Euclidean and Manhattan results are "exactly the same" is unexpected for a distance-based cost. No table backs it, so treat it as unverified §5.4.
• Compute cost dominates. Training takes 3 h to 336 h on one A40. The authors say that for large sizes, training takes too much computational time on one GPU §5.3, §6.

Lineage

• Builds on: JAMPR, Falkner et al. (cited as falkner2020learning) is the base model, extended with route and vehicle encoders §2.2, §3. The Attention Model of Kool et al. (cited as kool2018attention) is the basis of JAMPR §2.2, §3. Self-attention (cited as vaswani2017attention) is used inside the encoder-decoder §2.2. A title search of the wiki found no card for these works.
• Related card: Multi-Decoder Attention Model with Embedding Glimpse for Solving Vehicle Routing Problems, an attention-based VRP solver.
• Compared against: Google OR-Tools (cited as perron2011operations), the only baseline in the experiments §2.1, §5.
• Mentioned as future work: the learned partitioning approach of Li et al. (cited as li2021learning) and the destruction operator of Lu et al. (cited as lu2019learning). The authors plan to combine learned partitioning with JAMPR §7.
• Superseded by: not known.