The Facilities Location Problem

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram CDF Player or other Wolfram Language products.

Requires a Wolfram Notebook System

Edit on desktop, mobile and cloud with any Wolfram Language product.

The facilities location problem (also known as the -median problem), in its continuous version, starts with a shape in the plane and seeks to locate hosts so as to minimize the average travel distance if each point goes to the nearest host. This is more familiar in the discrete version, where one has points in the plane and wants to select of them as hosts so as to minimize the total travel distance. When , this is known as the Fermat–Weber problem. In this Demonstration, a discrete version based on a number of points inside the polygon is solved by integer-linear programming (ILP) and the Voronoi diagram of the computed hosts is shown. Such a discrete problem is an approximation to the continuous problem.

Contributed by: Tim Neuman and Stan Wagon (February 2013)
(Macalester College)
Open content licensed under CC BY-NC-SA


Snapshots


Details

The distance function used here is planar distance, and motion from a point to the host is straight-line motion, not the shortest path inside the polygon. This distinction is relevant only for nonconvex polygons, and can lead to disconnected Voronoi regions, as in the second snapshot. For the continuous version of the problem for the square, it is not known what the optimal solution is, even when is, say, 7. Using ILP, as done here, and perhaps following up the computation with some local optimization, allows one to investigate possible solutions. But the big picture is known in that, under certain conditions, the optimal solution consists almost entirely of regular hexagons, as discussed in [2]. That paper also shows that the general problem is NP-complete. For more information on the continuous version, see [1].

To set up the problem as an ILP, variables and are introduced, where all subscripts run from 1 to and are the given points. The idea is that a value of 1 indicates that is a host, and an value of 1 indicates that is the nearest host to . The objective function is , where gives the distance from to . The constraints are:

• all variables are integers;

, ;

;

for each pair , ;

, for each .

The last constraint ensures that each point goes to one host; the next-to-last constraint ensures that a point goes to a host iff the value for that host-point gets a value of 1. Thus the use of ≤ in the sum constraint is a convenience; the travel distance always decreases, so the sum will in fact be exactly .

References

[1] S. P. Fekete, J. S. B. Mitchell, and K. Beurer, "On the Continuous Fermat–Weber Problem," Operations Research, 53(1), 2005 pp. 61–76. doi:10.1287/opre.1040.0137.

[2] C. H. Papadimitriou, "Worst-Case and Probabilistic Analysis of a Geometric Location Problem," SIAM Journal of Computing, 10(3), 1981 pp. 542–557. doi:10.1137/0210040.



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.
Send