Communications - Scientific Letters of the University of Zilina 2009, 11(4):5-8 | DOI: 10.26552/com.C.2009.4.5-8

Multi-Threaded Ant Colony Optimization with Asynchronous Communications for the Vehicle Routing Problem

Maria Lucka1, Stanislav Piecka2
1 Faculty of Education, University of Trnava, Slovakia
2 Faculty of Controlling and Informatics, University of Zilina, Slovakia

In this paper we study behaviour of Ant Colony Optimization algorithm for solving the Vehicle Routing Problem implemented by POSIX Threads in parallel cluster environment. The algorithm is based on a fine-grained parallelism strategy which uses asynchronous communication for cooperation in finding solutions. Our aim is to analyze the effect of proposed method on speedup, execution and communication time with respect to the quality of solution.

Keywords: ant colony optimization, parallel metaheuristic, vehicle routing problem, POSIX threads

Published: December 31, 2009  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Lucka, M., & Piecka, S. (2009). Multi-Threaded Ant Colony Optimization with Asynchronous Communications for the Vehicle Routing Problem. Communications - Scientific Letters of the University of Zilina, 11(4), 5-8. doi: 10.26552/com.C.2009.4.5-8
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. DANTZIG, G., RAMSER, R.: The truck dispatching problem. Management Science 6, pp. 80-91, 1959. Go to original source...
    2. CHRISTOFIDES, N., MINGOZZI, A., TOTH, P.: The Vehicle Routing Problem. Combinatorial Optimization, Wiley, Chichester, 1979.
    3. DORIGO, M., GAMBARDELLA, L. M.: Ant Colony System: A cooperative learning approach to the Travelling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1(1), pp. 53-66, 1997. Go to original source...
    4. DOERNER, K. F., HARTL, R. F., BENKNER, S., LUCKA, M.: Cooperative Savings based Ant Colony Optimization - Multiple Search and Decomposition Approaches. Parallel Processing Letters, 16(3), pp. 351-369, 2006. Go to original source...
    5. CRAINIC, T. G.: Parallel Solution Methods for Vehicle Routing Problems. CIRRELT-2007-28, 2007.
    6. GOLDEN, B. L., WASIL, E. A., KELLEY, J. P., CHAO, K. M.: The impact of metaheuristics on solving the vehicle routing problem: algorithms, problem sets, and computational results. Fleet management and logistics, Norwell: Kluwer, 1998. Go to original source...
    7. LUCKA, M., PIECKA, S.: Parallel POSIX Threads Based Ant Colony Optimization using asynchronous Communications. Proceeding of 8th International Conference APLIMAT 2009, pp. 613-620, 2009. Go to original source...
    8. REIMANN, M., DOERNER, K. F., HARTL, R. F.: D-Ants. Savings Based Ants divide and conquer the vehicle routing problem. Computers & Operations Research, 31 (4) (2004), 563-591. Go to original source...
    9. ANDREWS, G. R.: Foundations of Multithreaded, Parallel, and Distributed Programming. Addison-Wesley, Reading, MA, 2000. http://www.cs.arizona.edu/people/greg/mpdbook.
    10. SCHROEDER-PREIKSCHAT, W.: The logical design of parallel operating systems. Prentice-Hall, Englewood Cliffs, NJ, pp. 29, 1994.

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content