Influence of parameters of the ant colony algorithm on the traveling salesman problem solution

Authors

DOI:

https://doi.org/10.15587/1729-4061.2014.26290

Keywords:

routing of small-batch trucking, traveling salesman problem, ant colony algorithm, algorithm’s control parameters

Abstract

Transportation of many freights can be given as the travelling salesman problem, when freight is delivered from one distribution center to customers during one trip. There are used exact, heuristic and metaheuristic methods for the solving this problem. It was chosen the ant colony algorithm from metaheuristic methods because it is close to the statement of the travelling salesman problem at the expense of its physical resemblance. However, the control parameters of the algorithm influent on its efficiency. Therefore, investigation of the searching of control parameter values, by which the algorithm will look for the optimal route as soon as possible, was carried out.

The ant colony algorithm for the travelling salesman problem was implemented in MATLAB environment. At the first step for the networks with 15, 20, 25 and 30 nodes, that answer to the real delivery systems, there was determined the set of values of the control parameters, which ensure the largest efficiency of the ant colony algorithm –α=1,β=5,ρ=0,2. At the second step, there was determined minimal amount of iterations needed for searching of the optimal route for these networks. At the third step there was determined that insertion of three elite ants enabled to decrease amount of iterations for the optimal route searching (for example, for 20-nodes network from 307 to 69).

Obtained results can be used not only for the travelling salesman problem solving but also for vehicle routing of small-batch trucking, when the ant colony algorithm considers additional conditions.

Author Biographies

Ігор Андрійович Могила, Lviv Polytechnic National University 12, Bandera str., Lviv, Ukraine, 79013

Assistant

Transport Technologies Department

Ірина Іванівна Лобач, Lviv Polytechnic National University 12, Bandera str., Lviv, Ukraine, 79013

Transport Technologies Department

Оксана Андріївна Якимець, Lviv Polytechnic National University 12, Bandera str., Lviv, Ukraine, 79013

Transport Technologies Department

References

  1. Lashchenykh, O., Kuzkin, O. (2006). Metody i modeli optymizatcii transportnykh protcecsiv i system [Optimization methods and models for transport processes and systems]. Zaporizhzhia, ZNTU, 434.
  2. Hamdy, A. Taha (2005). Vvedenie v issledovanie operatsii [Operations research: an introduction]. Moscow, Williams, 912.
  3. Pozhydaiev, M. (2010). Algoritmy resheniia zadachi marshrutizatcii transporta [Algorithms for solving of vehicle route problem] Ph.D. dissertation, 05.13.18. Tomsk State University, 136.
  4. Shtovba, S. (2005). Muravinyie alhoritmy: teoriya i primenenie [The ant algorithm: theory and application]. Programmirovanie, 4, 1–16.
  5. Shtovba, S., Rudyy, O. (2004). Murashyni alhorytmy optymizatciyi [Ant colony for optimization]. Visnyk VPI, 4, 62–69.
  6. Shtovba, S. (2003). Muravinyie alhoritmy [Ant algorithms]. Exponenta Pro, 4, 70–75.
  7. Jones, M. T. (2004). Programmirovanie iskusstvennogo intelekta v prilozheniyah [AI application programming]. Moscow, DMK Press, 312.
  8. Subbotin, S., Oliynyk, A., Oliynyk, O. (2009). Neiteratyvni, evoliutciyni ta multiahentni metody syntezu nechitkolohichnykh i neyromerezhnykh modeley [Non-iterative, evolutionary and multi-agent methods of synthesis of fuzzy-logic and neural-network models]. Zaporizhzhia, ZNTU, 375.
  9. Dorigo, M., Stuzle, T. (2004). Ant Colony Optimization. Cambridge, A Bradford Book, 305.
  10. Kazharov, A., Kureichik, V. (2013). Ispolzovanie shablonnyh reshenii v muravinyh algoritmah [The usage of cut-and-dried solutions in the ant colony algorithms]. Izvestiya SFedU: Engineering Sciences, 7 (144), 17–22.
  11. Danchuk, V., Svatko, V. (2012). Optymizatciyi poshuku shlyakhiv po hrafu v dynamichniy zadachi komivoyazhera metodom modyfikovanoho murashynoho alhorytmu [Finding ways optimization on graf in dynamic problem by modified method of ant colony algorithm]. Systemni doslidzhennya ta informatciyni tekhnolohiyi, 2, 78–86.
  12. Cheng, C.-B., Mao, C.-P. (2007). A modified ant colony system for solving the travelling salesman problem with time windows. Mathematical and Computer Modelling, 46 (9-10), 1225–1235. doi:10.1016/j.mcm.2006.11.035
  13. Yang, J., Shi, X., Marchese, M., Liang, Y. (2008). An ant colony optimization method for generalized TSP problem. Progress in Natural Science, 18 (11), 1417–1422. doi:10.1016/j.pnsc.2008.03.028
  14. Dorigo, M., Gambardella, L. M. (1997). Ant Colony Systems: a Cooperative Learning Approach to the Traveling Salesman Problem. IEEE Transactions on Evolutionary Computation, 1 (1), 53–66. doi:10.1109/4235.585892
  15. Ignatiev, A. (2009). Ispolzovanie algoritma muravinuh koloniy dlia resheniia zadachi marshrutizatcii transportnih sredstv [The usage of the ant colony algorithm for vehicle routing problem solving]. Proceedings of the IV international scientific and practical conference “Modern information technologies and IT-education”. Moscow, Lomonosov MSU. Available at: http://2009.it-edu.ru/docs/Sekziya_8/3_Ignat%27ev_Ignatyev.doc
  16. Jun-Mam, K., Yi, Z. (2012).Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem. Energy Procedia, 17, 319–325. doi: 10.1016/j.egypro.2012.02.101.
  17. Hlaing, Z. C., Khine, M. A. (2011). Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm. International Journal of Information and Education Technology, vol. 1, № 5, 404-409. doi: 10.7763/ijiet.2011.v1.67.
  18. Ivanova, I. (2012). Issledovanie raboti muravinogo algoritma na primere zadachi kommivoiazhera [Investigation of ant colony algorithm functioning based on travelling salesman problem example]. Research and Technology: Step into the Future, Vol. 7, № 3, 39–46.

Downloads

Published

2014-07-24

How to Cite

Могила, І. А., Лобач, І. І., & Якимець, О. А. (2014). Influence of parameters of the ant colony algorithm on the traveling salesman problem solution. Eastern-European Journal of Enterprise Technologies, 4(4(70), 18–23. https://doi.org/10.15587/1729-4061.2014.26290

Issue

Vol. 4 No. 4(70) (2014): Mathematics and cybernetics - applied aspects

Section

Mathematics and Cybernetics - applied aspects

License

Copyright (c) 2014 Ігор Андрійович Могила, Ірина Іванівна Лобач, Оксана Андріївна Якимець

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.

The consolidation and conditions for the transfer of copyright (identification of authorship) is carried out in the License Agreement. In particular, the authors reserve the right to the authorship of their manuscript and transfer the first publication of this work to the journal under the terms of the Creative Commons CC BY license. At the same time, they have the right to conclude on their own additional agreements concerning the non-exclusive distribution of the work in the form in which it was published by this journal, but provided that the link to the first publication of the article in this journal is preserved.

A license agreement is a document in which the author warrants that he/she owns all copyright for the work (manuscript, article, etc.).
The authors, signing the License Agreement with TECHNOLOGY CENTER PC, have all rights to the further use of their work, provided that they link to our edition in which the work was published.
According to the terms of the License Agreement, the Publisher TECHNOLOGY CENTER PC does not take away your copyrights and receives permission from the authors to use and dissemination of the publication through the world's scientific resources (own electronic resources, scientometric databases, repositories, libraries, etc.).
In the absence of a signed License Agreement or in the absence of this agreement of identifiers allowing to identify the identity of the author, the editors have no right to work with the manuscript.
It is important to remember that there is another type of agreement between authors and publishers – when copyright is transferred from the authors to the publisher. In this case, the authors lose ownership of their work and may not use it in any way.