127,99 €
Mehr erfahren.
- Herausgeber: John Wiley & Sons
- Kategorie: Fachliteratur
- Sprache: Englisch
Praise for the First Edition This book is refreshing to read since it takes an important topic... and presents it in a clear and concise manner by using examples that include visual presentations of the problem, solution methods, and results along with an explanation of the mathematical and procedural steps required to model the problem and work through to a solution." --Journal of Classification Thoroughly updated and revised, Network and Discrete Location: Models, Algorithms, and Applications, Second Edition remains the go-to guide on facility location modeling. The book offers a unique introduction to methodological tools for solving location models and provides insight into when each approach is useful and what information can be obtained. The Second Edition focuses on real-world extensions of the basic models used in locating facilities, including production and distribution systems, location-inventory models, and defender-interdictor problems. A unique taxonomy of location problems and models is also presented. Featuring examples using the author's own software--SITATION, MOD-DIST, and MENU-OKF--as well as Microsoft Office® Excel®, the book provides: * A theoretical and applied perspective on location models and algorithms * An intuitive presentation of the uses and limits of modeling techniques * An introduction to integrated location-inventory modeling and defender-interdictor models for the design of reliable facility location systems * A full range of exercises to equip readers with an understanding of the basic facility location model types Network and Discrete Location: Models, Algorithms, and Applications, Second Edition is an essential resource for practitioners in applied and discrete mathematics, operations research, industrial engineering, and quantitative geography. The book is also a useful textbook for upper-level undergraduate, graduate, and MBA courses.
Sie lesen das E-Book in den Legimi-Apps auf:
Seitenzahl: 758
Veröffentlichungsjahr: 2013
Ähnliche
Contents
Cover
Title Page
Copyright
Dedication
Preface to the First and Second Editions
Acknowledgments
Chapter 1: Introduction to Location Theory and Models
1.1 Introduction
1.2 Key Questions Addressed by Location Models
1.3 Example Problem Descriptions
1.4 Key Dimensions of Location Problems and Models
1.5 A Taxonomy of Location Models
1.6 Summary
Exercises
Chapter 2: Review of Linear Programming
2.1 Introduction
2.2 The Canonical form of a Linear Programming Problem
2.3 Constructing the Dual of an LP Problem
2.4 Complementary Slackness and the Relationships between the Primal and the Dual Linear Programming Problems
2.5 Solving a Linear Programming Problem in Excel
2.6 The Transportation Problem
2.7 The Shortest Path Problem
2.8 The Out-of-Kilter Flow Algorithm
2.9 Integer Programming Problems
2.10 Summary
Exercises
Chapter 3: An Overview of Complexity Analysis
3.1 Introduction
3.2 Basic Concepts and Notation
3.3 Example Computation of An Algorithm's Complexity
3.4 The Classes P and NP (and NP-Hard and NP-Complete)
3.5 Summary
Exercises
Chapter 4: Covering Problems
4.1 Introduction and the Notion of Coverage
4.2 The Set Covering Model
4.3 Applications of the Set Covering Model
4.4 Variants of the Set Covering Location Model
4.5 The Maximum Covering Location Model
4.6 An Interesting Model Property or it Ain't Necessarily So
4.7 The Maximum Expected Covering Location Model
4.8 Summary
Exercises
Chapter 5: Center Problems
5.1 Introduction
5.2 Vertex P-Center Formulation
5.3 The Absolute 1- and 2-Center Problems on a Tree
5.4 The Unweighted Vertex P-Center Problem on a General Graph
5.5 The Unweighted Absolute P-Center Problem on a General Graph
5.6 Summary
Exercises
Chapter 6: Median Problems
6.1 Introduction
6.2 Formulation and Properties
6.3 1-Median Problem on a Tree
6.4 Heuristic Algorithms for the P-median Problem
6.5 An Optimization-Based Lagrangian Algorithm for the P-median Problem
6.6 Computational Results using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm
6.7 Another Interesting Property or it Still Ain't Necessarily So
6.8 Summary
Exercises
Chapter 7: Fixed Charge Facility Location Problems
7.1 Introduction
7.2 Uncapacitated Fixed Charge Facility Location Problems
7.3 Capacitated Fixed Charge Facility Location Problems
7.4 Summary
Exercises
Chapter 8: Extensions of Location Models
8.1 Introduction
8.2 Multiobjective Problems
8.3 Hierarchical Facility Location Models
8.4 Models of Interacting Facilities
8.5 Multiproduct Flows and Production/Distribution Systems
8.6 Location/Routing Problems
8.7 HUB Location Problems
8.8 Dispersion Models and Models for the Location of Undesirable Facilities
8.9 An Integrated Location-Inventory Model
8.10 Reliability and Facility Location Modeling
8.11 Summary
Exercises
Chapter 9: Location Modeling in Perspective
9.1 Introduction
9.2 The Planning Process for Facility Location
9.3 Summary
Exercises
References
Index
Copyright © 2013 by John Wiley & Sons, Inc. All rights reserved
Published by John Wiley & Sons, Inc., Hoboken, New Jersey
Published simultaneously in Canada
No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750–8400, fax (978) 750–4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748–6011, fax (201) 748–6008, or online at http://www.wiley.com/go/permission.
Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.
For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762–2974, outside the United States at (317) 572–3993 or fax (317) 572–4002.
Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.
Library of Congress Cataloging-in-Publication Data:
Daskin, Mark S., 1952-
Network and discrete location : models, algorithms, and applications / Mark S. Daskin, Department of Industrial and Operations Engineering, University of Michigan, Ann Arbor, MI. – Second edition.
pages cm
Includes bibliographical references and index.
ISBN 978-0-470-90536-4 (cloth)
1. Industrial location–Mathematical models. I. Title.
T57.6.D373 2013
658.2′101156–dc23
2013002857
ISBN: 9780470905364
To
The absolute centers of my life
Preface to the First and Second Editions
Importance of Location Modeling
Almost every private and public sector enterprise that we can think of has been faced with the problem of locating facilities at one time or another in its history. Industrial firms must determine locations for fabrication and assembly plants as well as warehouses. Retail outlets must locate stores. Government agencies must locate offices and other public services including schools, hospitals, fire stations, ambulance bases, vehicle inspection stations, and landfills.
In every case, the ability of a firm to produce and market its products effectively or of an agency to deliver high-quality services is dependent in part on the location of the firm's or agency's facilities in relation to other facilities and to its customers. The focus of this book is on the development and solution of mathematical facility location models that can assist public and private sector decision makers.
Since the publication of the first edition of the text, we have witnessed three key changes in the location arena. First, we have seen the explosion of online services and retailers. During the recent holiday season, my immediate family probably spent more money online for gifts than we did at traditional brick-and-mortar stores. That said, any online company—be it Amazon.com, a photo retail outlet such as B&H Photo (bhphotovideo.com), a photo processor such as Adoramapix.com, or a retailer such as Macy's (macys.com)—must be concerned about where it processes and fulfills orders. Amazon must determine how many fulfillment centers it should maintain and where they should be. (As of the time of this writing, they have 10 such centers in the United States in the following states: Arizona, Delaware, Indiana, Kansas, Kentucky, Nevada, Pennsylvania, South Carolina, Tennessee, and Virginia.)1 The models that were relevant in the pre-Internet age are still relevant. In fact, the proliferation of wireless technologies has increased the need for careful location analysis for such devices as cell phone towers and wireless meter readers (Gavirneni, Clark, and Pataki, 2004).
At the same time, many brick and mortar facilities are entering new services. Walgreen's pharmacies, for example, now incorporate mini-clinics in many of its stores and offers flu shots at even more locations. Thus, the need for careful market and location analysis persists after, and may be heightened by, the emergence of the Internet age.
The second major development in the location world that has occurred since the publication of the first edition has been the explosion of interest in reliable and resilient facilities. This work has been motivated by some of the major natural disasters that have impacted various parts of the world (e.g., Hurricane Katrina and, more recently, Hurricane Sandy) and the terrorist attacks on the United States on September 11, 2001. This has spawned a new area of facility location modeling that is now described in Section 8.10.
The third major development in the location world has been the integration of more operational decisions into strategic location models. For example, numerous models have been proposed that integrate inventory management decisions into strategic facility location models. These new models are often nonlinear models and, as such, require new solution techniques. Section 8.9 addresses integrated location/inventory models.
Goals of the Text
This text attempts to realize a number of goals. First, the book attempts to introduce the reader to a number of classical facility location models on which other more complicated and realistic models are based. Second, the book tries to assist the reader in developing his or her own modeling skills. Toward that end, many of the exercises at the end of the chapters ask the reader to formulate problems or to extend traditional formulations. Third, the text introduces the reader to a number of key methodologies that are used in solving facility location problems and the related problem of allocating demands to facilities. These methodologies include: linear programming, selected graph-theoretic algorithms, heuristic algorithms, Lagrangian relaxation, branch and bound, dual ascent algorithms, and Bender's decomposition. When it comes to methodologies, the goal is to teach the reader how the basic approach works, when it is useful, what information is provided by the approach, and how good the results are likely to be when the approach is employed. It is my hope that the modeling and methodological skills that the reader develops in the course of using this text will be transferable to problem contexts above and beyond those that arise in locating facilities. Fourth, the text attempts to introduce students to selected applications both through the text itself and through the exercises at the end of the chapters. Finally, the online appendix for the book provides students with software capable of solving most of the basic location problems on moderate-sized networks.
Required Background
The background required for most of this book is quite minimal. Students should be familiar with elementary notions of linear algebra including the use of summation signs, subscripted variables, and other basic notation. In addition, some exposure to linear programming is desirable though not absolutely necessary as Chapter 2 reviews the essential concepts of linear programming that are used later in the text. The software included in the online appendix to the text runs on Windows machines only and users should be familiar with the basics of such machines.
Outline of the Text
Chapter 1 introduces the reader to facility location problems. A taxonomy of facility location problems and models is presented. Using this taxonomy, we distinguish between problems and models that are covered in the text and those that are outside the scope of the book. Specifically, within the broad family of facility location models, the text addresses problems that can be posed as network or discrete location problems. In fact, many real-world problems are of this sort. Specifically, decision makers must select sites from some finite set of candidate locations (as in discrete location problems) or they must locate facilities on a network (e.g., a highway network). Problems in which facilities can be located anywhere on the plane are outside the scope of the text. A new taxonomy of location models has been added in the Second Edition of the text.
Virtually all of the problems addressed in the text are formulated as integer linear programming problems. As such, linear programming is a key methodological tool used in solving the problems of interest. In addition, specialized linear programming problems are needed to obtain inputs to location problems or to solve allocation problems that arise once facility locations are known. For example, the shortest path distances between candidate locations and customers or demands are needed as inputs into many location models. Also, once facility locations are known, a special linear programming model known as the transportation problem is often used to assign customers to facilities. Chapter 2 provides an overview of linear programming in general. It also covers shortest path problems, the transportation problem, and the out-of-kilter flow algorithm—a general-purpose algorithm for solving linear programming problems with network structure. In the Second Edition, sections have been added discussing the solution of linear programming problems in Excel® and using AMPL® (Fourer, Gay, and Kernighan, 1993). The Second Edition also includes a brief outline of branch and bound, a technique used to solve integer linear programming problems.
Chapter 3 introduces the reader to complexity theory. Using concepts presented in this chapter, we can distinguish between problems that can be optimally solved in an efficient manner and those for which no efficient, provably optimal, algorithm exists. For those problems for which an efficient, provably optimal, algorithm does not exist—and this includes most of the problems of interest in network and discrete location modeling—we are justified in using a heuristic or approximate algorithm. In addition, using notions introduced in this chapter, we can discuss the (worst case) running time of algorithms in a manner that is (with the exception of parallel processor machines) independent of the computer on which the algorithms are executed.
Chapters 4 through 7 introduce four classical facility location problems: covering, center, median, and fixed charge location problems. In many cases, the quality of service depends on whether or not the nearest facility is within some distance or time standard of the customer requesting the service. For example, one well-known pizza firm promises to deliver a pizza within 30 minutes. To realize this sort of promise, the firm must be sure that it has enough stores to reach all customers within 30 minutes. Many express delivery services have similar service guarantees for either pickups or deliveries. Many emergency medical services must serve a given fraction of the calls within a specified time (Swor and Cone, 2002). This leads to the notion of facilities being able to cover demands. Chapter 4 presents location covering models. The chapter begins with the set covering model that finds the locations of the minimum number of facilities needed to ensure a given level of service. Often this number is excessively large. This leads to the maximum covering location model that finds the locations of a given number of facilities to maximize the number of demands that can be served within the service standard. When we cannot serve all customers within the service standard with a reasonable number of facilities, another alternative is to relax the service standard. Center problems find the locations of a given number of facilities so that all customers are served within as tight a service standard as possible. In other words, they find the most stringent service standard that allows all customers to be served using a given number of facilities. Chapter 5 deals with center problems.
Covering and center problems focus on the worst-case service. In many contexts, it is also important to examine the average service time or distance. The operating costs of many systems are strongly influenced by the average distance between facilities and customers. For example, in delivery systems, the trucking costs increase with the number of vehicle miles that must be traversed. Median problems, which are the focus of Chapter 6, find the locations of a given number of facilities to minimize the average distance between customers and the nearest facility.
When the number of facilities is an input to the model, we are implicitly assuming that the cost of locating at each of the candidate sites is approximately equal.2 In that case, the number of facilities is a good proxy for the facility location costs. In many situations, however, the location costs may differ significantly across the candidate locations. In such cases, we will want to minimize both the operating costs (as is done using median models) and the fixed facility location costs. Chapter 7 deals with fixed charge location problems. These models generalize many of the earlier models. In addition, Chapter 7 introduces models in which facilities can serve only a limited number of demands.
Chapter 8 introduces a number of extensions to the basic models discussed in Chapters 4 through 7. Facility location problems are inherently strategic in nature. As such, multiple objectives must be considered in location analyses. Therefore, Chapter 8 begins with a discussion of multiobjective problems. In many cases, the facilities being located interact with each other. This leads to a discussion of hierarchical facility location models and, more generally, of models of interacting facilities. Problems with multiple products represent an important class of facility location problems. Within this class, production and distribution problems are of considerable importance. Such problems are covered in Section 8.5. Distribution of goods often occurs using routes with multiple customers. Chapter 8 also introduces location/routing models. In other cases, logistics systems operate using a hub-and-spoke system. The networks associated with many airlines also exhibit this fundamental structure. Hub location models are also discussed in this chapter. Dispersion models and location models for obnoxious facilities are also covered in Chapter 8. Such models are useful in cases in which the facilities being located pose a risk of physical, economic, or psychological harm to either people or other facilities. Specifically, dispersion models might be used in locating missile silos or franchise stores (which should be located to minimize the degree of competition between stores of the same franchise), while obnoxious facility location models could be used to site landfills, hazardous waster repositories, or nuclear power plants. In all such cases, one objective is to maximize distances rather than to minimize distances. As noted above, there has been a significant increase in the development of integrated location/inventory models. The basics of these models are covered in Section 8.9. Finally, there has been an explosive growth in the modeling of reliable systems, or systems that can perform well when parts of the system have been destroyed by either natural or man-made disasters. Section 8.10 covers such models.
As important as mathematical models are in assisting decision makers in locating facilities, they are only one part of a broader planning process. Chapter 9 presents one paradigm of the overall planning process that includes four major steps: (i) problem definition, (ii) analysis,(iii) communication and decision, and (iv) implementation.
Finally, the online appendix includes several software packages that can be used for location and related modeling. SITATION is a menu-based system that solves many of the basic problems discussed in the text. This program has been significantly rewritten since the first edition. It now includes embeds Lagrangian relaxation in a branch-and-bound algorithm for many of the models. It is also now a Windows-based program. The appendix also includes MENU-OKF that can be used to solve network flow problems and a number of data sets and spreadsheets discussed in the text.
Notes
1. See http://www.amazon.com/Locations-Careers/b?ie=UTF8&node=239366011 (accessed at 11:52 am on January 3, 2013).
2. In public sector problems, we often take the number of facilities as given since the costs associated with locating and operating the facilities are frequently borne by one group while another group frequently derives the benefits from the facilities being located. In these cases, combining the costs and benefits into one performance measure may be inappropriate; it may be preferable to solve the problem using a range of values for the number of facilities to locate.
Acknowledgments
No project of this magnitude could be accomplished without the help, support, and encouragement of many other individuals. I am indebted to many people including:
My parents who have always been there when I needed them and who tried, over the years, to instill within me a love of mathematics, science, and engineering. May their memories be for a blessing.My brother who has so often helped me maintain a sense of humor by reminding me not to take myself too seriously.Richard de Neufville who introduced me to systems analysis and optimization and who later suffered as my dissertation advisor. He also was the first to introduce me to location analysis.David Marks from whom I took my first graduate course on optimization and who is responsible, in many ways, for my having majored in civil engineering.Amedeo Odoni who has been an important professional mentor for the last 35 years.David Eaton with whom I worked on my first applied location problem and from whom I learned much of what I know about real problems.Maria Paola Scaparra from whom I learned much of what I know about defender-interdictor problems.Joe Schofer and Frank Koppelman for their many years of guidance and support. Special thanks are due to Joe for his advice on parts of Chapter 9.Karen Donohue, Yinyi Xie, Susan Lash, and Dawn Barnes-Shuster who served as teaching assistants in IE C28, the course at Northwestern University that motivated this project.The many students of IE C28 whose questions, comments, and ideas helped clarify my own thinking on numerous occasions.Art Hurter, Wally Hopp, and Phil Jones for their encouragement during the course of this project. Special thanks are due to Wally for having read early versions of the book as carefully as he did.John Ivan, Rapee Vattanakul, Mirali Sharifi-Takieh, and Chandra Bhat for their detailed comments on sections of the book.The many PhD students with whom I have worked over the years and from whom I have learned as much about location modeling or more than I have possibly taught them, including: Jossef Perl, Michael Watson, Sanjay Melkote, Rosemary Berger, Susan Hesse Owen, Zuo-Jun Max Shen, Lawrence Snyder, Leyla Ozsen, Michael Lim, Federico Liberatore, Kaiyue Zheng and Kayse Lee Maass.Michael Kuby whose careful reading of the entire text and thoughtful comments and suggestions significantly improved the original draft.Kate Roach and Maria Allegra of John Wiley & Sons, Inc., whose encouragement and support of this project were clearly critical for the first edition.Susanne Steitz-Filler, also of John Wiley & Sons, Inc., who encouraged me to revise this book and who was exceptionally supportive in the publishing of my second book, Service Science.Finally, I am most deeply indebted to my wife, Babette, and my daughters, Tamar and Keren, for their support, encouragement, love, and patience throughout this project. They spent many evenings and weekends staring at my back as I typed text, figures, equations, and code into one or more of my computers. Without them, this book would never have been finished. I hope that we can reclaim our time together now that this book is completed.
Mark S. Daskin
Chapter 1
Introduction to Location Theory and Models
1.1 Introduction
If you ask what to look for in buying a house, any realtor will tell you that there are three things that are important: location, location, and location. The theory behind this answer is that the community in which you elect to live and the location within that community are likely to affect your quality of life at least as much as the amenities within your house. For example, if you live within walking distance of the local elementary school, your children will not need to be bused to school. If you live near a community center, you may be able to avoid involvement in car pools taking children to and from activities. If your house is too close to a factory, noise, traffic, and pollution from the factory may degrade your quality of life.
Location decisions also arise in a variety of public and private sector problems. For example, state governments need to determine locations for bases for emergency highway patrol vehicles. Similarly, local governments must locate fire stations and ambulances. In all three of these cases, poor locations can increase the likelihood of property damage and/or loss of life. In the private sector, industry must locate offices, production and assembly plants, distribution centers, and retail outlets. Poor location decisions in this environment lead to increased costs and decreased competitiveness.
In short, the success or failure of both private and public sector facilities depends in part on the locations chosen for those facilities. This book presents methods for finding desirable or optimal facility locations.
We should emphasize from the beginning that the word “optimal” is used in a mathematical sense. That is, we will define quantifiable objectives that depend on the locations of the facilities. We will then identify algorithms (rigorous procedures) for finding optimal or at least good facility locations.
Two factors limit the broader optimality of the sites suggested by the optimization models discussed in this text. First, in many cases, nonquantifiable objectives and concerns will influence siting decisions to a great extent. Often, the qualitative factors that influence siting decisions are critically important. Thus, to the extent that the procedures discussed in this text ignore qualitative concerns and factors, the sites identified by the mathematical algorithms are optimal only in a narrow sense of the word. Second, the performance of a system is affected by many factors of which location is only one. For example, the ability of an ambulance service to save lives (an objective that many would attribute to such a service) depends not only on the proximity of the ambulance bases to the calls for service (which can be measured and optimized to some extent) but also on such factors as the training and skill of the paramedics, the public's knowledge of emergency medical procedures and when it is appropriate to call for an ambulance, the existence of a 911 emergency line, and the protocols and technologies employed by the paramedics.
In the face of (1) exogenous qualitative concerns that influence siting decisions and (2) nonlocation factors that affect the performance of facilities, one might legitimately ask, “Why bother developing mathematical location models?” There are a number of answers to this question. First, while location is not the only factor influencing the success or failure of an enterprise, it is critical in many cases. Poorly sited ambulances will lead to an increased average response time with the associated increase in mortality, that is, more deaths. Second, while exogenous qualitative factors will influence siting decisions, mathematical models allow us to quantify the degradation in the quantifiable objectives that comes from recognizing the qualitative concerns. Thus, if it is important to locate an ambulance in one district for political reasons, the increase in average response time (or maximum response time) resulting from the imposition of this political constraint can be quantified. Third, the modeling process (identifying objectives and constraints and collecting data) often improves the decisions that are made even if the models are never run. Fourth, there are nonlocation problems in which models identical to those discussed in later chapters arise. For example, the problem of selecting tools in a flexible manufacturing context is mathematically similar to that of locating ambulances in a city (Daskin, Jones, and Lowe, 1990).
Section 1.2 outlines a number of key questions that are addressed in location models. Section 1.3 extends the discussion of ambulance location problems and introduces some of the terminology used in location modeling. In this section, we also describe qualitatively another location problem—that of locating landfill sites for solid wastes. Section 1.4 identifies a number of key dimensions along which facility location models can be constructed. Section 1.5 outlines a taxonomy of location models based largely on the underlying topology of the space in which the demands and facilities are embedded. After outlining the taxonomy in Section 1.5.1, Section 1.5.2 develops a simple analytic location model from which insight about key tradeoffs in location problems can be derived. Finally, Section 1.6 summarizes the chapter.
1.2 Key Questions Addressed by Location Models
Mathematical location models are designed to address a number of questions including:
The answers to these questions depend intimately on the context in which the location problem is being solved and on the objectives underlying the location problem. In some cases, such as ambulance siting problems, we will want to locate the facilities as near as possible to the demand sites. In locating radioactive waste repositories, we will want to be in a geologically stable region and would like to be as far as possible from major population centers.
The number of facilities to be located as well as the size of the individual facilities is often a function of the service/cost tradeoffs. In many cases, not only does the quality of service improve as the number of facilities located increases but the cost of providing the service also increases. For example, having more ambulances is generally preferable to having fewer ambulances, since the likelihood of having an available ambulance near a call for service increases with the number of vehicles deployed. In addition, there are no significant economies of scale in ambulance operations, that is, having a single site with multiple ambulances is not much cheaper than having the same number of ambulances at multiple locations. Thus, having a large number of single vehicle ambulance bases is likely to be preferable to having a small number of multivehicle bases. At some point, however, the quality of medical care provided by the paramedics degrades as more ambulances are added to the system. The reason for this is that there are not enough demands requiring a variety of medical skills to maintain the paramedics' training. In many manufacturing contexts, there are significant economies of scale, which drive the location decisions toward having a smaller number of large facilities.
Facility location models are also concerned with the allocation of demands to facilities. In some cases, it is important that demands at a site not be split between facilities. For example, in some retailing operations, a retail store must be supplied by a single warehouse. For administrative reasons, the store's supply cannot be split between different warehouses. In other cases, such as ambulance services, demands can be served by any available facility. Facility location models must reflect these different demand allocation policies and must then allocate demands (or fractions of the total demand in a region) to different facilities. In many cases, demands will be allocated to the nearest (available) facility; in other cases, doing so may not be optimal.
1.3 Example Problem Descriptions
In this section, we outline a number of different facility location contexts and qualitatively define some of the classical location problems.
1.3.1 Ambulance Location
As indicated above, poor ambulance locations can cost lives! To illustrate this point, a commonly cited statistic is that if a person's brain is denied oxygen for more than 4 min (e.g., as a result of a stroke or heart attack), the likelihood of the individual surviving to lead a normal life drops below 50%. This suggests that we would like to locate ambulances so that the maximum response time is well under 4 min. Thus, one objective might be to minimize the number of ambulances needed so that all demand nodes are within a given number of minutes (the service standard) of the nearest ambulance. Such a model formulation is known as a set covering model. Demands are said to be covered if the nearest ambulance is located not more than X min away, where X is the service standard used in the model (e.g., 4 min). Set covering models have been used by a number of authors in locating ambulances and other emergency service vehicles (e.g., Toregas et al., 1971; Walker, 1974; Plane and Hendrick, 1977; Daskin and Stern, 1981; Jarvis, Stevenson, and Willemain, 1975).
One of the common problems associated with the set covering model is that the solution is likely to call for locating more vehicles than the community can afford. If we deployed one less vehicle and relocated the remaining vehicles to maximize the number of demands that can be served within the given service standard (e.g., 4 min), the fraction of the demands that would not be serviceable within the service standard would generally be far less than 1/N, where N is the number of ambulances called for by the set covering model. In other words, the last few ambulances add relatively little to the fraction of demands that can be served within the service standard but add significantly to the cost of the ambulance service. This suggests an alternate objective: maximize the number of demands that can be covered within a specified service standard using a given number of vehicles. Such a model is known as a maximum covering model. In practice, the fleet size that is input into such a model is often varied from 1 up to the number required for full coverage as indicated by the set covering model. This allows us to trace out the tradeoff between additional vehicles and coverage. Such a curve is shown in Figure 1.1. In this example, ten vehicles are needed to cover all demands. In other words, the solution to the set covering model for this problem is ten vehicles. The maximum covering model would then be solved for one through nine vehicles in the system. Notice that the incremental coverage decreases as additional vehicles are added to the system. Maximum covering models and their variants have also been used in analyzing ambulance systems and related emergency services (e.g., Daskin, 1982, 1983; Eaton et al., 1985; Church and ReVelle, 1974; Belardo et al., 1984).
Figure 1.1 Typical tradeoff in maximum covering model.1
In some cases, logical choices for the service standard might not be readily available. The choice of 4 min in the discussion of the covering models was predicated on the observation that irreversible brain damage is likely to occur if the brain is denied oxygen for more than 4 min. However, this does not necessarily imply that 4 min is the appropriate service standard. A shorter service standard could be justified by the observation that the clock for brain damage begins at the onset of the medical incident (the stroke or heart attack that denies the brain oxygen), while the clock for the response time begins only once the vehicle begins to roll out of its base. There is often a long time (several minutes) between when a medical incident arises and when a vehicle begins traveling to the scene. This additional time is consumed by the time required to recognize the need for an ambulance, the time to notify the dispatcher of the need, and the time required by the dispatcher to assign the call to a vehicle and to notify the vehicle's crew of the call. On the other hand, a longer service standard may be dictated by budgetary considerations. Requiring all demands to be served within 4 min may be too costly. It would be cheaper to have all demands served within 5 min or some longer time period. This suggests yet another model and another objective function: minimize the maximum response time (the time between a demand site and the nearest ambulance) using a given number (P) of vehicles. Such a model is referred to as the P-center problem.
Covering and center problems focus on the worst-case behavior of the system, for example, the maximum response time. In practice, there is often a tradeoff between minimizing the maximum response time and minimizing the average response time. This suggests yet a fourth model and objective that might be used in locating ambulances: minimize the average response time (the time between a demand site and the nearest ambulance) using a given number (P) of vehicles. This model is called the P-median problem (Hakimi, 1964, 1965).
While we have outlined a number of different objectives that might be used in locating ambulances, it is important that we realize explicitly some of the factors that have been ignored in this discussion. The importance of doing so was enunciated particularly well by Jacobsen (1990, p. 205) who pointed out that formulating a problem incorrectly (e.g., failing to account for important problem factors) is likely to be far more important than whether or not you obtain an optimal or suboptimal solution to a particular problem formulation. Thus, while the focus of this book is generally on finding optimal solutions (or near optimal solutions) to specific mathematical statements of facility location problems, we must always ask whether the model being solved adequately represents the real problem being analyzed.
In the context of ambulance location, at least three facets of the real-world problem have been ignored in the discussion above. First, the models outlined above ignore the stochastic (or random) nature of demands and the fact that the nearest vehicle might not be available when called upon to serve a demand. A variety of approaches have been adopted to address this problem including: extending the deterministic models outlined above (Aly and White, 1978; Weaver and Church, 1983b, 1984; Daskin, 1982, 1983); incorporating queuing theory into location models (Larson, 1974; Fitzsimmons, 1973); and simulation approaches (Swoveland et al., 1973). Once the inputs to the model are recognized as being random variables, the outputs are likely to be random variables as well. Thus, we might no longer be interested only in the average response time (as in the P-median model) but also in the distribution of response times. Also, just as the demands are stochastic, so are the travel times. Models with stochastic travel times have also been developed (Weaver and Church, 1983a; Mirchandani and Odoni, 1979; Daskin and Haghani, 1984; Daskin, 1987).
Second, there is a need to balance the workload of the different vehicles. This stems from the needs (1) to preserve morale among the emergency medical service employees and (2) to maintain the skill level of all paramedics at some minimal level by ensuring that they are all exposed to a minimum number of medical emergencies of differing types.
As in all situations, we must ask whether facility location is really the correct problem. The quality of medical care delivered to the public and the likelihood of people surviving major medical incidents (e.g., auto crashes, assaults with deadly weapons, heart attacks, and strokes) depend on many factors in addition to the location of ambulances in the community. The installation of a 911 emergency phone line can reduce the time needed to contact an ambulance dispatcher. This reduction in time may be greater (as compared with its cost) than that achievable by any relocation of ambulances. Improving the quality of hospital emergency room care may also go a long way toward reducing fatalities. It may be more cost effective to spend public funds on such improvements than it would be on relocating vehicles or adding ambulances. Instituting a community-wide CPR (cardiopulmonary resuscitation) education program might also be a cost-effective way of saving lives.2
The analysis assumed that all calls are equally important. In fact, this is not the case. Calls are often differentiated into critical (life-threatening) and noncritical calls. Also, some patients can be cared for at the scene of the incident, while others require transport to the hospital. In addition, the models outlined above fail to recognize the temporal variation in the overall intensity of calls (typically Friday night is the busiest time of the week) and the temporal variation in the spatial distribution of calls (more incidents will be reported from business districts during working hours than during the early morning hours). This temporal variation in demand suggests that having fixed sites may not be optimal; using relocatable ambulances may be preferable (Carson and Batta, 1990).
Once we distinguish between the severity of different demands for ambulance services, we recognize it may be advantageous to institute a multitiered system in which paramedics with differing levels of training are deployed (along with vehicles with correspondingly different levels of equipment). It may not be cost effective to have all paramedics trained at the highest level and to have all vehicles capable of responding to all types of medical emergencies. We may be able to deploy more vehicles and paramedics by (i) disaggregating calls based on their severity and (ii) allowing response units and personnel to be specialized for certain types of calls. In a multitiered system, dispatching rules become even more complicated. Not only might it not be advantageous to dispatch the nearest available vehicle (since doing so might leave large portions of the service area uncovered), but we must now decide which type of vehicle and crew to dispatch to each event. The possibilities are shown schematically in Figure 1.2. If possible, we should dispatch an EMT (emergency medical technician) to a noncritical call and a paramedic in an advanced life support (ALS) vehicle to a critical incident. However, we might also want to dispatch an EMT to a critical call if the vehicle is likely to get to the scene before the ALS vehicle. Doing so would give the public the impression that something is being done about the emergency. This policy, however, ties up extra resources since two vehicles would then be dispatched under these conditions. Similarly, if an ALS vehicle is very near a noncritical incident, we might elect to dispatch the ALS vehicle. This policy has the advantage of getting medical assistance to the scene quickly, but has the disadvantage of tying up an expensive ALS vehicle and highly trained crew that might be needed elsewhere while they are busy serving the noncritical incident.
Figure 1.2 Dispatching options in a multitiered system.
Finally, we note that the models we have briefly outlined, in particular the set covering model, the maximum covering model, and the P-center model, have all been used extensively in a broad range of public sector facility location problems including the location of libraries, schools, clinics, hospitals, and bus stops.
1.3.2 Siting Landfills for Hazardous Wastes
We turn briefly to another problem, that of locating landfills for disposal of hazardous wastes. First, any such site must be deemed geologically stable and suitable. Given this condition, the choice between sites might be dictated by a number of objectives. First, we would like to be as close as possible to the waste generation sites to minimize the transport costs as well as the exposure of the public to the hazardous wastes while they are en route to the disposal site. Minimizing the average (or total) shipping distance over some period of time results in a P-median formulation. However, many of the waste generation sites may be close to heavily populated regions. In this case, we would like the disposal sites to be far from populated areas. This suggests the use of a maxisum or maxian model in which we attempt to locate a given number (P) of facilities to maximize the (population weighted) distance between population centers and the nearest sites (Church and Garfinkel, 1978; Minieka, 1983). Clearly, this objective and the P-median objective conflict. The presence of conflicting objectives is common in facility location problems.
Both models take the number of facilities as given. In practice, we need to balance the initial capital investment costs against the ongoing operating costs. Thus, we might like to minimize the sum of the fixed site preparation costs and the discounted present cost of the stream of operating costs (e.g., on-site operating costs and transport costs). This leads to what is known as a fixed charge facility location problem.
Finally, we would like to reduce the inequities across communities. No community wants to be the dumping site for the rest of the state or the rest of the country. Thus, we might like to spread the risk or disbenefit around to the extent that it is possible to do so (e.g., Ratick and White, 1988; Erkut and Neuman, 1992; Wyman and Kuby, 1994). This has recently become an issue not only in the location of disposal sites but also in the routing of materials from generation sites to disposal facilities (Lindner-Dutton, Batta, and Karwan, 1991; ReVelle, Cohon, and Shobrys, 1991; List and Mirchandani, 1991; List et al., 1991).
1.3.3 Summary
In summary, modeling location problems requires an understanding of the real-world operations that are to be reflected in the model. Models need not reflect every aspect of the real-world operations. In fact, parsimonious models are generally better than complex inscrutable models. The ability to know what must be incorporated into a model and what can safely be treated as exogenous is both an art and a science. As illustrated above, location problems often involve multiple conflicting objectives. The purpose of modeling is to identify the tradeoffs between the objectives while capturing as much of the richness of the real-world problem as is necessary to ensure the credibility of the modeler and model itself. Finally, we must always ask whether improving facility locations is the most cost-effective way of improving the system under study.
1.4 Key Dimensions of Location Problems and Models3
Location problems and models may be classified in a number of ways. The classification may be based on the topography that is used (e.g., planar problems versus discrete location problems, problems on trees versus those on general graphs, and problems using different distance metrics) or the number of facilities to be located. Problems may also be classified based on the nature of the inputs (e.g., whether they are static or dynamic, known with certainty or only known in a probabilistic sense). Models may further be classified based on whether single or multiple products or demands must be accommodated by the facilities being located, whether there is one objective or multiple objectives, whether the beneficiaries and investors are the same or different actors, whether the facilities are of unlimited capacity or are capacitated, as well as a variety of other classification criteria. This section identifies key dimensions or characteristics of facility location problems and models.
1.4.1 Planar versus Network versus Discrete Location Models
One of the key differences between location models is in the way in which demands and candidate facility locations are represented. In planar location models, demands occur anywhere on a plane. We often represent demands using a spatially distributed probability distribution [which gives the likelihood of demands arising at any given coordinate]. In such problems, facilities may be located anywhere on the plane. This modeling approach is to be contrasted with network location models, in which demands and travel between demand sites and facilities are assumed to occur only on a network or graph composed of nodes and links. Often, we assume that demands occur only at the nodes of the network, though some network location models have permitted demands to be generated anywhere on the links of the network. In network location models, facilities can be located only on the nodes or links of the network. One of the key questions we will be interested in considering is: when is location only on the nodes of the network optimal? The presence of an underlying network often facilitates the development of solution algorithms. Discrete location models allow for the use of arbitrary distances between nodes. As such, the structure of the underlying network is lost. However, by removing the restriction that the distances between nodes are obtained from an underlying network, the more general class of discrete location models allows a broader range of problems to be modeled. Discrete location problems are generally formulated as mixed integer programming problems as discussed below. For a further discussion of the differences between these three types of models, the reader is referred to Chhajed, Francis, and Lowe (1993).
The focus of this book is on network and discrete location models. Handler and Mirchandani (1979) and Mirchandani and Francis (1990) provide excellent overviews of network location models, while planar location models are discussed in Hurter and Martinich (1989) and Love, Morris, and Wesolowsky (1988).
1.4.2 Tree Problems versus General Graph Problems
Within the class of network location models, we often distinguish between problems that arise on trees and those that must be formulated on a more general (fully connected) graph. Figure 1.3 illustrates a number of different trees and general networks.
Figure 1.3 Example trees and graphs.
A tree is a network in which there is at most one path from any node to any other node. In other words, a tree is an acyclic graph or a graph with no cycles. In general, we will focus our attention on spanning trees (trees in which there is exactly one path between any node and any other node). If such a tree has N nodes, it will have links.
Our interest in trees as opposed to more general graphs results from two considerations. First, many real-life problems can be represented quite well as trees. For example, the links depicting major highways within a region often form a tree as long as we ignore the cycles formed by beltways surrounding major urban areas. Also, major parts of power transmission and telecommunication networks—particularly the portions used for the delivery of local services—are essentially trees. Second, given a verbal or mathematical statement of a location problem, it is often the case that we can solve the problem easily on a tree while solving it on a more general network is exceptionally difficult. In Chapter 3, we formalize the notions of easy and difficult problems using complexity theory.
1.4.3 Distance Metrics
Location models are also often characterized by the distance metric (the method of measuring distances) that is used. For network location models, we will generally use the shortest distance between any pair of points using links in the network. In Chapter 2, we discuss algorithms for finding the shortest paths between points in a network. In planar location problems, one of three distance metrics is typically employed:
where is the distance between the ith and jth points and gives the coordinates of the ith point. A bit of thought will show that the metric (the metric when p= 2) is the same as the Euclidean distance between two points and that the metric is equivalent to the Manhattan or right-angle distance. What is the metric? This is left as an exercise for the reader.
1.4.4 Number of Facilities to Locate
Another way of characterizing facility location problems is by the number of facilities to be located. In some problems (e.g., the P-median, P-center, and maximum covering problems), the number of facilities to locate is exogenously specified. In other cases (e.g., the set covering problem and the fixed charge facility location problem), the number of facilities is endogenous to the problem and is a model output. For those problem statements in which the number of facilities to locate is exogenously specified, we also distinguish between single-facility location problems and those in which multiple facilities are to be sited. Often, single-facility location problems are dramatically easier than are their multifacility counterparts.
1.4.5 Static versus Dynamic Location Problems
Most of the location models that we will consider will be static problems. In static models, the inputs do not depend on time; typically, we will use a single “representative” set of inputs and solve the problem for a single “representative” period.
As noted above in the discussion of ambulance systems, inputs are rarely static. Thus, while most location models are static, most location problems are dynamic in that the inputs (and consequently the outputs as well) depend on time. Inputs that may depend on time include demands, costs, and available and preexisting candidate facility locations. In dynamic problems, the models must explicitly include multiple periods of time. Different periods might allow us (i) to capture hourly differences in the mean number of demands for service, (ii) to reflect differences between the spatial patterns of demands on weekdays and weekends, or (iii) to account for increases in demands or costs over a period of years.
In dynamic problems, we are concerned not only with the question of where to locate facilities but also with the question of when to invest in new facilities or to close existing facilities. In some models of dynamic location problems, once a facility is opened it is assumed to be available for all future periods. In other models, facilities may be opened, closed, or moved throughout the planning horizon (Ballou, 1968; Sweeney and Tatham, 1976; Van Roy and Erlenkotter, 1982; Wesolowsky, 1973; Wesolowsky and Truscott, 1975).
While most researchers and planners have a good idea of what is meant by a static location model, there is considerably less agreement about what is meant by a dynamic location model. One approach might be to identify a single set of locations that perform well with respect to a number of spatially different demand patterns that occur at different times. Such a problem statement might arise in locating fire stations that need to respond well to demands during working hours as well as on weekends. This approach might also be appropriate in locating facilities to serve demands that vary in a cyclic manner (e.g., Osleeb and Ratick, 1990). A second approach to the dynamic location problem would be that of identifying the optimal evolution of facility locations over time. Such a model would be appropriate for a firm that needs to locate warehouses to supply its customers and that plans to expand from a set of regional retail outlets to a national chain. In some cases, it is best to find an optimal first period decision as opposed to a plan for all future time periods (Daskin, Hopp, and Medina, 1992). Finally, an alternate definition of the dynamic location problem would be that of positioning vehicles in real time to respond to minute-by-minute changes in the fleet of available (nonbusy) vehicles. This problem in particular has been analyzed by Kolesar and Walker (1974) using set covering models.4
1.4.6 Deterministic versus Probabilistic Models
Just as the inputs to models may be either static or dynamic, so too the inputs may be deterministic (certain) or probabilistic (subject to uncertainty). In dealing with location problems over time, many of the inputs are likely to be uncertain. For example, future calls for ambulance services are not known with certainty. Instead they must be predicted and, as such, are subject to uncertainty. This book focuses on deterministic models, though in some cases we can readily generalize the algorithms or model formulations to include some probabilistic components. Louveaux (1993) reviews stochastic location models.
1.4.7 Single- versus Multiple-Product Models
The models outlined above have all implicitly assumed that we are dealing with a single homogenous product or service and that all demands are identical. Most location models make this assumption. However, in practice, it is often important to distinguish between different products or services all of which will be served by the same set of facilities. For example, it may be important to distinguish between critical and noncritical calls.
In some cases, products are distinguished by having different origins and destinations. For example, a single set of transshipment facilities may be used by an automobile manufacturer in shipping finished vehicles from assembly plants to dealers. At such transshipment points, vehicles are offloaded from railcars and loaded onto trucks for final delivery to customers (typically, dealers). Each assembly plant/customer combination would represent a different product. In other words, we would need to distinguish between Cadillac Sevilles going from a Cadillac assembly plant to a Cadillac dealer in San Diego and Chevrolet Corvettes going from a Chevrolet plant to a dealer in Los Angeles, even though both vehicles might use the same transshipment point in southern California.
1.4.8 Private versus Public Sector Problems
In private sector problems, the investment costs and benefits are typically measured in monetary units. Furthermore, the costs and benefits are generally incident on the same actors: the firm, its management, and its investors all of whom share common objectives and goals. All this makes cost/benefit analysis relatively easy.
In public sector location problems, many nonmonetary cost and benefits must also be considered. For example, in locating hazardous waste repositories, there are a number of environmental costs that may be difficult to translate into monetary units. In locating emergency services, the dollar value of the lives saved as a result of shorter travel times may be exceedingly difficult to assess. In siting public schools, the benefits may be measured in terms of the number of students who graduate from high school. In public sector problems, not only are costs and benefits often incommensurable, but there are often multiple benefit measures (as discussed in Section 1.4.9). In addition, while the costs of public sector projects may be borne by the public at large, the benefits are often concentrated on fewer people. Thus, investment in public schools directly benefits school-aged children and their parents. Such investments do not directly benefit other members of society, such as the elderly. Finally, public sector investments are often complicated by the political process in which beneficiaries of one investment may agree to support projects from which they do not directly benefit. Thus, groups representing the elderly may agree to support additional funding of public schools provided other groups' support enhanced health care legislation.5
1.4.9 Single- versus Multiple-Objective Problems and Models
Most models capture a single objective; however, most problems are inherently multiobjective in nature. Since one of the purposes of location modeling is to help identify tradeoffs, single-objective models must often be run with a range of input parameters (e.g., running a P-median problem with a number of values of P to trace the tradeoff between average distance to a facility and the number of facilities sited). Alternatively, multiple models need to be employed (e.g., Eaton and Daskin, 1980).
1.4.10 Elastic versus Inelastic Demand
Most models treat demand as given and independent of the level of service. In fact, demand in almost all cases depends on the level of service provided. This, in turn, depends on the facility locations and the types and sizes of facilities used. In some cases, demand is likely to be relatively inelastic (independent of the level of service). For example, if someone needs an ambulance, he or she is unlikely to inquire about the cost. An individual is also unlikely to bother to find out the expected arrival time of the vehicle and to identify alternative means of getting to the hospital if the expected response time is too long. On the other hand, consumers' choices of where to shop depend critically on the amenities within the shopping center, the location of the center, and the number and variety of stores in the shopping center. Despite the fact that demand in most real-world location problems exhibits some degree of elasticity with respect to service (which depends in part on the location decisions), we will generally treat demand as inelastic. Recent work by Perl and Ho (1990) has examined some of the implications of elastic demand on public facility location models. Kuby (1989) formulates a model that maximizes the number of firms that can coexist in a market. His model also incorporates elastic demand.
1.4.11 Capacitated versus Uncapacitated Facilities
Many facility location models (e.g., standard set covering, maximum covering, P-median, and P-center models) treat facilities as having unlimited capacity. Other models impose explicit capacity limits on facilities. In still other cases, the size of a facility is a model output.
1.4.12 Nearest Facility versus General Demand Allocation Models
As discussed above, the allocation of demand to facilities is a critical issue in location modeling. Often, demands are assigned to the nearest facility provided that facility has the capacity to serve the demand. In capacitated problems, this may result in the need to split the demand at a site between several facilities. If this is not permissible in a particular problem setting, explicit constraints must be included in the model (typically, in the form of integer variables) to force all of the demand at a particular location to be assigned to a single facility. This may result in some demands being assigned to facilities other than the closest site. In still other cases, models must recognize that a fraction of the demand at a site will be served by the nearest facility, and the remainder of the demand will be served by more remote facilities when the nearest facility is busy.
1.4.13 Hierarchical versus Single-Level Models
In many systems, a hierarchy of facilities exists with flows between the facilities that are being located. For example, in a national health care system, rural health centers are likely to refer patients to clinics, which, in turn, may refer patients to community hospitals. In some such systems, services provided at the lower level (e.g., the rural health center) are offered at higher levels; in other cases, these services are not replicated. Narula (1986) refers to these as successively inclusive and successively exclusive facility hierarchies
