Capstone: RouteWise Delivery Planner

Milestone 1: City data and a deterministic generator

Goal. Model the city with frozen dataclasses and generate realistic, reproducible test cities of any size. Every later test depends on this, so determinism is not optional: use one random.Random(seed) instance and never the global random functions.

The generator lays intersections on a jittered square grid (side about √(1.6 n)), joins horizontal and vertical neighbours plus a few random diagonals, and gives each edge a travel time of length ÷ MAX_SPEED × congestion with congestion ≥ 1. That last detail matters in Milestone 2: because no road is faster than MAX_SPEED, straight-line distance ÷ MAX_SPEED never overestimates travel time. The depot sits at the centre; customers get distinct other nodes, demand 1–8 crates, a window opening between minute 0 and 360 of width 60–180, and 2–8 minutes of service. Make sure every customer is reachable before its window closes, or the instance is unsolvable.

Concepts: dataclasses and validation in __post_init__ (M13), seeded randomness and csv (M40, M09), type hints (M16), raising good exceptions (M07).

• Customer rejects ids below 1, negative demand, and ready > due
• generate_city(n, seed) is deterministic and different seeds give different cities
• Customer ids are 1..n on distinct non-depot nodes; the network is connected
• No edge is faster than MAX_SPEED; every customer is reachable before due
• save_city then load_city returns an equal City

Hints

• Rounding a travel time down could make it slightly faster than MAX_SPEED. Round up (math.ceil(x * 1000) / 1000).
• To guarantee reachability, compute Dijkstra from the depot inside the generator (that is why data imports graph, never the other way round) and widen any window that closes too early.
• Python's float → str → float round trip is exact (repr is shortest round-tripping), so CSV equality tests are fair.

Milestone 2: Road graph, Dijkstra, A*, and the distance matrix

Goal. A RoadGraph stored as an adjacency list (a dict from node to a list of (neighbour, minutes) arcs), shortest paths with Dijkstra's algorithm and A*, path reconstruction, and a DistanceMatrix that computes each row lazily and caches it.

Dijkstra settles nodes in order of distance using a binary heap; with lazy deletion (push duplicates, skip stale pops) it runs in O((V + E) log V). A* orders the heap by g + h, where g is the cost so far and h estimates the rest. If h never overestimates (it is admissible) and satisfies the triangle inequality (it is consistent), A* returns the same optimal cost as Dijkstra while settling fewer nodes. Our heuristic is straight-line distance ÷ the fastest arc speed in the graph, which is admissible by construction.

Routing needs travel times between the depot and every customer, often millions of lookups. Running one full Dijkstra per source (n + 1 runs) and caching the rows turns each lookup into a dict access.

Concepts: graph representations (M26), Dijkstra and A* (M31), heaps (M25), hash maps as caches (M23), complexity (M19), NumPy arrays (M48).

Draw some walls and compare Dijkstra with A*: both find a shortest path, but A* explores a narrow corridor toward the goal.

• add_edge rejects unknown nodes (KeyError) and negative times (ValueError)
• dijkstra returns settled distances and predecessors, with optional early exit
• a_star equals Dijkstra's cost on random graphs, including directed and unreachable cases
• A* settles fewer nodes than Dijkstra on generated cities
• DistanceMatrix computes each row at most once and is symmetric on two-way roads

Hints

• Return PathResult(math.inf, ()) for unreachable targets rather than raising: "no path" is a normal answer, not an error.
• max_speed() is the maximum of length / minutes over arcs. If some arc has zero minutes but positive length, the speed is infinite and the only admissible heuristic is 0.
• Put a tie-breaker in heap tuples ((f, g, node)) so Python never compares incomparable payloads.

Milestone 3: Routes, plans, and feasibility

Goal. The core domain model. An Instance bundles the depot, customers, a travel-time oracle, van capacity, and the horizon. A Route is a tuple of customer ids (the depot is implicit at both ends); a Plan is a tuple of routes, one per van. schedule(route, inst) simulates the van and returns a Schedule of Visits plus every violation; check_plan adds plan-level problems: unknown, duplicated, or missing customers.

The simulation is the heart of the system, so make it obviously correct: arrival = clock + travel; start = max(arrival, ready) (waiting is allowed); late if start > due; clock = start + service. After the last stop, drive back and compare with the horizon. Every heuristic later calls this function, so the tests for it are the foundation of trust.

Concepts: frozen dataclasses and dataclasses.replace (M13), typing.Protocol for the travel oracle (M12, M16), the data model (M11), designing APIs (M46).

The two orders have the same travel time, yet one waits 20 minutes and the other does not. Time windows make route direction matter, which is why Clarke-Wright (Milestone 5) tries reversed merges.

• Route and Plan are immutable and coerce lists to tuples
• schedule waits for windows and reports capacity, lateness, horizon, and unreachable stops
• route_cost includes both depot legs; plan_cost sums routes
• check_plan catches unknown, duplicated, and unserved customers
• Instance.from_city, subset, and relaxed work

Hints

• Use the pseudo id DEPOT = 0 so inst.time(a, b) works for depot legs without special cases. That is why customer ids start at 1.
• Return violations as strings in a tuple; feasible is just not violations.
• Compare floats with a small epsilon (1e-9) so 59.999999 vs 60 does not flip feasibility.

Milestone 4: An exact baseline with Held-Karp

Goal. Before writing heuristics, write the referee. Held-Karp solves the single-van TSP exactly with dynamic programming over subsets: best[S][j] is the cheapest way to leave the depot, visit exactly the customers in set S, and stop at j. Represent S as a bitmask, and best[S ∪ {k}][k] = min over j of best[S][j] + t(j, k). The answer closes the tour back to the depot. That is O(n² 2ⁿ) time instead of brute force's O(n!): for n = 10, about 100,000 steps instead of 3.6 million permutations.

Held-Karp ignores capacity and windows, so its answer is a lower bound for any route over the same customers. Tests use it two ways: Held-Karp must equal brute force on 6 customers, and every heuristic must be at least the optimum and, after 2-opt, within 15% of it on 9-customer instances.

Concepts: dynamic programming and state design (M32), bitmasks (M34), recursion vs tabulation (M28), test oracles (M17).

• held_karp matches brute force on several random 6-customer instances
• The returned order visits each customer once and achieves the returned cost
• Empty input returns (0.0, ()); more than 12 customers raises ValueError

Hints

• Store a parent[mask][k] table alongside best, then walk it backwards from the best final customer, removing each bit as you go.
• Lists of lists indexed by [mask][j] are several times faster than a dict of tuples here.

Milestone 5: Construction heuristics and 2-opt

Goal. Three ways to build a feasible plan fast, and one way to polish it.

• Nearest neighbour (greedy): from the current stop, drive to the closest customer that keeps the route feasible (capacity, window, and still home by the horizon). If none fits, go home and start a new van. O(n²), simple, and often 20–30% worse than optimal.
• Clarke-Wright savings: start with one van per customer. Serving i and j on one route instead of two saves s(i, j) = t(0, i) + t(0, j) − t(i, j). Process savings from largest to smallest and merge two routes when i and j are at their ends and the merged route is feasible. It is the classic workhorse of vehicle routing and usually beats nearest neighbour.
• 2-opt local search: remove two edges and reconnect by reversing the segment between them. The change in cost needs only four lookups, so you can test every pair in O(n²). Accept a move only if it strictly shortens the route and keeps it feasible, and the route can never get worse.

Concepts: greedy algorithms and their limits (M33), sorting with keys and deterministic tie-breaks (M29), slicing and reversal (M20), problem-solving patterns: construct then improve (M35).

• nearest_neighbor and clarke_wright produce feasible plans covering every customer
• Both raise InfeasibleCustomerError for a customer no dedicated van could serve
• two_opt never lengthens a route, keeps the same customers, and preserves feasibility
• Heuristic + 2-opt is at least Held-Karp's optimum and within 15% of it on 9 customers
• Clarke-Wright beats nearest neighbour in total travel on generated cities

Hints

• For Clarke-Wright, keep routes: dict[key, list[int]] and owner: dict[customer, key] so finding a customer's route is O(1). Try the four merge orientations (a+b, b+a, a+reversed b, reversed a+b) and take the first feasible one.
• Sort savings with key (-saving, i, j) so ties break the same way every run.
• In 2-opt, the O(1) delta assumes symmetric travel times. Double-check with a full route_cost before accepting, then call schedule for feasibility.

Milestone 6: Assigning customers to vans (the sweep algorithm)

Goal. A cluster-first, route-second method. Imagine a clock hand rotating around the depot. Sort customers by polar angle (math.atan2(dy, dx), normalized to [0, 2π)) and fill a van until the next customer would overflow its capacity, then start the next van. Route each cluster with nearest neighbour, which may split it further if windows conflict. Finally, plan_routes(inst, method, improve=True) becomes the single entry point the CLI calls.

Sweep produces geographically compact "pizza slice" routes, which drivers like, but it ignores time windows while clustering, so on tight-window days it uses more vans than savings. Comparing the two on your generated cities and writing down why is exactly the kind of analysis interviewers love.

Concepts: trigonometry and floating point (M34), sorting with composite keys (M29), strategy dispatch with a dict of functions (M18, M46).

• polar_angle returns 0, π/2, π, 3π/2 for east, north, west, south
• sweep_clusters partitions the customers in angle order without overflowing a van
• sweep and every method of plan_routes return feasible plans
• plan_routes rejects unknown methods; 2-opt never makes a plan longer
• A 200-customer city is planned feasibly in a few seconds

Hints

• Start the running load at infinity so the first customer always opens the first cluster: no special case.
• Try several start_angle values and keep the cheapest plan: a cheap, effective improvement.

Milestone 7: Predicting delivery times (ETA model)

Goal. The planner assumes a leg takes planned travel + service minutes. Reality differs: rush hour, rain, big orders, and one van with a sticky tail lift. Generate synthetic history whose actual minutes depend on those factors plus noise, then train a scikit-learn Pipeline: a ColumnTransformer that one-hot encodes weekday, weather, and van and passes numeric columns through, feeding a GradientBoostingRegressor (or Ridge for a linear baseline).

The rule of honest ML evaluation: always compare with a naive baseline on held-out data. A model with MAE 3 minutes is impressive if the planner's own estimate is off by 6, and worthless if it is off by 2.5. Split deterministically, fit on the training part only, and report MAE and RMSE for model and baseline side by side.

Concepts: supervised learning, train/test splits, and baselines (M55), pipelines and encoders (M56), reproducibility and monitoring (M59), error metrics and noise (M54).

• generate_history is deterministic with valid fields
• split is reproducible and rejects bad fractions
• Both gbr and ridge beat the naive baseline's MAE on the test split
• Gradient boosting cuts the baseline's MAE by more than half; training is reproducible
• simulate_deliveries yields one delivery per customer, deterministic per seed

Hints

• Encode records as a float matrix (weather as its index) and give ColumnTransformer column indexes. No pandas needed.
• Ridge needs scaled numeric features; gradient boosting does not. Choose the numeric transformer per model.
• RMSE ≥ MAE always. If your RMSE is far above MAE, a few huge errors dominate: look at them.

Milestone 8: Persistence with SQLite

Goal. A Store class wrapping sqlite3 with the schema from the ER diagram. Saving a plan inserts one plans row and many plan_stops rows in a single transaction (with self._conn: commits on success and rolls back on error). Always use ? placeholders, never f-strings: that is how you prevent SQL injection.

with self._conn:                      # one transaction
    cur = self._conn.execute(
        "INSERT INTO plans (label, method, capacity, created_at) VALUES (?, ?, ?, ?)",
        (label, plan.method, capacity, stamp),
    )
    self._conn.executemany(
        "INSERT INTO plan_stops (plan_id, route_index, position, customer_id) VALUES (?, ?, ?, ?)",
        [(cur.lastrowid, r, p, c) for r, route in enumerate(plan.routes) for p, c in enumerate(route.stops)],
    )

Concepts: relational modelling, keys, and transactions (M44), context managers (M15), analytical SQL for KPIs (M61), secure code (M43).

• A saved plan loads back equal, with route and stop order preserved
• Plan ids increase; latest_plan_id and list_plans summarize correctly
• Data survives closing and reopening the database file
• Unknown plan ids raise PlanNotFoundError
• Deliveries round-trip, and re-recording a customer replaces its row

Hints

• Turn on PRAGMA foreign_keys = ON per connection; SQLite leaves it off by default.
• list_plans is one LEFT JOIN with COUNT(DISTINCT route_index), not a Python loop of queries (the N+1 query problem).

Milestone 9: KPIs and the daily report

Goal. Turn a plan (and, after the day, its actual deliveries) into numbers the board cares about: customers served, vans used, total travel and van time, waiting time, planned and actual on-time percentage, mean delay, and van utilization (mean load ÷ capacity). Render them as a Markdown table for the wiki or as aligned text for the terminal.

Keep calculation and presentation separate: compute_kpis returns a frozen Kpis dataclass, and render_report only formats. You can then test the numbers exactly and the rendering loosely, and add an HTML or JSON renderer later without touching the maths.

Concepts: string formatting and f-string format specs (M03), summary statistics (M54), communicating results (M53), separation of concerns (M46).

• KPIs for a hand-checked single-route plan match exactly (travel 40, van time 70, wait 20)
• Utilization, actual on-time %, and mean delay are right with two vans and one late delivery
• An empty plan gives 0 customers, 0 utilization, and 100% planned on-time
• Markdown output has a KPI table and a routes table; text output has no pipes
• Unknown formats raise ValueError

Hints

• Build a list of (metric, value) rows once, then format it two ways.
• Use f"{x:.1%}" for percentages and f"{x:+.1f}" to show the sign of a delay.

Milestone 10: The CLI, end to end

Goal. An argparse interface with three subcommands. generate writes a city; plan loads it, plans with the chosen method, stores the plan, and optionally simulates the day; report loads a plan (the latest by default) and prints or writes the report. main(argv) takes a list and returns an exit code, so tests call it directly with tmp_path instead of spawning processes. Expected failures (no plans, unknown id) print to stderr and return 1; usage errors exit with 2 (argparse does that for you).

Concepts: modules, packages, and __main__.py (M08), packaging and entry points (M41), testing with fixtures and capsys (M17), tooling (M42).

• generate, plan, and report work end to end in a temporary directory
• plan --simulate stores deliveries and the report shows actual on-time %
• report --out writes a file and uses the stored capacity
• Missing plans return exit code 1 with a message on stderr; bad arguments exit with 2
• All grading tests pass and ruff is clean

Hints

• Dispatch with a dict: {"generate": _generate, "plan": _plan, "report": _report}[args.command](args).
• Close the store before rendering (use with Store(path) as store:) so tests on Windows can delete the temporary database.