🚀 Optimizing Facility Location with the Weiszfeld Method 🏭📍

Ever wondered how companies decide where to set up a new warehouse, service center, or distribution hub? The answer lies in Facility Location Optimization — a powerful problem in operations research with real-world impact.

🔍 Weiszfeld Algorithm, a classic yet elegant iterative method to find the optimal location that minimizes the weighted sum of distances to a set of demand points.

💡 Imagine multiple customer locations, each with a different demand/weight(w). The goal? Place a new facility so that the total transportation cost (weighted distance) is minimized.

✨ The Weiszfeld method works like magic:

Start with an initial guess (e.g., a centroid).
Iteratively re-calculate a weighted average, adjusting based on proximity.
Watch it converge beautifully to the optimal spot!

📈 The animated trajectory shows how the solution steps closer and closer to the best location. It’s simple, fast, and incredibly insightful for both teaching and practical use!

🔗 Whether you're in supply chain, urban planning, or logistics, this method gives you a mathematically grounded, efficient way to make smarter decisions.

In the animation, the initial guess is assumed to be (1,1).

Weiszfeld Algorithm

The Weiszfeld algorithm is an iterative method used to solve the single-facility location problem in a Euclidean space. It finds the optimal point \( x \in \mathbb{R}^2 \) that minimizes the weighted sum of distances to given demand points.

Problem Statement

Given:

Demand points \( p_1, p_2, \dots, p_n \in \mathbb{R}^d \)
Positive weights \( w_1, w_2, \dots, w_n \)

The objective is to minimize:

\[ f(x) = \sum_{i=1}^{n} w_i \cdot \| x - p_i \| \]

Weiszfeld Iteration Formula

Starting from an initial guess \( x^{(0)} \), the location is updated iteratively:

\[ x^{(k+1)} = \frac{\sum_{i=1}^{n} \frac{w_i p_i}{\|x^{(k)} - p_i\|}}{\sum_{i=1}^{n} \frac{w_i}{\|x^{(k)} - p_i\|}} \]

Notation Explanation

Where:

\( x^{(k)} \): the current estimate of the optimal location at iteration \( k \)
\( p_i \): the coordinates of the \( i \)-th demand point
\( w_i \): the weight (importance) of the \( i \)-th demand point
\( \|x^{(k)} - p_i\| \): the Euclidean distance between the current estimate and demand point \( p_i \)

Stopping Criterion

The iterations stop when:

\[ \|x^{(k+1)} - x^{(k)}\| < \varepsilon \]

Where \( \varepsilon \) is a small positive tolerance value.

Singularity Handling

If at any point \( x^{(k)} = p_i \) for some \( i \), the denominator becomes zero. In such cases, the algorithm stops and returns \( x = p_i \) as the solution.

Worked Example with 3 Demand Points

Let’s consider 3 demand points with equal weights:

Point	Coordinates	Weight
\( p_1 \)	(1, 3)	1
\( p_2 \)	(4, 4)	1
\( p_3 \)	(5, 1)	1

Step 1: Initial Guess

We start with the centroid:

\[ x^{(0)} = \frac{1}{3} \left( (1,3) + (4,4) + (5,1) \right) = \left( \frac{10}{3}, \frac{8}{3} \right) \approx (3.33, 2.67) \]

Step 2: Apply Weiszfeld Iteration

Calculate distances:

\[ \begin{align*} \|x^{(0)} - p_1\| &\approx 2.37 \\ \|x^{(0)} - p_2\| &\approx 1.49 \\ \|x^{(0)} - p_3\| &\approx 2.36 \\ \end{align*} \]

Apply the Weiszfeld formula:

\[ x^{(1)} = \frac{ \frac{(1,3)}{2.37} + \frac{(4,4)}{1.49} + \frac{(5,1)}{2.36} }{ \frac{1}{2.37} + \frac{1}{1.49} + \frac{1}{2.36} } \approx (3.44, 2.88) \]

Step 3: Iterate

Repeat the computation using the new point until the change in \( x^{(k)} \) is less than the chosen tolerance \( \varepsilon \).

Intuition

The algorithm computes a weighted average of the demand points, where closer and more heavily weighted points exert stronger influence. This leads to a balance point minimizing total travel cost.

Applications

Facility location planning (e.g., warehouses, hospitals, service centers)
Clustering and data science (approximating centroids)
Operations research and logistics

Python Code