Facility Locations with the Manhattan Metric in the Presence of Barriers to Travel

Abstract

This paper considers the optimal location of p facilities in the plane, under the assumption that all travel occurs according to the Manhattan (or rectilinear or I 1 ) metric in the presence of impenetrable barriers to travel. Facility users are distributed over a finite set of demand points, with the weight of each point proportional to its demand intensity. Each demand point is assigned to the closest facility. The objective is to locate facilities so as to minimize average Manhattan travel distance to a random demand. We show that an optimal set of facility locations can be drawn from a finite set of candidate points, all of which are easy to determine.