"""The three experiments (>= 5 seeds each, mean +- std, tables + plots). python run_experiments.py # all three, 10 seeds python run_experiments.py --seeds 5 --only 1 Exp 1 A* vs UCS vs Greedy for 6..10 stops: nodes expanded/generated, cost, time Exp 2 BT vs BT+FC vs BT+FC+AC-3 for 15/20/30 orders: assignments, backtracks, time Exp 3 NN vs historical-average vs distance-based travel times: lateness in the replay """ import argparse import json import math import shutil import time import numpy as np import pandas as pd from delivery import config as C from delivery import plots as P from delivery.csp import AssignmentCSP from delivery.eval import ReplaySampler, replay from delivery.instances import generate_instance, generate_route_instance from delivery.integration import plan from delivery.pipeline import load_all, time_model, zone_weights from delivery.search import RouteProblem, brute_force, solve_route RES = C.ROOT / "report" / "results" FIG = C.ROOT / "report" / "figures" def ms(x): x = np.asarray(x, float) return f"{x.mean():.4g} ± {x.std():.3g}" def table(df, by, cols): rows = [] for key, g in df.groupby(by, sort=False): key = key if isinstance(key, tuple) else (key,) rows.append(list(key) + [ms(g[c]) for c in cols]) out = pd.DataFrame(rows, columns=list(by) + cols) return out def md(df): cols = list(df.columns) lines = ["| " + " | ".join(cols) + " |", "|" + "---|" * len(cols)] lines += ["| " + " | ".join(str(v) for v in r) + " |" for r in df.values] return "\n".join(lines) # ------------------------------------------------------------------------------ exp 1 def exp1(mats, seeds): rows, bf_checks = [], [] algos = [("UCS", "ucs", "zero"), ("Greedy", "greedy", "admissible"), ("A* (max-incoming h)", "astar", "max_in"), ("A* (sum/wait h)", "astar", "admissible")] for n in range(6, 11): for s in seeds: tm = time_model(mats, "nn", s % 5) inst = generate_route_instance(n, 1000 * n + s, tm, n_zones=tm.Z) prob = RouteProblem(inst.orders, inst.depot, inst.vans[0].shift_start, tm) res = {} for label, algo, h in algos: r = solve_route(prob, algo, heuristic=h) res[label] = r rows.append({"stops": n, "seed": s, "algorithm": label, "expanded": r.stats["expanded"], "generated": r.stats["generated"], "cost_min": r.cost, "time_ms": 1000 * r.stats["time_s"]}) opt = res["UCS"].cost for row in rows[-len(algos):]: row["gap_pct"] = 100 * (row["cost_min"] - opt) / opt if n <= 8: t0 = time.perf_counter() bf = brute_force(prob) bf_checks.append({"stops": n, "seed": s, "brute_force": bf.cost, "astar": res["A* (sum/wait h)"].cost, "match": abs(bf.cost - res["A* (sum/wait h)"].cost) < 1e-6, "bf_time_ms": 1000 * (time.perf_counter() - t0), "permutations": bf.stats["permutations"]}) df = pd.DataFrame(rows) df.to_csv(RES / "exp1_search.csv", index=False) bf = pd.DataFrame(bf_checks) bf.to_csv(RES / "exp1_bruteforce_check.csv", index=False) t = table(df, ["stops", "algorithm"], ["expanded", "generated", "cost_min", "gap_pct", "time_ms"]) fig, axes = P.plt.subplots(1, 3, figsize=(14, 4)) for k, (label, _, _) in enumerate(algos): g = df[df.algorithm == label].groupby("stops") for ax, col in zip(axes, ["expanded", "time_ms", "gap_pct"]): m, sd = g[col].mean(), g[col].std(ddof=0) ax.errorbar(m.index + (k - 1.5) * 0.06, m.values, yerr=sd.values, color=P.SERIES[k], marker="o", ms=5, capsize=3, label=label) axes[0].set_yscale("log"); axes[0].set_title("Nodes expanded (log)") axes[1].set_yscale("log"); axes[1].set_title("Run time (ms, log)") axes[2].set_title("Cost gap to optimum (%)") for ax in axes: ax.set_xlabel("stops per van"); ax.set_xticks(range(6, 11)) axes[0].legend(loc="upper left") P.save(fig, C.OUTPUTS / "exp1_search.png") return t, bf # ------------------------------------------------------------------------------ exp 2 def exp2(mats, zones, seeds): rows = [] # "rush" instances: all windows 09:00-12:00, 15-45 min wide, capacity with zero slack. # Variables in input order for the three-way comparison (a fixed, uninformed order shows # the pruning itself); a 4th row adds the most-constrained-first order on top. solvers = [("BT", False, False, "input"), ("BT+FC", True, False, "input"), ("BT+FC+AC3", True, True, "input"), ("BT+FC+AC3 +degree order", True, True, "degree")] w = zone_weights(zones) for n in (15, 20, 30): for s in seeds: inst = generate_instance(n, s, n_zones=len(zones), zone_weights=w, cap_slack=1.0, max_stops=min(10, math.ceil(n / 3) + 1), day=(9 * 60, 12 * 60), widths=(15, 30, 45)) tm = time_model(mats, "nn", inst.weekday) csp = AssignmentCSP(inst, tm) for label, fc, ac3, vo in solvers: r = csp.solve(fc=fc, ac3=ac3, max_assignments=200_000, time_limit=30, var_order=vo) rows.append({"orders": n, "seed": s, "solver": label, "status": r.status, "assignments": r.stats["assignments"], "backtracks": r.stats["backtracks"], "checks": r.stats["checks"], "fc_prunes": r.stats["fc_prunes"], "ac3_prunes": r.stats["ac3_prunes"], "time_ms": 1000 * r.stats["time_s"], "nn_edges": len(csp.edges)}) df = pd.DataFrame(rows) df.to_csv(RES / "exp2_csp.csv", index=False) t = table(df, ["orders", "solver"], ["assignments", "backtracks", "checks", "time_ms", "nn_edges"]) t.insert(3, "assignments median", df.groupby(["orders", "solver"], sort=False).assignments.median().values) st = df.groupby(["orders", "solver"], sort=False).status t["solved/unsat/limit"] = st.apply(lambda s: f"{(s == 'solved').sum()}/{(s == 'unsat').sum()}/{(s == 'limit').sum()}").values fig, axes = P.plt.subplots(1, 3, figsize=(14, 4)) x = np.arange(3) for k, (label, _, _, _) in enumerate(solvers): g = df[df.solver == label].groupby("orders", sort=True) for ax, col in zip(axes, ["assignments", "backtracks", "time_ms"]): m = g[col].median() q1, q3 = g[col].quantile(0.25), g[col].quantile(0.75) ax.bar(x + (k - 1.5) * 0.2, m.values + (1 if col != "time_ms" else 0), 0.19, yerr=[m.values - q1.values, q3.values - m.values], color=P.SERIES[k], label=label, capsize=3, edgecolor=P.SURFACE, linewidth=2, error_kw={"ecolor": P.MUTED, "elinewidth": 1}) titles = ["Assignments (median, IQR, log)", "Backtracks (+1, median, log)", "Time (ms, median, log)"] for ax, ti in zip(axes, titles): ax.set_yscale("log"); ax.set_title(ti); ax.set_xticks(x); ax.set_xticklabels(["15", "20", "30"]) ax.set_xlabel("orders") axes[0].legend(loc="upper left") P.save(fig, C.OUTPUTS / "exp2_csp.png") return t # ------------------------------------------------------------------------------ exp 3 def exp3(mats, zones, trips, seeds, reps=30): sampler = ReplaySampler(trips[trips.split == "test"]) w = zone_weights(zones) rows = [] scenarios = {"standard windows 30-120 min": (30, 45, 60, 90, 120), "tight windows 15-30 min": (15, 30)} for scen, widths in scenarios.items(): for s in seeds: inst = generate_instance(20, 100 + s, n_zones=len(zones), zone_weights=w, widths=widths) for kind in ("nn", "hist", "dist"): tm = time_model(mats, kind, inst.weekday) res = plan(inst, tm, suggest=False) rp = replay(inst, res, sampler, tm, n_reps=reps, seed=s) planned_time = sum(r.finish - inst.vans[v].shift_start for v, r in res.routes.items() if r.sequence) rows.append({"scenario": scen, "seed": s, "model": tm.name, "plan_status": res.status, "loops": len(res.loops), "learned_rules": len(res.learned_edges), "planned_late": res.n_late, "replay_late": rp["late_mean"], "replay_late_pct": 100 * rp["late_frac"], "replay_late_minutes": rp["late_minutes_mean"], "unserved": rp["unserved"], "planned_route_min": planned_time}) df = pd.DataFrame(rows) df.to_csv(RES / "exp3_lateness.csv", index=False) t = table(df, ["scenario", "model"], ["replay_late", "replay_late_pct", "replay_late_minutes", "planned_late", "planned_route_min", "learned_rules"]) t["plans ok"] = df.groupby(["scenario", "model"], sort=False).plan_status.apply( lambda s: f"{(s == 'ok').sum()}/{len(s)}").values fig, axes = P.plt.subplots(1, 2, figsize=(12, 4.2), sharey=False) models = list(df.model.unique()) for a, (ax, scen) in enumerate(zip(axes, scenarios)): d = df[df.scenario == scen] for k, m in enumerate(models): g = d[d.model == m] ax.bar(k, g.replay_late_pct.mean(), 0.6, color=P.SERIES[k], edgecolor=P.SURFACE, linewidth=2) ax.scatter(np.full(len(g), k) + np.linspace(-0.18, 0.18, len(g)), g.replay_late_pct, s=12, color=P.INK, zorder=4) ax.annotate(f"{g.replay_late_pct.mean():.1f}%", (k, g.replay_late_pct.mean()), xytext=(14, 4), textcoords="offset points", color=P.INK2) ax.set_xticks(range(len(models))); ax.set_xticklabels(models) ax.set_title(f"Late in replay: {scen}") ax.set_ylabel("% of orders late (bar = mean, dots = seeds)") P.save(fig, C.OUTPUTS / "exp3_lateness.png") return t, sampler.backoffs def main(): ap = argparse.ArgumentParser() ap.add_argument("--seeds", type=int, default=10) ap.add_argument("--only", type=int, default=0) args = ap.parse_args() seeds = list(range(args.seeds)) RES.mkdir(parents=True, exist_ok=True); FIG.mkdir(parents=True, exist_ok=True); C.OUTPUTS.mkdir(exist_ok=True) trips, zones, dist, mats = load_all() summary = {} if args.only in (0, 1): print("Experiment 1: search"); t0 = time.time() t, bf = exp1(mats, seeds) print(t.to_string(index=False)); print(f"A* == brute force: {int(bf.match.sum())}/{len(bf)} ({time.time()-t0:.0f}s)") summary["exp1"] = md(t) + f"\n\nA* vs brute force (6-8 stops): {int(bf.match.sum())}/{len(bf)} identical optimal costs.\n" if args.only in (0, 2): print("Experiment 2: CSP"); t0 = time.time() t = exp2(mats, zones, seeds) print(t.to_string(index=False)); print(f"({time.time()-t0:.0f}s)") summary["exp2"] = md(t) if args.only in (0, 3): print("Experiment 3: lateness replay"); t0 = time.time() t, back = exp3(mats, zones, trips, seeds) print(t.to_string(index=False)); print("replay back-offs:", dict(back), f"({time.time()-t0:.0f}s)") summary["exp3"] = md(t) + f"\n\nReplay pool back-offs: {dict(back)}\n" for name, txt in summary.items(): (RES / f"{name}_table.md").write_text(txt, encoding="utf-8") for f in C.OUTPUTS.glob("exp*.png"): shutil.copy(f, FIG / f.name) print("tables -> report/results/, figures -> outputs/ and report/figures/") if __name__ == "__main__": main()