The Facilities Location Problem

The facilities location problem (also known as the

k

-median problem), in its continuous version, starts with a shape in the plane and seeks to locate

k

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

n

points in the plane and wants to select

k

of them as hosts so as to minimize the total travel distance. When

k=1

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