Minimizing Total Distance Cost
The Business Problem
Imagine a logistics company that needs to build exactly two distribution warehouses to serve a scattered network of retail stores or customers. Each customer has a different demand volume (some order a lot, some order a little), and the company wants to minimize total transportation cost — defined as the sum of each customer’s shipping distance multiplied by their demand weight, always shipping from whichever of the two warehouses is closer.
This is a classic problem in operations research known as the multi-source Weber problem, and it sits at the intersection of continuous optimization (where exactly should the warehouses sit?) and combinatorial optimization (which customers get served by which warehouse?).
Mathematical Formulation
Given $n$ customer locations $\mathbf{p}_i \in \mathbb{R}^2$ with demand weights $w_i$, and two facility locations $\mathbf{f}_1, \mathbf{f}_2 \in \mathbb{R}^2$, we want to solve:
where $c_i \in {1, 2}$ denotes which facility serves customer $i$. In practice, once the facility locations are fixed, the optimal assignment is trivial — each customer simply goes to the nearer facility:
$$
c_i = \arg\min_{k \in {1,2}} \left| \mathbf{p}_i - \mathbf{f}_k \right|_2
$$
The hard part is finding the facility positions themselves. For a single facility, the optimal point minimizing the weighted sum of Euclidean distances is called the weighted geometric median, and it’s found using Weiszfeld’s algorithm, an iterative fixed-point method:
For two facilities, we combine this with an alternating scheme very similar to k-means clustering:
- Assign every customer to its nearest facility.
- Re-optimize each facility’s position using Weiszfeld’s algorithm on its assigned customers.
- Repeat until the facility positions stop moving.
Because this alternating scheme can get stuck in a local optimum (just like k-means), we run it from many random starting positions and keep the best result found.
Full Python Implementation
1 | # ============================================================== |
Console Output
Best total cost found: 168.4827 Facility 1 location: (8.978, 6.448) Facility 2 location: (3.346, 6.470)
Code Walkthrough
Problem data. Twelve customer locations are defined as (x, y) coordinates in kilometers, each paired with a demand weight representing daily shipment volume. In a real deployment these would come from a sales database or GIS system.
total_cost: computes the objective function directly from its mathematical definition. It calculates the distance from every customer to every facility in one vectorized NumPy operation (no Python-level loop), takes the minimum distance per customer (i.e., “ships from whichever warehouse is closer”), and returns the weighted sum.
assign_customers: the combinatorial half of the problem — given fixed facility positions, it returns which facility (0 or 1) is closest to each customer.
weiszfeld_update: the continuous half of the problem. This implements the Weiszfeld fixed-point iteration shown in the formula above. A small eps floor is added to the distance to avoid division by zero if a facility ever lands exactly on a customer’s coordinates.
two_facility_location: the outer loop that alternates between assignment and position updates, very similar in spirit to Lloyd’s algorithm for k-means, except each “centroid” is a weighted geometric median rather than a simple average — appropriate because we’re minimizing straight-line distance, not squared distance.
Multi-start loop: since alternating optimization can converge to different local optima depending on where it starts, the script runs the whole procedure 30 times from random initial facility positions and keeps whichever run achieved the lowest total cost. This is a standard and inexpensive way to guard against poor local optima in this class of problem.
Speed Notes
The 3D cost-landscape plot in principle requires evaluating the objective function at every point on an 80×80 grid — 6,400 evaluations. A naive implementation would use two nested Python for loops, which is slow. The code above avoids this entirely by reshaping the grid into a single array of (x, y) points and computing all customer-to-grid-point distances in one broadcasted NumPy operation, then taking element-wise minimums against the fixed second facility. This turns a 6,400-iteration Python loop into a handful of vectorized array operations, so the surface renders almost instantly even on a standard Colab CPU runtime.
Understanding the Visualizations
Figure 1 — Customer Assignment & Optimization Path. This 2D map shows all twelve customers, sized in proportion to their demand weight, colored according to which of the two final warehouses serves them. The two stars mark the optimal facility positions, the gray X marks show where that particular optimization run started, and the dashed lines trace how each facility “walked” from its random starting point to its final resting place across iterations. Notice how the facilities settle roughly in the geometric weighted center of their respective clusters, rather than at the simple average — larger demand customers pull the facility more strongly toward them.
Figure 2 — 3D Cost Landscape. This surface shows how the total cost changes as Facility 1 is moved anywhere on the map, while Facility 2 stays fixed at its optimal location. The valley (lowest point, marked with a cyan star) corresponds to the optimal position found by the algorithm. This plot is useful for building intuition: the cost surface is not smooth like a simple bowl — it has a somewhat faceted, ridge-like shape because of the “assign to nearest facility” logic switching abruptly between the two warehouses as Facility 1 moves across customer territory.
Figure 3 — Convergence Across Random Starts. Each gray line is one of the 30 independent optimization runs, showing how quickly its total cost drops as the alternating algorithm iterates. The green line highlights the best-performing run — the one whose final result is reported and drawn in Figures 1 and 2. Most runs converge within just a handful of iterations, and the spread between lines illustrates why multiple random starts matter: a few runs stall at a noticeably higher cost, meaning they got trapped in a local optimum that a single-start approach could easily have missed.
Takeaways
The two-facility location problem is a compact but genuinely useful example of combining discrete decisions (which warehouse serves which customer) with continuous optimization (where exactly to place each warehouse). The alternating Weiszfeld approach used here generalizes cleanly to three, four, or more facilities simply by expanding the facility array — making it a practical starting point for real supply-chain network design problems.
