Comparison of the results of using various evolution algorithms to solve the problem of route optimization of unmanned vehicles

Fedina A.A., Nurgaliev A.I., Skvortsova D.A.
 pdf (2500K)

In this paper, a comparative analysis of the exact and heuristic algorithms presented by the method of branches and boundaries, genetic and ant algorithms, respectively, is carried out to find the optimal solution to the traveling salesman problem using the example of a courier robot. The purpose of the work is to determine the running time, the length of the obtained route and the amount of memory required for the program to work, using the method of branches and boundaries and evolutionary heuristic algorithms. Also, the most appropriate of the listed methods for use in the specified conditions is determined. This article uses the materials of the conducted research, implemented in the format of a computer program, the program code for which is implemented in Python. In the course of the study, a number of criteria for the applicability of algorithms were selected (the time of the program, the length of the constructed route and the amount of memory necessary for the program to work), the results of the algorithms were obtained under specified conditions and conclusions were drawn about the degree of expediency of using one or another algorithm in various specified conditions of the courier robot. During the study, it turned out that for a small number of points  $\leqslant10$, the method of branches and boundaries is the most preferable, since it finds the optimal solution faster. However, when calculating the route by this method, provided that the points increase by more than 10, the operating time increases exponentially. In this case, more effective results are obtained by a heuristic approach using a genetic and ant algorithm. At the same time, the ant algorithm is distinguished by solutions that are closest to the reference ones and with an increase of more than 16 points. Its relative disadvantage is the greatest resource intensity among the considered algorithms. The genetic algorithm gives similar results, but after increasing the points more than 16, the length of the found route increases relative to the reference one. The advantage of the genetic algorithm is its lower resource intensity compared to other algorithms.

The practical significance of this article lies in the potential possibility of using the results obtained for the optimal solution of logistics problems by an automated system in various fields: warehouse logistics, transport logistics, «last mile» logistics, etc.

Keywords: unmanned vehicles, optimization algorithms, branches and bounds method, genetic algorithm, ant algorithm, traveling salesman problem, logistics systems
Citation in English: Fedina A.A., Nurgaliev A.I., Skvortsova D.A. Comparison of the results of using various evolution algorithms to solve the problem of route optimization of unmanned vehicles // Computer Research and Modeling, 2022, vol. 14, no. 1, pp. 45-62
Citation in English: Fedina A.A., Nurgaliev A.I., Skvortsova D.A. Comparison of the results of using various evolution algorithms to solve the problem of route optimization of unmanned vehicles // Computer Research and Modeling, 2022, vol. 14, no. 1, pp. 45-62
DOI: 10.20537/2076-7633-2022-14-1-45-62
URL: http://crm-en.ics.org.ru/journal/article/3160/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Copyright © 2009–2024 Institute of Computer Science