Headway
6

Models line · 06 of 13

Van assignment

Which van takes which order is a constraint problem. Backtracking runs always; forward checking and AC-3 switch on and off independently, and every run reports assignments, backtracks, checks and prunes.

Variables
one per order, three vans
Constraints
reachable window, capacity, at most 10 stops, different-van pairs from the model
Hard instance
4,136 assignments with backtracking alone, 20 with pruning and ordering
Files
delivery/csp.py tests/test_csp.py

Same rules, solvers switched

python run_demo.py
=== 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

Constraint graph

Demo day. Grey edges come from the model; the dashed red edge was learned from a late route.
Demo day. Grey edges come from the model; the dashed red edge was learned from a late route.