requirements.txt
colorama==0.4.6 contourpy==1.4.0 cycler==0.12.1 fonttools==4.68.0 iniconfig==2.3.1 kiwisolver==1.5.1 matplotlib==3.11.2 numpy==2.5.4 packaging==26.3 pandas==3.1.1 pillow==13.0.0 pluggy==1.7.0 pyarrow==26.0.1 Pygments==2.21.0 pyparsing==3.3.3 pyshp==3.1.6 pytest==9.2.0 python-dateutil==4.0.0 tzdata==2026.6
README
Intelligent Systems course project. A dispatcher has ~20 deliveries with time windows and 3 vans. The system learns how long trips take in New York (NYC TLC taxi data), assigns orders to vans with a CSP, and orders each van's stops with A* search. When a route turns out late, the first late pair becomes a new "different van" rule and the CSP re-runs.
NN time matrix (24 h x 20 x 20) -> CSP: order -> van (BT / FC / AC-3) -> A* stop order per van
^ |
+---------- late pair becomes a new "different van" rule (<= 5 loops) +Project website: https://p4-delivery-routing.vercel.app (source in site/). Presentation: https://p4-delivery-routing.vercel.app/slides.html (arrow keys, F fullscreen, N speaker notes).
Layout
| Path | What |
|---|---|
delivery/data.py |
download + preprocess NYC TLC trips (real data) |
delivery/instances.py |
seeded order / van generator (generated data) |
delivery/nn.py |
hand-written numpy MLP (zone embeddings, Adam, early stopping) |
delivery/baselines.py |
historical (pair, hour) average and distance-linear baselines |
delivery/travel_time.py |
hourly zone-to-zone time matrices, FIFO interpolation, lower bounds |
delivery/search.py |
UCS / Greedy / A* (+ brute force) with node counters |
delivery/csp.py |
assignment CSP: BT, FC, AC-3 as switches, counters |
delivery/integration.py |
the feedback loop, no-solution report, window widening |
delivery/eval.py |
metrics and the replay simulation on held-out real trips |
tests/ |
pytest suite (normal, edge, impossible cases) + small committed data fixture |
make_data.py, train_nn.py, run_demo.py, run_experiments.py |
entry points |
models/ |
trained MLP (mlp.npz) and predicted time matrices (time_matrices.npz) |
instances/ |
generated instance set (15/20/30 orders x 10 seeds) |
docs/data_dictionary.md |
every column, real or generated |
site/ |
showcase website deployed on Vercel |
report/ |
report draft, presentation outline, demo script, contribution template, results, figures |
Setup (Windows, Python 3.13)
cd IS-Project-P4-Delivery-Routing
python -m venv .venv
.venv\Scripts\activate
pip install -r requirements.txtLinux/macOS: source .venv/bin/activate. Disk needed: about 320 MB for the venv and 40 MB for the raw data. PyTorch and scikit-learn are deliberately not used (disk space); the NN and the linear baseline are plain numpy.
Run (exact commands, in order)
python make_data.py # download 1 month (38 MB) + preprocess -> data/processed, instances/
python train_nn.py # ~15 s: train MLP, baselines, test metrics, time matrices, NN figures
python -m pytest -q # 38 tests, ~2 s
python run_demo.py # demo day: console walk-through + outputs/demo_*.png + outputs/demo_report.html
python run_demo.py --impossible # same day with an unreachable order -> "NO SOLUTION" report + widening
python run_experiments.py # 3 experiments x 10 seeds (~15 s) -> report/results, report/figuresrun_experiments.py --seeds 5 --only 2 runs one experiment with fewer seeds. All randomness is seeded (delivery/config.py: SEED = 42, instance seeds in the scripts). The tests run without the full dataset: they use tests/fixtures/ (3,000 real trips).
Results in one paragraph
On the held-out last week (93,592 trips) the MLP reaches MAE 3.23 min, essentially tied with the historical zone-pair/hour average (3.24) and clearly better than the distance-only linear model (4.14) and the global mean (5.45). Its real advantage is in sparse cells: on test trips whose (pair, hour) cell had fewer than 3 training trips, MAE is 3.25 vs 4.69 for the historical average. A* with the admissible sum/wait heuristic returns the optimum in 30/30 brute-force checks and expands 4x fewer nodes than UCS at 10 stops. Forward checking and AC-3 cut median CSP assignments on hard 30-order instances from 166 to 105, and most-constrained-first ordering to 37. In the replay, travel-time models with hour information (NN, historical) cause fewer late deliveries than the distance model when windows are tight (5.2% / 5.1% vs 8.1%). Full details: report/report.md.