PARALLEL COOPERATIVE SAVINGS BASED ANT COLONY OPTIMIZATION — MULTIPLE SEARCH AND DECOMPOSITION APPROACHES
Abstract
In this paper we study different parallel implementations of the Savings based Ant System algorithm developed for solving the Vehicle Routing Problem. We analyze the effects of low-level parallelization, multiple search strategies and domain decomposition approaches. For the different strategies speedup and efficiency as well as solution quality are reported. Different information exchanges are analyzed within the multiple search strategies.
References
- IEEE Transactions on Evolutionary Computation 1(1), 53 (1997). Crossref, Google Scholar
- Operations Research 12, 568 (1964). Crossref, ISI, Google Scholar
M. Reimann , M. Stummer and K. Doerner , A Savings based Ant System for the Vehicle Routing Problem, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2002), eds.W. B. Langdon (Morgan Kaufmann, San Francisco, 2002) pp. 1317–1325. Google Scholar- Computers & Operations Research 31(4), 563 (2004). Crossref, ISI, Google Scholar
- , Combinatorial Optimization , eds.
N. Christofides ( Wiley , Chicester , 1979 ) . Google Scholar - , Fleet management and logistics , eds.
T. G. Crainic and G. Laporte ( Kluwer , Norwell , 1998 ) . Google Scholar N. Jozefowiez , F. Semet and E.-G. Talbi , Parallel and Hybrid Models for Multiobjective Optimization: Application to the Vehicle Routing Problem,LNCS 2439,PPSN VII (), eds.M. Geuervos (2002) pp. 271–280. Google Scholar- Parallel Computing 29, 607 (2003). Crossref, ISI, Google Scholar
- Parallel Computing 27, 1521 (2001). Crossref, ISI, Google Scholar
- Computers & Operations Research 32, 1685 (2005). Crossref, ISI, Google Scholar
-
E. Alba (ed.) , Parallel Metaheuristics: A New Class of Algorithms ( Wiley , 2005 ) . Crossref, Google Scholar E. Alba , MALLBA: A library of skeletons for combinatorial optimization, Proceedings of the Euro-Par,LNCS 2400, ed.R. F. B. Monien (2002) p. 927932. Google Scholar- Journal of Heuristics 10(3), 357 (2004). Crossref, ISI, Google Scholar
- Genetic Programming and Evolvable Machines 3(4), 345 (2002). Crossref, Google Scholar
- , Handbook of Metaheuristics, eds.
F. Glover and G. A. Kochenberger (Kluwer, 2002) pp. 251–285. Google Scholar - P. Delisle, M. Krajecki, M. Gravel, C. Gagne, A Shared Memory Parallel Implementation of Ant Colony Optimization, in Preprints of the 6th Metaheuristics International Conference 2005, Vienna, Austria, August 2005, 257–264 . Google Scholar
-
P. Delisle , Parallel Implementation of an Ant Colony Optimization Metaheuristic with OpenMP , Proceedings of the 3rd European Workshop on OpenMP, EWOMP2001 . Google Scholar - Genetic Programming and Evolvable Machines 3(4), 345 (2002). Crossref, Google Scholar
- Future Generation Computer Systems 17, 441 (2001). Crossref, ISI, Google Scholar
- , High Performance Algorithms and Software in Nonlinear Optimization, eds.
R. Leone (Kluwer Academic, Dordrecht, 1998) pp. 87–100. Crossref, Google Scholar - Journal of Heuristics 8, 305 (2002). Crossref, ISI, Google Scholar
T. Stuetzle , Parallelization Strategies for Ant Colony Optimization, Proceedings of the Fifth International Conference on Parallel Problem Solving from Nature, PPSN-V,LNCS, Lecture Notes in Computer Science 1498, eds.A. E. Eiben (Springer, Amsterdam, 1998) pp. 722–731. Google Scholar- Networks 23, 661 (1993). Crossref, ISI, Google Scholar
- Central European Journal of Operations Research 7(1), 25 (1999). ISI, Google Scholar
- , Handbook of Metaheuristics, eds.
F. Glover and G. A. Kochenberger (Kluwer, 2002) pp. 251–285. Google Scholar - Operations Research 22, 340 (1974). Crossref, ISI, Google Scholar
- , Parallel Metaheuristics , ed.
Alba ( Wiley , 2005 ) . Crossref, Google Scholar - Information Processing Letters 82 , 7 . Crossref, ISI, Google Scholar
K. F. Doerner , Parallel Ant Systems for the Capacitated Vehicle Routing Problem,Lecture Notes in Computer Science ,Evolutionary Computation in Combinatorial Optimization: 4th European Conference, EvoCOP 2004 () (Springer, Coimbra, Portugal, 2004) pp. 72–83. Google ScholarS. Benkner , Communication Strategies for Parallel Cooperative Ant Colony Optimization on Clusters and Grids Complimentary, proceedings of PARA04 (2005) pp. 3–12. Google ScholarK. F. Doerner , R. F. Hartl and M. Lucka , A Parallel D-Ant Version for the Vehicle Routing Problem, Proceedings of the Parallel Numerics '05 (2005) pp. 109–118. Google Scholar


