臺灣博碩士論文加值系統

對於許多企業來說，一個好的物流系統可有效降低供應鏈中的物流成本。透過設施區位與配送途程等決策將可建立一個物流系統，而這些決策可視為一個區位-途程問題(Location Routing Problem)。區位-途程問題即同時針對設施數量、設施區位與配送途程進行最佳化以達到系統總成本的最小化。一個典型的區位-途程問題將包含三個主要的決策：選擇設施區位、指派顧客到已建置的設施與決定車輛配送之途程。由於區位-途程結合了兩個NP-hard的問題：設施區位問題(Facility Location Problem)以及車輛途程問題(Vehicle Routing Problem)，故其求解非常困難。因此，大部分之研究均採用啟發式演算法進行求解。
蟻群最佳化演算法(Ant Colony Optimization)是根據自然界蟻群搜尋食物之方式所建構出之萬用啟發式演算法(Meta-heuristic)。蟻群最佳化演算法已經被廣泛的應用於許多組合最佳化問題(Combinational Optimization Problems)。然而，蟻群最佳化演算法於區位-途程問題之應用並不多，而且至目前為止並無相關研究採用蟻群最佳化演算法求解整個區位-途程問題。蟻群最佳化演算法僅被應用於求解區位-途程問題中的車輛途程問題(Vehicle Routing Problem)。因此，本研究將建構一具有多階段初始解建構準則(multi-phase solution construction rule)之蟻群最佳化演算法，並將其應用於多場站時窗限制區位-途程問題(Multiple Depots Location Routing Problem with Time Windows)與其相關子問題，包括：車輛途程問題、時窗限制車輛途程問題(Vehicle Routing Problem with Time Windows)、多場站車輛途程問題(Multiple Depot Vehicle Routing Problem)、多場站時窗限制車輛途程問題(Multiple Depot Vehicle Routing Problem with Time Windows)、單一資源容量限制設施區位問題(Single Source Capacitated Facility Location Problem)與多場站區位-途程問題(Multiple Depot Location Routing Problem)。此外，本研究亦結合蟻群最佳化演算法、模擬退火法(Simulated Annealing)與拉式啟發式演算法 (Lagrangian Heuristic)建構出數個混合式演算法(Hybrid Algorithm)以改善蟻群最佳化演算法之求解績效。最後，透過大量標竿題庫之求解以測試各演算法之績效。求解結果顯示本研究所建構之演算法在求解多場站時窗限制區位-途程問題與其相關子問題方面均有非常不錯的表現。

The design of a logistics system is an important issue in many organizations due to the significant contribution of distributing cost to the total supply chain cost. The success of the logistics system may depend on the location-distribution decisions which are the same as the location routing problem (LRP). The LRP is to find the optimal number and locations of the distribution centers (DCs) as well as the distribution routes starting and ending at the DC, so as to minimize the total system cost. A typical LRP includes the making of three decisions: facility location, customer allocation to facilities and vehicle routing. The LRPs are very difficult to solve since they combine two NP-hard problems: the Facility Location Problem (FLP) and the Vehicle Routing Problem (VRP). Due to the problem complexity, simultaneous solution methods are limited to heuristic algorithms.
The Ant Colony Optimization (ACO) is a distributed meta-heuristic algorithm based on the behavior of ant searching for food. The ACO has been applied extensively in the fields of the combinational optimization problems. However, to our best knowledge, few researchers applied the ACO to solve LRPs and no one solved the whole problem only using ACO. The ACO is only applied to solve the VRP in LRP. Therefore, the main purpose of this dissertation is to propose a novel framework of ACO, which adopts a multi-phase solution construction rule, to solve a Multiple Depot Location Routing Problem with Time Windows (MDLRPTW) and its variant problems, including Vehicle Routing Problem, Vehicle Routing Problem with Time Windows (VRPTW), Multiple Depot Vehicle Routing Problem (MDVRP), Multiple Depot Vehicle Routing Problem with Time Windows (MDVRPTW), Single Source Capacitated Facility Location Problem (SSCFLP) and Multiple Depot Location Routing Problem (MDLRP). An additional purpose here is to hybrid ACO with Simulated Annealing (SA) or Lagrangian heuristic to improve the solution quality. Finally, enormous benchmark instances are tested for all the proposed algorithms. The computational results demonstrate the suitability of applying ACO and hybrid ACO for aforementioned problems.

Contents
摘要 i
ABSTRACT iii
誌謝 v
Contents vi
List of Tables ix
List of Figures xiii
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Scope 3
1.3 Purposes 4
1.4 Contributions of the Dissertation 8
1.5 Organizations of the Dissertation 8
Chapter 2 Literature Review 11
2.1 Facility Location Problems 11
2.2 Vehicle Routing Problems 13
2.2.1 Large Scale Vehicle Routing Problem 14
2.2.2 Vehicle Routing Problem with Time Windows 15
2.2.3 Multiple Depot Vehicle Routing Problem 16
2.3 Location Routing Problems 17
2.4 Heuristic Approaches 22
2.4.1 Simulated Annealing 23
2.4.2 Tabu Search 23
2.4.3 Variable Neighborhood Search 24
2.4.4 Genetic Algorithms 25
2.4.5 Memetic Algorithms 25
2.4.6 Lagrangian Relaxation 26
2.5 Hybrid Algorithms 27
2.5.1 Sequential Hybridization 28
2.5.2 Parallel Hybridization 28
2.6 Ant Colony Optimization 29
2.6.1 Ant System 31
2.6.2 Elitist Ant System 32
2.6.3 Rank-Based Ant System 33
2.6.4 Max-Min Ant System 34
2.6.5 ANTS System 34
2.6.6 Hyper-Cube Framework 35
2.6.7 Ant Colony System 36
2.6.8 Ant-Q 39
2.6.9 Applications of ACO 39
2.7 Summary 39
Chapter 3 Vehicle Routing Problems 41
3.1 Mathematical Model of the VRP and VRPTW 41
3.2 Ant Colony System for the VRP and VRPTW 44
3.2.2 Local Search 45
3.2.3 Pheromone Updating Rule 46
3.2.4 Overall Procedure of ACS 47
3.3 Simulated Annealing for the VRP and VRPTW 47
3.4 Hybrid Ant Colony System for the VRP and VRPTW 48
3.5 Numerical Analysis of the VRP 49
3.5.1 Results for the VRP Benchmark Instances 49
3.5.2 Results for the LSVRP Benchmark Instances 53
3.5.3 Computational Efficiency of ACS for VRP 56
3.5.4 Parameter Sensitivity of ACS for VRP 58
3.6 Numerical Analysis of the VRPTW 61
3.6.1 Computational Results of VRPTW 62
3.6.2 Comparison of ACS, ACS-SA and Other Algorithms 62
3.6.3 Parameter Sensitivity of ACS for VRPTW 66
3.7 Summary 68
Chapter 4 Multiple Depot Vehicle Routing Problems 69
4.1 Mathematical Model of the MDVRP and MDVRPTW 69
4.2 Multiple Ant Colony System for the MDVRP and MDVRPTW 71
4.2.1 Solution Construction 73
4.2.2 Local Search of MACS 74
4.2.3 Pheromone Updating Rule 75
4.2.4 Overall Procedure of MACS 76
4.3 Hybrid Ant Colony System for the MDVRP and MDVRPTW 76
4.4 Numerical Analysis of MDVRP 78
4.4.1 Computational Results of MDVRP 79
4.4.2 Parameter Sensitivity of MACS for MDVRP 82
4.5 Numerical Analysis of MDVRPTW 85
4.5.1 Computational Results of MDVRPTW 85
4.5.2 Computational Efficiency for MDVRPTW 87
4.5.3 Parameter Sensitivity of MACS for MDVRPTW 88
4.6 Summary 90

Chapter 5 Single Source Capacitated Facility Location Problem 91
5.1 Mathematical Model of the SSCFLP 91
5.2 Multiple Ant Colony System for SSCFLP 92
5.2.1 Solution Construction 93
5.2.2 Local Search 95
5.2.3 Pheromone Updating Rules 97
5.2.4 Overall Procedure of MACS 98
5.3 Lagrangian Heuristic for SSCFLP 98
5.3.1 Calculate the Lower Bound 99
5.3.2 Calculate the Approximate Lower Bound 100
5.3.3 Calculate the Upper Bound 101
5.3.4 Updating the Lagrangian Multipliers 102
5.3.5 Overall Procedure of Lagrangian Heuristic 103
5.4 Hybrid Algorithm (LH-ACS) for SSCFLP 103
5.5 Numerical Analysis of SSCFLP 105
5.5.1 Parameter Sensitivity 106
5.5.2 Computational Results of Holmberg et al.’s Instances 111
5.5.3 Computational Results of Beasley’s Instances 119
5.5.4 Comparison of LH, LH-MT1R, LH-ACS and LH-MT1R-ACS 122
5.6 Summary 126
Chapter 6 Multiple Depot Location Routing Problems 128
6.1 Formulation for the MDLRP and MDLRPTW 129
6.2 Sequential Solving Strategy for the MDLRP and MDLRPTW 133
6.3 Iterative Solving Strategy for the MDLRP and MDLRPTW 133
6.4 Numerical Analysis of the MDLRP 141
6.4.1 Computational Results of MDLRP 142
6.4.2 Parameter Sensitivity of I-MACS for MDLRP 152
6.5 Numerical Analysis of the MDLRPTW 156
6.5.1 Computational Results of MDLRPTW 157
6.5.2 Parameter Sensitivity of I-MACS for MDLRPTW 167
6.6 Summary 171
Chapter 7 Conclusions and Future Research 172
7.1 Conclusions 172
7.2 Future Research 176
References 177
AppendixⅠ-List of Publications 189


List of Tables
Table 2-1 Classification of LRP with regard to its problem perspective 18
Table 2-2 Classification of LRP with regard to its solution method 19
Table 3-1 The computational results of Christofides et al. instances 50
Table 3-2 Comparison of different methods for Christofides et al. instances 51
Table 3-3 Comparison of computational speed of algorithms for Christofides et al. instances 52
Table 3-4 The computational results of Golden et al. instances 54
Table 3-5 Comparison of different methods for Golden et al. instances 55
Table 3-6 Comparison of computational speed of algorithms for Golden et al. instances 56
Table 3-7 The improvement of gap(%) as iteration progresses in ACS-SA 57
Table 3-8 Average gaps and run times for differentβof ACS for VRP 59
Table 3-9 Average gaps and run times for different q0 of ACS for VRP 59
Table 3-10 Average gaps and run times for different ?? of ACS for VRP 60
Table 3-11 Average gaps and run times for different b of ACS for VRP 60
Table 3-12 Average gaps and run times for different S of ACS for VRP 60
Table 3-13 The information of Solomon’s VRPTW benchmark problems 61
Table 3-14 The computational results of type 1 problems 63
Table 3-15 The computational results of type 2 problems 64
Table 3-16 Percentage deviation and number of new best solutions for VRPTW 64
Table 3-17 Comparison of algorithms for VRPTW 65
Table 3-18 Comparison of computational speed of algorithms for VRPTW 66
Table 3-19 Average gaps and run times for differentβof ACS for VRPTW 67
Table 3-20 Average gaps and run times for different q0 of ACS for VRPTW 67
Table 3-21 Average gaps and run times for different ?? of ACS for VRPTW 67
Table 3-22 Average gaps and run times for different b of ACS for VRPTW 67
Table 3-23 Average gaps and run times for different S of ACS for VRPTW 68
Table 4-1 Parameter settings of MACS, SH-MACS-SA and EH-MACS-SA 79
Table 4-2 The computational results for MDVRP instances 80
Table 4-3 Comparison of results for MDVRP instances 81
Table 4-4 Comparison of computational speed of algorithms for MDVRP instances 82
Table 4-5 Average gaps and run times for different β of EH-MACS-SA for MDVRP 83
Table 4-6 Average gaps and run times for different ρ of EH-MACS-SA for MDVRP 83
Table 4-7 Average gaps and run times for different q0 of EH-MACS-SA for MDVRP 84

Table 4-8 Average gaps and run times for different ?? and ?? of EH-MACS-SA for MDVRP 84
Table 4-9 The computational results for MDVRPTW instances 86
Table 4-10 Comparison of results for MDVRTW instances 86
Table 4-11 Comparison of computational speed of algorithms for MDVRPTW instances 87
Table 4-12 Average gaps and run times for different β of EH-MACS-SA for MDVRPTW 89
Table 4-13 Average gaps and run times for different ρ of EH-MACS-SA for MDVRPTW 89
Table 4-14 Average gaps and run times for different q0 of EH-MACS-SA for MDVRPTW 89
Table 4-15 Average gaps and run times for different ?? and ?? of EH-MACS-SA for MDVRPTW 90
Table 5-1 Parameter settings of LH, MACS and LH-ACS 106
Table 5-2 Average gaps and run times for different r of MACS for SSCFLP 107
Table 5-3 Average gaps and run times for different β of MACS for SSCFLP 107
Table 5-4 Average gaps and run times for different ?? of MACS for SSCFLP 107
Table 5-5 Average gaps and run times for different q0 of MACS for SSCFLP 108
Table 5-6 Average gaps and run times for different q0’ of MACS for SSCFLP 108
Table 5-7 Average gaps and run times for different ρ of MACS for SSCFLP 108
Table 5-8 Average gaps and run times for different ρ’ of MACS for SSCFLP 108
Table 5-9 Average gaps and run times for different α1 of LH-ACS for SSCFLP 110
Table 5-10 Average gaps and run times for different ?? of LH-ACS for SSCFLP 110
Table 5-11 Average gaps and run times for different q0’ of LH-ACS for SSCFLP 110
Table 5-12 Average gaps and run times for different ρ’ of LH-ACS for SSCFLP 111
Table 5-13 The computational results of LH for the Holmberg’s problems p1-p40 113
Table 5-14 The computational results of LH for the Holmberg’s problems p41-p71 114
Table 5-15 The computational results of MACS for the Holmberg’s problems p1-p40 115
Table 5-16 The computational results of MACS for the Holmberg’s problems p41-p71 116
Table 5-17 The computational results of LH-ACS for the Holmberg’s problems p1-p40 117
Table 5-18 The computational results of LH-ACS for the Holmberg’s problems p41-p71 118
Table 5-19 Comparison of different algorithms for the Holmberg’s problems 118

Table 5-20 Comparison of computational speed of algorithms for Holmberg’s instances 119
Table 5-21 The Computational results of LH for very large problems 120
Table 5-22 The Computational results of MACS for very large problems 120
Table 5-23 The Computational results of LH-ACS for very large problems 120
Table 5-24 Comparison of different algorithms for very large problems 121
Table 5-25 Comparison of computational speed of algorithms for very large problems 121
Table 5-26 Comparison of LH and LH-MT1R for the Holmberg’s problems p1-p40 123
Table 5-27 Comparison of LH and LH-MT1R for the Holmberg’s problems p41-p71 124
Table 5-28 Comparison of LH-ACS and LH-MT1R-ACS for the Holmberg’s problems p1-p40 125
Table 5-29 Comparison of LH-ACS-heuristic and LH-MT1R-ACS for the Holmberg’s problems p41-p71 126
Table 6-1 The computational results of Perl’s instances 143
Table 6-2 Comparison of results for Perl’s instances 144
Table 6-3 Comparison of computational speed of algorithms for Perl’s instances 144
Table 6-4 The computational results of Barreto’s instances 146
Table 6-5 Comparison of results for Barreto’s instances 147
Table 6-6 Comparison of computational speed of algorithms for Barreto’s instances 148
Table 6-7 The computational results of Prins’s instances 150
Table 6-8 Comparison of results for Prins’s instances 151
Table 6-9 Comparison of computational speed of algorithms for Prins’s instances 151
Table 6-10 Average gaps and run times for different r of I-MACS for MDLRP 152
Table 6-11 Average gaps and run times for different ??, β and ?? of I-MACS for MDLRP 153
Table 6-12 Average gaps and run times for different ρ, ρ’ and ρ” of I-MACS for MDLRP 154
Table 6-13 Average gaps and run times for different q0, q0’ and q0” of I-MACS for MDLRP 155
Table 6-14 The information of MDLRPTW instances 157
Table 6-15 The computational results of S-MACS for the N type instances 158
Table 6-16 The computational results of I-MACS for the N type instances 159
Table 6-17 The comparison of our algorithms for the N type instances 160
Table 6-18 The computational results of S-MACS for the W type instances 161
Table 6-19 The computational results of I-MACS for the W type instances 162
Table 6-20 The comparison of our algorithms for the W type instances 163
Table 6-21 The computational results of S-MACS for the NW type instances 164
Table 6-22 The computational results of I-MACS for the NW type instances 165
Table 6-23 The comparison of our algorithms for the NW type instances 166
Table 6-24 Average gaps and run times for different r of I-MACS for MDLRPTW 167
Table 6-25 Average gaps and run times for different ??, β and ?? of I-MACS for MDLRPTW 168
Table 6-26 Average gaps and run times for different ρ, ρ’ and ρ” of I-MACS for MDLRPTW 169
Table 6-27 Average gaps and run times for different q0, q0’ and q0” of I-MACS for MDLRPTW 170
Table 7- 1 Summary of computational results of our algorithms 175
List of Figures
Figure 1-1 Interdependence among location, allocation and routing 2
Figure 1-2 The related problems of MDLRPTW solved in this dissertation 5
Figure 1-3 The relation between ACS for VRPs, MACS for MDVRPs, MACS for SSCFLP and MACS for MDLRPs 6
Figure 2-1 A classification of hybrid EAs 27
Figure 2-2 Sequential hybridization 28
Figure 2-3 Parallel synchronous hybridization 29
Figure 2-4 Parallel asynchronous heterogeneous hybridization 29
Figure 2-5 An Example with real ants 30
Figure 3-1 The framework of the two-phase ACS-SA for VRPs 49
Figure 3-2 The comparison of ACS-SA with different G for instance K20 57
Figure 3-3 The objective function value and run time at different S for problem C14 61
Figure 4-1 The framework of MACS for the MDVRP and MDVRPTW 72
Figure 4-2 The framework of SH-MACS-SA for the MDVRP and MDVRPTW 77
Figure 4-3 The framework of EH-MACS-SA for the MDVRP and MDVRPTW 78
Figure 4-4 The comparison of MACS and EH-MACS-SA with same G for pr20 88
Figure 4-5 The comparison of MACS and SH-MACS-SA for pr20 88
Figure 5-1 Insert move of the SSCFLP 96
Figure 5-2 Swap move of the SSCFLP 96
Figure 5-3 The flowchart of LH-ACS 105
Figure 5-4 The objective function value and run time at different S of MACS for problem h56 109
Figure 5-5 The objective function value and run time at different S of LH-ACS for problem h56 111
Figure 5-6 The LB and UB obtained by LH-ACS and LH-MT1R-ACS for h51 122
Figure 6-1 The framework of S-MACS for the MDLRPs 133
Figure 6-2 The framework of I-MACS for the MDLRP 134

1.Ahuja, R. K., Orlin, J. B., Pallottino, S., Scaparra, M. P., Scutellà, M. G. (2004) “A Multi-exchange Heuristic for the Single-source Capacitated Facility Location Problem,” Management Science, Vol. 50, pp. 749-760.
2.Albareda-Sambola, M., Fernández, E. and Laporte G. (2007) “Heuristic and Lower Bound for a Stochastic Location-routing Problem,” European Journal of Operational Research, Vol. 179, pp. 940-955.
3.Alfa, A. S., Heragu, S. S. and Chen, M. (1991) “A 3-opt Based Simulated Annealing Algorithm for Vehicle Routing Problems,” Computers & Industrial Engineering, Vol. 21, pp. 635-639.
4.Ambrosino, D. and Scutellà, M. G. (2005) “Distribution Network Design: New Problems and Related Models,” European Journal of Operational Research, Vol. 165, pp. 610-624.
5.Bahnski, M. L. (1965) “Integer Programming: Methods, Uses, Computation,” Management Science, Vol. 12, pp. 253-313.
6.Baker, B. M. and Ayechew, M. A. (2003) “A Genetic Algorithm for the Vehicle Routing Problem,” Computer & Operations Research, Vol. 30, pp. 787-800.
7.Barbarosoglu, G. and Ozgur, D. (1999) “A Tabu Search Algorithm for the Vehicle Routing Problem,” Computer & Operations Research, Vol. 26, pp. 255-270.
8.Barreto, S. S. (2004) Analysis and Modelling of Location-routing Problems, Ph.D. Dissertation, University of Aveiro, Aveiro, Portugal.
9.Barreto, S., Ferreira, C., Paixão, J. and Santos, B. S. (2007) “Using Clustering Analysis in Capacitated Location-routing Problem,” European Journal of Operational Research, Vol. 179, pp. 968-977.
10.Beasley, J. E. (1993) “Lagrangean Heuristic for Location Problem,” European Journal of Operational Research, Vol. 65, pp. 383-399.
11.Berger, J., Barkaoui, M. and Bräysy, O. (2001) “A Parallel Hybrid Genetic Algorithm for the Vehicle Routing Problem with Time Windows,” Working paper, Defense Research Establishment Valcartier, Canada.
12.Berger, R. T., Coullard, C. R. and Daskin M. S. (2007) “Location-routing Problems with Distance Constraints,” Transportation Science, Vol. 41, pp. 29-43.
13.Blum, C. (2005) “Ant Colony Optimization: Introduction and Recent Trends,” Physics of Life Reviews, Vol. 2, pp. 353-373.
14.Blum, C., Roli, A. and Dorigo, M. (2001) “HC-ACO: The Hyper-cube Framework for the Ant Colony Optimization,” Proceedings of MIC’2001-Metaheuristics International Conference, Vol. 2, pp. 399-403.
15.Bornstein, C. T. and Azlan, H. B. (1998) “The Use of Reduction Tests and Simulated Annealing for the Capacitated Location Problem,” Location Science, Vol.6, pp. 67-81.
16.Bouhafs, L., Hajjam, A. and Koukam, A. (2006) “A Combination of Simulated Annealing and Ant Colony System for the Capacitated Location-routing Problem,” Lecture Notes in Computer Science, Vol. 4251, pp. 409-416.
17.Bräysy, O., Dullaert, W. and Gendreau, M. (2004) “Evolutionary Algorithms for the Vehicle Routing Problem with Time Windows,” Journal of Heuristics, Vol. 10, pp. 587-611.
18.Breedam, A. V. (1995) “Improvement Heuristics for the Vehicle Routing Problem Based on Simulated Annealing,” European Journal of Operational Research, Vol. 86, pp. 480-490.
19.Bullnheimer, B., Hartl, R. F. and Strauss, C. (1999a) “Applying the Ant System to the Vehicle Routing Problem,” In S. Voss, S. Martello, I. H. Osman, and C. Roucairol (Editors), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Dordrecht, Netherlands, Kluwer, Academic Publishers, pp. 285-296.
20.Bullnheimer, B., Hartl, R. F. and Strauss, C. (1999b) “A New Rank Based Version of the Ant System - A Computational Study,” Central European Journal of Operations Research, Vol. 7, pp. 25-38.
21.Bullnheimer, B., Hartl, R. F. and Strauss, C. (1999c) “An Improved Ant System for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 89, pp. 319-328.
22.Caballero, R., González, M., Guerrero, F. M., Molina, J. and Paralera, C. (2007) “Solving a Multiobjective Location Routing Problem with a Metaheuristic Based on Tabu Search. Application to a real case in Andalusia,” European Journal of Operational Research, Vol. 177, pp. 1751-1763.
23.Chao, I. M., Golden, B. L. and Wasil, E. A. (1993) “A New Heuristic for the Multi-depot Vehicle Routing Problem that Improves upon Best-known Solutions,” American Journal of Mathematical & Management Science, Vol. 13, pp. 371-406.
24.Chen, C. H. and Ting, C. J. (2005) “A Hybrid Ant Colony System for Vehicle Routing Problem with Time Windows,” Journal of Eastern Asia Society for Transportation Studies, Vol. 6, pp. 2822-2836.
25.Chen, C. H. and Ting, C. J. (2006) “An Improved Ant Colony System Algorithm for the Vehicle Routing Problem,” Journal of the Chinese Institute of Industrial Engineering, Vol. 23, pp. 115-126.
26.Chen, C. H. and Ting, C. J. (2006) “Applying Multiple Ant Colony System to Solve the Single Source Capacitated Facility Location Problem,” Lecture Notes in Computer Science, Vol. 4150, pp. 508-509.
27.Chen, C. H., Ting, C. J. and Chang, P. C. (2005) “Applying a Hybrid Ant Colony System to the Vehicle Routing Problem,” Lecture Notes in Computer Science, Vol. 3483, pp. 417-426.
28.Chen, T. K., Lee, L. H. and Ke, O. (2001) “Hybrid Genetic Algorithm in Solving Vehicle Routing Problem with Window Constraints,” Asia-Pacific Journal of Operational Research, Vol. 18, pp. 121-130.
29.Chiang, W. C. and Russell, R. A. (1997), “A Reactive Tabu Search Metaheuristics for the Vehicle Routing Problem with Time Windows,” INFORMS Journal on Computing, Vol. 9, pp. 417-430.
30.Christofides, N. (1985) “Vehicle Routing,” In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy, Kan and D. B. Shmoys (Editors), The Traveling Salesman Problem, Wiley, Chicester.
31.Christofides, N. and Eilon, S. (1969) “An Algorithm for the Vehicle-dispatching Problem,” Operational Research Quarterly, Vol. 20, pp. 309-318.
32.Christofides, N., Mingozzi, A. and Toth, P. (1979) “The Vehicle Routing Problem,” In N. Christofides, A. Mingozzi, P. Toth and C. Sandi (Editors), Combinatorial Optimization, Wiley, Chichester.
33.Colorni, A., Dorigo, M. and Maniezzo, V. (1991) “Distributed Optimization by Ant Colonies,” In F. Varela and P. Bourgine (Editors), Proceeding of the European Conference on Artificial Life, Elsevier, Amsterdam.
34.Colorni, A., Dorigo, M., Maniezzo, V. and Trubian, M. (1994) “Ant System for Job-shop Scheduling,” Belgian Journal of Operations Research, Statistics and Computer Science, Vol. 34, pp. 39-53.
35.Cordeau, J. F., Gendreau, M. and Laporte, G. (1997) “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems,” Networks, Vol. 30, pp. 105-119.
36.Cordeau, J-F, Laporte, G. and Mercier, A. (2001) “A Unified Tabu Search Heuristic for Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 52, pp. 928-936.
37.Cordeau, J-F, Laporte, G. and Mercier, A. (2004) “Improved Tabu Search Algorithm for the Handling of Route Duration Constraints in Vehicle Routing Problems with Time Windows,” Journal of the Operational Research Society, Vol. 55, pp. 542-546.
38.Cornuejols, G., Fisher, M. L., Nemheuser, G. L. (1977) “Location of Bank Accounts to Optimize Float: An Analysis study of Exact and Approximate Algorithms,” Management Science, Vol. 23, pp. 789-810.
39.Cortinhal, M. J., Captivo, M. E. (2003) “Upper and Lower Bounds for the Single Source Capacitated Location Problem,” European Journal of Operational Research, Vol. 151, pp. 333-351.
40.Costa, D. and Hertz, A. (1997) “Ants can Colour Graphs,” Journal of the Operational Research Society, Vol. 48, pp. 295-305.
41.Czech, Z. J. and Czarnas, P. (2002) “A Parallel Simulated Annealing for the Vehicle Routing Problem with Time Windows,” Proceedings 10th Euromicro Workshop on Parallel, Distributed and Network-based Processing, Canary Islands, Spain, pp. 376-383.
42.Daskin, M. S. (1995) Network and Discrete Location: Models, Algorithms and Applications, John Wiley and Sons, Inc., New York.
43.Díaz, J. A. and Fernández, E. (2002) “A Branch-and-Price Algorithm for the Single Source Capacitated Plant Location Problem,” Journal of the Operational Research Society, Vol. 53, pp. 728-740.
44.Doerner, .K, Gronalt, M., Hartl, R. F., Reimann, M., Strauss, C. and Stummer, M. (2002) “SavingsAnts for the Vehicle Routing Problem,” Lecture Notes in Computer Science, Vol. 2279, pp. 11-20.
45.Doerner, .K. F., Hartl, R. F., Kiechle, G., Lucka, M. and Reimann, M. (2004) “Parallel Ant Systems for the Capacitated Vehicle Routing Problem,” Lecture Notes in Computer Science, Vol. 3004, pp. 72-83.
46.Dongarra, J. (2006) “Performance of Various Computers Using Standard Linear Equations Software,” Report CS-89-85, University of Tennessee.
47.Dorgio, M. (1992) Optimization, Learning and Natural Algorithms [In Italian], Ph.D. Dissertation, Dipartimento di Elettronica, Politecnico di Milano, Milan.
48.Dorigo, M. and Gambardella, L. M. (1997a) “Ant Colonies for the Traveling Salesman Problem,” BioSystems, Vol. 43, 73-81.
49.Dorigo, M. and Gambardella, L. M. (1997b) “Ant Colony System: A Cooperative Learning Approach for the Traveling Salesman Problem,” IEEE Transactions on Evolutionary Computation, Vol. 1, 53-66.
50.Dorigo, M. and T. Stützle, (2004) Ant Colony Optimization, Bradford Books, MIT Press.
51.Dorigo, M., Maniezzo, V., Colorni, A. (1996) “Ant System: Optimization by a Colony of Cooperating Agents,” IEEE Transactions on Systems, Man and Cybernetics Part B, Vol. 26, pp. 29-41.
52.Ellabib, I. M. (2005) Design and Analysis of Ant Colony System Based Approaches for Vehicle Routing Problem with Time Windows, Ph.D. Dissertation, Department of Systems Design Engineering, University of Waterloo, Waterloo, Canada.
53.Ellabib, I., Basir, O. A. and Calamai, P. (2002) “An Experimental Study of a Simple Ant Colony System for the Vehicle Routing Problem with Time Windows,” Lecture Notes in Computer Science, Vol. 2463, pp. 53-64.
54.Erlenkotter, D. (1978) “A Dual-Based Procedure for Uncapacitated Facility Location,” Operations Research, Vol. 26, pp. 992-1009.
55.Galvão, R. D. (1993) “The Use of Lagrangean Relation in the Solution of Uncapacitated Facility Location Problems,” Location Science, Vol. 1, pp. 57-59.
56.Gambardella, L. and Dorigo, M. (1995) “Ant-Q: A Reinforcement Learning Approach to the TSP,” 12th. International Machine Learning Conference (ML-95), pp. 252-260.
57.Gambardella, L. M. and Dorigo, M. (1997) “HAS-SOP: A Hybrid Ant System for the Sequential Ordering Problem,” Tech. Rep. No. IDSIA 97-11, IDSIA, Lugano, Switzerland.
58.Gambardella, L. M., Taillard, E. and Agazzi, G. (1999a) “Ant Colonies for Vehicle Routing Problems,” In D. Corne, M. Dorigo and F. Glover (Editors), New Ideas in Optimization, McGraw-Hill.
59.Gambardella, L. M., Taillard, E., and Agazzi, G. (1999b), “MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows,” In D. Corne, M. Dorigo and F. Glover (Editors), New Ideas in Optimization, McGraw-Hill, London, pp. 63-76.
60.Gambardella, L. Taillard, M., E. and Dorigo, M. (1999) “Ant Colonies for the Quadratic Assignment Problem,” Journal of the Operational Research Society, Vol. 50, pp. 167-176.
61.Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theorey of NP completeness, W.H. Freeman & Co., New York.
62.Gendreau, M., Hertz, A. and Laporte, G. (1994) “A Tabu Search Heuristic for the Vehicle Routing Problem,” Management Science, Vol. 40, pp. 1276-1290.
63.Ghiani, G., Guerriero, F. and Musmanno, R. (2002) “The Capacitated Plant Location Problem with Multiple Facilities in the Same Site,” Computers & Operations Research, Vol. 29, pp. 1903-1912.
64.Gillett, E. B. and Johnson, J. G. (1976) “Multi-terminal Vehicle-dispatch Algorithm,” Omega, Vol. 4, pp. 711-718.
65.Glover, F. (1989) “Tabu search-part Ⅰ,” ORSA Journal of Computing, Vol. 1, pp. 190-206.
66.Golden, B. L., Wasil, E. A. Kelly, J. P. and Chao, I-M. (1998) “Metaheuristic in Vehicle Routing,” In T. G. Crainic and G. Laporte (Editors), Fleet Management and Logistics, Kluwer, Boston, pp. 33-56.
67.Hansen, P. and Mladenovic, N. (2001) “Variable Neighborhood Search: Principles and Applications,” European Journal of Operational Research, Vol. 130, pp. 449-467.
68.Hansen, P.H., Hegedahl, B., Hjortkjær, S. and Obel B. (1994) “A Heuristic Solution to the Warehouse Location-routing Problem,” European Journal of Operational Research, Vol. 76, pp. 111-127.
69.Hindi, K. S., Pienkosz, K. (1999) “Efficient Solution of Large Scale, Single-Source, Capacitated Plant Location Problems,” Journal of the operational Research Society, Vol. 50, pp. 268-274.
70.Holland, J. H. (1975) “Adaptation in Natural and Artificial Systems,” University of Michigan Press, Ann Arbor, MI.
71.Holmberg, K., Rönnqvist, M., Yuan, D. (1999) “An Exact Algorithm for the Capacitated Facility Location Problems with Single Sourcing,” European Journal of Operational Research, Vol. 113, pp. 544-559.
72.Ho, S. C. and Gendreau, M. (2006) “Path Relinking for the Vehicle Routing Problem,” Journal of Heuristics, Vol. 12, pp. 55-72.
73.Jaramillo, J., Bhadury, H., J. and Batta, R. (2002) “On the Use of Genetic Algorithms to Solve Location Problems,” Computers & Operations Research, Vol. 29, pp. 761-779.
74.Jaszkiewicz, A. and Kominek, P. (2003) “Genetic Local Search with Distance Preserving Recombination Operator for a Vehicle Routing Problem,” European Journal of Operational Research, Vol. 151, pp. 352-364.
75.Karp, R. (1972) “Reducibility among Combinatorial Problems,” In R. Miller and J. Thatcher (Editors), Complexity of Computer Computations, Plenum Press, New York, pp. 85-104.
76.Kirkpatrick, S., Gelatt, C. D. and Vecchi, M. P. (1983) “Optimization by Simulated Annealing,” Science, Vol. 220, pp. 671-680.
77.Klincewicz, J. G. and Luss, H. (1986) “A Lagrangean Relaxation Heuristic for Capacitated Facility Location with Single Source Constraints,” Journal of the Operational Research Society, Vol. 37, pp. 495-500.
78.Kytöjoki, J., Nuortio, T., Bräysy, O. and Gendreau, M. (2007) “An efficient Variable Neighborhood Search Heuristic for Very Large Scale Vehicle Routing Problems,” Computers & Operations Research, Vol. 34, pp. 2743-2757.
79.Landa Silva, J. D. (2003) Metaheuristic and Multiobjective Approaches for Space Allocation, Ph.D. Dissertation, School of Computer Science and Information Technology, University of Nottingham.
80.Laporte, G. (1988) “Location Routing Problems,” in B. L. Golden and A. A. Assad (Editors), Vehicle Routing: Methods and Studies, North-Holland, Amsterdam, pp. 163-197.
81.Laporte, G., Louveaux, F. V. and Hamme, L. C. (1994) “Exact Solution to a Location Problem with Stochastic Demands,” Transportation Science, Vol. 28, pp. 95-103.
82.Lenstra, J. K., Rinnooy Kan, A. H. G. (1981) “Complexity of Vehicle Routing and Scheduling Problems,” Networks, Vol. 11, pp. 221-227.
83.Li, F., Golden, B. and Wasil, E. (2005) “Very Large-scale Vehicle Routing: New Test Problems, Algorithms, and Results,” Computers & Operations Research, Vol. 32, pp. 1165-1179.
84.Li, H. and Lim, A. (2003), “Local Search with Annealing-like Restarts to Solve the VRPTW,” European Journal of Operational Research, Vol. 150, pp. 115-127.
85.Lin, C. K. Y. and Kwok, R. C. W. (2006) “Multi-objective Metaheuristics for a Location-routing Problem with Multiple Use of Vehicles on Real Data and Simulation Data,” European Journal of Operational Research, Vol. 175, pp. 1833-1849.
86.Lin, C. K. Y., Chow, C. K. and Chen, A. (2002) “A Location-routing-loading Problem for Bill Delivery Services,” Computers & Industrial Engineering, Vol. 43, pp. 5-25.
87.Maniezzo, V. (1999) “Exact and Approximate Nondeterministic Tree-search Procedures for the Quadratic Assignment Problem,” INFORMS Journal on Compution, Vol. 11, pp. 358-369.
88.Maniezzo, V., Colorni, A. and Dorigo, M. (1994) “The Ant System Applied to the Quadratic Assignment Problem,” Tech. Rep. IRIDIA/94-28, Université Libre de Bruxelles, Belgium.
89.Martello, S. and Toth, P. (1990) Knapsack Problems: Algorithms and Computer Implementations, John Wiley & Sons, New York.
90.Melechovský, J., Prins, C. and Calvo, R. W. (2005) “A Metaheuristic to Solve a Location-routing Problem with Non-linear Costs,” Journal of Heuristics, Vol. 11, pp. 375-391.
91.Mester, D. and Bräysy, O. (2007) “Active-guided Evolution Strategies for Large-scale Capacitated Vehicle Routing Problem,” Computers & Operations Research, Vol. 34, pp. 2964-2975.
92.Mester, D., Bräysy, O. and Dullaert, W. (2007) “A Multi-parametric Evolution Strategies Algorithm for Vehicle Routing Problems,” Expert Systems with Applications, Vol. 32, pp. 508-517.
93.Min, H., Jayaraman, V. and Srivastava, R. (1998) “Combined Location-routing Problems: A Synthesis and Future Research Directions,” European Journal of Operational Research, Vol. 108, pp. 1-15.
94.Mladenovic, N. and Hansen, P. (1997) “Variable Neighborhood Search,” Computers and Operations Research, Vol. 24, pp. 1097-1100.
95.Nagy, G. and Salhi, S. (2006) “Location-routing: Issues, Models and Methods,” European Journal of Operational Research, Vol. 177, pp. 649-672.
96.Nozick, L. K., (2001) “The Fixed Charge Location Problem with Coverage Restrictions,” Transportation Research Part E, Vol. 37, pp. 281-296.
97.Osman, I. H. (1993) “Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem,” Annals of Operations Research, Vol. 41, pp. 421-451.
98.Özyurt, Z. and Aksen, D. (2007) “Solving the Multi-depot Location-routing Problem with Lagrangian Relaxation,” Extending the Horizons: Advances in Computing, Optimization, and Decision Technologies, Vol. 37, pp. 125-144.
99.Perl, J. (1983) “A Unified Warehouse Location-Routing Analysis,” Unpublished Ph.D. dissertation, Northwestern University, Illinois.
100.Perl, J. and Daskin, M. S. (1985) “A Warehouse Location-routing Problem,” Transportation Research Part B, Vol. 19B, pp. 381-396.
101.Pisinger, D. and Ropke, S. (2007) “A General Heuristic for Vehicle Routing Problems,” Computers & Operations Research, Vol. 34, pp. 2403-2435.
102.Polacek, M., Hartl, R. F., Doerner, K. and Reimann, M. (2004) “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows,” Journal of Heuristics, Vol. 10, pp. 613-627.
103.Potvin, J. Y., Kervahut, T., Garcia, B. L. and Rousseau, J. M. (1996) “The Vehicle Routing Problem with Time Windows, Part I: Tabu Search,” INFORMS Journal on Computing, Vol. 8, pp. 158-164.
104.Potvin, J. Y. and Bengio, S. (1996), “The Vehicle Routing Problem with Time Windows - Part II: Genetic Search,” INFORMS Journal on Computing, Vol. 8, pp. 165-172.
105.Prins, C. (2004) “A Simple and Effective Evolutionary Algorithm for the Vehicle Routing Problem,” Computers & Operations Research, Vol. 31, pp. 1985-2002.
106.Prins, C., Prodhon, C. and Calvo, R. W. (2004) “Nouveaux Algorithmes Pour le Problème de Localisation et Routage Sous Contraintes de Capacité,” In A. Dolgui and S. Dauzère-Pérès (eds) MOSIM’04, Vol. 2, Ecole des Mines de Nantes, Lavoisier, pp. 1115-1122.
107.Prins, C., Prodhon, C. and Calvo, R. W. (2006a) “Solving the Capacitated Location-routing Problem by a GRASP Complemented by a Learning Process and a Path Relinking,” 4OR, Vol. 4, pp. 47-64.
108.Prins, C., Prodhon, C. and Calvo, R. W. (2006b) “A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-routing Problem,” Lecture Notes in Computer Science, Vol. 3906, pp. 183-194.
109.Prins, C., Prodhon, C. and Calvo, R. W. (2006c) “Solving the Capacitated Location-routing Problem by a Cooperative Lagrangean Relaxation-granular Tabu Search heuristic,” Transportation Science, to appear.
110.Rego, C. and Roucairol, C. (1996) “A Parallel Tabu Search Algorithm Using Ejection Chains for the Vehicle Routing Problem,” In I. H. Osman and J. P. Kelly (Editors), Meta-heuristic: Theoy and Applications, Kluwer, Boston, MA, pp. 667-675.
111.Rego, C., (1998) “A Subpath Ejection Method for the Vehicle Routing Problem,” Management Science, Vol. 44, pp. 1447-1459.
112.Reimann, M., Doerner, K. and Hartl, R. F. (2004) “D-Ants: Savings Based Ant Divide and Conquer the Vehicle Routing Problem,” Computers & Operations Research, Vol. 31, pp. 563-591.
113.Renaud, J., Laporte, G. and Boctor, F. F. (1996) “A Tabu Search Heuristic for the Multi-depot Vehicle Routing Problem,” Computers & Operations Research, Vol. 23, pp. 229-235.
114.Robuste, F., Daganzo, C. F. and Souleyrette, R. (1990) “Implementing Vehicle Routing Models,” Transportation Research Part B, Vol. 24, pp. 263-586.
115.Rochat, Y. and Taillard, E. (1995) “Probabilistic and Intensification in Local Search for Vehicle Routing,” Journal of Heuristics, Vol. 1, pp. 147-167.
116.Rönnqvist, M., Tragantalerngsak, S. and Holt, J. (1999) “A Repeated Matching Heuristic for the Single-source Capacitated Facility Location Problem,” European Journal of Operational Research, Vol. 116, pp. 51-68.
117.Savelsbergh M. W. P. (1992) “The Vehicle Routing Problem with Time Windows: Minimizing Route Duration,” ORSA Journal on Computing, Vol. 4, pp. 146-154.
118.Solomon, M. M. (1987) “Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints,” Operations Research, Vol. 35, pp. 254-265.
119.Sridharan, R., (1995) “The Capacitated Plant Location Problem,” European Journal of Operational Research, Vol. 87, pp. 203-213.
120.Stützle, T. and Dorigo, M. (1999) “ACO Algorithms for the Quadratic Assignment Problem,” In D. Corne, M. Dorigo and F. Glover (Editors), New Ideas in Optimization, McGraw-Hill, pp. 33-50.
121.Stützle, T. and Hoos, H. H. (1997) “The MAX-MIN Ant System and Local Search for the Traveling Salesman Problem,” In T. Bäck, Z. Michalewicz and X. Yao (Editors), Proceedings of the 1997 IEEE International Conference on Evolutionary Computation (ICEC’97), Piscataway NJ, IEEE Press, pp. 309-314.
122.Stützle, T. and Hoos, H. H. (2000) “MAX-MIN Ant System,” Future Generation Computer System, Vol. 16, pp. 889-914.
123.Su, C. T. (1998) “Locations and Vehicle Routing Designs of Physical Distribution Systems,” Production Planning & Control, Vol. 9, pp. 650-659.
124.Taillard, E. (1993) “Parallel Iterative Search Methods for Vehicle Routing Problems,” Networks, Vol. 23, pp. 661-673.
125.Taillard, E., Badeau, P., Gendreau, M., Geurtin, F. and Potvin, J. Y. (1997), “A Tabu Search Heuristic for the Vehicle Routing Problem with Time Windows,” Transportation Science, Vol. 31, pp. 170-186.
126.Talbi, E. G., Roux, O., Fonlupt, C. and Robillard, D. (2001) “Parallel Ant Colonies for the Quadratic Assignment Problem,” Future Generation Computer Systems, Vol. 17, pp. 441-449
127.Tan, K. C., Lee, L. H. and Ou, K. (2001), “Artificial Intelligence Heuristics in Solving Vehicle Routing Problems with Time Window Constraints,” Engineering Applications of Artificial, Vol. 14, pp. 825-837.
128.Tarantilis, C. D. (2005) “Solving the Vehicle Routing Problem with Adaptive Memory Programming Methodology,” Computers & Operations Research, Vol. 32, pp. 2309-2327.
129.Ting, C. J. and Huang, C. H. (2005), “An Improved Genetic Algorithm for Vehicle Routing Problem with Time Windows,” International Journal of Industrial Engineering, Vol. 12, pp. 216-226.
130.Toth, P. and Vigo, D. (2003) “The Granular Tabu Search and Its Application to the Vehicle-routing Problem,” INFORMS Journal on Computing, Vol. 15, pp. 333-346.
131.Tragantalerngsak, S., Holt, J. and Rönnqvist, M. (1997) “Lagrangian Heuristics for the Two-echelon, Single-source, Capacitated Facility Location Problem,” European Journal of Operational Research, Vol. 102, pp. 611-625.
132.Tragantalerngsak, S., Holt, J. and Rönnqvist, M. (2000) “An Exact Method for the Two-echelon, Single-source, Capacitated Facility Location Problem,” European Journal of Operational Research, Vol. 123, pp. 473-489.
133.Tuzun, D. and Burke, L. I. (1999) “A Two-phase Tabu Search Approach to the Location Routing Problem,” European Journal of Operational Research, Vol. 116, pp. 87-99.
134.Wang, X., Sun, X. and Fang, Y. (2005) “A Two-phase Hybrid Heuristic Search Approach to the Location-routing Problem,” Systems, Man and Cybernetics, 2005 IEEE International Conference on, Vol. 4, pp. 3338-3343.
135.Watkins, C. J. and Dayan, P. (1992) “Q-learning,” Machine Learning, Vol. 8, pp. 279-292.
136.Wu, T. H., Low, C. and Bai, J. W. (2002) “Heuristic Solutions to Multi-depot Location-routing Problems,” Computers & Operations Research, Vol. 29, pp. 1393-1415.
137.Xu, J. and Kelly, J. P. (1996) “A Network Flow-based Tabu Search Heuristic for the Vehicle Routing Problem,” Transportation Science, Vol. 30, pp. 379-393.