UDC 004.942
1 Non-profit joint stock company “D. Serikbayev East Kazakhstan Technical University”, Ust-Kamenogorsk, Kazakhstan
 SRakhmetullina@edu.ektu.kz
|
2 School of Information Technologies and Intelligent Systems of D. Serikbayev East Kazakhstan Technical University, Ust-Kamenogorsk, Kazakhstan
gzhomartkyzy@edu.ektu.kz
|
3 Taras Shevchenko National University of Kyiv, V.M. Glushkov Institute of Cybernetics
of the NAS of Ukraine, Kyiv, Ukraine
yuri.krak@gmail.com
|
|
DEVELOPMENT OF AN ALGORITHM FOR SOLVING AN ASYMMETRIC
ROUTING PROBLEM BASED ON THE ANT COLONY METHOD
Abstract. One of the major problems of transport logistics is planning optimal delivery routes. Solving this problem leads to combinatorial optimizations that require complex computations. The present research considers an asymmetric problem of transport routing with a limitation of the carrying capacity of transport facilities, the duration of the route and a heterogeneous transport facilities fleet. An algorithm for solving the routing problem based on the ant colony method is proposed. The web application that has been developed implements the proposed algorithm for solving this problem. The obtained optimal routes were compared with the results of route building by other cartographic services. The proposed algorithm showed the best result.
Keywords: optimization, asymmetric routing problems, graph route search, web applications, ant colony method.
full text
REFERENCES
- Dantzig G.B., Ramser J.H. The truck dispatching problem. Management Science. 1959. Vol. 6, N 1. P. 80–91.
- Clarke G., Wright J.W. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research. 1964. Vol. 12, N 4. P. 568–581.
- Bozorg-Haddad O., Solgi M., Loїiciga H.A. Meta-Heuristic and Evolutionary Algorithms for Engineering Optimization. Hoboken: Wiley, 2017. 304 p.
- Wu Yi-W., Wang Y. Collection line optimisation in wind farms using improved ant colony optimisation. Wind Engineering. 2021. Vol. 45, Iss. 3. Р. 589–600. https://doi.org/10.1177/0309524X20917319.
- Pamosoaji A.K., Setyohadi D.B. Novel graph model for solving Collision-Free Multiple-Vehicle Traveling Salesman Problem using ant colony optimization. Algorithms. 2020. Vol. 13, Iss. 6. 153. https://doi.org/10.3390/a13060153 .
- Kiatwuthiamorn J., Thammano A. Swarm optimization algorithm based on the ant colony life cycle. Malaysian Journal of Computer Science. 2019. Sp. Iss. 2. P. 1–14. https://doi.org/10.22452/mjcs.sp2019no2.1.
- Chanpa R., Jabraeil Jamali M.A., Hatamlou A., Anari B. An optimized swarm intelligence algorithm based on the mass defence of bees. International Journal of Nonlinear Analysis and Applications. 2022. Vol. 13, Iss. 1. P. 3451–3462. https://doi.org/10.22075/ijnaa.2022.6108.
- Jafari-Marandi R., Smith B.K. Fluid genetic algorithm (FGA). Journal of Computational Design and Engineering. 2017. Vol. 4, Iss. 2. P. 158–167. https://doi.org/10.1016/j.jcde.2017.03.001 .
- Wang H., Zhang J., Dong J. Application of ant colony and immune combined optimization algorithm in path planning of unmanned craft. AIP Advances. 2022. Vol. 12, Iss. 2. 025313. https://doi.org/10.1063/5.0077858 .
- Mutar M.L., Burhanuddin M.A., Hameed A.S., Yusof N., Mutashar H.J. An efficient improvement of ant colony system algorithm for handling capacity vehicle routing problem. International Journal of Industrial Engineering Computations. 2020. Vol. 11, Iss. 4. P. 549–564. https://doi.org/10.5267/j.ijiec.2020.4.006 .
- Horbulin V.P., Hulianytskyi L.F., Sergienko I.V. Optimization of UAV team routes in the presence of alternative and dynamic depots. Cybernetics and Systems Analysis. 2020. Vol. 56, N 2. P. 195–203. https://doi.org/10.1007/s10559-020-00235-8.
- Greco F. (Ed.) Travelling Salesman Problem. Rijeka: In-The, 2008. 214 p. URL: http://www.exatas.ufpr.br .
- Borcinova Z. Two models of the capacitated vehicle routing problem. Croatian Operational Research Review. 2017. Vol. 8, N 2. P. 463–469. doi.org/10.17535/crorr.2017.0029 .
- Ban H.-B., Nguyen P.K. A hybrid metaheuristic for solving asymmetric distance-constrained vehicle routing problem. Computational Social Networks. 2021. Vol. 8, N 3. https://doi.org/10.1186/s40649-020-00084-7.
- Sergienko I.V., Hulianytskyi L.F., Sirenko S.I. Classification of applied methods of combinatorial optimization. Cybernetics and Systems Analysis. 2009. Vol. 45, N 5. P. 732–741. https://doi.org/10.1007/s10559-009-9134-0.
- Junaid M., Sohail A., Ahmed A., Baz A., Khan I.A., Alhakami H. A hybrid model for load balancing in cloud using file type formatting. IEEE Access. 2020. Vol. 8. P. 118135–118155. https://doi.org/10.1109/ACCESS.2020.3003825.
- Vimal S., Khari M., Crespo R.G., Kalaivani L., Dey N., Kaliappan M. Energy enhancement using Multiobjective Ant colony optimization with Double Q learning algorithm for IoT based cognitive radio networks. Computer Communications. 2020. Vol. 154. P. 481–490. https://doi.org/10.1016/j.comcom.2020.03.004.
- Dorigo M., Sttzle T. Ant colony optimization: overview and recent advances. In: Handbook of Metaheuristics. Gendreau M., Potvin J.-Y. (Eds.). Cham: Springer, 2019. P. 311–351.
- Pellonper T. Ant colony optimization and the vehicle routing. problem. M.Sc. Thesis. University of Tampere School of Information Sciences, Computer Science, 2014. URL: https://core.ac.uk/download/pdf/250133821.pdf .
- MVC Architecture. URL: https://www.javatpoint.com/php-mvc-architecture .
- API Google Maps. URL: https://developers.google.com/maps .
