Single-Facility Location Problems with Barriers

Preface......Page 6
Contents......Page 10
1 Measuring Distances......Page 16
1.1 Norms and Metrics......Page 17
1.2 General Gauges and Polyhedral Distance Functions......Page 19
1.3 Polyhedral Gauges in R[sup(2)]......Page 21
1.4 Relations Between Block Norms and the Manhattan Norm......Page 25
2 Shortest Paths in the Presence of Barriers......Page 28
2.1 Shortest Paths and the Concept of Visibility......Page 29
2.2 Optimality Conditions for Smooth Barriers......Page 33
2.3 Piecewise Linear Paths for Polyhedral Barriers......Page 43
2.4 Shortest Paths in the Plane with Polyhedral Barriers......Page 45
2.5 Shortest Paths and Polyhedral Gauges in the Plane......Page 48
3.1 Location Problems Without Barriers......Page 52
3.2 Introducing Barriers to Location Modeling......Page 55
3.3 The Visibility Graph......Page 60
4 Bounds for Location Problems with Barriers......Page 62
4.1 Lower Bounds......Page 63
4.2 Upper Bounds......Page 65
5 Planar Location Problems with Polyhedral Barriers......Page 70
5.1 Interrelations Between Barrier Problems and Unconstrained Location Problems......Page 71
5.2 The Iterative Convex Hull......Page 80
5.3 Algorithmic Consequences......Page 83
5.4 Mixed-Integer Programming Formulations......Page 87
5.5 Weber Objective Functions......Page 90
5.6 Multifacility Weber Problems......Page 92
5.7 Related Problems......Page 95
6 Location Problems with a Circular Barrier......Page 98
6.1 Properties of the Objective Function......Page 99
6.2 Algorithms and Heuristics......Page 109
7 Weber Problems with a Line Barrier......Page 114
7.1 Line Barriers with One Passage......Page 121
7.2 Line Barriers with Two Passages......Page 122
7.3 Line Barriers with N Passages, N > 2......Page 125
7.4 Example......Page 128
8 Weber Problems with Block Norms......Page 134
8.1 Constructing a Finite Dominating Set......Page 136
8.2 Generalization to Polyhedral Gauges......Page 144
9 Center Problems with the Manhattan Metric......Page 148
9.1 A Cell Decomposition of the Feasible Region......Page 149
9.2 Constructing a Dominating Set......Page 152
9.3 Algorithmic Consequences......Page 160
9.4 Extension to Block Norms......Page 163
10 Multicriteria Location Problems with Polyhedral Barriers......Page 166
10.1 Properties of the Objective Function......Page 168
10.2 Methodology for Bicriteria Problems......Page 172
10.3 An Example Problem with a Line Barrier......Page 178
11.1 Problem Formulation......Page 186
11.2 Mathematical Model: A Weber Problem with a Line Barrier......Page 189
11.3 Solution......Page 191
11.4 Alternative Models......Page 193
References......Page 196
E......Page 212
P......Page 213
W......Page 214