Location science

Preface......Page 5
Contents......Page 6
 1.1 Introduction......Page 17
 1.2 The Roots......Page 18
 1.3 Towards a New Science......Page 23
 1.4 Purpose and Structure of This Book......Page 25
 1.5 How to Use This Book......Page 26
 References......Page 35
Part I Basic Concepts......Page 38
  2.1 Introduction......Page 39
  2.2 Applications......Page 42
  2.3 Integer Programming Formulations for the p-Median Problem......Page 43
  2.4 Optimal Solution Procedures......Page 49
  2.5 Polyhedral Properties......Page 52
  2.6 p-Median Problem on a Graph and Additional Polyhedral Results......Page 53
  2.7 Heuristics......Page 57
   2.7.1 Classical Heuristics......Page 58
   2.7.2 Metaheuristics......Page 59
  2.8 Conclusions......Page 61
  References......Page 62
  3.1 Introduction......Page 65
  3.2 Polynomial Cases, Complexity and Approximation Results......Page 67
  3.3 Exact Methods......Page 68
  3.4 Heuristics......Page 72
  3.5 Variants......Page 73
   3.5.1 The Capacitated p-Center Problem......Page 74
   3.5.3 The Continuous p-Center Problem......Page 75
  3.6 Conclusions......Page 76
  References......Page 77
  4.1 Introduction......Page 80
  4.2 Overview and Modeling Issues......Page 82
   4.2.1 Set Partitioning Formulation of FLPs......Page 86
  4.3 Solution Algorithms for Fixed-Charge Facility Location......Page 87
   4.3.1 Lagrangean Relaxation......Page 88
   4.3.2 The Pricing Problem for SPSFLP......Page 90
  4.4 The Uncapacitated Facility Location Problem......Page 91
   4.4.1 Bounds for UFLP Derived from LP Duality......Page 92
   4.4.2 The UFLP as the Optimization of a Supermodular Set Function......Page 95
  4.5 Polyhedral Analysis of the UFLP......Page 99
   4.5.2 Valid Inequalities and Facets......Page 101
   4.5.3 Lifting Procedures......Page 104
  4.6 Conclusions......Page 105
  References......Page 106
  5.1 Introduction......Page 112
  5.2 Models......Page 114
  5.3 Theoretical Results......Page 121
  5.4 Solution Methods......Page 123
  5.5 Approximate Algorithms......Page 124
  5.6 Lagrangian Relaxation......Page 125
  5.7 Continuous Covering Location Problems......Page 128
  References......Page 129
Part II Advanced Concepts......Page 133
  6.1 Introduction......Page 134
   6.2.1 Individual-Facility Interactions......Page 136
   6.2.2 Facility-Facility Interactions......Page 141
   6.2.3 The Anti-covering Model......Page 142
  6.3 Computational Approach......Page 143
  6.4 Numerical Examples......Page 145
  6.5 Conclusions......Page 148
  References......Page 149
  7.1 Introduction......Page 153
  7.2 Location of Dimensional Facilities......Page 154
  7.3 Locating Lines and Hyperplanes......Page 156
   7.3.1 Applications......Page 157
    7.3.2.1 Distances Between Points and Hyperplanes......Page 158
    7.3.2.2 Dual Interpretation......Page 159
    7.3.3.1 Minsum Hyperplane Location with Vertical Distance......Page 161
    7.3.3.2 Minsum Hyperplane Location with Norm Distance......Page 163
    7.3.3.3 Minsum Hyperplane Location with Gauge Distance......Page 164
    7.3.4.2 The Finite Dominating Set Property......Page 165
    7.3.5.2 Linear Programming for Hyperplane Location with Vertical and Block Norm Distance......Page 167
    7.3.5.3 Enhancing the Enumeration for Line Location with Euclidean Distance......Page 169
   7.3.6 Ordered Median Line and Hyperplane Location Problem......Page 170
    7.3.7.1 Obnoxious Line and Hyperplane Location......Page 171
    7.3.7.2 Locating p Lines or Hyperplanes......Page 172
  7.4 Locating Circles and Spheres......Page 174
   7.4.1 Applications......Page 175
   7.4.2 Distances Between Points and Hyperspheres......Page 176
   7.4.3 The Minsum Hypersphere Location Problem......Page 177
    7.4.3.2 Location of Minsum Circles and Hyperspheres with Block Norm Distance......Page 179
    7.4.4.1 Relation to Minimal Covering Annulus Problem and Equity Problem......Page 181
    7.4.4.3 Location of a Minmax Circle with Rectangular Distance......Page 182
    7.4.5.1 Minimizing the Sum of Squared Distances......Page 183
    7.4.5.3 Location of a Circle with Fixed Radius......Page 184
    7.4.5.4 Locating a Hypersphere of One Norm Measuring Distances with Respect to Another Norm......Page 185
   7.5.2 The Widest Empty 1-Corner Corridor in the Plane......Page 186
   7.5.3 Two-Dimensional Facilities......Page 187
   7.5.4 General Approaches for Locating Dimensional Facilities......Page 188
  7.6 Conclusions......Page 189
  References......Page 190
  8.1 Introduction......Page 195
  8.2 Uncertainty Issues......Page 196
  8.3 Robust Facility Location Problems......Page 197
  8.4 Stochastic Facility Location Problems......Page 204
  8.5 Chance-Constrained Facility Location Problems......Page 213
  8.6 Challenges and Further Readings......Page 215
   8.6.1 Multi-Stage Stochastic Programming Models......Page 216
   8.6.2 Algorithms......Page 217
   8.6.3 Scenario Generation......Page 218
  8.7 Conclusions......Page 219
  References......Page 220
  9.1 Introduction......Page 224
  9.2 1-Facility Planar/Continuous Location Problems......Page 226
   9.2.1 Polyhedral Planar Minisum Location Problems......Page 232
    9.2.1.1 Bicriteria Case......Page 234
    9.2.1.2 Three-Criteria Case......Page 239
    9.2.1.3 Case Where Q>3......Page 242
   9.2.2 Other References in Continuous Multicriteria Location Problems......Page 244
    9.3.1.1 Pareto Locations in General Networks......Page 245
    9.3.1.2 Bi-Criteria Case......Page 248
    9.3.1.3 Q-Criteria Case......Page 256
    9.3.1.4 Multicriteria Median Problems on a Tree......Page 257
  9.4 Discrete Location Problems......Page 261
   9.4.1  Model and Notation......Page 262
   9.4.2 Determining the Entire Set of Pareto-Optimal Solutions......Page 263
   9.4.3 Determining Supported Pareto-Optimal Solutions......Page 265
   9.4.4 Other References in Discrete Location Problems......Page 266
  References......Page 267
  10.1 Introduction......Page 270
  10.2 The Ordered Median Function......Page 272
   10.3.1 The Single Facility Polyhedral Ordered Median Location Problem......Page 275
   10.3.2 Generalized Continuous Ordered Median Location Problems......Page 281
  10.4 The Ordered Median Problem on Networks......Page 287
   10.4.1 The Single Facility Ordered Median Problem......Page 290
   10.4.2 The p-Facility Ordered Median Problem......Page 293
    10.4.2.1 A Finite Set of Candidates for the Two Facility Case......Page 295
    10.4.2.2 A Discouraging Result for the p-Facility Case......Page 298
   10.5.1 A Three-Index Formulation......Page 301
   10.5.2 A Covering Formulation and Some Properties......Page 303
  10.6 Conclusions......Page 306
  References......Page 309
  11.1 Introduction......Page 312
  11.2 Continuous Problems......Page 313
  11.3 Network Problems......Page 316
  11.4 Discrete Problems......Page 318
  11.5 Modular Construction of Intrinsic Multi-Period Facility Location Models......Page 321
  11.6 The Value of the Multi-Period Solution......Page 330
  11.7 Conclusions......Page 332
  References......Page 333
  12.1 Introduction......Page 336
  12.2 Fundamentals......Page 338
   12.2.1 Features, Assumptions and Properties......Page 339
   12.2.2 Supermodular Properties......Page 342
   12.2.3 Objectives......Page 343
   12.3.1 Single Assignments......Page 345
   12.3.2 Multiple Assignments......Page 347
   12.4.1 Hub Network Topologies......Page 350
   12.4.2 Modeling Flow Costs......Page 352
   12.4.3 Capacitated Models......Page 354
   12.4.4 Uncertainty in Hub Location......Page 355
   12.4.5 Dynamic and Multi-Modal Models......Page 357
   12.4.6 Competition and Collaboration......Page 358
   12.5.1 Complexity Results......Page 361
   12.5.2 Heuristic Algorithms......Page 362
   12.5.3 Lower Bounding Procedures and Exact Algorithms......Page 363
  12.6 Conclusions......Page 365
  References......Page 366
  13.1 Introduction......Page 373
   13.2.1 Nature of Demand......Page 375
   13.2.2 Service Availability......Page 376
   13.2.3 Flow Pattern and Spatial Configuration......Page 377
   13.2.4 Decisions and Objectives......Page 378
   13.2.5 Classification Scheme......Page 379
   13.3.1 Health Care Systems......Page 380
   13.3.3 Telecommunications Systems......Page 381
   13.3.5 Air Transportation Systems......Page 382
  13.4 Families of Hierarchical Facility Location Problems......Page 383
   13.4.1 Multi-Level Facility Location Problems......Page 384
   13.4.2 Median and Covering Hierarchical Location Problems......Page 387
   13.4.3 Multi-Echelon Location-Routing Problems......Page 389
   13.4.4 Hierarchical Hub Location Problems......Page 391
  13.5 Conclusions......Page 393
  References......Page 394
  14.1 The Basic Model: The First 50 Years......Page 398
  14.2 Elements of Competitive Location Models......Page 403
  14.3 Consumer Behavior in Competitive Location Models......Page 406
  14.4 Results for Different Behavioral Assumptions......Page 411
   14.4.2 UD1a, Linear Market, von Stackelberg Solution......Page 412
   14.4.3 UD1a, Plane, Nash Equilibrium......Page 413
   14.4.4 UD1a, Plane, von Stackelberg Solution......Page 414
   14.4.6 UD1a, Networks, von Stackelberg Solution......Page 415
   14.4.7 UD1b, Linear Market, Nash Equilibria......Page 417
   14.4.8 UD1b, Plane, Nash Equilibria......Page 419
   14.4.10 UD1, Linear Market, Nash Equilibria......Page 420
   14.4.11 UD1, Linear Market, von Stackelberg Solution......Page 421
   14.4.13 UD1, Plane, von Stackelberg Solution......Page 422
   14.4.15 UD2a, Plane, von Stackelberg Solution......Page 423
   14.4.18 UD2b, Plane, von Stackelberg Solution......Page 424
   14.4.20 UP1, Linear Market, Nash Equilibria......Page 425
   14.4.22 UP1, Network, Nash Equilibria......Page 426
   14.4.25 UP2, Network, von Stackelberg Solution......Page 427
  14.5 Summary, Extensions, and Outlook......Page 428
   References......Page 429
  15.1 Introduction......Page 437
  15.2 Problem Definition and Notation......Page 439
  15.3 Formulations and Exact Algorithms......Page 441
   15.3.1 Flow Formulations......Page 442
   15.3.2 Set-Partitioning Formulations......Page 445
   15.3.3 Valid Inequalities......Page 447
  15.4 Heuristic Algorithms......Page 450
  15.5 Location-Arc Routing......Page 452
  15.6 Conclusions......Page 454
  References......Page 455
  16.1 Introduction......Page 458
  16.2 From Logistics to Location Models......Page 460
   16.2.1 Why Logistics Matters in Location Modeling......Page 461
   16.2.2 Building Blocks of Logistics......Page 462
    16.2.2.1 Procurement......Page 463
    16.2.2.4 Routing and Distribution......Page 464
   16.3.1 Notation......Page 465
   16.3.2 The BILL Model......Page 466
  16.4 Challenges in Industrial Logistics......Page 469
   16.4.2 Uncertainty, Risk and Disaster Events......Page 470
   16.4.3 Digital Supply Chain Transformation and Supply Chain Integration......Page 471
   16.5.1 Reverse Logistics......Page 472
   16.5.2 Supply Chain Risk......Page 476
  16.6 Conclusions......Page 479
  References......Page 480
  17.1 Introduction......Page 482
   17.2.1 Customers......Page 485
   17.2.2 Facilities......Page 486
   17.2.3 Costs, Revenues, and Constraints......Page 490
    17.2.3.1 Travel Cost and Coverage Constraints......Page 491
    17.2.3.2 Congestion Costs and Service Level Constraints......Page 492
    17.2.3.4 Revenues and Overall Objectives......Page 498
  17.3 Customer Response: Demand Levels and Allocations......Page 499
   17.3.1 Customer Utility Functions......Page 500
    17.3.2.1 Customer Reaction Models with Deterministic Utility 1: Models with Allocation-Only Reaction (AR)......Page 502
    17.3.2.2 Customer Reaction Models with Deterministic Utility 2: Models with Demand-Only Reaction (DR)......Page 507
    17.3.2.3 Customer Reaction Models with Deterministic Utility 3: Full Response Models (FR)......Page 509
    17.3.2.4 Proportional Allocation (PA) Models......Page 510
  17.4 General SLCIS Model Specification......Page 513
   17.5.1 Coverage-Type (CT) Models......Page 515
   17.5.2 Service-Objective (SO) Models......Page 527
   17.5.3 Balanced-Objective (BO) Models......Page 528
   17.5.4 Explicit Customer Response (ECR) Models......Page 531
   17.5.5 Proportional Allocation (PA) Models......Page 534
  17.6 Conclusions......Page 536
  References......Page 538
  18.1 Introduction......Page 541
  18.2 Terminology and Examples......Page 543
  18.3 Case Study......Page 545
  18.4 Aggregation Error Measures......Page 550
  18.5 Error Bounds......Page 555
  References......Page 558
Part III Applications......Page 561
  19.1 Introduction......Page 562
  19.2 Overview of GIS......Page 563
   19.2.1 GIS Software......Page 565
  19.3 Generalities on Facility Location Problems......Page 567
  19.4 Interconnections Between Location Science and GIS: Emerging Trends......Page 570
   19.4.1 Location Modeling with Spatio-Temporal Big Data......Page 571
   19.4.2 GIS Tools Integration to Data Analytics Libraries......Page 573
   19.4.3 GIS as Interactive DSS......Page 575
  19.5 Using GIS in Location Science Applications......Page 576
  19.6 Conclusions......Page 586
  References......Page 588
  20.1 Sustainability and ``Green'' in Location Problems......Page 594
  20.2 Environmental Considerations in Location Problems......Page 596
   20.2.1 Accounting for Emissions in Facility Location Problems......Page 598
  20.3 Reverse Logistics Network Design......Page 601
   20.3.1 A Generic Reverse Logistics Network Design Model......Page 603
   20.3.2 Extensions......Page 605
  20.4 Location Problems Related to Alternative Fuel Vehicles......Page 607
  20.5 Research Prospects......Page 609
  References......Page 610
  21.1 General Description of Humanitarian Supply Chains......Page 614
   21.1.1 International and Regional Distribution Centers......Page 615
   21.1.2 Dispensing Points......Page 617
   21.1.3 Transportation Flows......Page 618
  21.2 Humanitarian Facility Location Problems......Page 619
   21.2.2 Locations in Local Humanitarian Supply Chains......Page 620
   21.2.3 General Overview......Page 622
   21.3.1 Notation......Page 623
   21.3.2 Basic Mathematical Model......Page 624
   21.4.1 Location and Prepositioning......Page 626
   21.4.2 Location-Routing Problems......Page 629
  References......Page 630
  22.1 Introduction......Page 633
  22.2 Notation......Page 635
  22.3 Identifying Critical Facilities: Interdiction Models......Page 636
  22.4 Hardening Facilities: Protection Models......Page 639
   22.5.1 Planning Against Worst-Case Disruptions......Page 643
   22.5.2 Planning Against Random Disruptions......Page 646
   22.5.3 Planning Against Specific Disruption Scenarios......Page 649
  22.6 Future Trends......Page 652
  References......Page 654
  23.1 Introduction......Page 659
   23.2.1 Objective Functions in Healthcare Facility Location......Page 660
   23.2.2 An Overview of Healthcare Facility Location Models......Page 663
    23.2.2.1 Modeling Capacity......Page 664
    23.2.2.2 Assumptions on Allocation......Page 665
    23.2.2.3 Assumptions on Demand and Patient Choice......Page 666
    23.2.2.4 Assumptions on Facility Types and Patient Flows: Hierarchical Models......Page 667
    23.2.2.5 Modeling Dynamic Aspects of Location Decisions......Page 669
    23.2.2.6 Further Reading......Page 670
   23.3.1 The Strategic and Tactical Level: Finding Ambulance Base Locations and Assigning Ambulances......Page 671
    23.3.1.1 A Double Coverage Model......Page 672
    23.3.1.2 Considering Ambulance Utilization......Page 674
   23.3.2 The Operational Level: Ambulance Relocation......Page 675
    23.3.2.1 Ambulance Preparedness......Page 676
  23.4 Hospital Layout Planning......Page 677
   23.4.1 The Quadratic Assignment Problem......Page 678
   23.4.2 A Mixed-Integer Programming Formulation......Page 679
   23.4.3 Further Reading......Page 681
  23.5 Conclusions......Page 682
  References......Page 683
  24.1 Introduction......Page 689
  24.2 Objectives and Network Assessment......Page 692
   24.3.1 Location of a Single Alignment......Page 696
   24.3.2 Rapid Transit Network Design......Page 698
  24.4 Location of Stations......Page 699
  24.5 Conclusions......Page 701
  References......Page 702
  25.1 Introduction......Page 706
   25.2.1 Political Districting......Page 708
   25.2.2 Sales Territory Design......Page 710
   25.2.3 Service Districting......Page 712
   25.3.1 Basic Units......Page 714
   25.3.2 Districts......Page 715
   25.4.2 Balance......Page 716
    25.4.3.1 Graph-Based Measures......Page 718
    25.4.3.2 Geometric Measures......Page 719
    25.4.3.3 Mathematical Modelling......Page 720
    25.4.4.1 Geometric Measures......Page 722
    25.4.4.2 Distance-Based Measures......Page 723
   25.4.5 District Center......Page 726
  25.5 Solution Approaches......Page 727
   25.5.1 Location-Allocation Methods......Page 728
   25.5.2 Exact Methods......Page 730
   25.5.3 Computational Geometry Methods......Page 731
   25.5.4 Construction Methods......Page 733
    25.5.5.1 Greedy Randomized Adaptive Search Procedure (GRASP)......Page 734
    25.5.5.2 Tabu Search (TS)......Page 736
    25.5.5.3 Simulated Annealing (SA)......Page 737
    25.5.5.4 Genetic Algorithm (GA)......Page 738
    25.5.5.5 Hybrid and Miscellaneous Approaches......Page 739
  25.6 Conclusions......Page 740
  References......Page 741
  26.1 Introduction......Page 745
  26.2 Bike Sharing......Page 746
  26.3 Location Decisions in Public Transport......Page 747
  26.4 Electric Vehicle Charging Station Location......Page 749
  26.5 Spatial Planning for Health Care Facilities......Page 754
  26.6 School Location......Page 759
  26.7 Summary......Page 761
  References......Page 762
About the Editors......Page 765