Integrated models of facility location and network design.

摘要

Network location models have been extensively used for siting public and private facilities. In this dissertation, we present models to simultaneously optimize facility locations and the design of the underlying network. Motivated by the simple observation that changing the network topology is often more cost-effective than adding facilities to improve service levels, these models have a vast array of applications in regional planning, distribution, material handling, telecommunications, and other areas. The models in effect merge the heretofore separate areas of facility location and network design. We generalize three classical location models to determine their network topology endogenously: the uncapacitated fixed charge location problem (UFLP), the maximum covering model (MCLP), and the capacitated fixed charge location problem (CFLP). Both optimal and heuristic techniques for solving the problems are discussed. The exact procedure is based on a cutting-plane methodology that enables us to efficiently solve large-scale problem instances. We illustrate the benefit or impact of the models using simple examples as well as real-life data. These analyses help identify the tradeoffs between facility location and link construction decisions. We derive a number of fundamental properties of the models. These properties characterize the structure of optimal solutions. Although the problems are NP-hard in general, we identify a few special cases that are solvable in polynomial time and give appropriate algorithms in each instance. We conclude by identifying promising research directions.