"""End-to-end demo: NN travel times -> CSP van assignment -> A* stop order, with the feedback loop. python run_demo.py # default dispatcher day (seed 4), figures in outputs/ python run_demo.py --impossible # same day with one unreachable order -> "no solution" report python run_demo.py --seed 36 # another generated day Prints the input, the loop log, the routes, a search trace, CSP pruning counters and NN-on vs NN-off replay lateness; saves demo_*.png and demo_report.html to outputs/. """ import argparse import html import io import math from contextlib import redirect_stdout import numpy as np from delivery import config as C from delivery import plots as P from delivery.csp import AssignmentCSP, fmt_t from delivery.data import read_zone_shapes from delivery.eval import ReplaySampler, replay from delivery.instances import generate_instance from delivery.integration import describe_plan, plan, van_problem from delivery.pipeline import load_all, time_model, zone_weights from delivery.search import solve_route DEPOT_ZONE = 7 # Midtown Center plt = P.plt # ------------------------------------------------------------------------------ figures def stop_positions(inst, zones): """Centroid per stop, with stops in the same zone fanned out on a small circle.""" xy = zones.sort_values("idx")[["cx_km", "cy_km"]].to_numpy() pos, seen = {}, {} for o in inst.orders: k = seen.get(o.zone, 0); seen[o.zone] = k + 1 ang = 2.4 * k r = 0.0 if k == 0 else 0.28 pos[o.id] = xy[o.zone] + r * np.array([np.cos(ang), np.sin(ang)]) return xy, pos def draw_map(inst, res, zones, path): shapes_path = C.DATA_RAW / "taxi_zones.zip" shapes = read_zone_shapes(shapes_path) if shapes_path.exists() else {} xy, pos = stop_positions(inst, zones) top_ids = set(zones.LocationID) lid_of = dict(zip(zones.idx, zones.LocationID)) fig, axes = plt.subplots(1, 2, figsize=(15, 8.2), gridspec_kw={"width_ratios": [1, 1.25]}) has_jfk = any(zones.set_index("idx").loc[o.zone, "zone"] == "JFK Airport" for o in inst.orders) for ax, zoom in zip(axes, (False, True)): for lid, rings in shapes.items(): hot = lid in top_ids for ring in rings: ax.fill(ring[:, 0], ring[:, 1], facecolor="#e9e8e4" if hot else "#f4f3f0", edgecolor="#c9c8c2" if hot else "#e6e5e1", linewidth=0.5, zorder=1) for v in inst.vans: r = res.routes.get(v.id) if not r or not r.sequence: continue pts = [xy[inst.depot]] + [pos[i] for i in r.sequence] + ([xy[inst.depot]] if inst.return_to_depot else []) for k, (a, b) in enumerate(zip(pts[:-1], pts[1:])): ax.annotate("", xy=b, xytext=a, zorder=3, arrowprops=dict(arrowstyle="-|>", color=P.VAN_COLORS[v.id], lw=1.8, shrinkA=6, shrinkB=6, alpha=0.9, linestyle="--" if k == len(pts) - 2 else "-")) for n, oid in enumerate(r.sequence, 1): late = r.lateness[n - 1] > 1e-9 ax.scatter(*pos[oid], s=150, color=P.VAN_COLORS[v.id], edgecolor=P.LATE if late else P.SURFACE, linewidth=2, zorder=4) ax.annotate(str(oid), pos[oid], ha="center", va="center", fontsize=7, color="white", weight="bold", zorder=5) ax.scatter(*xy[inst.depot], marker="*", s=420, color=P.INK, edgecolor=P.SURFACE, zorder=6) ax.set_aspect("equal"); ax.grid(False); ax.set_xticks([]); ax.set_yticks([]) for s in ax.spines.values(): s.set_visible(False) manh = xy[[i for i in range(len(xy)) if zones.set_index("idx").loc[i, "zone"] != "JFK Airport"]] if zoom: ax.set_xlim(manh[:, 0].min() - 1.0, manh[:, 0].max() + 1.0) ax.set_ylim(manh[:, 1].min() - 0.8, manh[:, 1].max() + 0.8) ax.set_title("Zoom: Manhattan (numbers = order ids; red ring = late)") if has_jfk: ax.annotate("legs to/from JFK Airport continue off-map", (0.98, 0.02), xycoords="axes fraction", ha="right", fontsize=8.5, color=P.INK2) for i in range(len(xy)): if zones.set_index("idx").loc[i, "zone"] == "JFK Airport": continue ax.annotate(zones.set_index("idx").loc[i, "zone"][:22], xy[i], xytext=(0, -14), textcoords="offset points", ha="center", fontsize=6.5, color=P.MUTED, zorder=2) else: allp = xy ax.set_xlim(allp[:, 0].min() - 3, allp[:, 0].max() + 3) ax.set_ylim(allp[:, 1].min() - 3, allp[:, 1].max() + 3) ax.set_title("Routes on the 20 busiest taxi zones" + (" (incl. JFK)" if has_jfk else "")) handles = [plt.Line2D([], [], color=c, lw=2.5, label=f"van {v}") for v, c in enumerate(P.VAN_COLORS[:len(inst.vans)])] handles += [plt.Line2D([], [], marker="*", color=P.INK, lw=0, ms=14, label="depot"), plt.Line2D([], [], color=P.INK2, lw=1.5, ls="--", label="return leg")] axes[0].legend(handles=handles, loc="lower left") return P.save(fig, path) def draw_gantt(inst, res, path): rows = [] for v in inst.vans: r = res.routes.get(v.id) if r: rows += [(v.id, k, oid) for k, oid in enumerate(r.sequence)] fig, ax = plt.subplots(figsize=(13, 0.36 * len(rows) + 1.8)) y = 0 yt, yl = [], [] for v in inst.vans: r = res.routes.get(v.id) if not r: continue col = P.VAN_COLORS[v.id] ax.axhspan(y - 0.6, y + len(r.sequence) - 0.4, color=col, alpha=0.04, zorder=0) ax.annotate(f"van {v.id}\nshift {fmt_t(v.shift_start)}-{fmt_t(v.shift_end)}\nback {fmt_t(r.finish)}", (inst_min(inst) - 70, y + len(r.sequence) / 2 - 0.5), va="center", fontsize=8.5, color=P.INK2) for k, oid in enumerate(r.sequence): o = inst.order(oid) ax.barh(y, o.latest - o.earliest, left=o.earliest, height=0.62, color=col, alpha=0.22, edgecolor=col, linewidth=1, zorder=1) a, b = r.arrivals[k], r.begins[k] if b - a > 0.5: ax.plot([a, b], [y, y], color=P.INK2, lw=1, ls=":", zorder=2) late = r.lateness[k] > 1e-9 ax.barh(y, o.service, left=b, height=0.36, color=P.LATE if late else col, zorder=3) ax.scatter([a], [y], marker="|", s=120, color=P.INK, zorder=4) if late: ax.annotate(f"late {r.lateness[k]:.0f} min", (b + o.service, y), xytext=(4, 0), textcoords="offset points", va="center", color=P.LATE, fontsize=8) yt.append(y); yl.append(f"#{oid} (zone {o.zone})") y += 1 y += 0.6 ax.set_yticks(yt); ax.set_yticklabels(yl, fontsize=8); ax.invert_yaxis() lo, hi = inst_min(inst) - 75, max(r.finish for r in res.routes.values() if r) + 15 ticks = np.arange(60 * math.floor(lo / 60), hi + 1, 60) ax.set_xticks(ticks); ax.set_xticklabels([fmt_t(t) for t in ticks]); ax.set_xlim(lo, hi) ax.grid(axis="y", visible=False) ax.set_title("Timeline: time window (shaded), arrival (|), waiting (dotted), service (solid bar)") return P.save(fig, path) def inst_min(inst): return min(v.shift_start for v in inst.vans) def draw_constraint_graph(inst, res, path): csp = res.csp assign = res.assignment groups = {v.id: [i for i in sorted(assign) if assign[i] == v.id] for v in inst.vans} pos = {} nv = len(inst.vans) for v, ids in groups.items(): c = 2 * np.pi * v / nv + np.pi / 2 span = 2 * np.pi / nv * 0.78 for k, i in enumerate(ids): t = c - span / 2 + span * (k + 0.5) / max(1, len(ids)) pos[i] = np.array([np.cos(t), np.sin(t)]) fig, ax = plt.subplots(figsize=(8, 8)) for e, src in csp.edges.items(): a, b = tuple(e) pa, pb = pos[a], pos[b] if src == "learned": ax.plot(*zip(pa, pb), color=P.LATE, lw=2.6, ls="--", zorder=2) mid = (pa + pb) / 2 ax.annotate("learned", mid, color=P.LATE, fontsize=9, ha="center", bbox=dict(boxstyle="round,pad=0.2", fc=P.SURFACE, ec="none")) else: ax.plot(*zip(pa, pb), color=P.INK2, lw=1.4, zorder=1) for i, p in pos.items(): ax.scatter(*p, s=520, color=P.VAN_COLORS[assign[i]], edgecolor=P.SURFACE, linewidth=2, zorder=3) ax.annotate(str(i), p, ha="center", va="center", color="white", weight="bold", zorder=4) for v in inst.vans: c = 2 * np.pi * v.id / nv + np.pi / 2 ax.annotate(f"van {v.id}", 1.3 * np.array([np.cos(c), np.sin(c)]), ha="center", va="center", color=P.VAN_COLORS[v.id], weight="bold", fontsize=12) n_nn = sum(1 for s in csp.edges.values() if s == "nn") n_l = sum(1 for s in csp.edges.values() if s == "learned") handles = [plt.Line2D([], [], color=P.INK2, lw=1.4, label=f"different-van rule from NN times ({n_nn})"), plt.Line2D([], [], color=P.LATE, lw=2.6, ls="--", label=f"rule learned from a late route ({n_l})")] ax.legend(handles=handles, loc="lower center", bbox_to_anchor=(0.5, -0.08)) ax.set_xlim(-1.5, 1.5); ax.set_ylim(-1.5, 1.5); ax.set_aspect("equal"); ax.axis("off") ax.set_title("CSP constraint graph: orders (nodes) grouped by assigned van") return P.save(fig, path) def draw_stats(search_rows, csp_rows, loops, nn_rows, path): fig, axes = plt.subplots(2, 2, figsize=(13, 8.5)) ax = axes[0, 0] algos = ["UCS", "Greedy", "A*"] vans = sorted({r["van"] for r in search_rows}) for k, a in enumerate(algos): vals = [next(r["expanded"] for r in search_rows if r["van"] == v and r["algo"] == a) for v in vans] b = ax.bar(np.arange(len(vans)) + (k - 1) * 0.27, vals, 0.25, color=P.SERIES[k], label=a, edgecolor=P.SURFACE, linewidth=2) ax.bar_label(b, fontsize=8, color=P.INK2) ax.set_xticks(range(len(vans))); ax.set_xticklabels([f"van {v}" for v in vans]) ax.set_title("Search: nodes expanded per van (this day)"); ax.legend() ax = axes[0, 1] labels = [r["solver"] for r in csp_rows] for k, key in enumerate(["assignments", "backtracks"]): b = ax.bar(np.arange(len(labels)) + (k - 0.5) * 0.38, [r[key] for r in csp_rows], 0.36, color=P.SERIES[k], label=key, edgecolor=P.SURFACE, linewidth=2) ax.bar_label(b, fontsize=8, color=P.INK2) ax.set_xticks(range(len(labels))); ax.set_xticklabels(labels, fontsize=8.5) ax.set_title("CSP pruning on a hard rush-hour instance (20 orders)"); ax.legend() ax = axes[1, 0] ls = [l["loop"] for l in loops] late = [l.get("late_stops", 0) for l in loops] learned = [l["n_edges_learned"] for l in loops] b = ax.bar(np.array(ls) - 0.2, late, 0.38, color=P.LATE, label="late routes after A*") ax.bar_label(b, fontsize=9, color=P.INK2) b = ax.bar(np.array(ls) + 0.2, learned, 0.38, color=P.SERIES[0], label="learned rules in CSP") ax.bar_label(b, fontsize=9, color=P.INK2) ax.set_xticks(ls); ax.set_xlabel("integration loop"); ax.set_title("Feedback loop: CSP <- late pair <- A*") ax.legend() ax = axes[1, 1] names = [r["model"] for r in nn_rows] vals = [r["late_mean"] for r in nn_rows] b = ax.bar(range(len(names)), vals, 0.6, color=P.SERIES[:len(names)], edgecolor=P.SURFACE, linewidth=2) ax.bar_label(b, labels=[f"{v:.2f}" for v in vals], fontsize=9, color=P.INK2) ax.set_xticks(range(len(names))); ax.set_xticklabels(names) ax.set_title("NN on vs off: late deliveries in replay of real test-week trips") ax.set_ylabel("late deliveries per day (mean of 50 replays)") return P.save(fig, path) # ------------------------------------------------------------------------------ main def main(): ap = argparse.ArgumentParser() ap.add_argument("--seed", type=int, default=4) ap.add_argument("--impossible", action="store_true") ap.add_argument("--reps", type=int, default=50) args = ap.parse_args() C.OUTPUTS.mkdir(exist_ok=True) trips, zones, dist, mats = load_all() zname = zones.set_index("idx").zone inst = generate_instance(20, args.seed, n_zones=len(zones), zone_weights=zone_weights(zones), widths=(15, 30, 45, 60), depot=DEPOT_ZONE) if args.impossible: jfk = int(zones[zones.zone == "JFK Airport"].idx.iloc[0]) o = inst.orders[0] o.zone, o.earliest, o.latest = jfk, 8 * 60, 8 * 60 + 20 inst.name += "_impossible" tm = time_model(mats, "nn", inst.weekday) buf = io.StringIO() def out(*a): print(*a) print(*a, file=buf) out(f"=== INPUT: {inst.name}, weekday {C.WEEKDAY_NAMES[inst.weekday]}, depot zone {inst.depot} ({zname[inst.depot]})") out(f"travel times: NN-predicted taxi minutes x {C.VAN_FACTOR} (van factor)") for v in inst.vans: out(f" van {v.id}: shift {fmt_t(v.shift_start)}-{fmt_t(v.shift_end)}, capacity {v.capacity}, max {v.max_stops} stops") out(" order zone window demand service") for o in inst.orders: out(f" {o.id:5d} {o.zone:2d} {zname[o.zone][:28]:<28} {fmt_t(o.earliest)}-{fmt_t(o.latest)} {o.demand:5d} {o.service:5.0f}") traces = {} res = plan(inst, tm, traces=traces) out("\n=== INTEGRATION LOOP (NN -> CSP -> A*)") for l in res.loops: s = l["csp_stats"] out(f" loop {l['loop']}: CSP {l['csp_status']} (rules: {l['n_edges_nn']} from NN, {l['n_edges_learned']} learned; " f"{s['assignments']} assignments, {s['backtracks']} backtracks)") for nr in l["new_rules"]: out(f" van {nr['van']} late by {nr['late_by']:.1f} min -> new rule: orders {nr['pair'][0]} and {nr['pair'][1]} on different vans") if res.status == "no_solution": out("\n" + res.message) with open(C.OUTPUTS / "demo_impossible.txt", "w", encoding="utf-8") as f: f.write(buf.getvalue()) return out("\n=== SOLUTION") out(describe_plan(inst, res)) # loop-level late counts for the figure (re-plan each loop's assignment is costly; use recorded rules) for l in res.loops: l["late_stops"] = len(l["new_rules"]) out("\n=== A* SEARCH TRACE (van 0, first 12 expansions; f = g + h, minutes)") for t in traces.get(0, [])[:12]: out(f" #{t['step']:3d} at {str(t['at']):>5} visited {str(t['visited']):<16} clock {fmt_t(t['clock'])} " f"g {t['g']:6.1f} h {t['h']:6.1f} f {t['f']:6.1f}") search_rows = [] out("\n=== SEARCH COUNTERS per van (same stops, three algorithms)") for v in inst.vans: r = res.routes[v.id] if not r.sequence: continue prob = van_problem(inst, tm, v, r.sequence) for label, algo in (("UCS", "ucs"), ("Greedy", "greedy"), ("A*", "astar")): rr = solve_route(prob, algo) search_rows.append({"van": v.id, "algo": label, "expanded": rr.stats["expanded"], "generated": rr.stats["generated"], "cost": rr.cost}) out(f" van {v.id} {label:<6} expanded {rr.stats['expanded']:5d} generated {rr.stats['generated']:5d} " f"route time {rr.cost:6.1f} min {1000*rr.stats['time_s']:.1f} ms") out("\n=== CSP PRUNING: same rules, solvers switched on/off") out(" (a) this day's constraint set") for fc, ac3, label in ((False, False, "BT"), (True, False, "BT+FC"), (True, True, "BT+FC+AC3")): s = res.csp.solve(fc=fc, ac3=ac3, var_order="input").stats out(f" {label:<10} assignments {s['assignments']:5d} backtracks {s['backtracks']:5d} checks {s['checks']:5d}") hard = generate_instance(20, 4, n_zones=len(zones), zone_weights=zone_weights(zones), cap_slack=1.0, max_stops=8, day=(540, 720), widths=(15, 30, 45)) hcsp = AssignmentCSP(hard, time_model(mats, "nn", hard.weekday)) out(f" (b) hard rush-hour instance: 20 orders, windows 09:00-12:00, zero capacity slack, {len(hcsp.edges)} NN rules") csp_rows = [] for fc, ac3, label, vo in ((False, False, "BT", "input"), (True, False, "BT+FC", "input"), (True, True, "BT+FC+AC3", "input"), (True, True, "+degree order", "degree")): s = hcsp.solve(fc=fc, ac3=ac3, var_order=vo).stats csp_rows.append({**s, "solver": label}) out(f" {label:<14} assignments {s['assignments']:5d} backtracks {s['backtracks']:5d} " f"fc_prunes {s['fc_prunes']:5d} ac3_prunes {s['ac3_prunes']:4d} {1000*s['time_s']:.1f} ms") out(f"\n=== NN ON vs OFF: replay with real held-out trip durations ({args.reps} replays, test week)") sampler = ReplaySampler(trips[trips.split == "test"]) nn_rows = [] for kind in ("nn", "hist", "dist"): tmk = time_model(mats, kind, inst.weekday) rk = res if kind == "nn" else plan(inst, tmk, suggest=False) rp = replay(inst, rk, sampler, tmk, n_reps=args.reps, seed=0) label = {"nn": "NN on", "hist": "hist-avg", "dist": "NN off (distance)"}[kind] nn_rows.append({"model": label, **rp}) out(f" {label:<18} plan {rk.status:<4} late per day {rp['late_mean']:.2f} ± {rp['late_std']:.2f} " f"({100*rp['late_frac']:.1f}%), lateness {rp['late_minutes_mean']:.1f} min") figs = [draw_map(inst, res, zones, C.OUTPUTS / "demo_map.png"), draw_gantt(inst, res, C.OUTPUTS / "demo_gantt.png"), draw_constraint_graph(inst, res, C.OUTPUTS / "demo_constraint_graph.png"), draw_stats(search_rows, csp_rows, res.loops, nn_rows, C.OUTPUTS / "demo_stats.png")] out("\nfigures: " + ", ".join(str(f.relative_to(C.ROOT)) for f in figs)) write_html(buf.getvalue(), figs) out("report: outputs/demo_report.html") def write_html(text, figs): imgs = "\n".join(f'
{f.stem}
{f.stem}
' for f in figs) extra = [p for p in ("time_matrix_nn.png", "nn_mae_by_hour.png", "exp1_search.png", "exp2_csp.png", "exp3_lateness.png") if (C.OUTPUTS / p).exists()] imgs += "\n".join(f'
{p}
{p}
' for p in extra) page = f"""Delivery Routing Demo

P4 Delivery Routing with Learned Travel Times: demo run

NN travel-time matrix → CSP assigns orders to vans → A* orders each van's stops → late pair becomes a new CSP rule.

{imgs}

Console output

{html.escape(text)}
""" (C.OUTPUTS / "demo_report.html").write_text(page, encoding="utf-8") if __name__ == "__main__": main()