Network and discrete location: models, algorithms, and applications

✍ Scribed by Mark S. Daskin

• Publisher: Wiley
• Year: 1995
• Tongue: English
• Leaves: 517
• Series: Wiley Series in Discrete Mathematics and Optimization
• Edition: 1
• Category: Library

✦ Synopsis

The comprehensive introduction to the art and science of locating facilities to make your organization more efficient, effective, and profitable. For the professional siting facilities, the task of translating organizational goals and objectives into concrete facilities requires a working familiarity with the theoretical and practical fundamentals of facility location planning and modeling. The first hands-on guide to using and developing facility location models, Network and Discrete Location offers a practiceoriented introduction to model-building methods and solution algorithms, complete with software to solve classical problems of realistic size and end-of-chapter exercises to enhance the reader's understanding. The text introduces the reader to the key classical location problems (covering, center, median, and fixed charge) which form the nucleus of facility location modeling. It also discusses real-life extensions of the basic models used in locating: production and distribution facilities, interacting services and facilities, and undesirable facilities. The book outlines a host of methodological tools for solving location models and provides insights into when each approach is useful and what information it provides. Designed to give readers a working familiarity with the basic facility location model types as well as an intuitive knowledge of the uses and limits of modeling techniques, Network and Discrete Location brings students and professionals alike swiftly from basic theory to technical fluency.

✦ Table of Contents

Contents......Page 8
Preface......Page 12
1.1. Introduction......Page 18
1.2 Key Questions Addressed by Location Models......Page 20
1.3 Example Problem Descriptions......Page 21
1.4 A Taxonomy of Location Problems and Models......Page 27
1.5 Summary......Page 35
Exercises......Page 36
2.2 The Canonical Form of a Linear Programming Problem......Page 37
2.3 Constructing the Dual of an LP Problem......Page 40
2.4 Complementary Slackness and the Relationships Between the Primal and the Dual Linear Programming Problems......Page 42
2.5 The Transportation Problem......Page 48
2.6 The Shortest Path Problem......Page 58
2.7 The Out-of-Kilter Flow Algorithm......Page 70
Exercises......Page 81
3.1 Introduction......Page 97
3.2 Basic Concepts and Notation......Page 98
3.3 Example Computation of an Algorithm’s Complexity......Page 101
3.4 The Classes Ñ and NP (and NP-Hard and NP-Complete)......Page 102
3.5 Summary......Page 106
H Longitudes......Page 0
4.2 The Set Covering Model......Page 109
4.3 Applications of the Set Covering Model......Page 122
4.4 Variants of the Set Covering Location Model......Page 124
4.5 The Maximum Covering Location Model......Page 127
4.6 The Maximum Expected Covering Location Model......Page 147
4.7 Summary......Page 151
Exercises......Page 152
5.1 Introduction......Page 171
5.2 Vertex P-Center Formulation......Page 177
5.3 The Absolute 1- and 2-Center Problems on a Tree......Page 179
5.4 The Unweighted Vertex P-Center Problem on a General Graph......Page 190
5.5 The Unweighted Absolute P-Center Problem on a General Graph......Page 193
Exercises......Page 208
6.1 Introduction......Page 215
6.2 Formulation and Properties......Page 217
6.3 1-Median Problem on a Tree......Page 220
6.4 Heuristic Algorithms for the P-Median Problem......Page 225
6.5 An Optimization-Based Lagrangian Algorithm for the PMedian Problem......Page 238
6.6 Computational Results Using the Heuristic Algorithms and the Lagrangian Relaxation Algorithm......Page 249
6.7 Summary......Page 253
Exercises......Page 255
7.1 Introduction......Page 264
7.2 Uncapacitated Fixed Charge Facility Location Problems......Page 267
7.3 Capacitated Fixed Charge Facility Location Problems......Page 292
7.4 Summary......Page 319
Exercises......Page 320
8.2 Multiobjective Problems......Page 326
8.3 Hierarchical Facility Location Problems......Page 334
8.4 Models of Interacting Facilities......Page 345
8.5 Multiproduct Flows and Production/Distribution Systems......Page 350
8.6 Location/Routing Problems......Page 356
8.7 Hub Location Problems......Page 366
8.8 Dispersion Models and Models for the Location of Undesirable Facilities......Page 380
8.9 Summary......Page 390
Exercises......Page 391
9.2 The Planning Process for Facility Location......Page 400
9.3 Summary......Page 415
Exercises......Page 416
A SITATION Operations Guide......Page 418
B NET-SPEC Operations Guide......Page 463
C MOD-DIST Operations Guide......Page 467
D COLORSET Operations Guide......Page 476
E MENU-OKF Operations Guide......Page 480
F PRINTER.CNS File Description......Page 491
References......Page 500
Author Index......Page 508
Subject Index......Page 511