Delivery Routing: untangling a route with 2-opt, then splitting a full van into trips

The data in this project is synthetic — delivery-stop coordinates and parcel counts generated locally by data/make_data.py, no real addresses. That is deliberate: grading needs a known reference route length to measure yours against, and it keeps the project download-free and PII-free (delivery addresses are personal data). No signup, no GPU.

Before you start

New to route optimisation? Start here.

A van has to visit a list of stops and come back to the depot. In what order? This is the Travelling Salesman Problem (TSP) — find the shortest round trip through all the stops. There’s no fast way to find the guaranteed shortest for many stops, so you use heuristics: quick methods that get close.

Two do most of the work, and Part A builds both:

Nearest-neighbour — start at the depot, always drive to the closest stop you haven’t visited yet, repeat. Fast, but it strands far-off stops for last and makes long jumps back across the map.
2-opt — take an existing route and repeatedly reverse a segment whenever that makes the route shorter. Each improving move untangles a place where the route crossed itself. It stops when no reversal helps.

Part B adds the constraint every real dispatcher has: the van has a capacity, and the parcels add up to more than it can carry in one trip. So one route becomes several — you have to split the stops into capacity-feasible trips and route each. What you’ll learn is in Section 3.

New to Python too? See Start Here — it starts from zero, and shows how to run this in your browser with nothing to install.

1. The Brief

You’re planning a parcel van’s morning from a single depot. Part A: turn the drop list into a route. Build the nearest-neighbour tour the dispatcher would drive by instinct, then improve it with 2-opt and measure the kilometres you save. Part B: each stop now has a parcel count and the van has a fixed capacity — and the total won’t fit in one load. Split the stops into several capacity-feasible trips (each out-and-back from the depot) and keep the total distance down.

Vehicle routing is a multi-billion-dollar problem — parcel carriers, field service, grocery delivery, waste collection all live and die by it. The two moves here (a good construction heuristic, then local improvement) are the backbone of every practical router, and the capacity split is the first step from a textbook TSP toward the real Vehicle Routing Problem.

2. Difficulty & time

Difficulty 6 / 10. Part A is two algorithms that must be implemented correctly (the 2-opt swap condition is easy to get subtly wrong). Part B adds a genuine second decision — partition the stops into feasible trips and route each — and a feasibility constraint that makes the naive answer useless. Calibrated against the ledger (G10): a peer of warehouse-sim (6), fraud-rings (6), and spatial-autocorrelation (6). Above nearest-facility (4, one assignment pass) and spatial-clusters (5); it sits below the 7-8 band because the heuristics are standard and you’re beating a baseline, not proving optimality.

Time is separate from difficulty: Part A is about an hour; Part B is 2.5–3 hours. The scripts run in under a second.

3. What you’ll be able to do after

Build a nearest-neighbour tour and explain why greedy construction leaves long backtracks.
Improve a route with 2-opt — implement the reversal correctly and show it removes self-crossings.
Quantify the win — measure how much shorter the improved route is than the naive one.
Route under capacity — split stops into capacity-feasible trips and route each so the total distance stays low, recognising why a single tour is infeasible.

The finished result

By the end of Part A you’ll have turned a 60-stop drop list into a route, untangled it, and measured the kilometres 2-opt saves over the dispatcher’s nearest-neighbour instinct:

nearest-neighbour tour:  748.2 km   self-crossings: 5
2-opt tour:              673.0 km   self-crossings: 0   (10.1% shorter)

A greedy route with five self-crossings — then the same stops in a cleaner order about 75 km shorter, the crossings gone. In Part B that same builder, run under a van capacity, serves all 50 stops in 6 trips.

4. Prereqs & time box

You can write nested loops and functions, use numpy arrays (including a distance matrix), and read a CSV with pandas. No operations-research background needed — the orientation and Part A build both heuristics from scratch. The only geometry is straight-line distance.

Where to write and run code

Two ways to run this project — pick either:

In your browser (no install). If the project page shows a ▶ Run button, click it to run Part A right here — nothing to set up. Part A uses only pandas and numpy, which run in the browser.
On your computer. The one-time setup — installing Python, downloading the code from the course site (no GitHub, no git), opening a terminal, creating a virtual environment, installing the requirements, and running Part A step by step — is covered once in Start Here. Come back here once python -c "import pandas" runs without error. Part B (writing your own solution) needs this local setup.

Time box

Part A — Guided Build: 60–90 minutes. Hard cap.
Part B — Your Turn: 2.5–4 hours. Hard cap.

5. Setup & data

The data is synthetic and generated locally — see the banner above and SOURCES.md for full provenance. One command creates both parts’ data:

python data/make_data.py

That writes two CSVs into data/ (git-ignored; regenerate anytime, byte-for-byte identical because the seeds are fixed):

Part A — stops_a.csv (60 rows: stop_id, x_km, y_km).
Part B — stops_b.csv (50 rows: stop_id, x_km, y_km, demand).

Coordinates are projected planar km on a ~100 km metro grid; the depot is at (50, 50). The van capacity is 60 parcels (total Part B demand is 304, so ≥ 6 trips). Distances are straight-line — fine for a projected local grid.

6. Part A — Guided Build

You’ll route 60 stops, two ways, and measure the improvement. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

python part_a/route.py

Prefer the browser? If this page has a ▶ Run button, click it instead of the command above — Part A runs in your browser with nothing to install. The STEP output and every checkpoint below are identical either way.

The full, commented script is in part_a/route.py. The spine:

Step 1 — The distance matrix.

Checkpoint: a 61×61 matrix (60 stops + depot at index 0); the farthest stop is 67.6 km from the depot. Routing is just choosing the visit order.

Step 2 — Nearest-neighbour construction.

Checkpoint: the greedy tour is 748.2 km and crosses itself 5 times — greedy strands far-off stops and jumps back for them.

Step 3 — 2-opt improvement.

Checkpoint: reversing shortening segments cuts the tour to 673.0 km (10.1% shorter) and the self-crossings drop to 0. Writes part_a/route_a.csv.

Step 4 — Why 2-opt works: no crossings left.

Checkpoint: crossings 5 → 0. Two crossing edges can always be uncrossed by a reversal, and uncrossing is always shorter — so a route with crossings is never optimal.

Why this and not that

Why not just nearest-neighbour. It’s greedy: early choices look cheap but leave expensive leftovers, so the tour backtracks. The 10% it leaves on the table is free once you add 2-opt.
Why 2-opt specifically. It’s the simplest local search that targets the exact failure mode (crossings), it’s easy to implement, and it gives most of the achievable gain for little code.
Why it stops where it does. 2-opt reaches a local optimum — no single reversal helps — which isn’t guaranteed globally optimal, but is a large, reliable improvement over raw construction.

Functions you’ll meet (and where to read more)

Function	What it does here	Docs
broadcasting `P[:,None,:] - P[None,:,:]`	Build the full distance matrix at once	broadcasting
`np.hypot` / `np.sqrt`	Euclidean distance	hypot
`min(unvisited, key=...)`	Pick the nearest unvisited stop	min
slice-reverse `lst[i:k+1][::-1]`	The 2-opt segment reversal	slicing

If something looks off

I ran python part_b/starter.py, then pytest, and it says FAILED — did I break something? No — the Part B starter is built to fail. It chunks the stops in file order, ignoring where they are on the map, so it scores about 0.38 and sits below the 0.85 floor on purpose, to give you a bad plan to beat. Group nearby stops into capacity-feasible trips and 2-opt each (as in Part A) and the score climbs past the floor — that red FAILED turning green is the whole exercise.
A checkpoint number doesn’t match. The data is seeded, so the numbers are exact. Re-run python data/make_data.py (you may have skipped or edited it), then re-run Part A.
Setup problems (Python not found, pip, FileNotFoundError, re-activating the venv): see the troubleshooting list in Start Here.

7. Part B — Your Turn

Part B is the optional “your turn” half — a guided fill-in-the-blank, not a blank page. You get a working starter (part_b/starter.py) that already handles the easy version; your job is to finish the # TODO it marks out. More open than Part A’s step-by-step, but you are never staring at an empty file. If you finished Part A and want to prove the skill, this is where it happens. New to Python? It’s completely fine to stop after Part A and come back later.

Same core skill — build and improve routes — but now under a capacity constraint on a new stop set (stops_b.csv). Each stop has a demand (parcels); the van holds 60. Total demand is 304, so a single tour is impossible. Split the stops into capacity-feasible trips (each depot → stops → depot, total demand ≤ 60, every stop served once) and minimise the total distance across all trips. The starter chunks the stops in file order (ignoring geography) and scores 0.38, so it fails.

The transfer: Part A found the order for one tour; Part B first has to decide which stops share a trip (a partition), then route each — and the single-tour answer from Part A is now infeasible, not just suboptimal. Reuse your route builder per trip.

Reference rule (reproduce it to match the yardstick)

Capacity-aware nearest-neighbour: from the depot, repeatedly drive to the nearest unvisited stop whose demand still fits the van’s remaining capacity; when nothing fits, return to the depot and start a new trip. Then run 2-opt on each trip. (A stronger option is the Clarke-Wright savings algorithm — either clears the floor.)

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

routes.csv — columns trip_id, stop_seq, stop_id (one row per stop; stop_seq gives the order within each trip).
report.json — with keys stops, achieved_metric (you can leave achieved_metric null; the grader scores you).

Then:

python part_b/starter.py
pytest part_b/test_solution.py -q

If pytest reports everything as skipped, it just means the output files don’t exist yet — run python part_b/starter.py first (once your solution fills in the TODOs), then re-run.

You’re done when the tests pass. The score is 0 if the plan is infeasible (any trip over capacity 60, or a stop missing/duplicated), otherwise reference_km / your_total_km, and you need ≥ 0.85 (the reference reaches 1.00). Each trip is measured depot → stops (in stop_seq order) → depot. The file-order-chunk baseline is feasible but ~2.6× longer → 0.38.

Constraints — what must be true of your solution, not how to get there

No trip’s total demand exceeds 60.
Every stop is served exactly once, across all trips.
Every trip starts and ends at the depot (implied — you list only the stops, in order).
Keep total distance within ~18% of the reference (that’s the 0.85 floor).

Hints

Hint 1 — why file order fails

Chunking the stops in the order they appear ignores where they are, so each trip criss-crosses the map. Feasible, but ~2.6× the reference distance. The fix is to make each trip a cluster of nearby stops.

Hint 2 — build trips greedily, then improve

Grow one trip at a time with nearest-neighbour, but skip any stop whose demand won’t fit the remaining capacity; when nothing fits, close the trip and start another. Then 2-opt each trip exactly as in Part A — a trip is just a small TSP.

Hint 3 — feasibility first, distance second

A shorter plan that puts a trip over capacity scores 0, not a little less — feasibility is a hard gate. Track each trip’s load as you add stops, and confirm every stop appears exactly once before you worry about shaving kilometres.

8. Self-check

You don’t need the answer key. You’re done when all of these hold:

pytest passes — feasible (no trip over 60) and total distance within ~18% of the reference.
You have ≥ 6 trips (total demand 304 ÷ capacity 60 = 5.07, so at least 6), each a compact cluster of nearby stops rather than a spread across the whole map.
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: 2-opt should shorten each trip a little versus capacity-aware nearest-neighbour alone. If applying 2-opt changes nothing, check that your swap actually reverses the segment between the two chosen edges.

9. Stretch

Clarke-Wright savings. Implement the classic savings heuristic (merge routes that save the most distance while respecting capacity) and compare its total to your nearest-neighbour + 2-opt.
Or-opt moves. Add Or-opt (relocate a run of 1–3 stops to a better position, possibly in another trip) on top of 2-opt and see how much more you can shave.
(Genuinely hard) Balance the trips. Add a soft objective to keep trips similar in length (a driver-fairness constraint) and watch it trade against total distance — the kind of multi-objective tension real routing software exposes as a slider.

10. Ship it

Put this in a portfolio repo and it counts. In that repo’s README:

State the finding in one sentence a planner gets: “2-opt cut the single-route distance ~10% over nearest-neighbour; under a van capacity, a capacity-aware build + 2-opt served all stops in 6 trips at ~40% of a naive file-order plan’s distance.”
Show the before/after route (crossings gone) and the capacitated trips coloured by trip.
Include the 2-opt swap and the capacity check, with one paragraph on why a crossing is always an improvement waiting to happen. That paragraph is what signals you understand routing, not just a library call.

Keep make_data.py and the tests in the repo so anyone can reproduce your numbers from zero.

11. Sources

Rendered from SOURCES.md.

Field	Value
Dataset	Synthetic delivery stops (Part A 60; Part B 50 with parcel demand) + a central depot, capacity 60
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seeds `20260754` (A) and `20260755` (B)
Source URL	Not applicable — generated, not fetched
License	Not applicable — synthetic, no third-party rights
Access / generation date	2026-07-18
Redistribution	Permitted — synthetic; output regenerated from the seeded script, never committed
robots.txt checked	Not applicable — no scraping
ToS URL	Not applicable — no external source

Synthetic data teaches the mechanic; it does not prove a finding about the real world. The stops and demands were generated on purpose — the routing techniques are the point, not a claim about any real delivery network.

Next up

Finished this one? Continue the Supply Chain track:

Transshipment: least-cost flow through a network, and modelling a warehouse’s throughput limit → · Browse all courses