Learned Delivery Routing

How it fits together

Three techniques, one loop.

Each part answers one question. The neural network says how long a trip takes; the CSP says which van; the search says in what order.

01 · LEARN

Neural network

A numpy MLP predicts trip minutes from pickup zone, drop-off zone, hour, weekday and typical distance. Output: a 24 × 20 × 20 hourly time matrix.

→

02 · ASSIGN

Constraint solver

Variable = van per order. Rules: the window is reachable from the depot, capacity, at most 10 stops, and "different van" pairs derived from the NN times. Backtracking, Forward Checking and AC-3 are switchable.

→

03 · ORDER

A* search

State = (stop, visited set, clock). Cost = travel plus waiting. An admissible time-dependent heuristic; UCS and Greedy as baselines.

↺ Feedback: if a van's best route is still late, the first late pair becomes a new "different van" rule and the CSP runs again (up to 5 loops). If nothing works, the system reports which orders are unserviceable and why, and tries widening windows in 15-minute steps.

Data

Real trips, generated orders.

NYC Taxi & Limousine Commission trip records, January 2022. From 2.46 M yellow-taxi trips we keep weekdays, durations of 1 to 120 minutes and the 20 busiest zones (19 in Manhattan plus JFK), about 300 k trips. The split is by day: three weeks to train, the last week to test.

Orders, time windows, demands and van capacities are generated by a seeded generator (15, 20 and 30 orders × 10 seeds). Taxi times only approximate van times, so we apply a documented van factor of 1.2.

Step	Trips
Yellow taxi, Jan 2022	2.46 M
Weekdays, 1–120 min, valid zones	filtered
Both ends in the top-20 zones	≈ 300 k
Test set (last week)	93,592

Neural network

Ties the lookup table, wins where data is thin.

A hand-written numpy MLP: zone one-hots (acting as embeddings), hour and weekday encodings and the pair distance, trained with Adam, Huber loss and early stopping. Compared against three baselines on the same held-out week.

Model	MAE (min)	RMSE	Bias
NN (MLP) ours	3.23	5.44	−1.87
Historical average (pair, hour)	3.24	5.42	−1.61
Distance-linear	4.14	6.40	−1.62
Global mean	5.45	8.88	−1.31

Honest reading: overall the NN is tied with the historical lookup table. Its advantage shows on rare (pair, hour) cells with fewer than 3 training trips: MAE 3.25 vs 4.69. Every model under-predicts the slower test week by about 1.7 minutes.

Training and validation loss per epoch — Learning curve with early stopping.

Mean absolute error by hour for each model — Error by hour of day, all models.

Predicted zone-to-zone travel time matrices at different hours — The deliverable the planner uses: the predicted zone-to-zone time matrix, by hour.

A* with a heuristic that never lies.

The obvious heuristic, "cheapest incoming trip at the current hour", is not admissible when travel times change through the day (our counter-example: 40 > 35). Our fix takes the minimum over all later departure times and adds a waiting bound. Step through the real A* trace for van 0 on the demo day:

Expansion 1

g, minutes so farh, admissible estimate left

f = g + h stays at 461 while h hands its estimate over to g. The bound is tight from the start because the time windows force most of the waiting.

Stops	Algorithm	Nodes expanded	Gap to optimum
6	UCS	95.5 ± 16.5	0%
6	Greedy	64.7 ± 16.4	6.7%
6	A* (ours)	34.0 ± 20.4	0%
10	UCS	1,519 ± 161	0%
10	Greedy	1,312 ± 440	4.6%
10	A* (ours)	368.7 ± 249	0%

10 seeds per size. A* matched brute force in 30/30 checks. Honest note: at this size UCS is still faster in milliseconds, because each A* node costs more to evaluate.

Nodes expanded, cost gap and time for UCS, Greedy and A* from 6 to 10 stops — Experiment 1: A* vs UCS vs Greedy, 6 to 10 stops.

Constraint satisfaction

Pruning, switched on and off.

The same hard rush-hour instance (20 orders, windows 09:00 to 12:00, zero spare capacity, 4 rules from the NN), solved four ways. Pick a solver:

Bars show assignments tried. With only 3 values per variable and "≠" constraints AC-3 adds little; forward checking's capacity pruning and most-constrained-first ordering do most of the work.

Orders	Solver	Median assignments	Solved / unsat / limit
30	BT	165.5	8 / 0 / 2
30	BT + FC	105.5	8 / 0 / 2
30	BT + FC + AC-3	104.5	8 / 1 / 1
30	+ most-constrained first	36.5	9 / 1 / 0

CSP assignments and backtracks for 15, 20 and 30 orders — Experiment 2: BT vs FC vs AC-3 for 15, 20, 30 orders.

Constraint graph of the demo day with the learned rule dashed — Demo-day constraint graph. The dashed red edge is the rule learned in loop 1.

Demo day · Thursday, 20 orders, 3 vans

Late once, learned, fixed.

=== INTEGRATION LOOP (NN -> CSP -> A*) loop 1: CSP solved (rules: 2 from NN, 0 learned; 20 assignments, 0 backtracks) van 0 late by 2.1 min -> new rule: orders 16 and 5 on different vans loop 2: CSP solved (rules: 2 from NN, 1 learned; 20 assignments, 0 backtracks) status: ok -- all 20 orders on time after 2 loop(s)

In loop 1, van 0 would serve JFK Airport (15:00–15:30) and then Upper East Side North (window from 15:45): 2.1 minutes late. That pair becomes a rule; in loop 2 every order is on time.

Map of the three van routes across Manhattan and JFK — Routes per van, with a zoom on Manhattan.

Timeline of each van showing time windows, arrivals, waiting and service — Timeline: window, arrival, waiting and service for every stop.

When there is no solution

Run with --impossible: order 0 moves to JFK with a window of 08:00–08:20.

NO SOLUTION: not every order can be served on time. Unserviceable orders / reasons: - order 0: window not reachable from the depot by any van: van 0: earliest arrival 08:48 is after the window closes 08:20 van 1: earliest arrival 09:46 is after the window closes 08:20 van 2: earliest arrival 10:43 is after the window closes 08:20 Suggestion: widening the windows of orders [0] by 30 min (15-min steps) makes it feasible.

Replay simulation

NN on vs off, with real trip times.

Each plan is replayed with real trip durations drawn from the held-out week, and late deliveries are counted. Experiment 3, 10 seeds per scenario:

With tight windows, hour-aware travel times (NN or historical) are late about 5% of the time versus 8% for distance only. With loose windows all three models are close, so the extra modelling only pays when the schedule is tight.

Late deliveries per model and scenario in the replay — Experiment 3: lateness in the replay.

Limits

Taxis are not vans: the 1.2 factor is a documented assumption, not a measurement.
Plans use mean times with no safety buffer, so 1–8% of deliveries are still late in the replay.
One month of data; seasonality and weather are not modelled.

Reproduce it

Run it yourself.

Python 3.13, plain numpy (no PyTorch or scikit-learn). All randomness is seeded.

python -m venv .venv
.venv\Scripts\activate            # Linux/macOS: source .venv/bin/activate
pip install -r requirements.txt

python make_data.py               # download 1 month (38 MB) and preprocess
python train_nn.py                # ~15 s: train MLP, baselines, time matrices
python -m pytest -q               # 38 tests: normal, edge and impossible cases
python run_demo.py                # demo day + outputs/demo_report.html
python run_demo.py --impossible   # the "NO SOLUTION" case
python run_experiments.py         # 3 experiments x 10 seeds

Routing vans with learned travel times.

Three techniques, one loop.

Neural network

Constraint solver

A* search

Real trips, generated orders.

Ties the lookup table, wins where data is thin.

A* with a heuristic that never lies.

Expansion 1

Pruning, switched on and off.

Late once, learned, fixed.

When there is no solution

NN on vs off, with real trip times.

Limits

Run it yourself.

Who built it.