Nickel / Puerto Location Theory

A Unified Approach
1. Auflage 2006
ISBN: 978-3-540-27640-1
Verlag: Springer Berlin Heidelberg
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 437 Seiten

Although modern location theory is now more than 90 years old, the focus of researchers in this area has been mainly problem oriented. However, a common theory, which keeps the essential characteristics of classical location models, is still missing. This monograph addresses this issue. A flexible location problem called the Ordered Median Problem (OMP) is introduced. For all three main subareas of location theory (continuous, network and discrete location) structural properties of the OMP are presented and solution approaches provided. Numerous illustrations and examples help the reader to become familiar with this new location model. By using OMP classical results of location theory can be reproved in a more general and sometimes even simpler way. Algorithms enable the reader to solve very flexible location models with a single implementation. In addition, the code of some algorithms is available for download.

Autoren/Hrsg.

Nickel, Stefan

Puerto, Justo

Inhaltsverzeichnis

1;Preface;7
2;Contents;9
3;List of Figures;15
4;List of Tables;19
5;List of Algorithms;21
6;Part I Location Theory and the Ordered Median Function;22
6.1;1 Mathematical Properties of the Ordered Median Function;24
6.1.1;1.1 Introduction;24
6.1.2;1.2 Motivating Example;25
6.1.3;1.3 The Ordered Median Function;27
6.1.4;1.4 Towards Location Problems;36
7;Part II The Continuous Ordered Median Location Problem;42
7.1;2 The Continuous Ordered Median Problem;43
7.1.1;2.1 Problem Statement;43
7.1.2;2.2 Distance Functions;47
7.1.3;2.3 Ordered Regions, Elementary Convex Sets and Bisectors;54
7.2;3 Bisectors;63
7.2.1;3.1 Bisectors - the Classical Case;63
7.2.2;3.2 Possible Generalizations;64
7.2.3;3.3 Bisectors - the General Case;66
7.2.4;3.4 Bisectors of Polyhedral Gauges;85
7.2.5;3.5 Bisectors of Elliptic Gauges;94
7.2.6;3.6 Bisectors of a Polyhedral Gauge and an Elliptic Gauge;103
7.2.7;3.7 Approximation of Bisectors;116
7.3;4 The Single Facility Ordered Median Problem;124
7.3.1;4.1 Solving the Single Facility OMP by Linear Programming;124
7.3.2;4.2 Solving the Planar Ordered Median Problem Geometrically;129
7.3.3;4.3 Non Polyhedral Case;136
7.3.4;4.4 Continuous OMPs with Positive and Negative Lambdas;142
7.3.5;4.5 Finding the Ordered Median in the Rectilinear Space;153
7.4;5 Multicriteria Ordered Median Problems;155
7.4.1;5.1 Introduction;155
7.4.2;5.2 Multicriteria Problems and Level Sets;156
7.4.3;5.3 Bicriteria Ordered Median Problems;157
7.4.4;5.4 The 3-Criteria Case;169
7.4.5;5.5 The Case Q > 3;176
7.4.6;5.6 Concluding Remarks;180
7.5;6 Extensions of the Continuous Ordered Median Problem;182
7.5.1;6.1 Extensions of the Single Facility Ordered Median Problem;182
7.5.2;6.2 Extension to the Multifacility Case;186
7.5.3;6.3 The Single Facility OMP in Abstract Spaces;191
7.5.4;6.4 Concluding Remarks;210
8;Part III Ordered Median Location Problems on Networks;212
8.1;7 The Ordered Median Problem on Networks;213
8.1.1;7.1 Problem Statement;213
8.1.2;7.2 Preliminary Results;216
8.1.3;7.3 General Properties;219
8.2;8 On Finite Dominating Sets for the Ordered Median Problem;225
8.2.1;8.1 Introduction;225
8.2.2;8.2 FDS for the Single Facility Ordered Median Problem;226
8.2.3;8.3 Polynomial Size FDS for the Multifacility Ordered Median Problem;230
8.2.4;8.4 On the Exponential Cardinality of FDS for the Multifacility Facility Ordered Median Problem;252
8.3;9 The Single Facility Ordered Median Problem on Networks;265
8.3.1;9.1 The Single Facility OMP on Networks: Illustrative Examples;266
8.3.2;9.2 The k-Centrum Single Facility Location Problem;270
8.3.3;9.3 The General Single Facility Ordered Median Problem on Networks;282
8.4;10 The Multifacility Ordered Median Problem on Networks;291
8.4.1;10.1 The Multifacility k-Centrum Problem;291
8.4.2;10.2 The Ordered p-Median Problem with .s-Vector .s = (a,M.s . . . , a, b, s . . ., b);297
8.4.3;10.3 A Polynomial Algorithm for the Ordered p-Median Problem on Tree Networks with .s-Vector, .s = (a,M.s . . . , a, b, s . . ., b);299
8.5;11 Multicriteria Ordered Median Problems on Networks;304
8.5.1;11.1 Introduction;304
8.5.2;11.2 Examples and Remarks;306
8.5.3;11.3 The Algorithm;308
8.5.4;11.4 Point Comparison;310
8.5.5;11.5 Segment Comparison;311
8.5.6;11.6 Computing the Set of E.cient Points Using Linear Programming;322
8.6;12 Extensions of the Ordered Median Problem on Networks;326
8.6.1;12.1 Notation and Model De.nitions;327
8.6.2;12.2 Tactical Subtree with Convex Ordered Median Objective;329
8.6.3;12.3 Strategic Subtree with Convex Ordered Median Objective;332
8.6.4;12.4 The Special Case of the Subtree k-Centrum Problem;335
8.6.5;12.5 Solving the Strategic Continuous Subtree k-Centrum Problem;340
8.6.6;12.6 Concluding Remarks;342
9;Part IV The Discrete Ordered Median Location Problem;343
9.1;13 Introduction and Problem Statement;344
9.1.1;13.1 De.nition of the Problem;345
9.1.2;13.2 A Quadratic Formulation for the Discrete;348
9.2;14 Linearizations and Reformulations;354
9.2.1;14.1 Linearizations of (OMP);354
9.2.2;14.2 Reformulations;367
9.2.3;14.3 Computational Results;385
9.3;15 Solution Methods;393
9.3.1;15.1 A Branch and Bound Method;393
9.3.2;15.2 Two Heuristic Approaches for the OMP;405
9.4;16 Related Problems and Outlook;430
9.4.1;16.1 The Discrete OMP;430
9.4.2;16.2 Conclusions and Further Research;433
10;References;434
11;Index;445