Nonlinear network location models

Author

John Norman Hooker

Date of Award

8-1984

Degree Type

Dissertation

Degree Name

Doctor of Philosophy

Major

Management Science

Major Professor

Robert S. Garfinkel

Committee Members

Jim Ho, Ken Gilbert, Bruce Ralston, Rick Rosenthal, Carl Wagner

Abstract

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.

Recommended Citation

Hooker, John Norman, "Nonlinear network location models. " PhD diss., University of Tennessee, 1984.
https://trace.tennessee.edu/utk_graddiss/12888