- Known answer
- 3 stops, optimum 49 min, order C, B, A
- Brute-force check
- A* optimal in 30 of 30 instances, 6 to 8 stops
- At 10 stops
- A* expands 369 nodes, UCS 1,519
Small example with a known answer
tests/test_search.py
def known_problem():
# zones on a line, tt = 5*|i-j| + 1; depot zone 0; service 5 min; start 08:00
stops = [Order(0, 1, 480, 600, 1, 5), Order(1, 2, 480, 600, 1, 5), Order(2, 3, 480, 500, 1, 5)]
return RouteProblem(stops, depot=0, start=480, tm=line_tm())
# ----------------------------------------------------------------------------- normal cases
@pytest.mark.parametrize("algo", ["astar", "ucs"])
def test_known_answer_small_example(algo):
# hand-computed: only C(3) first keeps C's window; best is C,B,A = 16+5+6+5+6+5+6 = 49 min
r = solve_route(known_problem(), algo=algo)
assert r.sequence == [2, 1, 0]
assert r.cost == pytest.approx(49.0)
assert r.feasible and r.stats["expanded"] > 0 and r.stats["generated"] > 0Trace and counters, demo day
python run_demo.py
=== 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