Nonlinear network location models

Network location models can help identify minimal-cost locations for one or more facilities on a transport or communications network. Cost is a function of distance between facilities and demand points and may be reckoned as dollar cost, average or worst-case travel time, loss in patronage, social inequity or a variety of other measures of dis-utility. Techniques for finding least-cost solutions have been devised for only linear and a few other cost functions. The main object of this study is to describe a unified approach to solving such problems for a broad class of cost functions, particularly the nonlinear functions characteristic of public-sector location problems. It presents a reasonably efficient, computer-implemented algorithm for solving any single-facility problem in which cost is a convex function of distances, and a second algorithm for solving any small multiple-facility problem in which the cost function is convex and each demand point is served by a closest facility. Both algorithms accommodate a wide variety of side constraints. Numerous applications, especially in connection with social welfare problems, are discussed.

Another object of this study is to explore the metrical structure of networks. Such an exploration is the natural result of the fact that general nonlinear problems, unlike most network location problems hither to investigated, must be solved "on the network." Networks, conceived as metrical structures rather than the discrete objects of graph theory, are abstracted as "graphic spaces," a type of metric space. A graphic space is shown to preserve the essential property of networks that permits solution of nonlinear location problems, their decomposability into treelike pieces on which the metric is convex. The fact that a network is a tree if and only if it has a convex metric is generalized to graphic spaces. The algorithm for solving single-facility problems on networks is similarly generalized.