Network and Discrete Location

MARK S. DASKIN, PhD, is Clyde W. Johnson Collegiate Professor of Industrial and Operations Engineering as well as Department Chair at the University of Michigan. Dr. Daskin is the former editor-in-chief of both Transportation Science and IIE Transactions and continues to serve on the editorial boards of both journals. He is also on the editorial board of the IIE Transactions on Healthcare Systems Engineering and is the author of the award-winning book Service Science, also published by Wiley.

• Preface to the First and Second Editions xiAcknowledgments xvii1. Introduction to Location Theory and Models 11.1 Introduction 11.2 Key Questions Addressed by Location Models 31.3 Example Problem Descriptions 41.3.1 Ambulance Location 41.3.2 Siting Landfills for Hazardous Wastes 101.3.3 Summary 101.4 Key Dimensions of Location Problems and Models 111.4.1 Planar Versus Network Versus Discrete Location Models 111.4.2 Tree Problems Versus General Graph Problems 121.4.3 Distance Metrics 131.4.4 Number of Facilities to Locate 141.4.5 Static Versus Dynamic Location Problems 151.4.6 Deterministic Versus Probabilistic Models 161.4.7 Single- Versus Multiple-Product Models 161.4.8 Private Versus Public Sector Problems 171.4.9 Single- Versus Multiple-Objective Problems and Models 171.4.10 Elastic Versus Inelastic Demand 181.4.11 Capacitated Versus Uncapacitated Facilities 181.4.12 Nearest Facility Versus General Demand Allocation Models 181.4.13 Hierarchical Versus Single-Level Models 191.4.14 Desirable Versus Undesirable Facilities 191.5 A Taxonomy of Location Models 201.5.1 Typology of Location Models 201.5.2 A Simple Analytic Model 221.6 Summary 26Exercises 272. Review of Linear Programming 292.1 Introduction 292.2 The Canonical Form of a Linear Programming Problem 312.3 Constructing the Dual of an LP Problem 342.4 Complementary Slackness and the Relationships Between the Primal and the Dual Linear Programming Problems 362.5 Solving a Linear Programming Problem in Excel 432.6 The Transportation Problem 472.7 The Shortest Path Problem 642.7.1 The Shortest Path Problem in Excel 782.7.2 The Shortest Path Problem in AMPL 802.8 The Out-of-Kilter Flow Algorithm 802.9 Integer Programming Problems 922.10 Summary 96Exercises 973. An Overview of Complexity Analysis 1113.1 Introduction 1113.2 Basic Concepts and Notation 1123.3 Example Computation of an Algorithm’s Complexity 1153.4 The Classes P and NP (and NP-Hard and NP-Complete) 1173.5 Summary 122Exercises 1234. Covering Problems 1244.1 Introduction and the Notion of Coverage 1244.2 The Set Covering Model 1254.3 Applications of the Set Covering Model 1374.4 Variants of the Set Covering Location Model 1404.5 The Maximum Covering Location Model 1434.5.1 The Greedy Adding Algorithm: A Heuristic Algorithm for Solving the Maximum Covering Location Model 1464.5.2 Lagrangian Relaxation: An Optimization-Based Heuristic Algorithm for Solving the Maximum Covering Location Model 1544.5.3 Other Solution Approaches and Example Results 1634.6 An Interesting Model Property or It Ain’t Necessarily So 1644.7 The Maximum Expected Covering Location Model 1684.8 Summary 174Exercises 1755. Center Problems 1935.1 Introduction 1935.2 Vertex P-Center Formulation 1985.3 The Absolute 1- and 2-Center Problems on a Tree 2015.3.1 Absolute 1-Center on an Unweighted Tree 2015.3.2 Absolute 2-Centers on an Unweighted Tree 2055.3.3 Absolute 1-Center on a Weighted Tree 2065.4 The Unweighted Vertex P-Center Problem on a General Graph 2115.5 The Unweighted Absolute P-Center Problem on a General Graph 2155.5.1 Characteristics of the Solution to the Absolute P-Center Problem 2155.5.2 An Algorithm for the Unweighted Absolute P-Center on a General Graph 2195.6 Summary 229Exercises 2306. Median Problems 2356.1 Introduction 2356.2 Formulation and Properties 2376.3 1-Median Problem on a Tree 2416.4 Heuristic Algorithms for the P-Median Problem 2466.5 An Optimization-Based Lagrangian Algorithm for the P-Median Problem 2606.5.1 Methodological Development 2606.5.2 Numerical Example 2656.5.3 Extensions and Enhancements to the Lagrangian Procedures 2716.6 Computational Results Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm 2716.7 Another Interesting Property or It Still Ain’t Necessarily So 2776.8 Summary 283Exercises 2857. Fixed Charge Facility Location Problems 2947.1 Introduction 2947.2 Uncapacitated Fixed Charge Facility Location Problems 2977.2.1 Heuristic Construction Algorithms 2987.2.2 Heuristic Improvement Algorithms 3057.2.3 A Lagrangian Relaxation Approach 3117.2.4 A Dual-Based Approach 3147.3 Capacitated Fixed Charge Facility Location Problems 3257.3.1 Lagrangian Relaxation Approaches 3287.3.2 Bender’s Decomposition 3457.4 Summary 355Exercises 3568. Extensions of Location Models 3628.1 Introduction 3628.2 Multiobjective Problems 3628.3 Hierarchical Facility Location Models 3758.3.1 Basic Notions of Hierarchical Facilities 3758.3.2 Basic Median-Based Hierarchical Location Formulations 3798.3.3 Coverage-Based Hierarchical Location Formulations 3838.3.4 Extensions of Hierarchical Location Formulations 3858.4 Models of Interacting Facilities 3878.4.1 Flows Between Facilities 3878.4.2 Facilities with Proximity Constraints 3908.5 Multiproduct Flows and Production/Distribution Systems 3938.6 Location/Routing Problems 3998.7 Hub Location Problems 4108.8 Dispersion Models and Models for the Location of Undesirable Facilities 4258.8.1 Dispersion Models 4268.8.2 A Maxisum Model for the Location of Undesirable Facilities 4298.9 An Integrated Location-Inventory Model 4358.9.1 A Multiobjective Location-Inventory/Covering Model 4488.9.2 A Look at Aggregation Effects 4528.10 Reliability and Facility Location Modeling 4558.10.1 The Expected Failure Case 4588.10.2 Modeling a Malevolent Attacker 4618.11 Summary 466Exercises 4689. Location Modeling in Perspective 4809.1 Introduction 4809.2 The Planning Process for Facility Location 4819.2.1 Problem Definition 4819.2.2 Analysis 4839.2.3 Communication and Decision 4899.2.4 Implementation 4959.2.5 Caveats on the Planning Process 4969.3 Summary 496Exercises 497References 499Index 509