Search and Find
Service
Contents
6
Introduction
8
References
11
1 Distance Functions in Location Problems
12
1.1 Distance and Norms Specifications
13
1.2 Distances Function
13
1.3 Different Kinds of Distances
15
1.3.1 Aisle Distance
15
1.3.2 Distance Matrix
15
1.3.3 Minimum Lengths Path
16
1.3.4 Block Distance
16
1.3.5 Gauges Measures
17
1.3.6 Variance of Distances
18
1.3.7 Hilbert Curve
18
1.3.8 Mahalanobis Distance
19
1.3.9 Hamming Distance
19
1.3.10 Levenshtein Distance
19
1.3.11 Hausdorff Distance
20
1.4 Summary
23
References
23
2 An Overview of Complexity Theory
25
2.1 Advantage of Complexity Theory
26
2.1.1 Computational Complexity
26
2.2 Abstract Models of Computation: Abstract Machines
26
2.2.1 Preliminary Definitions
26
2.2.2 Turing Machine Models
27
2.3 Big-O Notation (Wood 1987)
28
2.3.1 Example
29
2.4 Time Complexity
30
2.4.1 Constant Time
30
2.4.2 Linear Time (Sipser 1996)
30
2.4.3 Polynomial Time (Papadimitriou 1994)
30
2.4.4 Exponential Time (Sipser 1996)
31
2.5 Decision Problems
31
2.6 Reduction
31
2.6.1 Linear Reduction
32
2.6.2 Polynomial Reduction
32
2.6.3 Polynomial Reduction: Many-One Polynomially Reducible
32
2.7 Examples
32
2.7.1 Traveling Salesman Optimization Problem
33
2.7.2 Satisfiability Problem
33
2.7.3 Hamiltonian Cycle Problem
34
2.7.4 Clique Problem
34
2.8 Complexity Classes
34
2.8.1 Class P
34
2.8.2 Class NP
35
2.8.3 Class NP-Complete
37
2.8.4 Class NP-Hard
40
2.9 Further Reading
41
References
41
3 Single Facility Location Problem
43
3.1 Problem Formulation
44
3.1.1 A General Formulation of the Problem
44
3.1.2 Rectilinear Distance with Point Facilities
45
3.1.3 Square Euclidean Distance with Point Facilities
46
3.1.4 Euclidean Distance with Point Facilities
46
3.1.5 LP-Norm Distance with Point Facilities
46
3.1.6 Regional Facilities Problem (Drezner 1986)
47
3.2 Solution Techniques
48
3.2.1 Techniques for Discrete Space Location Problems
48
(Heragu 1997)
48
3.2.2 Techniques for Continues Space Location Problems
50
3.3 Case Study (Heragu 1997)
72
References
74
4 Multifacility Location Problem
75
4.1 Applications and Classifications
75
4.2 Models
76
4.2.1 MiniSum
76
4.2.2 MiniMax
81
4.2.3 Other Models
83
4.3 Solution Techniques
87
4.3.1 MiniSum
87
4.3.2 MiniMax
94
4.3.3 Solution Techniques for other Models
95
4.3.4 Some Heuristic and Metaheuristic Methods
95
4.4 Case Study
96
References
96
5 Location Allocation Problem
99
5.1 Classification of Location-Allocation Problem
99
5.1.1 Classifications of Facilities
100
5.1.2 Classified on the Physical Space or Locations
100
5.1.3 Classifications of the Demand
100
5.2 Models
101
5.2.1 General LA Model (Cooper 1963)
101
5.2.2 LA Model Each Customer Covered by Only One Facility
102
5.2.3 LA Model with FacilityÌs Opening Cost
103
5.2.4 Capacitated LA Model with Stochastic Demands
104
(Zhou and Liu 2003)
104
5.3 Solution Techniques
105
5.3.1 Exact Solutions (Cooper 1963)
106
5.3.2 Heuristic Methods
107
Procedure 1
110
Procedure 2
111
5.3.3 Metaheuristic Methods (Salhi and Gamal 2003)
111
5.4 Case Study
111
5.4.1 A Facility Location Allocation Model for Reusing Carpet
112
Materials (Louwers et al. 1999)
112
5.4.2 A New Organ Transplantation Location-Allocation Policy
113
(Bruni et al. 2006)
113
References
114
6 Quadratic Assignment Problem
116
6.1 Formulations of QAP
119
6.1.1 Integer Programming Formulations (ILP)
119
6.1.2 Mixed Integer Programming Formulations (MILP)
121
6.1.3 Formulation by Permutations
123
6.1.4 Trace Formulation
124
6.1.5 Graph Formulation
124
6.2 QAP Related Problems
125
6.2.1 The Quadratic Bottleneck Assignment Problem (QBAP)
125
6.2.2 The Biquadratic Assignment Problem (BiQAP)
125
6.2.3 The Quadratic Semi-Assignment Problem (QSAP)
126
6.2.4 The Multiobjective QAP (MQAP)
126
6.2.5 The Quadratic Three-Dimensional Assignment Problem
127
(Q3AP)
127
6.2.6 The Generalized Quadratic Assignment Problem (GQAP)
128
6.2.7 Stochastic QAP (SQAP)
129
6.3 Solution Techniques
130
6.3.1 Computational Complexity
130
6.3.2 Lower Bounds
130
6.3.3 Exact Algorithms
133
6.3.4 Heuristic Algorithms
134
6.3.5 Metaheuristic Algorithms
135
6.3.6 Comparing QAP Algorithms
139
6.4 Case Study
140
6.4.1 Hospital Layout as a Quadratic Assignment Problem
140
(Elshafei 1977)
140
6.4.2 Backboard Wiring Problem (Steinberg 1961)
141
6.4.3 Minimizing WIP Inventories (Benjaafar 2002)
141
6.4.4 Zoning in Forest (Bos 1993)
142
6.4.5 Computer Motherboard Design Problem (Miranda 2005)
142
References
142
7 Covering Problem
149
7.1 Problem Formulation
150
7.2 Total Covering Problem
151
7.2.1 Maximizing the Number of Points Covered More than Once
153
7.2.2 Multiple Total Covering Problems (Mirchandani et al. 1990)
153
7.2.3 Total Covering Problem with the Preference of Selecting
154
Location of Existing Facilities (Daskin 1995)
154
7.2.4 Total Edge Covering Problem (Daskin 1995)
155
7.2.5 Notes on Total Covering Problems
157
7.3 Partial Covering Problem
159
7.3.1 Minimizing Costs Arisen from Not Covering Demand Points
160
(Mirchandani and Francis 1990)
160
7.3.2 Minimizing Costs of Locating Facilities and Costs Arisen
160
from Not Covering Demand Points
160
7.3.3 Maximum Covering Location Problems (Berman
161
et al. 2003)
161
7.3.4 Expected Maximum Covering Problem (Daskin 1995)
162
7.3.5 Maximum Covering Problem Considering Non-Ascending
164
Coverage Function (Berman et al. 2003)
164
7.4 The Bi-Objective Covering Tour Problem (Jozefowieza
166
et al. 2007)
166
7.5 A Fuzzy Multi Objective Covering Based Vehicle Location
167
Model for Emergency Services (Araz et al. 2007)
167
7.6 Solving Methods
169
7.6.1 Exact Methods
169
7.6.2 Heuristic Methods
176
7.6.3 Metaheuristic Methods
177
7.7 Case Study
177
7.7.1 Combination of MCDM and Covering Techniques
177
(Farahani and Asgari 2007)
177
References
180
8 Median Location Problem
181
8.1 Classification
182
8.1.1 1-Median
182
8.1.2 P-Median
182
8.1.3 An Example
182
8.2 Mathematical Models
183
8.2.1 Classic Model
183
8.2.2 Capacitated Plant Location Problem Model (CPLPM)
184
8.2.3 Capacitated P-median Problem (Lorenaa 2004)
186
8.3 Solution Techniques
187
8.3.1 Lemma
188
8.3.2 Solving 1-Median Problem Algorithm on Tree
188
(Goldman 1971)
188
8.3.3 Exact Methods
189
8.3.4 Heuristic Algorithms
189
8.3.5 Metaheuristic Algorithms
190
8.4 Comparison of Methods
191
8.5 Studying Statically the Methods for Solutions of Median
191
Problem (Reese 2005)
191
8.5.1 Classification of Solving Methods by Period
192
8.5.2 Classification of Different Solving Methods
192
8.6 Case Study
192
8.6.1 Post Center Locations (Alba and Dominquez 2006)
192
8.6.2 Entrance Exam Facilities (Correa et al. 2004)
193
8.6.3 Polling Station Location (Ghiani et al. 2002)
193
References
194
9 Center Problem
196
9.1 Applications and Classifications
197
9.1.1 K-Network P-Center Problem
198
9.1.2
198
Facility
198
-Centdian Problem
198
9.1.3
198
Centrum Multi-Facility Problem
198
9.1.4 P-Center Problem with Pos/Neg Weights
199
9.1.5 Anti P-Center Problem
199
9.1.6 Continuous P-Center Problem
199
9.1.7 Asymmetric P-Center Problem
199
9.2 Models
199
9.2.1 Vertex P-Center Problem
199
9.2.2 Vertex P-Center Problem with Demand-Weighted Distance
201
9.2.3 Capacitated Vertex P-Center Problem
201
9.3 Exact Solution Approaches
202
9.3.1 Center Problems on a Tree Network
202
9.3.2 Center Problems on a General Graph
210
9.4 Approximate Solution Approaches
217
9.5 Case Study
218
9.5.1 A Health Resource Case (Pacheco and Casado 2005)
218
References
219
10 Hierarchical Location Problem
221
10.1 Applications and Classifications
222
10.2 Flow-Based Hierarchical Location Problem
224
10.2.1 Flow-Based Formulation for Single-Flow Systems (S ahin
224
and S ural 2007)
224
10.2.2 Flow-Based Formulation for Multi-Flow Systems (S ahin
226
and S ural 2007)
226
10.3 Median-Based Hierarchical Location Problem
227
(Daskin 1995)
227
10.3.1 Median-Based Formulation for Globally Inclusive Service
227
Hierarchies
227
10.3.2 Median-Based Formulation for Locally Inclusive Service
229
Hierarchies
229
10.3.3 Median-Based Formulation for Successively Exclusive
230
Service Hierarchies
230
10.4 Coverage-Based Hierarchical Location Problem
230
(Daskin 1995)
230
10.4.1 Hierarchical Maximal Covering Location Problem
231
10.4.2 Hierarchical Maximal Covering Location Problem
232
with Covering all Kinds of Demands
232
10.5 Median-Based Hierarchical Relocation Problem (Teixeira
234
and Antunes 2008)
234
10.5.1 Median-Based Hierarchical Relocation Problem
234
with Closest Assignment
234
10.5.2 Median-Based Hierarchical Relocation Problem with Path
236
Assignment
236
10.6 Solving Algorithms for Hierarchical Location Problem
237
10.7 Case Study
240
10.7.1 A Hierarchical Model for the Location of Maternity
240
Facilities in the Municipality of Rio de Janeiro
240
(Galv Ú ao et al. 2002 and 2006)
240
10.7.2 Locational Analysis for Regionalization of Turkish Red
240
Crescent Blood Services (S ahin et al. 2007)
240
10.7.3 School Network Planning in Coimbra, Portugal (Teixeira
241
and Antunes 2008)
241
References
241
11 Hub Location Problem
244
11.1 Applications and Classifications
246
11.2 Models
248
11.2.1 Single Hub Location Problem (OÌKelly 1987)
248
11.2.2 P-Hub Location Problem (OÌKelly 1987)
250
11.2.3 Multiple Allocation P-Hub Location Model (P-Hub
252
Median Location Model) (Campbell 1991)
252
11.2.4 P-Hub Median Location Problem with Fixed Costs
253
(OÌ Kelly 1992)
253
11.2.5 Single Spoke Assignment P-Hub Median Location
254
Problem (Single Allocation P-Hub Location Problem)
254
(Daskin 1995)
254
11.2.6 The Extension Model of Fixed Cost for Connecting
256
a Spoke to a Hub (Campbell 1994)
256
11.2.7 Minimum Value Flow on any Spoke/Hub Connection
257
Problem (Campbell 1994)
257
11.2.8 Capacity Limitation of Hub Location Problem
258
(Campbell 1994)
258
11.2.9 P-Hub Center Location Problem (Campbell 1994)
259
11.2.10 Hub Covering Location Problem (Campbell 1994)
260
11.3 Solution Techniques
262
11.3.1 Various Kinds of Algorithms
262
11.3.2 Some Relevant Algorithms
266
11.4 Case Study
267
11.4.1 The Policy of Open Skies in the Middle East
268
(Adler and Hashai 2005)
268
11.4.2 A Hub Port in the East Coast of South America (Aversa
268
et al. 2005)
268
11.4.3 A Hub Model in Brunswick, Canada (Eiselt 2007)
268
11.4.4 A Hub/Spoke Network in Brazil (Cunha and Silva 2007)
269
References
269
12 Competitive Location Problem
272
12.1 Applications and Classifications
272
12.1.1 Game Theories (Winston and Wayne 1995)
275
12.1.2 Static Competition
277
12.1.3 Competition with Foresight
277
12.1.4 Dynamic Models and Competitive Equilibrium
277
12.1.5 Point vs. Regional Demand
278
12.1.6 Patronizing Behavior
278
12.1.7 Attraction Function
279
12.1.8 Decision Space
280
12.2 Models
281
12.2.1 Gravity Problem
281
12.2.2 The Maximum Capture Problem Model (MAXCAP)
284
(Serra and ReVelle 1995)
284
12.2.3 The Maximum Capture Problem with Price Model
286
(PMAXCAP) (Serra and ReVelle 1998)
286
12.2.4 Flow Capturing Location Allocation Problem Model
289
(FCLAP)
289
12.3 Case Study
292
12.3.1 A Case in Toronto (Aboolian et al. 2006)
292
12.3.2 A Case in Yuanlin Taiwan (Wu and Lin 2003)
293
References
294
13 Warehouse Location Problem
296
13.1 Classifications
297
13.2 Models
298
13.2.1 Warehouse Location Problem without Fixed
298
Installation Costs (William et al. 1958)
298
13.2.2 Warehouse Location Problem with Fixed Cost
300
of Establishment (Akinc and Khumawala 1977)
300
13.2.3 Capacitated Warehouse Location Problem with
302
Constraints in Customers Being Serviced (Nagy 2004)
302
13.2.4 Single Stage Capacitated Warehouse Location Model
303
(Sharma and Berry 2007)
303
13.2.5 Redesigning a Warehouse Network (Melachrinoudis
306
and Min 2007)
306
13.3 Solution Methods
310
13.3.1 Exact Solution Methods
310
13.3.2 Heuristic and Metaheuristic Methods
311
13.4 Case Study
313
13.4.1 Redesigning a Warehouse Network
313
(Melachrinoudis and Min 2007)
313
13.4.2 Warehouse Location Problems for Air Freight Forwarders
313
(Wan et al. 1998)
313
References
314
14 Obnoxious Facility Location
316
14.1 Applications and Classifications
317
14.1.1 Applications
317
14.1.2 Revolution of Undesirable Facility Problem
317
14.1.3 Classification of Undesirable Facility Problems
319
14.2 Models
320
14.2.1 Dispersion Problem (Daskin 1995)
320
14.2.2 Undesirable Facility Location Problem (Daskin 1995)
321
14.2.3 Hazardous Materials Routing Problem
324
14.2.4 Obnoxious Facilities Location-Routing Problem
332
14.2.5 Multiobjective Obnoxious Facilities Location Problem
338
(Rakas et al. 2004)
338
14.3 Solutions and Techniques
340
14.4 Case Study
342
14.4.1 Obnoxious Facility Location and Routing in Anatolian
342
Region of Turkey (Alumur and Kara 2007)
342
14.4.2 Designing Emergency Response Network for Hazardous
343
Materials Transportation (Berman et al. 2007)
343
14.4.3 Locating Waste Pipelines to Minimize their Impact
343
on Marine Environment (Ceceres et al. 2007)
343
References
344
15 Dynamic Facility Location Problem
347
15.1 Classifications
348
15.2 Mathematical Formulations
349
15.2.1 Static Model (Wesolowsky 1973)
349
15.2.2 Dynamic P-Median Model (Owen and Daskin 1998)
350
15.2.3 Multiperiod Model (Wesolowsky and Truscott 1975)
352
15.2.4 Probabilistic Model (Rosental et al. 1978)
353
15.3 Solution Techniques
354
15.3.1 Fundamental Lemmas
355
15.3.2 Single Relocation at Discrete Time
356
15.3.3 Multiple Relocations at Discrete Times
357
Without Relocation Costs (Z.-Farahani et al. 2009)
357
15.3.4 Multiple Relocations at Discrete Times
358
with Relocation Costs
358
15.3.5 Complete Enumeration
359
15.3.6 Non-Duplicating Enumeration
359
15.3.7 Incomplete DP
360
15.3.8 An Especial BIP
360
15.3.9 Relocation at Continues Times
364
15.3.10 Iterative Algorithm for Obtaining Optimal Solution
367
15.3.11 Static Stochastic Techniques
368
15.4 Case Study
369
15.4.1 A Dynamic Model for School Network Planning (Antunes
370
and Peeters 2000)
370
15.4.2 A Multiperiod Set Covering for Dynamic Redeployment
370
of Ambulances (Rajagopalan et al. 2008)
370
15.4.3 A Multi-period Model for Combat Logistics (Gue 2003)
371
References
372
16 Multi-Criteria Location Problem
373
16.1 Applications and Classifications
374
16.2 Models
375
16.2.1 Private and Public Facilities
375
16.2.2 Balancing Objective Functions
376
16.2.3 Pull, Push and PullÒPush Objectives
377
16.2.4 Mathematical Models
379
16.3 Solution Techniques
383
16.3.1 The MCDM Techniques
383
16.3.2 Metaheuristics for the MODM
385
16.3.3 Multi-Objective Combinatorial Optimization
385
16.4 Case Study
386
16.4.1 LRP (Lin and kwok 2006)
386
16.4.2 Facility Layout (Chiang et al. 2006)
387
16.4.3 Fire Station Locations
388
16.4.4 The 2-Facility Centdian Network Problem (Perez-Brito
389
et al. 1998)
389
16.4.5 Military Logistics (Z-Farahani and Asgari 2007)
390
16.4.6 A Paper Recycling System (Pati et al. 2008)
390
References
391
17 Location-Routing Problem
394
17.1 An Introduction to VRP
394
17.1.1 Definition of VRP
394
17.1.2 The Traveling Salesman Problem
397
17.1.3 A Classification of Capacitated VRP
397
17.2 LRP
398
17.2.1 Applications of LRP
400
17.2.2 Classifications of LRP
401
17.3 Models
405
17.3.1 Classifications
405
17.3.2 Mathematical Models
406
17.4 Solution Techniques
411
17.4.1 Heuristic Methods
411
17.4.2 Metaheuristic Methods
412
17.5 Case Study
412
17.5.1 Bill Delivery Services (Lin et al. 2002)
412
17.5.2 Contaminated Waste Disposal (Caballero et al. 2007)
413
17.5.3 Logistics System (Lin and Kwok 2006)
414
References
414
18 Storage System Layout
417
18.1 Assumptions and Classifications
418
18.2 Storage Location Assignment Problem Based on Product
421
Information
421
18.2.1 Dedicated Storage Location Policy
421
18.2.2 Cube-Per-Order Index (COI)
427
18.2.3 Class-Based Storage Location Policy
427
18.2.4 Class-Based Dedicated Storage Location Policy (COI)
429
18.2.5 Full Turn-over Based Storage
431
18.3 Storage Location Assignment Problem
434
Based on Item Information (SLAP/II)
434
18.3.1 Assignment Problem and Vector Assignment Problem
434
18.3.2 Shared Storage Policies
435
18.3.3 Duration-of-Stay Storage Policy
436
18.3.4 Shared Storage Policies for Unbalanced Input and Output
438
18.3.5 Static Shared Storage Policies
439
18.3.6 Adaptive Shared Storage Policies
439
18.4 Storage Location Assignment Problem
442
Based on No Information (SAP/NI)
442
18.4.1 Randomized Storage Location Policy
442
18.5 Comparing Storage Policies
444
18.6 Family Grouping
444
18.7 Continuous Warehouse Layout
445
18.7.1 Storage Region Configuration
446
18.8 Dynamic Storage Location Assignment Problems
446
(Gu 2005)
446
18.9 Case Study
446
References
447
19 Location-Inventory Problem
449
19.1 Applications and Classifications
451
19.2 Models
453
19.2.1 Model of Shen et al. (2003)
453
19.2.2 Model of Nozick and Turnquist (1998)
455
19.2.3 Model of Erlebacher and Meller (2000)
456
19.2.4 Model of Daskin et al. (2002)
458
19.2.5 Model of Shen and Qi (2007)
461
19.2.6 Model of Miranda and Garrido (2008)
463
19.3 Solution Approaches
465
19.3.1 Solution Approach of Erlebacher and Meller (2000)
465
19.3.2 Solution Approach of Daskin et al. (2002)
466
19.3.3 Solution Approach of Shen and Qi (2007)
466
19.3.4 Solution Approach of Miranda and Garrido (2006)
467
19.3.5 Solution Approach of Miranda and Garrido (2008)
467
19.4 Case Study
467
19.4.1 Distribution System for Finished Automobiles in US
468
(Nozick and Turnquist 1998)
468
References
468
20 Facility Location in Supply Chain
470
20.1 Design Phases in Supply Chain
470
20.2 Network Design in Supply Chain
471
20.2.1 The Role of Network Design in the Supply Chain
471
20.2.2 Factors Influencing Network Design Decisions
472
20.3 ClassicalModels
472
20.3.1 Fixed Charge Facility Location Problem (Daskin
473
et al. 2005)
473
20.3.2 Uncapacitated Facility Location Model with Single
474
Sourcing
474
20.3.3 Capacitated Facility Location Model
474
20.3.4 Locating Plants and Distribution Centers with Multiple
476
Commodity
476
20.4 Integrated Decision Making Models
477
20.4.1 Integrated Location-Routing Models (LR)
477
20.4.2 Integrated Inventory-Routing Models (IR)
478
20.4.3 Integrated Location-Inventory Models (LI)
478
20.5 Basic Model Formulation
479
20.5.1 Model Inputs
479
20.5.2 Model Outputs (Decision Variables)
480
20.5.3 Objective Function and its Constraints
480
20.6 Model with Routing Cost Estimation
480
20.7 Model with Capacitated DCs
481
20.8 Model with Multiple Levels of Capacity (Amiri 2006)
482
20.8.1 Model Inputs
482
20.8.2 Model Outputs (Decision Variables)
483
20.8.3 Objective Function and its Constraints
483
20.9 Model with Service Considerations
483
20.10 Profit Maximizing Model with Demand Choice Flexibility
485
20.11 Model with Multiple Commodities
487
20.12 Model with Unreliable Supply
488
20.12.1 Model Inputs
489
20.12.2 Model Outputs (Decision Variables)
489
20.12.3 Objective Function and its Constraints
489
20.13 Model with Facility Failures (Snyder 2003)
490
20.13.1 Objective Function and its Constraints
491
20.14 Planning Under Uncertainty (Snyder et al. 2007)
492
20.14.1 Model Inputs
493
20.14.2 Model Outputs (Decision Variables)
493
20.14.3 Objective Function and its Constraints
493
20.15 Solution Techniques
494
20.16 Case Study
496
20.16.1 An Industrial Case in Supply Chain Design
496
and Multilevel Planning in US (Sousa et al. 2008)
496
20.16.2 Multi-Objective Optimization of Supply Chain Networks
498
in Turkey (Altiparmak et al. 2006)
498
References
498
21 Classification of Location Models and Location Softwares
502
21.1 Classification of Location Models
502
21.1.1 Taxonomy vs. Classification Scheme
502
21.1.2 Taxonomy
503
21.1.3 Classification Schemes
508
21.2 Facility Location Softwares
510
21.2.1 LoLA
512
21.2.2 SITATION
513
21.2.3 S-Distance
516
21.2.4 Other Facility Location Softwares
517
References
517
22 Demand Point Aggregation Analysis for Location Models
519
22.1 Applications
520
22.1.1
520
Median
520
Problem
520
22.1.2
520
Center
520
Problem
520
22.1.3 Covering Problem
521
22.2 Aggregation Errors
521
22.2.1 Spatial Aggregation Demand
521
22.2.2 Methods for Reducing Aggregation Errors
523
22.3 Computational Approach
528
References
529
Appendix: Metaheuristic Methods
531
Genetic Algorithm
531
The Simple Genetic Algorithm
532
Tabu Search
533
Two Important Concepts
533
A Simple Tabu Search Algorithm
534
Ant Colony Optimization
534
Simulated Annealing
535
Neural Networks
536
References
537
Index
540
All prices incl. VAT