Facility Location: which depots to open, and why nearest-assignment breaks under capacity

The data in this project is synthetic — candidate sites, build costs, capacities, and customer demand generated locally by data/make_data.py. That is deliberate: grading needs a provably-optimal reference plan, which only a controlled small instance provides, and it keeps the project download-free. No signup, no GPU.

Before you start

New to facility location? Start here.

You have a set of candidate depot sites and a set of customers. Each site costs a fixed amount to build, and serving a customer from a depot costs money in proportion to distance × demand. Which sites should you open?

Open too few and everyone travels far — transport cost soars (and there may not be enough capacity).
Open too many and you pay build cost you didn’t need.

Facility location picks the subset of sites to open that minimises build + transport cost. It’s a combinatorial choice: with n sites there are 2ⁿ possible open/closed combinations. For a small n you can check them all and be certain you found the best.

Part A does the classic uncapacitated version, where each customer is simply served by its nearest open depot. Part B adds a capacity to each depot — and that quietly breaks “nearest.” Once a popular depot fills up, some of its nearby customers must be served from farther away, so the assignment itself becomes an optimisation (a min-cost transportation problem), and it has to be solved inside the search over which depots to open. 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

A grocer is deciding which of several candidate depot sites to build. Part A: with no capacity limits, find the open set that minimises build + transport, and see why “just open the cheapest sites to build” is wrong — it ignores where the customers are. Part B: each depot can only handle so much throughput, and now even a set with enough total capacity fails if you send everyone to their nearest depot (the popular ones overflow). You’ll pair the open-set search with a capacity-feasible min-cost assignment.

Facility location underlies warehouse-network design, retail and clinic siting, cell-tower placement, and server placement in a CDN. The capacitated version is the realistic one: capacity is what turns a clean “nearest depot” rule into a genuine assignment problem, and getting that pairing right is the whole job.

2. Difficulty & time

Difficulty 7 / 10. Two coupled decisions — which sites to open (a combinatorial search) and how to assign customers under capacity (a min-cost flow) — that have to be solved together. The debug surface is real: an open set with enough total capacity can still be infeasible under nearest assignment, and the cost function has two competing terms. Calibrated against the ledger (G10): a peer of transshipment (7, also min-cost flow with a modelling twist); above the difficulty-6 band (warehouse-sim, delivery-routing) and well above nearest-facility (4), which assigns to fixed facilities and never chooses which to open.

Time is separate from difficulty: Part A is about an hour; Part B is 3–4 hours. The scripts run in a few seconds (the reference brute-forces subsets).

3. What you’ll be able to do after

Solve uncapacitated facility location — search open/closed subsets and score each as build + nearest-depot transport.
Explain why greedy siting fails — “open the cheapest-to-build sites” ignores geography and costs more than the optimum.
Recognise why capacity breaks nearest-assignment — show that a popular depot overflows even when total capacity is sufficient.
Pair open-set search with a min-cost assignment — solve the capacitated transportation problem for each candidate open set and pick the best.

The finished result

By the end of Part A you’ll have brute-forced the least-cost depot network and watched it beat both obvious shortcuts — open everything, and open the cheapest-to-build sites:

open ALL 10 sites:              cost 5690   (build cost dominates)
open the single best site F08:  cost 5402   (transport dominates)
optimum: open 4 sites [F00, F04, F05, F09], cost 3551
cheapest-4-by-build [F04, F05, F09, F01]:   cost 4562   (28% over the optimum)

The winner opens a well-placed handful — neither extreme, nor the cheapest-to-build set — because siting is a joint build-vs-transport trade-off; Part B’s capacity limit then forces a fifth depot.

4. Prereqs & time box

You can write functions and loops, use numpy arrays, and read CSVs with pandas. Part B calls networkx.min_cost_flow for the assignment (the transshipment project in this batch introduces it, but this project is self-contained). The skill is modelling — the open-set search and the assignment — not implementing a solver.

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 pandas, numpy, and networkx, 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 networkx" 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: 3–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 — sites_a.csv (10 rows: site_id, x, y, fixed_open_cost) and customers_a.csv (22 rows: customer_id, x, y, demand).
Part B — sites_b.csv (adds capacity per site) and customers_b.csv.

Coordinates are projected planar km; distances are euclidean. Total customer demand is 103; total site capacity is 317, so several depots are needed and the capacity binds. The numbers describe no real company.

6. Part A — Guided Build

You’ll find the least-cost open set with no capacity limits. Run the whole thing, or (better) one # %% cell at a time — see Start Here:

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

Step 1 — The trade-off: too few vs too many.

Checkpoint: open all 10 sites → cost 5690 (build dominates); open the single best site → 5402 (transport dominates). The optimum is in between.

Step 2 — Score any open set.

Checkpoint: a plan’s cost = build cost of the open depots + each customer’s distance×demand to its nearest open one. Scoring is easy; searching is the work.

Step 3 — Brute-force the optimum.

Checkpoint: over all 2¹⁰ = 1024 subsets, the optimum opens 4 sites (F00, F04, F05, F09) at cost 3551 — far below open-all (5690) and best-single (5402).

Step 4 — Why “open the cheapest sites” misses it.

Checkpoint: the 4 cheapest-to-build sites cost 4562 — 28% over the optimum — because they ignore where the customers are. Writes part_a/facility_a.csv.

Why this and not that

Why search subsets, not pick greedily. Build cost and transport cost trade off jointly; a site cheap to build can be badly placed. Only searching combinations captures the trade-off — greedy by build cost lands 28% high here.
Why brute force is OK here. 10 sites is 1024 subsets — instant, and provably optimal. Past ~20–25 sites the subset count explodes and you need an integer program or a heuristic; the concept is the same.
Why the U-shape. Adding a depot cuts transport but adds build cost; the total falls then rises, so the answer is an interior number of depots, not an extreme.

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

Function	What it does here	Docs
`itertools.combinations`	Enumerate open/closed subsets	combinations
broadcasting for the distance matrix	Customer×site distances at once	broadcasting
`min(open, key=...)`	Nearest open depot per customer	min
`nx.min_cost_flow`	(Part B) the capacitated assignment	min_cost_flow

If something looks off

Opening more depots came out cheaper — did I make a mistake? No — that’s the whole point. The single best depot costs 5402, but the four-depot optimum costs 3551: with too few depots everyone travels far, so transport cost swamps the build cost you saved. Each depot you add raises build cost and lowers transport, and the total is U-shaped, so the cheapest plan is an interior number of depots — not the fewest. The 4-depot plan beating the 1-depot one is correct, not a bug.
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 — choose the open set — but each depot now has a capacity (sites_b.csv). Find the open set and the assignment that minimise build + transport, with no depot over capacity and every customer’s demand met. The starter reuses Part A (open the uncapacitated-best set, assign nearest) and scores 0: nearest assignment overloads the popular depots even though that set’s total capacity is enough.

The transfer: Part A’s “nearest open depot” is no longer valid — a full depot can’t take its nearest customers, so the assignment becomes a min-cost transportation problem (which depot serves which customer, and how much), and it must be solved for each candidate open set. Same open-set search, a genuinely harder assignment inside it.

Reference rule (reproduce it to match the yardstick)

Brute-force the open set: for every subset of sites whose total capacity ≥ total demand, solve the capacity-feasible min-cost assignment (a transportation problem — model it as a min-cost flow: each open depot supplies up to its capacity, each customer demands its amount, arc cost = distance, a sink absorbs unused capacity), and keep the subset with the lowest build + transport.

Acceptance criteria (checkable)

Your solution writes into part_b/out/:

assignment.csv — columns customer_id, site_id, units (how much each depot ships to each customer; a customer’s demand may be split across depots).
report.json — with keys total_cost, 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 infeasible (a customer’s demand unmet, or a depot shipping more than its capacity), otherwise reference_cost / your_cost, and you need ≥ 0.95 (the reference reaches 1.00). A depot that ships anything counts as opened (pays its build cost).

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

No depot ships more than its capacity.
Every customer’s demand is met exactly (splitting across depots is allowed).
A depot incurs its build cost if — and only if — it ships something.
Keep total cost within ~5% of the reference (the 0.95 floor).

Hints

Hint 1 — why nearest-assignment fails now

Take Part A’s best open set and count how much each depot would receive under nearest assignment. A couple of popular depots exceed their capacity — so the plan can’t run, even though the set’s total capacity covers demand. Capacity is per-depot, not a pool.

Hint 2 — the assignment is a min-cost flow

For a fixed open set, “who serves whom under capacity, at least cost” is a transportation problem. Build a graph: each open depot is a supply of its capacity, each customer a demand, an arc depot→customer with cost = distance and capacity = the customer’s demand, and a sink edge from each depot to absorb unused capacity. networkx.min_cost_flow returns the cheapest feasible assignment.

Hint 3 — search open sets, but prune

You still search subsets, but skip any whose total capacity is below total demand (infeasible), and only then run the assignment. Add each open depot’s build cost to its assignment’s transport cost and keep the minimum. With 10 sites this is fast enough to be exact.

8. Self-check

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

pytest passes — feasible (no depot over capacity, all demand met) and within 5% of the reference.
Your open set has more depots than Part A’s uncapacitated optimum (capacity forces at least one extra), and no depot is at over 100% load.
Re-running from python data/make_data.py reproduces the same numbers — the data is seeded.

And the tell-tale: your total cost should be a bit higher than Part A’s uncapacitated optimum on the same sites — capacity always costs something. If it’s equal or lower, you haven’t enforced capacity (or a depot is overloaded).

9. Stretch

Integer program. Model it as a MILP (binary open variables + continuous assignment) with pulp or scipy.optimize.milp and confirm it matches the brute force — then push past 10 sites, where brute force can’t go.
Single-sourcing. Require each customer to be served by exactly one depot (no splitting). That makes the assignment itself combinatorial — strictly harder than the min-cost flow.
(Genuinely hard) p-median / p-center. Fix the number of depots to open and minimise total distance (p-median), or minimise the worst customer’s distance (p-center), and compare the maps the three objectives produce.

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: “the least-cost network opens 5 of 10 candidate depots; a nearest-depot plan on the uncapacitated-best 4 sites is infeasible because two depots overflow — capacity turns siting into a joint open-and-assign optimisation.”
Show the map of open depots with customer assignments, and the U-shaped cost-vs-depot-count curve.
Include the min-cost-assignment model and one paragraph on why nearest-assignment breaks under capacity. That paragraph is what signals you understand facility location, not just a distance calc.

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 facility-location instance: 10 candidate sites (build cost, capacity) + 22 customers (demand), projected planar km
Type	Synthetic
Generated by	`data/make_data.py` (this repo), seed `20260758`
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 instance was generated on purpose — the facility-location techniques are the point, not a claim about any real network.

Next up

That’s the top of the Geospatial track. Browse all courses → to pick your next build.