Part I Location Theory and the Ordered Median Function
1. Mathematical Properties of the Ordered Median Function ....... 3
1.1. Introduction ............................................... 3
1.2. Motivating Example ......................................... 4
1.3. The Ordered Median Function ................................ 6
1.4. Towards Location Problems ................................. 15
Part II The Continuous Ordered Median Location Problem
2. The Continuous Ordered Median Problem ....................... 23
2.1. Problem Statement ......................................... 23
2.2. Distance Functions ........................................ 27
2.2.1. The Planar Case .................................... 31
2.3. Ordered Regions, Elementary Convex Sets and Bisectors ..... 34
2.3.1. Ordered Regions .................................... 34
2.3.2. Ordered Elementary Convex Sets ..................... 35
2.3.3. Bisectors .......................................... 39
3. Bisectors ................................................... 43
3.1. Bisectors - the Classical Case ............................ 43
3.2. Possible Generalizations .................................. 44
3.3. Bisectors - the General Case .............................. 46
3.3.1. Negative Results ................................... 47
3.3.2. Structural Properties .............................. 48
3.3.3. Partitioning of Bisectors .......................... 59
3.4. Bisectors of Polyhedral Gauges ............................ 65
3.5. Bisectors of Elliptic Gauges .............................. 74
3.6. Bisectors of a Polyhedral Gauge and an Elliptic Gauge ..... 83
3.7. Approximation of Bisectors ................................ 96
4. The Single Facility Ordered Median Problem ................. 105
4.1. Solving the Single Facility OMP by Linear Programming .... 105
4.2. Solving the Planar Ordered Median Problem
Geometrically ............................................ 110
4.3. Non Polyhedral Case ...................................... 117
4.4. Continuous OMPs with Positive and Negative Lambdas ....... 123
4.4.1. The Algorithms .................................... 127
4.5. Finding the Ordered Median in the Rectilinear Space ...... 134
5. Multicriteria Ordered Median Problems ...................... 137
5.1. Introduction ............................................. 137
5.2. Multicriteria Problems and Level Sets .................... 138
5.3. Bicriteria Ordered Median Problems ....................... 139
5.4. The 3-Criteria Case ...................................... 151
5.5. The Case Q > 3 ........................................... 158
5.6. Concluding Remarks ....................................... 162
6. Extensions of the Continuous Ordered Median Problem ........ 165
6.1. Extensions of the Single Facility Ordered Median
Problem .................................................. 165
6.1.1. Restricted Case ................................... 165
6.2. Extension to the Multifacility Case ...................... 169
6.2.1. The Non-Interchangeable Multifacility Model ....... 170
6.2.2. The Indistinguishable Multifacility Model ......... 172
6.3. The Single Facility OMP in Abstract Spaces ............... 174
6.3.1. Preliminary Results ............................... 176
6.3.2. Analysis of the Optimal Solution Set .............. 185
6.3.3. The Convex OMP and the Single Facility
Location Problem in Normed Spaces ................. 189
6.4. Concluding Remarks ....................................... 193
Part III Ordered Median Location Problems on Networks
7. The Ordered Median Problem on Networks ..................... 197
7.1. Problem Statement ........................................ 197
7.2. Preliminary Results ...................................... 200
7.3. General Properties ....................................... 203
8. On Finite Dominating Sets for the Ordered Median
Problem .................................................... 209
8.1. Introduction ............................................. 209
8.2. FDS for the Single Facility Ordered Median Problem ....... 210
8.3. Polynomial Size FDS for the Multifacility Ordered
Median Problem ........................................... 214
8.3.1. An FDS for the Multifacility Ordered Median
Problem when a = λ1 = ... = λk ≠ λk+1 = ... =
λм = b ............................................ 215
8.3.2. An FDS for the Ordered 2-Median Problem with
General Nonnegative λ-Weights ..................... 225
8.4. On the Exponential Cardinality of FDS for the
Multifacility Facility Ordered Median Problem ............ 236
8.4.1. Some Technical Results ............................ 239
8.4.2. Main Results ...................................... 245
9. The Single Facility Ordered Median Problem on Networks ..... 249
9.1. The Single Facility OMP on Networks: Illustrative
Examples ................................................. 250
9.2. The k-Centrum Single Facility Location Problem ........... 254
9.3. The General Single Facility Ordered Median Problem
on Networks .............................................. 266
9.3.1. Finding the Single Facility Ordered Median
of a General Network .............................. 267
9.3.2. Finding the Single Facility Ordered Median
of a Tree ......................................... 269
10. The Multifacility Ordered Median Problem on Networks ...... 275
10.1.The Multifacility /c-Centrum Problem ..................... 275
10.2.The Ordered p-Median Problem with As-Vector
 ...................................... 281
10.3.A Polynomial Algorithm for the Ordered p-Median Problem
on Tree Networks with As-Vector, ..... 283
11.Multicriteria Ordered Median Problems on Networks .......... 289
11.1.Introduction ............................................. 289
11.2.Examples and Remarks ..................................... 291
11.3.The Algorithm ............................................ 293
11.4.Point Comparison ......................................... 295
11.5.Segment Comparison ....................................... 296
11.6.Computing the Set of Efficient Points Using Linear
Programming .............................................. 307
12.Extensions of the Ordered Median Problem on Networks ....... 311
12.1.Notation and Model Definitions ........................... 312
12.2.Tactical Subtree with Convex Ordered Median Objective .... 314
12.2.1.Finding an Optimal Tactical Subedge ............... 314
12.2.2.Finding an Optimal Tactical Continuous Subtree
Containing a Given Node ........................... 315
12.3.Strategic Subtree with Convex Ordered Median Objective ... 317
12.3.1.Finding an Optimal Strategic Subedge .............. 318
12.3.2.Finding an Optimal Strategic Continuous
Subtree Containing a Given Node ................... 318
12.3.3.Submodularity of Convex Ordered Median
Functions ......................................... 318
12.4.The Special Case of the Subtree k-Centrum Problem ........ 320
12.4.1.Nestedness Property for the Strategic and
Tactical Discrete k-Centrum Problems .............. 321
12.4.2.A Dynamic Programming Algorithm for the
Strategic Discrete Subtree k-Centrum Problem ...... 322
12.5.Solving the Strategic Continuous Subtree k-Centrum
Problem .................................................. 325
12.6.Concluding Remarks ....................................... 327
Part IV The Discrete Ordered Median Location Problem
13.Introduction and Problem Statement ......................... 331
13.1.Definition of the Problem ................................ 332
13.2.A Quadratic Formulation for the Discrete OMP ............. 335
13.2.1.Sorting as an Integer Linear Program (ILP) ........ 336
13.2.2.Formulation of the Location-Allocation
Subproblem ........................................ 337
13.2.3.Quadratic Integer Programming Formulation
for OMP ........................................... 339
14.Linearizations and Reformulations .......................... 341
14.1.Linearizations of (OMP) .................................. 341
14.1.1.A First Linearization: (OMP1) ..................... 341
14.1.2.A Linearization Using Less Variables: (OMP2) ...... 346
14.1.3.Simplifying Further: (OMP3) ....................... 349
14.1.4.Comparison Between (OMP2) and (OMP3) .............. 352
14.2.Reformulations ........................................... 354
14.2.1.Improvements for (OMP1) ........................... 356
14.2.2.Improvements for (OMP3) ........................... 362
14.2.3.Improvements for (OMP2) ........................... 368
14.2.4.Comparison Between (OMP2*) and (OMP3*) ............ 371
14.3.Computational Results .................................... 372
15.Solution Methods ........................................... 381
15.1.A Branch and Bound Method ................................ 381
15.1.1.Combinatorial Lower Bounds ........................ 382
15.1.2.Branching ......................................... 387
15.1.3.Numerical Comparison of the Branching Rules ....... 389
15.1.4.Computational Results ............................. 390
15.2.Two Heuristic Approaches for the OMP ..................... 393
15.2.1.An Evolution Program for the OMP .................. 393
15.2.2.A Variable Neighborhood Search for the OMP ........ 399
15.2.3.Computational Results ............................. 407
16.Related Problems and Outlook ............................... 419
16.1 The Discrete OMP with  ............................. 419
16.1.1.Problem Formulation ............................... 419
16.1.2.Computational Results ............................. 421
16.2 Conclusions and Further Research ......................... 422
References .................................................... 423
Index ......................................................... 435
|
