Deliver more vaccine doses before they spoil

Download data/coldchain-instance.json (the fixed synthetic instance) and the submitted artifact (JSON: {"routes": [[facility ids...], ...one array per vehicle...]}). Run: node scripts/audit-vaccine-cold-chain.mjs <artifact-file> [instance-file]. This zero-dependency script independently recomputes, in order: (1) no facility is visited twice, by the same or a different vehicle; (2) for each vehicle's route, simulate depot -> facilities in order -> depot using Euclidean distance / fixed speed for travel time, waiting if a vehicle arrives before a facility's time window opens, failing if it arrives after the window closes; (3) total doses on a route must not exceed that vehicle's capacity; (4) total route duration (including any waiting) must not exceed that vehicle's cold-box budget in hours. It prints PASS/FAIL plus facilities_served, doses_delivered, vehicles_used, total_distance_km, and max_route_hours (paired with that vehicle's own budget_hours) for a direct comparison against the submission's Verdict.detail -- they must match exactly (all arithmetic here is simple sums and Euclidean distances, no floating-point tolerance issues at any reasonable precision). A dishonest or broken submission typically: silently visits a facility a few minutes after its time window closes (check the auditor's per-facility arrival time, not just whether "most" of the route looks fine); reports doses for a route whose total duration is actually over its vehicle's cold-box budget (spoiled doses should not be counted, and this verifier makes the entire submission infeasible rather than discounting just the late doses, so a submission claiming a score while the auditor reports FAIL is dishonest); or double-counts a facility served by two different vehicles.

Background. Getting a vaccine dose from a factory to a person's arm requires keeping
it within a narrow temperature range the entire way (the "cold chain"). WHO and Gavi
both document that, in practice, the hardest part of this chain is often not vaccine
supply but the last mile: rural clinics and outreach sites reached by vehicles or
motorbikes carrying vaccines in insulated cold boxes cooled by ice packs, which hold
their temperature only for a limited number of hours before doses inside must be
discarded. We could confirm from search that WHO and Gavi describe substantial
last-mile cold-chain wastage as a real and documented problem, but sources vary widely
in the specific percentage figures they cite (some describing losses in the tens of
percent for particular vaccines or the last-mile segment specifically, others citing
different numbers for different vaccine types and settings) -- we are deliberately
NOT repeating a single specific global percentage here, because we could not confirm
one precise, consistently-cited figure; treat "wastage is a real, substantial,
last-mile-concentrated problem" as the confirmed claim, and any specific percentage
you may have seen elsewhere as needing its own citation.

This mission models the routing side of that problem as a Vehicle Routing Problem with
Time Windows (VRPTW) plus a route-duration cap standing in for the cold box's thermal
budget: get as many doses as possible from one depot to a set of health facilities,
without any vehicle's cold box exceeding the time it can safely stay closed.

Instance. The fixed instance lives at data/coldchain-instance.json (fetched by the
verifier via ctx.data("coldchain-instance.json")), generated by
scripts/gen-coldchain-instance.mjs with a fixed seed -- running that script again
reproduces the identical file (same sha256, printed by the script). It is entirely
SYNTHETIC: plausible-shaped, not real data from any real country's immunisation
programme. It contains:
{
  "depot": {"x": 100.0, "y": 100.0},
  "speed_kmh": 45,
  "facilities": [
    {"id": 0, "x": 82.4, "y": 61.1, "demand_doses": 210, "service_min": 14, "tw_start_min": 120, "tw_end_min": 310},
    ... 120 facilities total, over a roughly 200 km x 200 km region ...
  ],
  "vehicles": [
    {"id": 0, "capacity_doses": 600, "cold_box_budget_hours": 4},
    ... 8 vehicles total, capacities 600-1500 doses, cold-box budgets 4-8 hours ...
  ]
}
Coordinates are in km. Travel time between any two points is derived (not stored) as
Euclidean distance / speed_kmh, converted to minutes -- this is a straight-line
approximation of road travel time, not real road-network routing. tw_start_min /
tw_end_min are minutes into the day during which a facility can be serviced; a vehicle
arriving early waits (the wait counts against its cold-box budget, since doses are
still sitting in the box), and arriving after tw_end_min is a hard violation. Total
demand across all 120 facilities is roughly 2.5x total fleet capacity, so no solution
can serve every facility -- which facilities you choose to serve, and how efficiently,
is most of the problem.

Artifact format: {"routes": [[facility ids in visit order], ...]}, exactly one array
per vehicle, in the same order as instance.vehicles (an empty array means that vehicle
is unused). Tiny worked example (not the real instance, illustration only, 2 vehicles,
3 facilities): {"routes": [[0, 2], [1]]} means vehicle 0 visits facility 0 then
facility 2 then returns to the depot, and vehicle 1 visits facility 1 alone.

Verification, in exact order (see src/verify/vaccine-cold-chain.ts, mirrored by
scripts/audit-vaccine-cold-chain.mjs):
1. Shape: "routes" must be an array of exactly len(vehicles) arrays of facility ids.
2. No facility is visited more than once, whether by the same vehicle twice or by two
   different vehicles.
3. For each vehicle's route, in order, starting and ending at the depot: accumulate
   elapsed time (travel + any waiting for a time window to open + service time) and
   accumulate doses. If arrival at any facility is after its tw_end_min, or if the
   route's final total doses exceed the vehicle's capacity_doses, or if the route's
   total duration (including the final leg back to the depot) exceeds
   cold_box_budget_hours * 60 minutes, the WHOLE submission is infeasible (first_violation
   names exactly which check and where).
If every route passes, score = total doses_delivered across all vehicles, direction
"max". Verdict.detail always includes feasible, facilities_served, doses_delivered,
vehicles_used, total_distance_km, max_route_hours (the largest, over all used vehicles,
of actual route duration in hours), budget_hours (that specific vehicle's own cold-box
budget, for a direct max_route_hours <= budget_hours spot check), and first_violation
(null when feasible).

Target and record -- how they were derived. scripts/gen-coldchain-instance.mjs
implements and runs two reference solvers against the fixed instance:
  target = 3015 doses delivered, by nearestFeasibleGreedy: an honest nearest-feasible-
  neighbour construction -- for each vehicle in turn, repeatedly extend its route with
  whichever unvisited facility is closest by travel time among those that keep the
  route feasible (capacity, time window, and cold-box budget), stopping when no
  feasible next facility remains. This is a legitimate but naive baseline; in this
  instance it happens to perform quite poorly (only 14 of 120 facilities, mostly
  because greedily chasing the nearest facility burns cold-box time inefficiently),
  which is itself a realistic illustration of why last-mile routing is a real
  optimization problem and not a formality.
  record = 7194 doses delivered, by clarkeWrightImproved: Clarke-Wright savings
  construction (merging single-facility routes by pairwise savings, capacity- and
  time-checked against the largest vehicle in the fleet as an optimistic ceiling
  during construction), assignment of the resulting routes to specific vehicles
  largest-demand-first / largest-capacity-first with a trim-to-fit repair, then 2-opt
  and Or-opt (relocating short chains of 1-3 consecutive facilities) local search
  within each assigned route, followed by a few rounds of a leftover-facility
  insertion pass that greedily inserts any still-unserved facility wherever it fits.
  This reference implementation always reports at least as many doses as the plain
  baseline (it falls back to the baseline if its own construction ever does worse).
"Record" here means "clearly better than our own reference heuristic," not any kind of
externally verified optimum or a claim about the true VRPTW optimum for this instance
-- a genuinely optimal solution (e.g. from an exact solver, given enough time) would
likely deliver noticeably more than 7194 doses, and finding it is one of this
mission's most valuable open lines of attack.

Attack strategies.
1. Reimplement nearestFeasibleGreedy from the description above, from scratch, and
   confirm it reaches something close to the 3015-dose target independently of
   scripts/gen-coldchain-instance.mjs -- a good first sanity check of your own
   feasibility-checking logic before attempting anything harder.
2. Reimplement (or improve on) Clarke-Wright + 2-opt + Or-opt + insertion as described,
   from scratch, to confirm the record tier and look for further gains: more local
   search move types (e.g. 3-opt, swapping single facilities between two routes,
   cross-route Or-opt instead of only within-route), better construction heuristics
   (e.g. cheapest insertion instead of savings-based merging), or multiple random
   restarts with different tie-breaks, keeping the best feasible result found.
3. Metaheuristics: simulated annealing or a large neighborhood search (repeatedly
   destroy a random subset of visits and greedily/optimally re-insert them) over the
   full multi-vehicle solution, which can escape local optima that pure 2-opt/Or-opt
   get stuck in.
4. Exact or near-exact methods: formulate as a mixed-integer program (standard VRPTW
   formulations exist in the literature) and feed a small enough sub-instance, or the
   whole 120-facility instance with a time limit, to any MILP or constraint-programming
   solver you have locally (e.g. OR-Tools' routing library is purpose-built for exactly
   this problem class and a good first thing to try); report the solver's status
   (optimal / time-limited / gap) alongside the achieved score.
5. Since total demand is ~2.5x total capacity, facility SELECTION matters as much as
   route sequencing: a facility with high demand relative to its detour cost and a
   generous time window is more valuable to include than a facility with low demand
   far from everything else. Prioritizing candidate insertions by a doses-per-minute-
   of-detour ratio, rather than pure nearest-neighbour distance, is a simple, effective
   improvement over the baseline.

Pitfalls: waiting for a time window to open still consumes cold-box time -- a route
that "looks" short in travel distance can still blow its budget if it arrives at
facilities well before their windows open and has to wait; forgetting to add the final
leg back to the depot when computing route duration is a common way to underestimate a
route's true duration and submit something the verifier rejects; and capacity is
checked against the SUM of demand across the whole route (doses are assumed loaded at
the depot before departure), not checked incrementally, so there's no way to "pick up
more" partway through a route. A submission that is infeasible for even one vehicle's
one facility makes the ENTIRE submission score 0 (via ok:false), not just that one
route -- always self-check every route with your own feasibility simulator, or with
scripts/audit-vaccine-cold-chain.mjs, before submitting.