1 The Weber Problem .......................................... 1
Zvi Drezner, Kathrin Klamroth, Anita Schöbel,
George O. Wesolowsky
1.1 Introduction ............................................... 1
1.2 History and Literature Review .............................. 3
1.3 Solution Procedures ........................................ 6
1.4 Properties of the Weber Problem ........................... 11
1.5 Other Distance Measures ................................... 13
1.6 Multiple Facilities ....................................... 16
1.7 Restricted Weber Problems ................................. 18
1.8 Line Location and Dimensional Facilities .................. 20
1.9 Extensions ................................................ 23
1.10 Epilogue .................................................. 24
References ................................................ 24
2 Continuous Covering Location Problems ...................... 37
Frank Plastria
2.1 Introduction ............................................... 37
2.2 Full Covering .............................................. 45
2.3 Maximal Covering ........................................... 56
2.4 Empty Covering ............................................. 60
2.5 Minimal Covering ........................................... 63
2.6 Push-Puil Covering Models .................................. 64
2.7 Positioning Models ......................................... 65
2.8 Multiple Facility Covering Location Models ................. 65
2.9 Extensive Facility Covering Location Models ................ 69
References ................................................. 72
3 Discrete Network Location Models ........................... 81
John Current, Mark Daskin, David Schilling
3.1 Introduction ............................................... 81
3.2 Basic Facility Location Models ............................. 82
3.3 Location-Routing Models .................................... 95
3.4 Facility Location-Network Design Models .................... 96
3.5 Multiob jective Models ..................................... 96
3.6 Dynamic Location Models .................................... 98
3.7 Stochastic Location Models ................................. 98
3.8 Solution Approaches for Location Models ................... 101
3.9 Conclusions ............................................... 107
References ................................................ 108
4 Location Problems in the Public Sector .................... 119
Vladimir Marianov, Daniel Serra
4.1 Introduction .............................................. 119
4.2 Covering Models in the Public Sector ...................... 120
4.3 p-Median Models in Public Facility Location ............... 132
4.4 Conclusions ............................................... 142
References ................................................ 143
5 Consumers in Competitive Location Models .................. 151
Tammy Drezncr, H. A. Eiselt
5.1 Introduction .............................................. 151
5.2 Incorporating Facilities Features ......................... 155
5.3 The Lack of Rationality ................................... 160
5.4 More Complex Customer Behavior ............................ 164
5.5 Conclusions ............................................... 169
References ................................................ 169
6 An Efficient Genetic Algorithm for the p-Median Problem ... 179
Burçin Bozkaya, Jianjun Zhang, Erhan Erkut
6.1 Introduction .............................................. 179
6.2 The p-Median Problem ...................................... 180
6.3 Genetic Algorithms ........................................ 182
6.4 Review of the Relevant Literature ......................... 184
6.5 The Proposed Genetic Algorithm ............................ 186
6.6 Computational Study ....................................... 192
6.7 Conclusions ............................................... 202
References ................................................ 204
7 Demand Point Aggregation for Location Models .............. 207
Richard L. Francis, Timothy J. Lowe, Arie Tamir
7.1 Introduction .............................................. 207
7.2 The Aggregation Problem ................................... 208
7.3 Aggregation Error ......................................... 210
7.4 Guidelines for Aggregation ................................ 214
7.5 An Aggregation Algorithm .................................. 215
7.6 Computational Experience .................................. 219
7.7 Error Bound Generalizations ............................... 222
7.8 Summary ................................................... 229
References ................................................ 230
8 Location Software and Interface with GIS and Supply
Chain Management .......................................... 233
Thorsten Bender, Holger Hermes, Jörg Kalcsics,
M. Teresa Mela, Stefan Nickel
8.1 Introduction .............................................. 233
8.2 LoLA Library of Location Algorithms ..................... 235
8.3 LOLA goes GIS ............................................. 249
8.4 Supply Chain Management ................................... 255
8.5 Outlook ................................................... 271
References ................................................ 272
9 Telecommunication and Location ............................ 275
Eric Gourdin, Martine Labbé, Hande Yaman
9.1 Introduction .............................................. 275
9.2 Uncapacitated Models ...................................... 278
9.3 Capacitated Concentrator Location Problem ................. 288
9.4 Capacitated Models ........................................ 299
9.5 Dynamic Models ............................................ 301
References ................................................ 302
10 Reserve Design and Facility Siting ....................... 307
Charles ReVelle, Justin C. Williams
10.1 Introduction ............................................. 307
10.2 Set Covering Problems .................................... 308
10.3 Maximal Covering Problems ................................ 311
10.4 Redundant/Backup Coverage Problems ....................... 313
10.5 Chance Constrained Covering Models ....................... 316
10.6 Expected Covering Models ................................. 323
10.7 Conclusion ............................................... 326
References ............................................... 326
11 Facility Location Problems with Stochastic Demands and
Congestion ............................................... 329
Oded Berman, Dmitry Krass
11.1 Introduction ............................................. 329
11.2 Coverage Problems with Stochastic Demand and
Congestion ............................................... 339
11.3 Problems with Median-Type Objective: The Stochastic
Queue Model .............................................. 356
11.4 Conclusions and Open Problems ............................ 368
References ............................................... 369
12 Hub Location Problems .................................... 373
James F. Campbell, Andreas T. Ernst, Mohan Krishnamoorthy
12.1 Introduction ............................................. 373
12.2 Background ............................................... 374
12.3 Recent Trends ............................................ 381
12.4 Models and Taxonomy ...................................... 383
12.5 Applications ............................................. 388
12.6 Solving Hub Location Problems ............................ 393
12.7 Conclusions .............................................. 400
References ............................................... 402
13 Location and Robotics ................................... 409
Oliver Karch, Hartmut Noltemeier, Thomas Wahl
13.1 Introduction ............................................ 400
13.2 Related Problems ........................................ 410
13.3 A Short Overview of the Localization Problem ............ 410
13.4 Solving the Geometric Problem ........................... 413
13.5 A Sharper Bound for |EC| ................................ 417
13.6 Problems in Realistic Scenarios ......................... 422
13.7 Adaptation to Practice .................................. 424
13.8 Suitable Distances for d(S, V*) and D(V1*, V2*) .......... 420
13.9 Our Implementation RoLoPro .............................. 432
13.10 Experimental Tests ...................................... 435
13.11 Possible Enhancements to the Algorithms ................. 436
References .............................................. 430
14 The Quadratic Assignment Problem ......................... 439
Franz Rendl
14.1 Introductory Example ..................................... 439
14.2 Equivalent Formulations of QAP ........................... 440
14.3 Applications ............................................. 442
14.4 Computational Complexity of QAP .......................... 443
14.5 Relaxations of QAP ....................................... 443
14.6 Heuristics ............................................... 453
14.7 Computational Experience ................................. 454
14.8 Bibliographical Notes .................................... 455
References ............................................... 455
|
