9464

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.

SNAPSHOTS

  • [Snapshot]
  • [Snapshot]
  • [Snapshot]

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.
    • 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 »

Files require Wolfram CDF Player or Mathematica.









 
RELATED RESOURCES
Mathematica »
The #1 tool for creating Demonstrations
and anything technical.
Wolfram|Alpha »
Explore anything with the first
computational knowledge engine.
MathWorld »
The web's most extensive
mathematics resource.
Course Assistant Apps »
An app for every course—
right in the palm of your hand.
Wolfram Blog »
Read our views on math,
science, and technology.
Computable Document Format »
The format that makes Demonstrations
(and any information) easy to share and interact with.
STEM Initiative »
Programs & resources for
educators, schools & students.
Computerbasedmath.org »
Join the initiative for modernizing
math education.
Powered by Wolfram Mathematica © 2014 Wolfram Demonstrations Project & Contributors  |  Terms of Use  |  Privacy Policy  |  RSS Give us your feedback
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to Mathematica Player 7EX
I already have Mathematica Player or Mathematica 7+