World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

PARALLEL COOPERATIVE SAVINGS BASED ANT COLONY OPTIMIZATION — MULTIPLE SEARCH AND DECOMPOSITION APPROACHES

    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

    • M. Dorigo and L. M. Gambardella, IEEE Transactions on Evolutionary Computation 1(1), 53 (1997). CrossrefGoogle Scholar
    • G. Clarke and J. W. Wright, Operations Research 12, 568 (1964). Crossref, ISIGoogle 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. Langdonet al. (Morgan Kaufmann, San Francisco, 2002) pp. 1317–1325. Google Scholar
    • M. Reimann, K. F. Doerner and R. F. Hartl, Computers & Operations Research 31(4), 563 (2004). Crossref, ISIGoogle Scholar
    • N.   Christofides , A.   Mingozzi and P.   Toth , Combinatorial Optimization , eds. N.   Christofides et al. ( Wiley , Chicester , 1979 ) . Google Scholar
    • B. L.   Golden et al. , 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. Geuervoset al. (2002) pp. 271–280. Google Scholar
    • T. K. Ralphs, Parallel Computing 29, 607 (2003). Crossref, ISIGoogle Scholar
    • M. Florian and M. Gendreau, Parallel Computing 27, 1521 (2001). Crossref, ISIGoogle Scholar
    • A. Le Bouthillier and T. G. Crainic, Computers & Operations Research 32, 1685 (2005). Crossref, ISIGoogle Scholar
    • E.   Alba (ed.) , Parallel Metaheuristics: A New Class of Algorithms ( Wiley , 2005 ) . CrossrefGoogle 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
    • S. Cahon, N. Melab and E.-G. Talbi, Journal of Heuristics 10(3), 357 (2004). Crossref, ISIGoogle Scholar
    • D. Merkle and M. Middendorf, Genetic Programming and Evolvable Machines 3(4), 345 (2002). CrossrefGoogle Scholar
    • M. Dorigo and T. Stuetzle, 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 et al. , Parallel Implementation of an Ant Colony Optimization Metaheuristic with OpenMP , Proceedings of the 3rd European Workshop on OpenMP, EWOMP2001 . Google Scholar
    • D. Merkle and M. Middendorf, Genetic Programming and Evolvable Machines 3(4), 345 (2002). CrossrefGoogle Scholar
    • E. G. Talbiet al., Future Generation Computer Systems 17, 441 (2001). Crossref, ISIGoogle Scholar
    • B. Bullnheimer, G. Kotsis and C. Strauss, High Performance Algorithms and Software in Nonlinear Optimization, eds. R. Leoneet al. (Kluwer Academic, Dordrecht, 1998) pp. 87–100. CrossrefGoogle Scholar
    • M. Middendorf, F. Reischle and H. Schmeck, Journal of Heuristics 8, 305 (2002). Crossref, ISIGoogle 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. Eibenet al. (Springer, Amsterdam, 1998) pp. 722–731. Google Scholar
    • E. D. Taillard, Networks 23, 661 (1993). Crossref, ISIGoogle Scholar
    • B. Bullnheimer, R. F. Hartl and Ch. Strauss, Central European Journal of Operations Research 7(1), 25 (1999). ISIGoogle Scholar
    • T. G. Crainic and M. Toulouse, Handbook of Metaheuristics, eds. F. Glover and G. A. Kochenberger (Kluwer, 2002) pp. 251–285. Google Scholar
    • B. Gillett and L. Miller, Operations Research 22, 340 (1974). Crossref, ISIGoogle Scholar
    • E.   Alba and G.   Luque , Parallel Metaheuristics , ed.   Alba ( Wiley , 2005 ) . CrossrefGoogle Scholar
    • E.   Alba , Information Processing Letters   82 , 7 . Crossref, ISIGoogle Scholar
    • K. F. Doerneret al., 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 Scholar
    • S. Benkneret al., Communication Strategies for Parallel Cooperative Ant Colony Optimization on Clusters and Grids Complimentary, proceedings of PARA04 (2005) pp. 3–12. Google Scholar
    • K. 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