Supply chain design is one of the richest applications of mathematical optimization. A classic — and notoriously challenging — problem is deciding where to open facilities (warehouses, distribution centers) and how to route goods from those facilities to customers, all at the same time. This is known as the Capacitated Facility Location Problem (CFLP) with transportation planning, and it belongs to the NP-hard family of combinatorial optimization problems.
Problem Formulation
Let’s define the problem precisely.
Sets:
- $I$ = set of candidate facility sites ${1, \dots, m}$
- $J$ = set of customer locations ${1, \dots, n}$
Parameters:
- $f_i$ = fixed opening cost of facility $i$
- $c_{ij}$ = unit transportation cost from facility $i$ to customer $j$
- $d_j$ = demand of customer $j$
- $s_i$ = capacity of facility $i$
Decision Variables:
- $y_i \in {0, 1}$ — 1 if facility $i$ is opened, 0 otherwise
- $x_{ij} \geq 0$ — amount shipped from facility $i$ to customer $j$
Objective (minimize total cost):
$$\min \sum_{i \in I} f_i y_i + \sum_{i \in I} \sum_{j \in J} c_{ij} x_{ij}$$
Subject to:
Demand fulfillment for each customer:
$$\sum_{i \in I} x_{ij} = d_j \quad \forall j \in J$$
Capacity constraint per facility:
$$\sum_{j \in J} x_{ij} \leq s_i y_i \quad \forall i \in I$$
Logical constraint (ship only from open facilities):
$$x_{ij} \geq 0, \quad y_i \in {0, 1}$$
This is a Mixed Integer Linear Program (MILP). We solve it with PuLP (CBC solver), then visualize the result in 2D and 3D.
Concrete Example
We set up a realistic scenario:
- 5 candidate facility sites scattered across a region
- 12 customers with varying demand levels
- Each facility has a different fixed opening cost and capacity
- Transportation cost is proportional to Euclidean distance × a cost-per-unit factor
Source Code
1 | # ============================================================= |
Code Walkthrough
Section 0 — Dependency
Only PuLP needs to be installed. numpy and matplotlib are pre-installed in Colab. The !pip install pulp --quiet line at the top handles this automatically.
Section 1 — Problem Data
We place 5 facilities and 12 customers on a $[0,10]^2$ map. Each facility has a fixed_cost (paid once if opened) and a capacity ceiling. Each customer has a demand that must be fully satisfied.
The transport cost matrix $c_{ij}$ is computed as:
$$c_{ij} = r \cdot |p_i^{fac} - p_j^{cus}|_2$$
where $r = 10$ is the cost rate per unit per distance unit.
Section 2 — MILP Model
PuLP builds the model symbolically. Binary variables $y_i$ encode open/close decisions; continuous variables $x_{ij}$ encode shipment flows. The lpSum calls translate directly to the mathematical formulation above. The solver is CBC (bundled with PuLP — no external solver needed).
Section 3 — Result Extraction
After solving, we read back variable values with pulp.value(). The argmax trick identifies each customer’s primary serving facility cleanly even when demand is split across multiple facilities.
Section 4 — Visualizations
Figure 1 — Network Map: Bezier-curved arcs represent flows (thicker = larger shipment). Open facilities are shown as stars ★, closed facilities as ✗. Customer dot size scales with demand; dot color matches the serving facility.
Figure 2 — Cost & Utilization: Left panel is a stacked bar (fixed cost base + transport cost overlay) per facility. Right panel is a horizontal bar showing utilization as a percentage of capacity — any bar exceeding 100% would indicate a violated constraint (none should).
Figure 3 — 3-D Analysis (two panels):
Left: A sensitivity sweep over transport cost rate $r \in [2, 20]$. The MILP is re-solved 15 times. The 3-D scatter reveals how the number of open facilities and total cost respond to changing logistics economics. At low cost rates, fewer (larger) facilities are preferred; at high rates, the optimizer opens more facilities to reduce distance.
Right: A 3-D bar chart of the flow matrix $x_{ij}$. Each bar’s height is the volume shipped from facility $i$ to customer $j$. This immediately shows the concentration of supply chains.
Figure 4 — Customer Analysis: Bars show each customer’s actual transport bill; the overlaid scatter shows their demand. Color ties each customer to its serving facility, making service territories visually obvious.
Execution Results
Status : Optimal Total cost : $9,518.1 ── Facility decisions ────────────────────────────────── F0: OPEN load=95/250 F1: OPEN load=75/200 F2: OPEN load=135/300 F3: OPEN load=35/220 F4: OPEN load=65/280 Fixed cost : $2,000 Transport cost : $7,518 Total cost : $9,518
▶ Figure 1 displayed
▶ Figure 2 displayed
▶ Figure 3 displayed
▶ Figure 4 displayed
Key Insights
The sensitivity analysis in Figure 3 is particularly revealing. At a low transport cost rate, the optimizer is happy to consolidate supply through fewer facilities — paying high transport costs is cheap anyway, so it avoids multiple fixed opening fees. As the transport rate rises, the penalty for long hauls grows, and the solver shifts strategy: open more facilities, place them closer to clusters of demand, and trade fixed costs for transport savings. This crossover behavior is the heart of the simultaneous optimization — you cannot find the right network design without solving both decisions together.
