- Day
- Thursday, 20 orders, 3 vans, depot Midtown Center
- Outcome
- late by 2.1 min in loop 1, every order on time in loop 2
- Outputs
- console, 4 figures, HTML report
- Script
- run_demo.py
Console output
python run_demo.py
=== INPUT: n20_s4, weekday Thu, depot zone 7 (Midtown Center)
travel times: NN-predicted taxi minutes x 1.2 (van factor)
van 0: shift 08:00-17:00, capacity 13, max 10 stops
van 1: shift 09:00-18:00, capacity 13, max 10 stops
van 2: shift 10:00-19:00, capacity 13, max 10 stops
order zone window demand service
0 19 Yorkville West 12:30-13:30 1 7
1 16 Upper East Side South 11:45-12:30 1 10
2 18 Upper West Side South 12:45-13:45 1 10
3 19 Yorkville West 15:00-15:30 1 10
4 5 Lenox Hill West 15:30-16:30 2 5
5 15 Upper East Side North 15:45-16:30 1 7
6 11 Penn Station/Madison Sq West 12:45-13:15 3 10
7 12 Sutton Place/Turtle Bay Nort 10:45-11:15 2 10
8 6 Lincoln Square East 13:00-14:00 3 5
9 10 Murray Hill 14:00-14:30 1 10
10 5 Lenox Hill West 14:30-15:15 1 7
11 5 Lenox Hill West 10:15-10:45 3 5
12 15 Upper East Side North 11:45-12:45 1 5
13 16 Upper East Side South 12:45-13:45 1 10
14 19 Yorkville West 11:30-12:00 1 7
15 18 Upper West Side South 16:15-16:45 1 7
16 3 JFK Airport 15:00-15:30 1 10
17 6 Lincoln Square East 15:30-16:30 1 5
18 6 Lincoln Square East 13:15-14:15 2 5
19 12 Sutton Place/Turtle Bay Nort 14:30-14:45 2 7
=== 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)
=== SOLUTION
status: ok -- all 20 orders on time after 2 loop(s)
van 0 (shift 08:00-17:00, load 9/13, 7 stops, back 16:29):
order 11 zone 5 window 10:15-10:45 arrive 08:11 serve 10:15
order 14 zone 19 window 11:30-12:00 arrive 10:27 serve 11:30
order 0 zone 19 window 12:30-13:30 arrive 11:43 serve 12:30
order 13 zone 16 window 12:45-13:45 arrive 12:49 serve 12:49
order 9 zone 10 window 14:00-14:30 arrive 13:11 serve 14:00
order 16 zone 3 window 15:00-15:30 arrive 14:53 serve 15:00
order 17 zone 6 window 15:30-16:30 arrive 16:13 serve 16:13
van 1 (shift 09:00-18:00, load 10/13, 7 stops, back 16:38):
order 1 zone 16 window 11:45-12:30 arrive 09:10 serve 11:45
order 2 zone 18 window 12:45-13:45 arrive 12:07 serve 12:45
order 8 zone 6 window 13:00-14:00 arrive 13:02 serve 13:02
order 19 zone 12 window 14:30-14:45 arrive 13:20 serve 14:30
order 10 zone 5 window 14:30-15:15 arrive 14:44 serve 14:44
order 5 zone 15 window 15:45-16:30 arrive 15:00 serve 15:45
order 15 zone 18 window 16:15-16:45 arrive 16:04 serve 16:15
van 2 (shift 10:00-19:00, load 11/13, 6 stops, back 15:49):
order 7 zone 12 window 10:45-11:15 arrive 10:09 serve 10:45
order 12 zone 15 window 11:45-12:45 arrive 11:10 serve 11:45
order 6 zone 11 window 12:45-13:15 arrive 12:15 serve 12:45
order 18 zone 6 window 13:15-14:15 arrive 13:10 serve 13:15
order 3 zone 19 window 15:00-15:30 arrive 13:37 serve 15:00
order 4 zone 5 window 15:30-16:30 arrive 15:19 serve 15:30
=== A* SEARCH TRACE (van 0, first 12 expansions; f = g + h, minutes)
# 1 at depot visited [] clock 08:00 g 0.0 h 461.0 f 461.0
# 2 at 11 visited [11] clock 10:20 g 140.0 h 321.0 f 461.0
# 3 at 14 visited [14] clock 11:37 g 217.0 h 244.0 f 461.0
# 4 at 14 visited [11, 14] clock 11:37 g 217.0 h 244.0 f 461.0
# 5 at 0 visited [0] clock 12:37 g 277.0 h 184.0 f 461.0
# 6 at 0 visited [11, 0] clock 12:37 g 277.0 h 184.0 f 461.0
# 7 at 0 visited [14, 0] clock 12:37 g 277.0 h 184.0 f 461.0
# 8 at 0 visited [11, 14, 0] clock 12:37 g 277.0 h 184.0 f 461.0
# 9 at 9 visited [11, 14, 9] clock 14:10 g 370.0 h 91.0 f 461.0
# 10 at 9 visited [11, 0, 9] clock 14:10 g 370.0 h 91.0 f 461.0
# 11 at 9 visited [14, 0, 9] clock 14:10 g 370.0 h 91.0 f 461.0
# 12 at 9 visited [11, 14, 0, 9] clock 14:10 g 370.0 h 91.0 f 461.0
=== SEARCH COUNTERS per van (same stops, three algorithms)
van 0 UCS expanded 132 generated 133 route time 508.7 min 0.8 ms
van 0 Greedy expanded 122 generated 125 route time 508.7 min 3.4 ms
van 0 A* expanded 68 generated 132 route time 508.7 min 3.3 ms
van 1 UCS expanded 130 generated 131 route time 457.9 min 0.8 ms
van 1 Greedy expanded 113 generated 115 route time 457.9 min 3.1 ms
van 1 A* expanded 46 generated 110 route time 457.9 min 2.6 ms
van 2 UCS expanded 64 generated 65 route time 348.5 min 0.3 ms
van 2 Greedy expanded 64 generated 65 route time 348.5 min 1.6 ms
van 2 A* expanded 21 generated 53 route time 348.5 min 1.2 ms
=== CSP PRUNING: same rules, solvers switched on/off
(a) this day's constraint set
BT assignments 384 backtracks 364 checks 1113
BT+FC assignments 21 backtracks 1 checks 0
BT+FC+AC3 assignments 20 backtracks 0 checks 0
(b) hard rush-hour instance: 20 orders, windows 09:00-12:00, zero capacity slack, 4 NN rules
BT assignments 4136 backtracks 4116 fc_prunes 0 ac3_prunes 0 9.0 ms
BT+FC assignments 1701 backtracks 1681 fc_prunes 1708 ac3_prunes 0 3.5 ms
BT+FC+AC3 assignments 1188 backtracks 1168 fc_prunes 1257 ac3_prunes 21 2.9 ms
+degree order assignments 20 backtracks 0 fc_prunes 12 ac3_prunes 0 0.1 ms
=== NN ON vs OFF: replay with real held-out trip durations (50 replays, test week)
NN on plan ok late per day 0.68 ± 0.47 (3.4%), lateness 7.5 min
hist-avg plan ok late per day 1.38 ± 0.87 (6.9%), lateness 24.8 min
NN off (distance) plan ok late per day 0.70 ± 0.81 (3.5%), lateness 6.1 min
figures: outputs\demo_map.png, outputs\demo_gantt.png, outputs\demo_constraint_graph.png, outputs\demo_stats.png
report: outputs/demo_report.html
Figures
When no plan exists
python run_demo.py --impossible
=== INTEGRATION LOOP (NN -> CSP -> A*) loop 1: CSP unsat (rules: 21 from NN, 0 learned; 0 assignments, 0 backtracks) 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.