10182

# The Facilities Location Problem

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.

### 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.

### PERMANENT CITATION

 Share: Embed Interactive Demonstration New! Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site. More details » Download Demonstration as CDF » Download Author Code »(preview ») Files require Wolfram CDF Player or Mathematica.

#### Related Topics

 RELATED RESOURCES
 The #1 tool for creating Demonstrations and anything technical. Explore anything with the first computational knowledge engine. The web's most extensive mathematics resource. An app for every course—right in the palm of your hand. Read our views on math,science, and technology. The format that makes Demonstrations (and any information) easy to share and interact with. Programs & resources for educators, schools & students. Join the initiative for modernizing math education. Walk through homework problems one step at a time, with hints to help along the way. Unlimited random practice problems and answers with built-in Step-by-step solutions. Practice online or make a printable study sheet. Knowledge-based programming for everyone.