1import itertools2 3import numpy as np4import pytest5 6from delivery.instances import Order, generate_route_instance7from delivery.search import RouteProblem, brute_force, make_heuristic, plan_van, simulate, solve_route8from delivery.travel_time import TimeModel9from conftest import line_tm10 11 12def known_problem():13 # zones on a line, tt = 5*|i-j| + 1; depot zone 0; service 5 min; start 08:0014 stops = [Order(0, 1, 480, 600, 1, 5), Order(1, 2, 480, 600, 1, 5), Order(2, 3, 480, 500, 1, 5)]15 return RouteProblem(stops, depot=0, start=480, tm=line_tm())16 17 18# ----------------------------------------------------------------------------- normal cases19@pytest.mark.parametrize("algo", ["astar", "ucs"])20def test_known_answer_small_example(algo):21 # hand-computed: only C(3) first keeps C's window; best is C,B,A = 16+5+6+5+6+5+6 = 49 min22 r = solve_route(known_problem(), algo=algo)23 assert r.sequence == [2, 1, 0]24 assert r.cost == pytest.approx(49.0)25 assert r.feasible and r.stats["expanded"] > 0 and r.stats["generated"] > 026 27 28@pytest.mark.parametrize("seed", range(5))29def test_astar_and_ucs_match_brute_force_on_6_stops(tm, seed):30 inst = generate_route_instance(6, seed, tm, n_zones=tm.Z)31 prob = RouteProblem(inst.orders, inst.depot, inst.vans[0].shift_start, tm)32 bf = brute_force(prob)33 a = solve_route(prob, "astar")34 u = solve_route(prob, "ucs")35 assert bf is not None36 assert a.cost == pytest.approx(bf.cost, abs=1e-6)37 assert u.cost == pytest.approx(bf.cost, abs=1e-6)38 39 40def _cost_to_go(prob, cur_zone, clock, remaining):41 best = np.inf42 for perm in itertools.permutations(remaining):43 t, z, ok = clock, cur_zone, True44 for k in perm:45 o = prob.stops[k]46 b = max(t + prob.tm.tt(z, o.zone, t), o.earliest)47 if b > o.latest + 1e-9:48 ok = False49 break50 t, z = b + o.service, o.zone51 if ok:52 t += prob.tm.tt(z, prob.depot, t)53 best = min(best, t - clock)54 return best55 56 57def test_admissible_heuristic_never_overestimates(tm):58 rng = np.random.default_rng(1)59 for seed in range(6):60 inst = generate_route_instance(6, seed, tm, n_zones=tm.Z)61 prob = RouteProblem(inst.orders, inst.depot, inst.vans[0].shift_start, tm)62 h = make_heuristic(prob, "admissible")63 for _ in range(15):64 k = int(rng.integers(0, 4))65 done = list(rng.permutation(6)[:k])66 sim = simulate(prob, done)67 cur = done[-1] if done else -168 clock = sim.departures[-1] if done else prob.start69 mask = sum(1 << d for d in done)70 cz = prob.stops[cur].zone if done else prob.depot71 true = _cost_to_go(prob, cz, clock, [j for j in range(6) if j not in done])72 assert h(cur, mask, clock) <= true + 1e-673 74 75def test_naive_current_hour_heuristic_can_overestimate():76 # traffic eases: 40 min for hours 0-9, 10 min from hour 10. Leaving at 09:40 the77 # interpolated trip takes 40*(5/6) + 10*(1/6) = 35 min, but the naive heuristic reads the78 # hour-9 value (40) -> overestimates -> not admissible. Our lower bound uses the minimum79 # over all later departure times and stays below the true cost.80 M = np.full((24, 2, 2), 10.0)81 M[:10] = 40.082 clock = 9 * 60 + 4083 prob = RouteProblem([Order(0, 1, 480, 1000, 1, 0)], depot=0, start=clock,84 tm=TimeModel(M, factor=1.0), return_to_depot=False)85 true = solve_route(prob, "ucs").cost86 assert true == pytest.approx(35.0)87 naive = make_heuristic(prob, "naive")(-1, 0, clock)88 assert naive == pytest.approx(40.0) and naive > true89 assert make_heuristic(prob, "admissible")(-1, 0, clock) <= true90 91 92def test_astar_expands_fewer_nodes_than_ucs(tm):93 tot_a = tot_u = 094 for seed in range(4):95 inst = generate_route_instance(8, seed, tm, n_zones=tm.Z)96 prob = RouteProblem(inst.orders, inst.depot, inst.vans[0].shift_start, tm)97 tot_a += solve_route(prob, "astar").stats["expanded"]98 tot_u += solve_route(prob, "ucs").stats["expanded"]99 assert tot_a < tot_u100 101 102def test_greedy_feasible_and_not_better_than_optimal(tm):103 for seed in range(4):104 inst = generate_route_instance(7, seed, tm, n_zones=tm.Z)105 prob = RouteProblem(inst.orders, inst.depot, inst.vans[0].shift_start, tm)106 g = solve_route(prob, "greedy")107 a = solve_route(prob, "astar")108 assert g.feasible109 assert g.cost >= a.cost - 1e-9110 111 112# ----------------------------------------------------------------------------- edge cases113def test_edge_empty_van():114 r = plan_van(RouteProblem([], 0, 480, line_tm()))115 assert r.sequence == [] and r.cost == 0 and r.feasible116 117 118def test_edge_single_stop_in_depot_zone():119 # intra-zone trip: tt(0,0) = 1 -> arrive 481, serve 5, return 1 -> cost 7120 r = solve_route(RouteProblem([Order(0, 0, 480, 490, 1, 5)], 0, 480, line_tm()))121 assert r.sequence == [0] and r.cost == pytest.approx(7.0)122 123 124def test_edge_zero_width_window_hit_exactly_and_boundary_arrival():125 # arrive at zone 2 at 480 + 11 = 491 exactly when the window [491, 491] is open126 r = solve_route(RouteProblem([Order(0, 2, 491, 491, 1, 0)], 0, 480, line_tm(), return_to_depot=False))127 assert r is not None and r.feasible and r.lateness == [0.0]128 129 130def test_edge_early_arrival_waits():131 r = solve_route(RouteProblem([Order(0, 1, 600, 610, 1, 5)], 0, 480, line_tm(), return_to_depot=False))132 assert r.waits[0] == pytest.approx(600 - 486)133 assert r.begins[0] == 600134 135 136# ----------------------------------------------------------------------------- impossible137def test_impossible_route_returns_none_then_least_late_route():138 # two stops at opposite ends that both close at 08:20: cannot serve both139 stops = [Order(0, 4, 480, 500, 1, 5), Order(1, 0, 480, 500, 1, 5)]140 prob = RouteProblem(stops, 2, 480, line_tm())141 assert solve_route(prob, "astar") is None142 assert brute_force(prob) is None143 soft = plan_van(prob)144 assert not soft.feasible and soft.first_late() is not None145 assert soft.stats.get("soft_fallback")