Location on Networks: Theory and Algorithms

Many kinds of organizations--large and small, public and private--are faced with decisions on where to locate their facilities so that they can provide optimal utility both to those who benefit from them and to the organization itself. What are the best available sites for locating--to give just a few examples--a system of fire stations, health outreach clinics, parking garages, shopping malls, radar stations, computer centers, elementary schools, police patrol cars, switching centers, warehouses? The (spatial) location of such facilities usually takes place in the context of a given transportation, communication, or transmission system, that for analytic purposes may be represented as a network of nodes (population centers, terminals, manufacturing sites) and links (highways, railways, telephone cables) connecting pairs of nodes.This study is concerned with the analytical aspects of facility location in systems where such an underlying network structure exists. While numerous texts have been published both on network analysis and on location theory (based on Euclidean or rectangular measures, as distinct from network distance measures defined in terms of such variables as maximum response time), this text is the first book-length treatment of the intersection of the two topics. The book serves both to summarize the present range of this approach and to advance it measurably.The authors write that "The orientation of this book is toward algorithmic solutions to network location problems [which are] often formulated as discrete optimization problems. While our primary concern is with practical optimum-seeking methods, we also discuss some heuristic approaches as well as results concerning upper bounds on the computational complexity of these problems...."The prerequisites for this text would be satisfied by an introductory course in operations research with primary emphasis on optimization techniques including linear programming and complex analysis. Prior knowledge of network analysis (graph theory) is useful though not essential. (An appendix is devoted to a brief introduction to the relevant concepts of graph theory.) A basic understanding of probability theory is also needed for some of the material. We have tried to keep the level of mathematics to a minimum beyond these prerequisites. We hope that the text will be of interest to transportation systems analysts, urban and regional planners, industrial, communication, and systems engineers, and academicians and professionals in management, geography, engineering, operations research, and applied mathematics."This book is the first in the MIT Press Series in Signal Processing, Optimization, and Control, edited by Alan S. Willsky.