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 w ith forbidden regions and barriers to travel. The former are those whe re 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 propertie s of the objective function, in the first case, we develop an algorith m for finding the optimal solution. The objective function in the barr ier case is shown to be non-convex. We use the concept of visibility t o create a network with the location point as the source and use Dijks tra's algorithm to compute the shortest distance to all the other dema nd points. Using simulated annealing we find an approximate optimal so lution. Numerical examples illustrate the implementation of the algori thms.