Nearest Facility: distances on a globe, and when the nearest one is full

The data in this project is synthetic — customer and facility coordinates generated locally by data/make_data.py, with no geocoding or address files. That is deliberate: grading needs the known-correct nearest facility and a reference feasible assignment, which real (PII-bearing, licensed) location data doesn’t come labelled with — and it keeps the project download-free. No signup, no GPU.

Before you start

New to distances on a map? Start here.

Latitude and longitude are angles, not distances. A degree of latitude is ~111 km anywhere. A degree of longitude shrinks as you go north — it’s ~101 km at 25°N but only ~56 km at 60°N (a factor of cos(latitude)). So if you treat (lat, lon) as flat x/y coordinates and use ordinary (Euclidean) distance, you stretch the map east–west and get distances — and therefore the “nearest” facility — wrong, most of all up north.

The right tool is great-circle distance, computed with the haversine formula, which measures the true distance between two points on a sphere.

The task both parts share: assign each customer to a facility. Part A picks the single nearest facility (and shows the Euclidean-on-degrees mistake). Part B adds a twist every logistics planner knows — the nearest facility has limited capacity, so once it’s full, some customers must go to their second choice.

What you’ll learn: compute haversine distance, assign customers to nearest facilities correctly, and then produce a capacity-feasible assignment that keeps total travel low. Section 3 lists exactly what you’ll be able to do.

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 which depot serves which customer across a wide country. The obvious “assign everyone to their nearest depot” runs into two real problems: measured naively (degrees as distance) it picks the wrong depot for thousands of customers, and even done correctly it ignores that a depot can only handle so much. You’ll fix the distance first, then the capacity — the two things that turn a textbook nearest-neighbour into an assignment a dispatcher could actually use.

Facility assignment / catchment analysis underlies delivery networks, store territories, clinic coverage, and warehouse design. Getting distance right on the globe (haversine, not flat degrees) and respecting capacity are the two most common places a naive version goes wrong.

2. Difficulty & time

Difficulty 4 / 10. One tool (numpy) but two genuine judgments: use great-circle distance, not degree-Euclidean, and turn “nearest” into a feasible assignment under capacity. Calibrated against the ledger (G10): a peer of maverick-spend (4), ab-test-readout (4), and newsvendor-stocking (4) — a clear method with one conditional twist, above the single-mechanic 3s (spatial-join, duplicate-invoices) because Part B adds a constraint that makes the naive answer infeasible, not just imperfect.

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

3. What you’ll be able to do after

Compute haversine distance between lat/lon points (vectorised) and explain why degree-Euclidean is wrong.
Assign nearest facilities correctly and quantify how much the degree shortcut mis-assigns, and where.
Produce a capacity-feasible assignment — respect each facility’s limit while keeping total travel low.
Recognise an infeasible plan — see why the lowest-distance assignment can be unusable.

The finished result

By the end of Part A you’ll have assigned the same 2,000 customers two ways — the degree shortcut versus true great-circle distance — and seen exactly where, and how often, the two disagree:

1 deg longitude = 100.8 km at 25N  ...  55.6 km at 60N   (1 deg latitude ~ 111 km everywhere)
euclidean-on-degrees vs haversine:  agree on 0.923 of 2,000 customers   (154 get a different depot)
disagreement climbs with latitude:  7.2% at 25-37N    5.8% at 37-48N    9.9% at 48-60N

Same “nearest facility” question, two different answers for 154 real customers — the gap widest up north, exactly where a degree of longitude is most compressed. Part B keeps this haversine distance but adds a capacity limit, so the nearest depot isn’t always available.

4. Prereqs & time box

You can write a function and use numpy arrays and a pandas DataFrame. No geospatial background needed — Part A gives you the haversine formula. Trig is used but not required to derive.

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–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 four CSVs into data/ (git-ignored; regenerate anytime, byte-for-byte identical because the seed is fixed):

Part A — customers_a.csv (2,000: customer_id, lat, lon) and facilities_a.csv (30: facility_id, lat, lon).
Part B — customers_b.csv (1,500) and facilities_b.csv (20: adds capacity = 85 each).

Coordinates are real lat/lon over 25–60°N, 120–70°W.

6. Part A — Guided Build

You’ll assign 2,000 customers to their nearest facility, two ways. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

python part_a/assign.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/assign.py. The spine:

Step 1 — Degrees aren’t distances. Show km-per-degree-longitude by latitude.

Checkpoint: 1° longitude ≈ 101 km at 25°N but ≈ 56 km at 60°N; 1° latitude ≈ 111 km everywhere.

Step 2 — Naive nearest: Euclidean on degrees.

Checkpoint: assigns all 2,000 — treating 1° north and 1° east as equal distance.

Step 3 — Correct nearest: haversine km.

Checkpoint: true great-circle nearest facility per customer.

Step 4 — Disagreement, by latitude.

Checkpoint: the two agree on only ~0.923 of customers (~154 differ), and the disagreement climbs with latitude (~10% at 48–60°N vs ~6–7% lower). Writes part_a/assignment_a.csv.

Why this and not that

Why haversine, not degree-Euclidean. Distance on a sphere isn’t Pythagoras on angles. Degree distance over-weights longitude the farther north you go, so it mis-ranks facilities that differ mostly east–west — thousands of customers routed to the wrong site.
Why the error concentrates up north. Longitude compression is worst at high latitude, so that’s where degree-distance distorts the ranking most. The latitude breakdown makes the cause visible.
Why vectorise. Broadcasting the haversine over all customer×facility pairs is a few lines and fast; you’ll reuse the same distance matrix in Part B.

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

Function	What it does here	Docs
`np.radians`	Convert degrees to radians for trig	radians
`np.sin` / `np.cos` / `np.arcsin`	The haversine formula	math routines
broadcasting `a[:,None]`	All customer×facility pairs at once	broadcasting
`arr.argmin(axis=1)`	The nearest facility per customer	argmin

If something looks off

Steps 2 and 3 both print “assigned 2,000 customers” — did switching to haversine change anything? Yes. Both methods assign all 2,000 customers; what changes is which facility each one gets, and that only shows up in Step 4 — where the two disagree on ~8% of customers (154 of them), climbing to ~10% up north where a degree of longitude is shortest. Those 154 are real people routed to the wrong depot, which is the whole point of using great-circle distance.
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, plus a capacity limit. Each of the 20 facilities can serve at most 85 customers (capacity in facilities_b.csv). Assign all 1,500 customers so no facility is over capacity, keeping total great-circle travel low. The starter assigns everyone to their nearest facility and ignores capacity — the lowest possible distance, but it overflows popular facilities (one hits ~159) so it’s infeasible and scores 0.

The transfer: Part A’s “nearest facility” is exactly what you can no longer always do. Use the same haversine distances, but assign under the capacity constraint.

Reference rule (reproduce it to match the yardstick)

Deterministic greedy: sort all (customer, facility) pairs by haversine distance ascending (tie-break by facility_id, then customer_id); walk the list and assign a customer to a facility iff that customer is still unassigned and the facility has capacity remaining.

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

assignment.csv — columns customer_id, facility_id (every customer, exactly once).
report.json — with keys customers, 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 assignment is infeasible (any facility over capacity, or a customer missing/duplicated), otherwise greedy_km / your_total_km, and you need ≥ 0.90 (the reference reaches 1.00). The nearest-ignore-capacity baseline is infeasible → 0.

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

No facility exceeds its capacity.
Every customer is assigned exactly once, to a real facility.
Use great-circle (haversine) distance for the cost.
Keep total travel within ~11% of the greedy reference (that’s the 0.90 floor).

Hints

Hint 1 — why nearest fails now

Count how many customers pick each facility under plain nearest-assignment; the busy ones blow past 85. Capacity is a hard limit, so some of those customers must be routed elsewhere.

Hint 2 — the greedy

Build every (distance, facility, customer) triple, sort ascending, and walk it: assign a customer the first time you reach a pair whose customer is still free and whose facility still has room. Track a per-facility load counter.

Hint 3 — keep it feasible (still not the code)

Total capacity (20 × 85 = 1,700) exceeds the 1,500 customers, so a feasible assignment exists — the greedy above always finds one because every customer’s pairs to every facility are in the sorted list.

8. Self-check

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

pytest passes — feasible (no facility over 85) and total travel within ~11% of the reference.
Your busiest facility has exactly ≤ 85 customers; if any has more, you didn’t enforce capacity.
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: your total distance should be a bit higher than the naive nearest-assignment’s (some customers were bumped to a farther, non-full facility). If it equals the nearest-only distance, you haven’t enforced capacity.

9. Stretch

Optimal, not greedy. Solve the capacitated assignment exactly as a min-cost flow or LP (scipy.optimize.linprog / a transportation problem) and compare its total distance to the greedy.
Unequal capacities. Give facilities different capacities (some big hubs, some small) and see how the assignment reshapes.
(Genuinely hard) Open a facility. Add a fixed cost to “use” a facility and decide which subset to open before assigning — the start of facility-location (a later project in this batch tackles exactly that).

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: “degree-distance mis-assigned ~8% of customers (up to 10% up north); haversine fixed it, and a capacity-aware assignment kept every depot within its limit for ~X% more travel.”
Show the Euclidean-vs-haversine disagreement by latitude, and the capacitated vs nearest loads.
Include the haversine function and one paragraph on why degrees aren’t distances. That paragraph is what signals you understand geospatial distance, not just argmin.

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 customer + facility lat/lon (Part A 2,000/30; Part B 1,500/20 with capacity 85)
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seeds `20260744` (A) and `20260745` (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 coordinates and capacities were generated on purpose — the distance and assignment techniques are the point, not a claim about any real network.

Next up

Finished this one? Continue the Geospatial track:

Geohash Rollup: a base-32 address for the map, that nests and has neighbours → · Browse all courses