Preface ......................................................... v
I. Introduction and General Results ........................... 1
1. Measuring Distances ......................................... 3
1.1. Norms and Metrics ..................................... 4
1.2. General Gauges and Polyhedral Distance Functions ...... 6
1.3. Polyhedral Gauges in R2 ............................... 8
1.4. Relations Between Block Norms and the Manhattan
Norm ................................................. 12
2. Shortest Paths in the Presence of Barriers ................. 15
2.1. Shortest Paths and the Concept of Visibility ......... 16
2.2. Optimality Conditions for Smooth Barriers ............ 20
2.3. Piecewise Linear Paths for Polyhedral Barriers ....... 30
2.4. Shortest Paths in the Plane with Polyhedral
Barriers ............................................. 32
2.5. Shortest Paths and Polyhedral Gauges in the Plane .... 35
3. Location Problems with Barriers: Basic Concepts and
Literature Review .......................................... 39
3.1. Location Problems Without Barriers ................... 39
3.2. Introducing Barriers to Location Modeling ............ 42
3.3. The Visibility Graph ................................. 47
4. Bounds for Location Problems with Barriers ................. 49
4.1. Lower Bounds ......................................... 50
4.2. Upper Bounds ......................................... 52
II. Solution Methods for Specially Shaped Barriers ............ 55
5. Planar Location Problems with Polyhedral Barriers .......... 57
5.1. Interrelations Between Barrier Problems and
Unconstrained Location Problems ...................... 58
5.2. The Iterative Convex Hull ............................ 67
5.3. Algorithmic Consequences ............................. 70
5.4. Mixed-Integer Programming Formulations ............... 74
5.5. Weber Objective Functions ............................ 77
5.6. Multifacility Weber Problems ......................... 79
5.7. Related Problems ..................................... 82
6. Location Problems with a Circular Barrier .................. 85
6.1. Properties of the Objective Function ................. 86
6.2. Algorithms and Heuristics ............................ 96
7. Weber Problems with a Line Barrier ........................ 101
7.1. Line Barriers with One Passage ...................... 108
7.2. Line Barriers with Two Passages ..................... 109
7.3. Line Barriers with N Passages, N > 2 ................ 112
7.4. Example ............................................. 115
III. Solution Methods for Special Distance and
Objective Functions ...................................... 119
8. Weber Problems with Block Norms ........................... 121
8.1. Constructing a Finite Dominating Set ................ 123
8.2. Generalization to Polyhedral Gauges ................. 131
9. Center Problems with the Manhattan Metric ................. 135
9.1. A Cell Decomposition of the Feasible Region ......... 136
9.2. Constructing a Dominating Set ....................... 139
9.3. Algorithmic Consequences ............................ 147
9.4. Extension to Block Norms ............................ 150
10. Multicriteria Location Problems with Polyhedral
Barriers .................................................. 153
10.1. Properties of the Objective Function ................ 155
10.2. Methodology for Bicriteria Problems ................. 159
10.3. An Example Problem with a Line Barrier .............. 165
IV. Application .............................................. 171
11. Location with Barriers Put to Work in Practice ............ 173
11.1. Problem Formulation ................................. 173
11.2. Mathematical Model: A Weber Problem with a Line
Barrier ............................................. 176
11.3. Solution ............................................ 178
11.4. Alternative Models .................................. 180
References .................................................... 183
Index ......................................................... 199
|
