1"""How the three parts work together.2 3 NN time matrix --> CSP assigns orders to vans --> A* orders the stops of each van4 ^ |5 | a route is late: the first late pair (previous |6 +-- stop, late stop) becomes a new "different van" <-+7 rule and the CSP re-runs (at most 5 loops)8 9If the CSP has no solution (or loops run out) we report the unserviceable orders with a10reason each and try widening their windows in 15-minute steps.11"""12from __future__ import annotations13 14from dataclasses import dataclass, field15 16from .csp import AssignmentCSP, fmt_t17from .search import RouteProblem, plan_van18 19MAX_LOOPS = 520 21 22@dataclass23class PlanResult:24 status: str # 'ok' | 'late' | 'no_solution'25 routes: dict = field(default_factory=dict)26 assignment: dict = field(default_factory=dict)27 loops: list = field(default_factory=list)28 learned_edges: list = field(default_factory=list)29 csp: AssignmentCSP | None = None30 unserviceable: list = field(default_factory=list) # (order id, reason)31 widening: dict | None = None32 message: str = ""33 34 @property35 def n_late(self):36 return sum(r.n_late for r in self.routes.values())37 38 39def van_problem(inst, tm, van, order_ids) -> RouteProblem:40 return RouteProblem([inst.order(i) for i in order_ids], inst.depot, van.shift_start, tm,41 inst.return_to_depot, van.shift_end, van.id)42 43 44def plan(inst, tm, fc: bool = True, ac3: bool = True, algo: str = "astar",45 max_loops: int = MAX_LOOPS, suggest: bool = True, traces: dict | None = None) -> PlanResult:46 learned: list = []47 loops = []48 last = None49 for loop in range(1, max_loops + 1):50 csp = AssignmentCSP(inst, tm, learned)51 res = csp.solve(fc=fc, ac3=ac3)52 info = {"loop": loop, "csp_status": res.status, "csp_stats": res.stats,53 "n_edges_nn": sum(1 for s in csp.edges.values() if s == "nn"),54 "n_edges_learned": sum(1 for s in csp.edges.values() if s == "learned"),55 "new_rules": []}56 loops.append(info)57 if res.status != "solved":58 out = PlanResult("no_solution", loops=loops, learned_edges=learned, csp=csp)59 if last is not None: # keep the best late plan we had60 out.routes, out.assignment = last.routes, last.assignment61 out.unserviceable = explain_no_solution(csp, inst, tm)62 if suggest:63 out.widening = suggest_widening(inst, tm, [u for u, _ in out.unserviceable if u is not None])64 out.message = format_no_solution(out)65 return out66 routes = {}67 for v in inst.vans:68 ids = [i for i, vv in res.assignment.items() if vv == v.id]69 ids.sort(key=lambda i: inst.order(i).earliest)70 tr = [] if traces is not None else None71 routes[v.id] = plan_van(van_problem(inst, tm, v, ids), algo=algo, trace=tr)72 if traces is not None:73 traces[v.id] = tr74 last = PlanResult("late", routes, res.assignment, loops, learned, csp)75 late_vans = [r for r in routes.values() if not r.feasible]76 if not late_vans:77 last.status = "ok"78 last.message = f"all {len(inst.orders)} orders on time after {loop} loop(s)"79 return last80 for r in late_vans:81 k = r.first_late()82 if k is None: # only the return to the depot overran the shift83 k = len(r.sequence) - 184 if k == 0:85 k = 1 if len(r.sequence) > 1 else 086 if k == 0:87 continue88 pair = (r.sequence[k - 1], r.sequence[k])89 learned.append(pair)90 info["new_rules"].append({"van": r.van, "pair": pair, "late_by": r.lateness[k]})91 last.message = (f"{last.n_late} late deliveries remain after {max_loops} loops; "92 f"learned rules: {learned}")93 last.unserviceable = [(oid, f"late by {late:.1f} min on van {r.van}")94 for r in last.routes.values()95 for oid, late in zip(r.sequence, r.lateness) if late > 1e-9]96 if suggest:97 last.widening = suggest_widening(inst, tm, [u for u, _ in last.unserviceable])98 return last99 100 101# --------------------------------------------------------------------------- no-solution reports102def explain_no_solution(csp: AssignmentCSP, inst, tm) -> list:103 out = []104 for oid, reasons in csp.unary_reasons.items():105 if not csp.domains0[oid]:106 out.append((oid, "window not reachable from the depot by any van: " + "; ".join(reasons)))107 if out:108 return out109 tot_d = sum(o.demand for o in inst.orders)110 tot_c = sum(v.capacity for v in inst.vans)111 if tot_d > tot_c:112 out.append((None, f"total demand {tot_d} exceeds total van capacity {tot_c}"))113 tot_s = sum(v.max_stops for v in inst.vans)114 if len(inst.orders) > tot_s:115 out.append((None, f"{len(inst.orders)} orders but only {tot_s} stops available"))116 if out:117 return out118 clique = csp.max_clique()119 if len(clique) > len(inst.vans):120 nb = csp.neighbors()121 drop = max(clique, key=lambda i: (len(nb[i]), i))122 for oid in clique:123 out.append((oid, f"orders {clique} are pairwise incompatible (cannot meet both windows in "124 f"either order with predicted times) but there are only {len(inst.vans)} vans"125 + ("; dropping this one helps most" if oid == drop else "")))126 return out127 for o in inst.orders: # which single removal makes it solvable?128 sub = _without(inst, o.id)129 learned = [tuple(e) for e, s in csp.edges.items() if s == "learned" and o.id not in e]130 if AssignmentCSP(sub, tm, learned).solve(fc=True, ac3=True, max_assignments=50_000).status == "solved":131 out.append((o.id, "removing this order makes the assignment feasible "132 "(capacity + different-van rules conflict)"))133 if not out:134 out.append((None, "no assignment satisfies capacity + different-van rules"))135 return out136 137 138def _without(inst, oid):139 d = inst.to_dict()140 d["orders"] = [o for o in d["orders"] if o["id"] != oid]141 from .instances import Instance142 return Instance.from_dict(d)143 144 145def suggest_widening(inst, tm, only_ids=None, step: float = 15.0, max_steps: int = 8) -> dict:146 only = set(only_ids) if only_ids else None147 for k in range(1, max_steps + 1):148 w = inst.widened(step * k, only)149 r = plan(w, tm, suggest=False)150 if r.status == "ok":151 return {"found": True, "minutes": step * k, "orders": sorted(only) if only else "all"}152 return {"found": False, "minutes": step * max_steps, "orders": sorted(only) if only else "all"}153 154 155def format_no_solution(res: PlanResult) -> str:156 lines = ["NO SOLUTION: not every order can be served on time.", "Unserviceable orders / reasons:"]157 for oid, why in res.unserviceable:158 lines.append(f" - {'order ' + str(oid) if oid is not None else 'instance'}: {why}")159 w = res.widening160 if w:161 who = "all windows" if w["orders"] == "all" else f"the windows of orders {w['orders']}"162 if w["found"]:163 lines.append(f"Suggestion: widening {who} by {int(w['minutes'])} min (15-min steps) makes it feasible.")164 else:165 lines.append(f"Widening {who} by up to {int(w['minutes'])} min (15-min steps) does not help.")166 return "\n".join(lines)167 168 169def describe_plan(inst, res: PlanResult) -> str:170 lines = [f"status: {res.status} -- {res.message}"]171 for v in inst.vans:172 r = res.routes.get(v.id)173 if r is None:174 continue175 load = sum(inst.order(i).demand for i in r.sequence)176 lines.append(f"van {v.id} (shift {fmt_t(v.shift_start)}-{fmt_t(v.shift_end)}, load {load}/{v.capacity}, "177 f"{len(r.sequence)} stops, back {fmt_t(r.finish)}):")178 for oid, a, b, late in zip(r.sequence, r.arrivals, r.begins, r.lateness):179 o = inst.order(oid)180 flag = f" LATE {late:.1f} min" if late > 1e-9 else ""181 lines.append(f" order {oid:2d} zone {o.zone:2d} window {fmt_t(o.earliest)}-{fmt_t(o.latest)} "182 f"arrive {fmt_t(a)} serve {fmt_t(b)}{flag}")183 return "\n".join(lines)