Using Block Norms for Location Modeling

In formulating a continuous location model with facilities represented as points in R n (e.g., typically in the plane), one must characterize the distance between two points as a function of their coordinates. Two criteria in selecting a distance function are (1) to obtain good approximations of actual distances, and (2) to obtain a mathematical model of the location problem that is easy to solve. In this paper, we show how a class of norms with polygonal contours, called block norms, can yield attractive choices as distance functions with respect to these criteria. In particular, we consider the following relevant properties of block norms: they generalize the concepts of rectilinear or city-block travel; they are dense in the set of all norms; they have interesting travel interpretations; in the plane, they can be expressed as a sum of the absolute values of linear functions; they often give better approximations to actual highway distances than the most frequently used family of norms, the l p norms; and, finally, they yield linear programming formulations of certain facility location problems (i.e., the Weber problem and the Rawls problem).