SOLVING THE ROUTING PROBLEM BY ANT COLONY OPTIMIZATION ALGORITHMS

Authors

  • Vladimir V. Zhikharevich
  • Nataliia A. Matsiuk
  • Sergey E. Ostapov

DOI:

https://doi.org/10.47839/ijc.15.2.841

Keywords:

Ant Colony Optimization, Multiagent Modeling, Optimization, Vehicle Routing Problem, Transport Infrastructure.

Abstract

The use of ant colony optimization algorithms for solving the routing problem in a process of products delivery taking into account a city transport infrastructure has shown in this research. The vehicle routing problem belongs to NP-hard task and its solution requires significant computing resources. Therefore, it is recommended to use metaheuristic methods to solve such problems including ant colony optimization algorithms. Solution of the Vehicle Routing Problem will cause a decrease of enterprises non-productive resources consumption and will promote the increase of their efficiency and competitiveness. The test example, consisting of eight consumers of freight and two transportation means with unlimited load capacity, moving around the certain city, is used for the implementation of the model. It can be further refined by taking into account various parameters besides transport infrastructure, including limitations on carrying capacity, a number of vehicles an working hours, an amount of consumers’ orders and a time for loading and unloading, etc.

References

V. V. Beglyarov, A. N. Beryoza, A. S. Storozhenko, “Hybrid ant multi-population genetic algorithm,” Herald of YuFU. Technical Science, no. 7, pp. 39-45, 2010. (in Russian)

J. E. Bell, P. R. McMullen, “Ant colony optimization techniques for the vehicle routing problem,” Advanced Engineering Informatics, no. 18, pp. 41-48, 2004.

J. Berger, M. Barkaoui, “A new hybrid genetic algorithm for the capacitated vehicle routing problem,” Journal of the Operational Research Society, vol. 41, issue 2, pp. 179-194, 2003.

A. S. Bjarnadottir, Solving the Vehicle Routing Problem with Genetic Algorithms, Technical University of Denmark, 2004, 127 p.

C. Blum, A. Roli, “Metaheuristics in combinatorial optimization: overview and conceptual comparison,” ACM Computing Surveys, vol. 35, issue 3, pp. 268-308, 2003.

M. Dorigo, “Ant colonies for the traveling salesman problem,” Biosystems, vol. 43, pp. 73-81, 1997.

M. Dorigo, G. Di Caro, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, issue 3, pp. 137-172, 1999.

J. S. Arias-Rojas, J. F. Jiménez, J. R. Montoya-Torres, “Solving of school bus routing problem by ant colony optimization,” Revista EIA, vol. 17, pp. 193-208, 2012.

E. A. Kochegurova, Yu. A. Martyinova, “Optimizing compilation of public transport routes when creating an automated decision support system,” Herald of the Tomsk Polytechnic University, vol. 323, issue 5, pp. 79-84, 2013. (in Russian)

V. M. Kureychik, A. A. Kazharov, “The using bee algorithms for combinatorial problems,” Artificial Intelligence, issue 3, pp. 583-589, 2010. (in Russian)

V. M. Kureychik, A. A. Kazharov, “The using of swarm intelligence in solving of the NP-hard problems,” Herald of YuFU. Technical Science, no. 7, pp. 30-36, 2011. (in Russian)

V.V. Kureychik, V.M. Kureychik, S. I. Rodzin, “The concept of evolutionary computation inspired by natural computing,” Herald of YuFU. Technical Science, Special issue “Intelligent CAD”, Taganrog, Publishing House TTI YuFU, vol. 4, issue 93, 256 p., 2009. (in Russian)

M. Manfrin, Ant Colony Optimization for the Vehicle Routing Problem, DEA defense at ULB, Brussels, 2004.

Mao-xiang, L., Hu, Si-ji, “Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm,” China Journal of Management Science, vol. 10, issue 5, pp. 51-56, 2002.

A. V. Martyinov, V. M. Kureychik, “Hybrid algorithm for solving the traveling salesman problem,” Herald of YuFU. Technical Science, vol. 4, issue 165, pp. 36-44, 2015. (in Russian)

N. Matsiuk, “Solution of travelling salesman problem for wholesale outlays considering repeated visitation of certain sales outlets,” MEST Journal, Belgrade : MESTE, vol. 3, issue 1, pp. 120-126, 2015.

R. Montemanni, L. M. Gambardella, A. E. Rizzoli, A. V. Donati, “Ant colony system for a dynamic vehicle routing problem,” Journal of Combinatorial Optimization, vol. 10, pp. 327-343, 2005.

Li, N., Wang, Sh., Li, Yu, “A hybrid approach of GA and ACO for VRP,” Journal of Computational Information Systems, vol. 7, issue 13, pp. 4939-4946, 2011.

T. Pellonperä, Ant Colony Optimization and the Vehicle Routing Problem, University of Tampere, 2014, 51 p.

R. Ruiz, C. Maroto, “A decision support system for a real vehicle routing problem,” European Journal of Operational Research, vol. 153, issue 3, pp. 593-606, 2004.

S. D. Shtovba, “Ant algorithms, exponenta pro,” Math Applications, no. 4, pp. 70-75, 2003.

Shuoben Bi, Xueshi Dong, Yan Ma, “The design and analysis of TSP problem based on genetic algorithm and ant colony algorithm,” International Journal of Education and Management Engineering, vol. 2, issue 9, pp. 56-60, 2012.

W. Zhong, Using Traveling Salesman Problem Algorithms to Determine Multiple Sequence Alignment Orders, Master Thesis, The University of Georgia, Athens, Georgia, 2003, 66 p.

K. Zoulel, F. C. Besma, K. Mekki, “TSP based evolutionary optimization approach for the vehicle routing problem,” in Proceedings of the 2nd Mediterranean Conference on Intelligent Systems and Automation, 23-25 March 2009, pp. 373-376.

Downloads

Published

2016-06-30

How to Cite

Zhikharevich, V. V., Matsiuk, N. A., & Ostapov, S. E. (2016). SOLVING THE ROUTING PROBLEM BY ANT COLONY OPTIMIZATION ALGORITHMS. International Journal of Computing, 15(2), 84-91. https://doi.org/10.47839/ijc.15.2.841

Issue

2016, Volume 15, Issue 2

Section

Articles

License

International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:
•    Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
•    Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
•    Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.