Schade – dieser Artikel ist leider ausverkauft. Sobald wir wissen, ob und wann der Artikel wieder verfügbar ist, informieren wir Sie an dieser Stelle.
- Format: PDF
- Merkliste
- Auf die Merkliste
- Bewerten Bewerten
- Teilen
- Produkt teilen
- Produkterinnerung
- Produkterinnerung
Bitte loggen Sie sich zunächst in Ihr Kundenkonto ein oder registrieren Sie sich bei
bücher.de, um das eBook-Abo tolino select nutzen zu können.
Hier können Sie sich einloggen
Hier können Sie sich einloggen
Sie sind bereits eingeloggt. Klicken Sie auf 2. tolino select Abo, um fortzufahren.
Bitte loggen Sie sich zunächst in Ihr Kundenkonto ein oder registrieren Sie sich bei bücher.de, um das eBook-Abo tolino select nutzen zu können.
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…mehr
- Geräte: PC
- eBook Hilfe
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.
Produktdetails
- Produktdetails
- Verlag: John Wiley & Sons
- Seitenzahl: 544
- Erscheinungstermin: 21. Juni 2013
- Englisch
- ISBN-13: 9781118537039
- Artikelnr.: 39054097
- Verlag: John Wiley & Sons
- Seitenzahl: 544
- Erscheinungstermin: 21. Juni 2013
- Englisch
- ISBN-13: 9781118537039
- Artikelnr.: 39054097
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.
1 Introduction to Location Theory and Models 1.1 INTRODUCTION 1.2 KEY QUESTIONS ADDRESSED BY LOCATION MODELS 1.3 EXAMPLE PROBLEM DESCRIPTIONS 1.3.1 Ambulance Location 1.3.2 Siting Landfills for Hazardous Wastes 1.3.3 Summary 1.4 KEY DIMENSIONS OF LOCATION PROBLEMS AND MODELS 1.4.1 Planar versus Network versus Discrete Location Models 1.4.2 Tree Problems versus General Graph Problems 1.4.3 Distance Metrics 1.4.4 Number of Facilities to Locate 1.4.5 Static versus Dynamic Location Problems 1.4.6 Deterministic versus Probabilistic Models 1.4.7 Single- versus Multiple-Product Models 1.4.8 Private versus Public Sector Problems 1.4.9 Single-versus Multiple-Objective Problems and Models 1.4.10 Elastic versus Inelastic Demand 1.4.11 Capacitated versus Uncapacitated Facilities 1.4.12 Nearest Facility versus General Demand Allocation Models 1.4.13 Hierarchical versus Single-Level Models 1.4.14 Desirable versus Undesirable Facilities 1.5 A TAXONOMY OF LOCATION MODELS 1.5.1 Typology of location models 1.5.2 A simple analytic model 1.6 SUMMARY 1.7 EXERCISES Figure 1.1 Typical tradeoff in maximum covering model Figure 1.2 Dispatching options in a multi-tiered system Figure 1.3 Example trees and graphs Figure 1.4 Alternative Taxonomy of Location Models Figure 1.5 Service area and directions of travel for a simple analytic location model Figure 1.6 Example service region subdivided into 9 subregions Figure 1.7 Typical cost components in a simple analytic model Figure 1.8 Ratio of actual to optimal cost versus ratio of actual to optimal number of facilities for the simple analytic model Table 1.1 Allowable range of alpha for various percentage errors in the optimal cost for the simple analytic model
Preface to the First and Second Editions xi Acknowledgments xvii 1.
Introduction to Location Theory and Models 1 1.1 Introduction 1 1.2 Key
Questions Addressed by Location Models 3 1.3 Example Problem Descriptions 4
1.3.1 Ambulance Location 4 1.3.2 Siting Landfills for Hazardous Wastes 10
1.3.3 Summary 10 1.4 Key Dimensions of Location Problems and Models 11
1.4.1 Planar Versus Network Versus Discrete Location Models 11 1.4.2 Tree
Problems Versus General Graph Problems 12 1.4.3 Distance Metrics 13 1.4.4
Number of Facilities to Locate 14 1.4.5 Static Versus Dynamic Location
Problems 15 1.4.6 Deterministic Versus Probabilistic Models 16 1.4.7
Single- Versus Multiple-Product Models 16 1.4.8 Private Versus Public
Sector Problems 17 1.4.9 Single- Versus Multiple-Objective Problems and
Models 17 1.4.10 Elastic Versus Inelastic Demand 18 1.4.11 Capacitated
Versus Uncapacitated Facilities 18 1.4.12 Nearest Facility Versus General
Demand Allocation Models 18 1.4.13 Hierarchical Versus Single-Level Models
19 1.4.14 Desirable Versus Undesirable Facilities 19 1.5 ATaxonomy of
Location Models 20 1.5.1 Typology of Location Models 20 1.5.2 A Simple
Analytic Model 22 1.6 Summary 26 Exercises 27 2. Review of Linear
Programming 29 2.1 Introduction 29 2.2 The Canonical Form of a Linear
Programming Problem 31 2.3 Constructing the Dual of an LP Problem 34 2.4
Complementary Slackness and the Relationships Between the Primal and the
Dual Linear Programming Problems 36 2.5 Solving a Linear Programming
Problem in Excel 43 2.6 The Transportation Problem 47 2.7 The Shortest Path
Problem 64 2.7.1 The Shortest Path Problem in Excel 78 2.7.2 The Shortest
Path Problem in AMPL 80 2.8 The Out-of-Kilter Flow Algorithm 80 2.9 Integer
Programming Problems 92 2.10 Summary 96 Exercises 97 3. An Overview of
Complexity Analysis 111 3.1 Introduction 111 3.2 Basic Concepts and
Notation 112 3.3 Example Computation of an Algorithm's Complexity 115 3.4
The Classes P and NP (and NP-Hard and NP-Complete) 117 3.5 Summary 122
Exercises 123 4. Covering Problems 124 4.1 Introduction and the Notion of
Coverage 124 4.2 The Set Covering Model 125 4.3 Applications of the Set
Covering Model 137 4.4 Variants of the Set Covering Location Model 140 4.5
The Maximum Covering Location Model 143 4.5.1 The Greedy Adding Algorithm:
A Heuristic Algorithm for Solving the Maximum Covering Location Model 146
4.5.2 Lagrangian Relaxation: An Optimization-Based Heuristic Algorithm for
Solving the Maximum Covering Location Model 154 4.5.3 Other Solution
Approaches and Example Results 163 4.6 An Interesting Model Property or It
Ain't Necessarily So 164 4.7 The Maximum Expected Covering Location Model
168 4.8 Summary 174 Exercises 175 5. Center Problems 193 5.1 Introduction
193 5.2 Vertex P-Center Formulation 198 5.3 The Absolute 1- and 2-Center
Problems on a Tree 201 5.3.1 Absolute 1-Center on an Unweighted Tree 201
5.3.2 Absolute 2-Centers on an Unweighted Tree 205 5.3.3 Absolute 1-Center
on a Weighted Tree 206 5.4 The Unweighted Vertex P-Center Problem on a
General Graph 211 5.5 The Unweighted Absolute P-Center Problem on a General
Graph 215 5.5.1 Characteristics of the Solution to the Absolute P-Center
Problem 215 5.5.2 An Algorithm for the Unweighted Absolute P-Center on a
General Graph 219 5.6 Summary 229 Exercises 230 6. Median Problems 235 6.1
Introduction 235 6.2 Formulation and Properties 237 6.3 1-Median Problem on
a Tree 241 6.4 Heuristic Algorithms for the P-Median Problem 246 6.5 An
Optimization-Based Lagrangian Algorithm for the P-Median Problem 260 6.5.1
Methodological Development 260 6.5.2 Numerical Example 265 6.5.3 Extensions
and Enhancements to the Lagrangian Procedures 271 6.6 Computational Results
Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm 271
6.7 Another Interesting Property or It Still Ain't Necessarily So 277 6.8
Summary 283 Exercises 285 7. Fixed Charge Facility Location Problems 294
7.1 Introduction 294 7.2 Uncapacitated Fixed Charge Facility Location
Problems 297 7.2.1 Heuristic Construction Algorithms 298 7.2.2 Heuristic
Improvement Algorithms 305 7.2.3 A Lagrangian Relaxation Approach 311 7.2.4
A Dual-Based Approach 314 7.3 Capacitated Fixed Charge Facility Location
Problems 325 7.3.1 Lagrangian Relaxation Approaches 328 7.3.2 Bender's
Decomposition 345 7.4 Summary 355 Exercises 356 8. Extensions of Location
Models 362 8.1 Introduction 362 8.2 Multiobjective Problems 362 8.3
Hierarchical Facility Location Models 375 8.3.1 Basic Notions of
Hierarchical Facilities 375 8.3.2 Basic Median-Based Hierarchical Location
Formulations 379 8.3.3 Coverage-Based Hierarchical Location Formulations
383 8.3.4 Extensions of Hierarchical Location Formulations 385 8.4 Models
of Interacting Facilities 387 8.4.1 Flows Between Facilities 387 8.4.2
Facilities with Proximity Constraints 390 8.5 Multiproduct Flows and
Production/Distribution Systems 393 8.6 Location/Routing Problems 399 8.7
Hub Location Problems 410 8.8 Dispersion Models and Models for the Location
of Undesirable Facilities 425 8.8.1 Dispersion Models 426 8.8.2 A Maxisum
Model for the Location of Undesirable Facilities 429 8.9 An Integrated
Location-Inventory Model 435 8.9.1 A Multiobjective
Location-Inventory/Covering Model 448 8.9.2 A Look at Aggregation Effects
452 8.10 Reliability and Facility Location Modeling 455 8.10.1 The Expected
Failure Case 458 8.10.2 Modeling a Malevolent Attacker 461 8.11 Summary 466
Exercises 468 9. Location Modeling in Perspective 480 9.1 Introduction 480
9.2 The Planning Process for Facility Location 481 9.2.1 Problem Definition
481 9.2.2 Analysis 483 9.2.3 Communication and Decision 489 9.2.4
Implementation 495 9.2.5 Caveats on the Planning Process 496 9.3 Summary
496 Exercises 497 References 499 Index 509 All referenced files may be
found at http://umich.edu/~msdaskin/discretelocation.
Introduction to Location Theory and Models 1 1.1 Introduction 1 1.2 Key
Questions Addressed by Location Models 3 1.3 Example Problem Descriptions 4
1.3.1 Ambulance Location 4 1.3.2 Siting Landfills for Hazardous Wastes 10
1.3.3 Summary 10 1.4 Key Dimensions of Location Problems and Models 11
1.4.1 Planar Versus Network Versus Discrete Location Models 11 1.4.2 Tree
Problems Versus General Graph Problems 12 1.4.3 Distance Metrics 13 1.4.4
Number of Facilities to Locate 14 1.4.5 Static Versus Dynamic Location
Problems 15 1.4.6 Deterministic Versus Probabilistic Models 16 1.4.7
Single- Versus Multiple-Product Models 16 1.4.8 Private Versus Public
Sector Problems 17 1.4.9 Single- Versus Multiple-Objective Problems and
Models 17 1.4.10 Elastic Versus Inelastic Demand 18 1.4.11 Capacitated
Versus Uncapacitated Facilities 18 1.4.12 Nearest Facility Versus General
Demand Allocation Models 18 1.4.13 Hierarchical Versus Single-Level Models
19 1.4.14 Desirable Versus Undesirable Facilities 19 1.5 ATaxonomy of
Location Models 20 1.5.1 Typology of Location Models 20 1.5.2 A Simple
Analytic Model 22 1.6 Summary 26 Exercises 27 2. Review of Linear
Programming 29 2.1 Introduction 29 2.2 The Canonical Form of a Linear
Programming Problem 31 2.3 Constructing the Dual of an LP Problem 34 2.4
Complementary Slackness and the Relationships Between the Primal and the
Dual Linear Programming Problems 36 2.5 Solving a Linear Programming
Problem in Excel 43 2.6 The Transportation Problem 47 2.7 The Shortest Path
Problem 64 2.7.1 The Shortest Path Problem in Excel 78 2.7.2 The Shortest
Path Problem in AMPL 80 2.8 The Out-of-Kilter Flow Algorithm 80 2.9 Integer
Programming Problems 92 2.10 Summary 96 Exercises 97 3. An Overview of
Complexity Analysis 111 3.1 Introduction 111 3.2 Basic Concepts and
Notation 112 3.3 Example Computation of an Algorithm's Complexity 115 3.4
The Classes P and NP (and NP-Hard and NP-Complete) 117 3.5 Summary 122
Exercises 123 4. Covering Problems 124 4.1 Introduction and the Notion of
Coverage 124 4.2 The Set Covering Model 125 4.3 Applications of the Set
Covering Model 137 4.4 Variants of the Set Covering Location Model 140 4.5
The Maximum Covering Location Model 143 4.5.1 The Greedy Adding Algorithm:
A Heuristic Algorithm for Solving the Maximum Covering Location Model 146
4.5.2 Lagrangian Relaxation: An Optimization-Based Heuristic Algorithm for
Solving the Maximum Covering Location Model 154 4.5.3 Other Solution
Approaches and Example Results 163 4.6 An Interesting Model Property or It
Ain't Necessarily So 164 4.7 The Maximum Expected Covering Location Model
168 4.8 Summary 174 Exercises 175 5. Center Problems 193 5.1 Introduction
193 5.2 Vertex P-Center Formulation 198 5.3 The Absolute 1- and 2-Center
Problems on a Tree 201 5.3.1 Absolute 1-Center on an Unweighted Tree 201
5.3.2 Absolute 2-Centers on an Unweighted Tree 205 5.3.3 Absolute 1-Center
on a Weighted Tree 206 5.4 The Unweighted Vertex P-Center Problem on a
General Graph 211 5.5 The Unweighted Absolute P-Center Problem on a General
Graph 215 5.5.1 Characteristics of the Solution to the Absolute P-Center
Problem 215 5.5.2 An Algorithm for the Unweighted Absolute P-Center on a
General Graph 219 5.6 Summary 229 Exercises 230 6. Median Problems 235 6.1
Introduction 235 6.2 Formulation and Properties 237 6.3 1-Median Problem on
a Tree 241 6.4 Heuristic Algorithms for the P-Median Problem 246 6.5 An
Optimization-Based Lagrangian Algorithm for the P-Median Problem 260 6.5.1
Methodological Development 260 6.5.2 Numerical Example 265 6.5.3 Extensions
and Enhancements to the Lagrangian Procedures 271 6.6 Computational Results
Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm 271
6.7 Another Interesting Property or It Still Ain't Necessarily So 277 6.8
Summary 283 Exercises 285 7. Fixed Charge Facility Location Problems 294
7.1 Introduction 294 7.2 Uncapacitated Fixed Charge Facility Location
Problems 297 7.2.1 Heuristic Construction Algorithms 298 7.2.2 Heuristic
Improvement Algorithms 305 7.2.3 A Lagrangian Relaxation Approach 311 7.2.4
A Dual-Based Approach 314 7.3 Capacitated Fixed Charge Facility Location
Problems 325 7.3.1 Lagrangian Relaxation Approaches 328 7.3.2 Bender's
Decomposition 345 7.4 Summary 355 Exercises 356 8. Extensions of Location
Models 362 8.1 Introduction 362 8.2 Multiobjective Problems 362 8.3
Hierarchical Facility Location Models 375 8.3.1 Basic Notions of
Hierarchical Facilities 375 8.3.2 Basic Median-Based Hierarchical Location
Formulations 379 8.3.3 Coverage-Based Hierarchical Location Formulations
383 8.3.4 Extensions of Hierarchical Location Formulations 385 8.4 Models
of Interacting Facilities 387 8.4.1 Flows Between Facilities 387 8.4.2
Facilities with Proximity Constraints 390 8.5 Multiproduct Flows and
Production/Distribution Systems 393 8.6 Location/Routing Problems 399 8.7
Hub Location Problems 410 8.8 Dispersion Models and Models for the Location
of Undesirable Facilities 425 8.8.1 Dispersion Models 426 8.8.2 A Maxisum
Model for the Location of Undesirable Facilities 429 8.9 An Integrated
Location-Inventory Model 435 8.9.1 A Multiobjective
Location-Inventory/Covering Model 448 8.9.2 A Look at Aggregation Effects
452 8.10 Reliability and Facility Location Modeling 455 8.10.1 The Expected
Failure Case 458 8.10.2 Modeling a Malevolent Attacker 461 8.11 Summary 466
Exercises 468 9. Location Modeling in Perspective 480 9.1 Introduction 480
9.2 The Planning Process for Facility Location 481 9.2.1 Problem Definition
481 9.2.2 Analysis 483 9.2.3 Communication and Decision 489 9.2.4
Implementation 495 9.2.5 Caveats on the Planning Process 496 9.3 Summary
496 Exercises 497 References 499 Index 509 All referenced files may be
found at http://umich.edu/~msdaskin/discretelocation.
1 Introduction to Location Theory and Models 1.1 INTRODUCTION 1.2 KEY QUESTIONS ADDRESSED BY LOCATION MODELS 1.3 EXAMPLE PROBLEM DESCRIPTIONS 1.3.1 Ambulance Location 1.3.2 Siting Landfills for Hazardous Wastes 1.3.3 Summary 1.4 KEY DIMENSIONS OF LOCATION PROBLEMS AND MODELS 1.4.1 Planar versus Network versus Discrete Location Models 1.4.2 Tree Problems versus General Graph Problems 1.4.3 Distance Metrics 1.4.4 Number of Facilities to Locate 1.4.5 Static versus Dynamic Location Problems 1.4.6 Deterministic versus Probabilistic Models 1.4.7 Single- versus Multiple-Product Models 1.4.8 Private versus Public Sector Problems 1.4.9 Single-versus Multiple-Objective Problems and Models 1.4.10 Elastic versus Inelastic Demand 1.4.11 Capacitated versus Uncapacitated Facilities 1.4.12 Nearest Facility versus General Demand Allocation Models 1.4.13 Hierarchical versus Single-Level Models 1.4.14 Desirable versus Undesirable Facilities 1.5 A TAXONOMY OF LOCATION MODELS 1.5.1 Typology of location models 1.5.2 A simple analytic model 1.6 SUMMARY 1.7 EXERCISES Figure 1.1 Typical tradeoff in maximum covering model Figure 1.2 Dispatching options in a multi-tiered system Figure 1.3 Example trees and graphs Figure 1.4 Alternative Taxonomy of Location Models Figure 1.5 Service area and directions of travel for a simple analytic location model Figure 1.6 Example service region subdivided into 9 subregions Figure 1.7 Typical cost components in a simple analytic model Figure 1.8 Ratio of actual to optimal cost versus ratio of actual to optimal number of facilities for the simple analytic model Table 1.1 Allowable range of alpha for various percentage errors in the optimal cost for the simple analytic model
Preface to the First and Second Editions xi Acknowledgments xvii 1.
Introduction to Location Theory and Models 1 1.1 Introduction 1 1.2 Key
Questions Addressed by Location Models 3 1.3 Example Problem Descriptions 4
1.3.1 Ambulance Location 4 1.3.2 Siting Landfills for Hazardous Wastes 10
1.3.3 Summary 10 1.4 Key Dimensions of Location Problems and Models 11
1.4.1 Planar Versus Network Versus Discrete Location Models 11 1.4.2 Tree
Problems Versus General Graph Problems 12 1.4.3 Distance Metrics 13 1.4.4
Number of Facilities to Locate 14 1.4.5 Static Versus Dynamic Location
Problems 15 1.4.6 Deterministic Versus Probabilistic Models 16 1.4.7
Single- Versus Multiple-Product Models 16 1.4.8 Private Versus Public
Sector Problems 17 1.4.9 Single- Versus Multiple-Objective Problems and
Models 17 1.4.10 Elastic Versus Inelastic Demand 18 1.4.11 Capacitated
Versus Uncapacitated Facilities 18 1.4.12 Nearest Facility Versus General
Demand Allocation Models 18 1.4.13 Hierarchical Versus Single-Level Models
19 1.4.14 Desirable Versus Undesirable Facilities 19 1.5 ATaxonomy of
Location Models 20 1.5.1 Typology of Location Models 20 1.5.2 A Simple
Analytic Model 22 1.6 Summary 26 Exercises 27 2. Review of Linear
Programming 29 2.1 Introduction 29 2.2 The Canonical Form of a Linear
Programming Problem 31 2.3 Constructing the Dual of an LP Problem 34 2.4
Complementary Slackness and the Relationships Between the Primal and the
Dual Linear Programming Problems 36 2.5 Solving a Linear Programming
Problem in Excel 43 2.6 The Transportation Problem 47 2.7 The Shortest Path
Problem 64 2.7.1 The Shortest Path Problem in Excel 78 2.7.2 The Shortest
Path Problem in AMPL 80 2.8 The Out-of-Kilter Flow Algorithm 80 2.9 Integer
Programming Problems 92 2.10 Summary 96 Exercises 97 3. An Overview of
Complexity Analysis 111 3.1 Introduction 111 3.2 Basic Concepts and
Notation 112 3.3 Example Computation of an Algorithm's Complexity 115 3.4
The Classes P and NP (and NP-Hard and NP-Complete) 117 3.5 Summary 122
Exercises 123 4. Covering Problems 124 4.1 Introduction and the Notion of
Coverage 124 4.2 The Set Covering Model 125 4.3 Applications of the Set
Covering Model 137 4.4 Variants of the Set Covering Location Model 140 4.5
The Maximum Covering Location Model 143 4.5.1 The Greedy Adding Algorithm:
A Heuristic Algorithm for Solving the Maximum Covering Location Model 146
4.5.2 Lagrangian Relaxation: An Optimization-Based Heuristic Algorithm for
Solving the Maximum Covering Location Model 154 4.5.3 Other Solution
Approaches and Example Results 163 4.6 An Interesting Model Property or It
Ain't Necessarily So 164 4.7 The Maximum Expected Covering Location Model
168 4.8 Summary 174 Exercises 175 5. Center Problems 193 5.1 Introduction
193 5.2 Vertex P-Center Formulation 198 5.3 The Absolute 1- and 2-Center
Problems on a Tree 201 5.3.1 Absolute 1-Center on an Unweighted Tree 201
5.3.2 Absolute 2-Centers on an Unweighted Tree 205 5.3.3 Absolute 1-Center
on a Weighted Tree 206 5.4 The Unweighted Vertex P-Center Problem on a
General Graph 211 5.5 The Unweighted Absolute P-Center Problem on a General
Graph 215 5.5.1 Characteristics of the Solution to the Absolute P-Center
Problem 215 5.5.2 An Algorithm for the Unweighted Absolute P-Center on a
General Graph 219 5.6 Summary 229 Exercises 230 6. Median Problems 235 6.1
Introduction 235 6.2 Formulation and Properties 237 6.3 1-Median Problem on
a Tree 241 6.4 Heuristic Algorithms for the P-Median Problem 246 6.5 An
Optimization-Based Lagrangian Algorithm for the P-Median Problem 260 6.5.1
Methodological Development 260 6.5.2 Numerical Example 265 6.5.3 Extensions
and Enhancements to the Lagrangian Procedures 271 6.6 Computational Results
Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm 271
6.7 Another Interesting Property or It Still Ain't Necessarily So 277 6.8
Summary 283 Exercises 285 7. Fixed Charge Facility Location Problems 294
7.1 Introduction 294 7.2 Uncapacitated Fixed Charge Facility Location
Problems 297 7.2.1 Heuristic Construction Algorithms 298 7.2.2 Heuristic
Improvement Algorithms 305 7.2.3 A Lagrangian Relaxation Approach 311 7.2.4
A Dual-Based Approach 314 7.3 Capacitated Fixed Charge Facility Location
Problems 325 7.3.1 Lagrangian Relaxation Approaches 328 7.3.2 Bender's
Decomposition 345 7.4 Summary 355 Exercises 356 8. Extensions of Location
Models 362 8.1 Introduction 362 8.2 Multiobjective Problems 362 8.3
Hierarchical Facility Location Models 375 8.3.1 Basic Notions of
Hierarchical Facilities 375 8.3.2 Basic Median-Based Hierarchical Location
Formulations 379 8.3.3 Coverage-Based Hierarchical Location Formulations
383 8.3.4 Extensions of Hierarchical Location Formulations 385 8.4 Models
of Interacting Facilities 387 8.4.1 Flows Between Facilities 387 8.4.2
Facilities with Proximity Constraints 390 8.5 Multiproduct Flows and
Production/Distribution Systems 393 8.6 Location/Routing Problems 399 8.7
Hub Location Problems 410 8.8 Dispersion Models and Models for the Location
of Undesirable Facilities 425 8.8.1 Dispersion Models 426 8.8.2 A Maxisum
Model for the Location of Undesirable Facilities 429 8.9 An Integrated
Location-Inventory Model 435 8.9.1 A Multiobjective
Location-Inventory/Covering Model 448 8.9.2 A Look at Aggregation Effects
452 8.10 Reliability and Facility Location Modeling 455 8.10.1 The Expected
Failure Case 458 8.10.2 Modeling a Malevolent Attacker 461 8.11 Summary 466
Exercises 468 9. Location Modeling in Perspective 480 9.1 Introduction 480
9.2 The Planning Process for Facility Location 481 9.2.1 Problem Definition
481 9.2.2 Analysis 483 9.2.3 Communication and Decision 489 9.2.4
Implementation 495 9.2.5 Caveats on the Planning Process 496 9.3 Summary
496 Exercises 497 References 499 Index 509 All referenced files may be
found at http://umich.edu/~msdaskin/discretelocation.
Introduction to Location Theory and Models 1 1.1 Introduction 1 1.2 Key
Questions Addressed by Location Models 3 1.3 Example Problem Descriptions 4
1.3.1 Ambulance Location 4 1.3.2 Siting Landfills for Hazardous Wastes 10
1.3.3 Summary 10 1.4 Key Dimensions of Location Problems and Models 11
1.4.1 Planar Versus Network Versus Discrete Location Models 11 1.4.2 Tree
Problems Versus General Graph Problems 12 1.4.3 Distance Metrics 13 1.4.4
Number of Facilities to Locate 14 1.4.5 Static Versus Dynamic Location
Problems 15 1.4.6 Deterministic Versus Probabilistic Models 16 1.4.7
Single- Versus Multiple-Product Models 16 1.4.8 Private Versus Public
Sector Problems 17 1.4.9 Single- Versus Multiple-Objective Problems and
Models 17 1.4.10 Elastic Versus Inelastic Demand 18 1.4.11 Capacitated
Versus Uncapacitated Facilities 18 1.4.12 Nearest Facility Versus General
Demand Allocation Models 18 1.4.13 Hierarchical Versus Single-Level Models
19 1.4.14 Desirable Versus Undesirable Facilities 19 1.5 ATaxonomy of
Location Models 20 1.5.1 Typology of Location Models 20 1.5.2 A Simple
Analytic Model 22 1.6 Summary 26 Exercises 27 2. Review of Linear
Programming 29 2.1 Introduction 29 2.2 The Canonical Form of a Linear
Programming Problem 31 2.3 Constructing the Dual of an LP Problem 34 2.4
Complementary Slackness and the Relationships Between the Primal and the
Dual Linear Programming Problems 36 2.5 Solving a Linear Programming
Problem in Excel 43 2.6 The Transportation Problem 47 2.7 The Shortest Path
Problem 64 2.7.1 The Shortest Path Problem in Excel 78 2.7.2 The Shortest
Path Problem in AMPL 80 2.8 The Out-of-Kilter Flow Algorithm 80 2.9 Integer
Programming Problems 92 2.10 Summary 96 Exercises 97 3. An Overview of
Complexity Analysis 111 3.1 Introduction 111 3.2 Basic Concepts and
Notation 112 3.3 Example Computation of an Algorithm's Complexity 115 3.4
The Classes P and NP (and NP-Hard and NP-Complete) 117 3.5 Summary 122
Exercises 123 4. Covering Problems 124 4.1 Introduction and the Notion of
Coverage 124 4.2 The Set Covering Model 125 4.3 Applications of the Set
Covering Model 137 4.4 Variants of the Set Covering Location Model 140 4.5
The Maximum Covering Location Model 143 4.5.1 The Greedy Adding Algorithm:
A Heuristic Algorithm for Solving the Maximum Covering Location Model 146
4.5.2 Lagrangian Relaxation: An Optimization-Based Heuristic Algorithm for
Solving the Maximum Covering Location Model 154 4.5.3 Other Solution
Approaches and Example Results 163 4.6 An Interesting Model Property or It
Ain't Necessarily So 164 4.7 The Maximum Expected Covering Location Model
168 4.8 Summary 174 Exercises 175 5. Center Problems 193 5.1 Introduction
193 5.2 Vertex P-Center Formulation 198 5.3 The Absolute 1- and 2-Center
Problems on a Tree 201 5.3.1 Absolute 1-Center on an Unweighted Tree 201
5.3.2 Absolute 2-Centers on an Unweighted Tree 205 5.3.3 Absolute 1-Center
on a Weighted Tree 206 5.4 The Unweighted Vertex P-Center Problem on a
General Graph 211 5.5 The Unweighted Absolute P-Center Problem on a General
Graph 215 5.5.1 Characteristics of the Solution to the Absolute P-Center
Problem 215 5.5.2 An Algorithm for the Unweighted Absolute P-Center on a
General Graph 219 5.6 Summary 229 Exercises 230 6. Median Problems 235 6.1
Introduction 235 6.2 Formulation and Properties 237 6.3 1-Median Problem on
a Tree 241 6.4 Heuristic Algorithms for the P-Median Problem 246 6.5 An
Optimization-Based Lagrangian Algorithm for the P-Median Problem 260 6.5.1
Methodological Development 260 6.5.2 Numerical Example 265 6.5.3 Extensions
and Enhancements to the Lagrangian Procedures 271 6.6 Computational Results
Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm 271
6.7 Another Interesting Property or It Still Ain't Necessarily So 277 6.8
Summary 283 Exercises 285 7. Fixed Charge Facility Location Problems 294
7.1 Introduction 294 7.2 Uncapacitated Fixed Charge Facility Location
Problems 297 7.2.1 Heuristic Construction Algorithms 298 7.2.2 Heuristic
Improvement Algorithms 305 7.2.3 A Lagrangian Relaxation Approach 311 7.2.4
A Dual-Based Approach 314 7.3 Capacitated Fixed Charge Facility Location
Problems 325 7.3.1 Lagrangian Relaxation Approaches 328 7.3.2 Bender's
Decomposition 345 7.4 Summary 355 Exercises 356 8. Extensions of Location
Models 362 8.1 Introduction 362 8.2 Multiobjective Problems 362 8.3
Hierarchical Facility Location Models 375 8.3.1 Basic Notions of
Hierarchical Facilities 375 8.3.2 Basic Median-Based Hierarchical Location
Formulations 379 8.3.3 Coverage-Based Hierarchical Location Formulations
383 8.3.4 Extensions of Hierarchical Location Formulations 385 8.4 Models
of Interacting Facilities 387 8.4.1 Flows Between Facilities 387 8.4.2
Facilities with Proximity Constraints 390 8.5 Multiproduct Flows and
Production/Distribution Systems 393 8.6 Location/Routing Problems 399 8.7
Hub Location Problems 410 8.8 Dispersion Models and Models for the Location
of Undesirable Facilities 425 8.8.1 Dispersion Models 426 8.8.2 A Maxisum
Model for the Location of Undesirable Facilities 429 8.9 An Integrated
Location-Inventory Model 435 8.9.1 A Multiobjective
Location-Inventory/Covering Model 448 8.9.2 A Look at Aggregation Effects
452 8.10 Reliability and Facility Location Modeling 455 8.10.1 The Expected
Failure Case 458 8.10.2 Modeling a Malevolent Attacker 461 8.11 Summary 466
Exercises 468 9. Location Modeling in Perspective 480 9.1 Introduction 480
9.2 The Planning Process for Facility Location 481 9.2.1 Problem Definition
481 9.2.2 Analysis 483 9.2.3 Communication and Decision 489 9.2.4
Implementation 495 9.2.5 Caveats on the Planning Process 496 9.3 Summary
496 Exercises 497 References 499 Index 509 All referenced files may be
found at http://umich.edu/~msdaskin/discretelocation.