Intelligent Systems · Project P4 · November 2026

Learned delivery routing

A neural network, a constraint solver and A* search, working as one system on real NYC taxi data.

Moaz Hassan El-GarawanyID 320240032 · AID S1
Ahmed Hossam El-dinID 320240051 · AID S1
1ProblemMoaz

Three questions every dispatcher asks.

HOW LONG?

Neural network

Predicts trip minutes between zones from pickup, drop-off, hour, weekday and distance → a 24 × 20 × 20 time matrix.

→
WHICH VAN?

CSP

Van per order. Windows reachable, capacity, ≤ 10 stops, and "different van" pairs from the NN times.

→
WHAT ORDER?

A* search

(stop, visited, clock). Cost = travel + waiting. Admissible time-dependent heuristic.

↺ Feedback loop: a late route turns its first late pair into a new "different van" rule, and the CSP runs again (up to 5 loops).
2DataMoaz

Real trips, generated orders.

  • NYC TLC yellow taxi trips, January 2022: 2.46 M trips.
  • Weekdays, 1 to 120 minutes, the 20 busiest zones (19 Manhattan + JFK): about 300 k trips.
  • Split by day: 3 weeks train, last week test (93,592 trips).
  • Orders, windows, demands and capacities are generated with a seed.
  • Taxi ≠ van: a documented van factor of 1.2.
2.46 Mraw trips
≈ 300 kafter filtering
20zones
93,592held-out test trips
3Neural networkMoaz

A hand-written MLP that learns the city's clock.

  • Inputs: pickup zone, drop-off zone, hour, weekday, pair distance.
  • Plain numpy: Adam, Huber loss, early stopping (best epoch 9 of 14).
  • Output used by the planner: the hourly zone-to-zone time matrix. Note JFK's row and the afternoon peak.
Predicted zone-to-zone travel time matrices at 08:00 and 18:00, and mean time by hour
4Against the baselinesMoaz

A tie overall, a clear win where data is thin.

ModelMAE (min)
NN (MLP)3.23
Historical avg (pair, hour)3.24
Distance-linear4.14
Global mean5.45
3.25NN MAE on rare (pair, hour) cells
4.69historical average on the same cells
−1.7min bias: the test week was slower for every model
5Van assignmentMoaz

Which van? A constraint problem.

  • Variable: the van for each order (3 values).
  • Unary: the window is reachable from the depot within the van's shift.
  • Binary: "different van" when neither order can follow the other, from NN times.
  • Global: capacity and at most 10 stops.
  • Backtracking, Forward Checking and AC-3 as switches, with counters.
Constraint graph of the demo day with the learned rule dashed
6Experiment 2: pruningAhmed

Pruning cuts the work 200×.

Hard rush-hour instance, 20 orders, assignments tried:

BT
4,136
BT + FC
1,701
+ AC-3
1,188
+ ordering
20

30 orders, median over 10 seeds: 166 → 106 → 105 → 37.

CSP assignments and backtracks for 15, 20 and 30 orders
7Route searchAhmed

A* with an admissible time-dependent heuristic.

  • State: (stop, visited set, clock). Cost: travel + waiting.
  • The naive "cheapest trip at the current hour" is not admissible when traffic changes (counter-example: 40 > 35).
  • Fix: minimum over all later departures, plus a waiting bound.
  • Checked against brute force: 30 / 30 optimal.
A* trace, van 0 (f = g + h, minutes) #1 at depot visited [] g 0 h 461 f 461 #2 at 11 visited [11] g 140 h 321 f 461 #3 at 14 visited [14] g 217 h 244 f 461 #5 at 0 visited [0] g 277 h 184 f 461 #9 at 9 visited [11,14,9] g 370 h 91 f 461 f stays at 461: the bound is tight.
8Experiment 1: searchAhmed

4.1× fewer nodes, same optimum.

369A* nodes expanded, 10 stops
1,519UCS nodes expanded
0%A* gap to optimum
4.6%Greedy gap, and not faster
Nodes expanded, run time and cost gap for UCS, Greedy and A* from 6 to 10 stops
9Integration and experiment 3Ahmed

A late route becomes a rule.

=== INTEGRATION LOOP (NN -> CSP -> A*) loop 1: CSP solved (2 NN rules) van 0 late by 2.1 min -> new rule: orders 16 and 5 on different vans loop 2: CSP solved (2 NN + 1 learned) all 20 orders on time after 2 loops

Replay on real held-out trips, tight windows: share of deliveries late.

NN (MLP)
5.2%
Historical
5.1%
Distance
8.1%
10Limits and conclusionAhmed

Limits and conclusion.

  • Taxi ≠ van: the 1.2 factor is an assumption.
  • Mean times, no buffer: 1 to 8% still late in the replay.
  • One month of data; no weather or seasons.
  • Takeaway: hour-aware travel times + CSP + A* give on-time plans, provably optimal per van.
Timeline of each van showing time windows, arrivals, waiting and service
Live demo · 5 minutes

Thank you. Live demo.

python run_demo.py python run_demo.py --impossible python -m pytest -q # 38 passed

Full project page: p4.iqraxis.com