Location Theory (eBook)

A Unified Approach

Stefan Nickel, Justo Puerto (Autoren)

eBook Download: PDF

2006
XXII, 437 Seiten
Springer Berlin (Verlag)
978-3-540-27640-1 (ISBN)

Infos

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.

Inhalt

Preface 7
Contents 9
List of Figures 15
List of Tables 19
List of Algorithms 21
Part I Location Theory and the Ordered Median Function 22
1 Mathematical Properties of the Ordered Median Function 24
1.1 Introduction 24
1.2 Motivating Example 25
1.3 The Ordered Median Function 27
1.4 Towards Location Problems 36
Part II The Continuous Ordered Median Location Problem 42
2 The Continuous Ordered Median Problem 43
2.1 Problem Statement 43
2.2 Distance Functions 47
2.3 Ordered Regions, Elementary Convex Sets and Bisectors 54
3 Bisectors 63
3.1 Bisectors - the Classical Case 63
3.2 Possible Generalizations 64
3.3 Bisectors - the General Case 66
3.4 Bisectors of Polyhedral Gauges 85
3.5 Bisectors of Elliptic Gauges 94
3.6 Bisectors of a Polyhedral Gauge and an Elliptic Gauge 103
3.7 Approximation of Bisectors 116
4 The Single Facility Ordered Median Problem 124
4.1 Solving the Single Facility OMP by Linear Programming 124
4.2 Solving the Planar Ordered Median Problem Geometrically 129
4.3 Non Polyhedral Case 136
4.4 Continuous OMPs with Positive and Negative Lambdas 142
4.5 Finding the Ordered Median in the Rectilinear Space 153
5 Multicriteria Ordered Median Problems 155
5.1 Introduction 155
5.2 Multicriteria Problems and Level Sets 156
5.3 Bicriteria Ordered Median Problems 157
5.4 The 3-Criteria Case 169
5.5 The Case Q > 3
5.6 Concluding Remarks 180
6 Extensions of the Continuous Ordered Median Problem 182
6.1 Extensions of the Single Facility Ordered Median Problem 182
6.2 Extension to the Multifacility Case 186
6.3 The Single Facility OMP in Abstract Spaces 191
6.4 Concluding Remarks 210
Part III Ordered Median Location Problems on Networks 212
7 The Ordered Median Problem on Networks 213
7.1 Problem Statement 213
7.2 Preliminary Results 216
7.3 General Properties 219
8 On Finite Dominating Sets for the Ordered Median Problem 225
8.1 Introduction 225
8.2 FDS for the Single Facility Ordered Median Problem 226
8.3 Polynomial Size FDS for the Multifacility Ordered Median Problem 230
8.4 On the Exponential Cardinality of FDS for the Multifacility Facility Ordered Median Problem 252
9 The Single Facility Ordered Median Problem on Networks 265
9.1 The Single Facility OMP on Networks: Illustrative Examples 266
9.2 The k-Centrum Single Facility Location Problem 270
9.3 The General Single Facility Ordered Median Problem on Networks 282
10 The Multifacility Ordered Median Problem on Networks 291
10.1 The Multifacility k-Centrum Problem 291
10.2 The Ordered p-Median Problem with .s-Vector .s = (a,M.s . . . , a, b, s . . ., b) 297
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
11 Multicriteria Ordered Median Problems on Networks 304
11.1 Introduction 304
11.2 Examples and Remarks 306
11.3 The Algorithm 308
11.4 Point Comparison 310
11.5 Segment Comparison 311
11.6 Computing the Set of E.cient Points Using Linear Programming 322
12 Extensions of the Ordered Median Problem on Networks 326
12.1 Notation and Model De.nitions 327
12.2 Tactical Subtree with Convex Ordered Median Objective 329
12.3 Strategic Subtree with Convex Ordered Median Objective 332
12.4 The Special Case of the Subtree k-Centrum Problem 335
12.5 Solving the Strategic Continuous Subtree k-Centrum Problem 340
12.6 Concluding Remarks 342
Part IV The Discrete Ordered Median Location Problem 343
13 Introduction and Problem Statement 344
13.1 De.nition of the Problem 345
13.2 A Quadratic Formulation for the Discrete 348
14 Linearizations and Reformulations 354
14.1 Linearizations of (OMP) 354
14.2 Reformulations 367
14.3 Computational Results 385
15 Solution Methods 393
15.1 A Branch and Bound Method 393
15.2 Two Heuristic Approaches for the OMP 405
16 Related Problems and Outlook 430
16.1 The Discrete OMP 430
16.2 Conclusions and Further Research 433
References 434
Index 445

Produkt-Details

• Erscheint lt. Verlag: 16.1.2006
• Zusatzinfo: XXII, 437 p.
• Verlagsort: Berlin
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Mathematik
• Themenwelt: Sozialwissenschaften ► Politik / Verwaltung
• Themenwelt: Technik
• Themenwelt: Wirtschaft ► Allgemeines / Lexika
• Themenwelt: Wirtschaft ► Betriebswirtschaft / Management ► Planung / Organisation
• Themenwelt: Wirtschaft ► Volkswirtschaftslehre
• Schlagworte: algorithms • Computational Geometry • linear optimization • Location Analysis • logistics • Mathematical Programming • Operations Research
• ISBN-10: 3-540-27640-8 / 3540276408
• ISBN-13: 978-3-540-27640-1 / 9783540276401