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
×

System Upgrade on Tue, May 28th, 2024 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

    https://doi.org/10.1142/S0129626406002691Cited by:34 (Source: Crossref)

    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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • M. Florian and M. Gendreau, Parallel Computing 27, 1521 (2001). Crossref, Web of ScienceGoogle Scholar
    • A. Le Bouthillier and T. G. Crainic, Computers & Operations Research 32, 1685 (2005). Crossref, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • B. Bullnheimer, R. F. Hartl and Ch. Strauss, Central European Journal of Operations Research 7(1), 25 (1999). Web of ScienceGoogle 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, Web of ScienceGoogle Scholar
    • E.   Alba and G.   Luque , Parallel Metaheuristics , ed.   Alba ( Wiley , 2005 ) . CrossrefGoogle Scholar
    • E.   Alba , Information Processing Letters   82 , 7 . Crossref, Web of ScienceGoogle 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