Technical Note—Algorithms for Weber Facility Location in the Presence of Forbidden Regions and/or Barriers to Travel

We describe algorithms for optimal single facility location problems with forbidden regions and barriers to travel. The former are those where location is not permitted, but one can travel through them, e.g., a lake. The latter are the regions where neither location nor travel is permitted, e.g., large parks in a city. Using the convexity properties of the objective function, in the first case, we develop an algorithm for finding the optimal solution. The objective function in the barrier case is shown to be non-convex. We use the concept of visibility to create a network with the location point as the source and use Dijkstra's algorithm to compute the shortest distance to all the other demand points. Using simulated annealing we find an approximate optimal solution. Numerical examples illustrate the implementation of the algorithms.