Fermat-Weber Problem
a basic form of minimizing a sum of distances
How do you find the single location that minimizes total travel distance to a set of given locations? That's the Fermat-Weber problem, a classic in facility location and spatial optimization. In other words: find the point minimizing the weighted sum of distances to all given points.
Math formulation:
Given points p^i, find
min ∑ w_i || x - p^i ||.
where w_i ≥ 0 are weights and the norm is the Euclidean distance.
Variations of this problem appear all over:
📦 Warehouse placement - minimize delivery distances to customers
🚑 Emergency service stations - reduce average ambulance response time
📍 Retail store location - position to maximize convenience for customers
📡 Wi-Fi router placement - maximize coverage by minimizing average signal distance
This deceptively simple problem is convex and has elegant iterative algorithms for its solution. Has this problem shown up in your work?
📚 Further Reading
- Wikipedia page:
https://en.wikipedia.org/wiki/Weber_problem
- Section 8.7 of Boyd and Vangerbhe's book "Convex Optimization":
https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
p.s. The graphic was made using a short notebook with Douglas-Rachford splitting to solve for the optimal point (pink circle). I reformulated the problem via the “consensus trick” and used the proximal operator for Euclidean norms. The motivated reader can try to derive this, and feel free to let me know if you figure it out!