On the accuracy of demand point solutions to the planar, manhattan metric, p-median problem, with and without barriers to travel

This paper examines the accuracy of demand point solutions to the planar, Manhattan metric, p-median problem, both with and without impenetrable barriers to travel. In the absence of barriers to travel, we show that tight worst case bounds are achieved by moving the facilities to their closest demand point. In the presence of barriers, we show that similar tight worst case bounds are achieved when the set of demand points is augmented with the set of barrier intersection candidate points. We report computational experiments for: 1. (a) random locations and random weights; 2. (b) clustered locations and spatially autocorrelated weights; and 3. (c) clustered locations and spatially autocorrelated weights with impenetrable barriers to travel. Our empirical findings are gathered from: 1. (a) census tract data from Buffalo, New York; and 2. (b) census tract data from Buffalo, with natural barriers to travel. Our conclusions show that: 1. (a) restricting facility location to demand points is an excellent approximation in the absence of barriers to travel; and 2. (b) the set of demand points should be augmented with the set of barrier intersection candidate points to preserve the overall quality of the solution in the presence of barriers to travel.