Locating Facilities on the Manhattan Metric with Arbitrarily Shaped Barriers and Convex Forbidden Regions

This paper considers two planar facility location problems while employing the Manhattan travel metric, and establishes that the search for an optimal solution can be restricted to a finite set of easily identifiable points.

Abstract

This paper considers two planar facility location problems while employing the Manhattan travel metric. We first consider the p-median problem in the presence of arbitrarily shaped barriers and convex forbidden regions. For this problem we establish that the search for an optimal solution can be restricted to a finite set of easily identifiable points. Next, we consider the stochastic queue median problem in the presence of arbitrarily shaped barriers. A procedure to obtain a global optimum solution for this problem is established. The results of the paper are illustrated via numerical examples. Finally, we comment on a connection between network location problems and planar location problems which use the Manhattan travel metric.