Application of genetic algorithms for solving transport problems
Authors: Полковникова Н.А. , Полковников А.К. 
Published: September 2022

В статье рассматривается решение классической NP-трудной задачи о коммивояжёре с применением модифицированного генетического алгоритма (ГА). Если в задаче коммивояжёра количество пунктов назначения больше 66, то задача становится трансвычислительной (превышает предел Бремерманна) и метод полного перебора становится неприменим в связи с высокой вычислительной сложностью. Для решения подобных NP-полных оптимизационных задач высокую эффективность показали ГА. Основная особенность ГА состоит в том, что анализируется не одно решение, а некоторое подмножество квазиоптимальных решений (маршрутов), называемых хромосомами и состоящие из генов (пунктов назначений). Решению задачи соответствует хромосома с наилучшим значением целевой функции. В разработанном ГА при реализации скрещивания предлагается два варианта: одноточечный или двухточечный кроссовер. Особенностью разработанного ГА является способность эффективно работать на популяциях с малым числом хромосом, что уменьшает вычислительную сложность алгоритма. Представлены результаты тестирования работы модифицированного ГА на бенчмарке из 70 пунктов назначений в среде Matlab 2021a, полученный результат показывает сходимость на тестовой выборке и высокую эффективность ГА. Решение задачи коммивояжёра также реализовано в виде программы в среде MS Visual Studio 2022 на языке Visual C# с возможностью загрузки географической карты и настройкой основных характеристик ГА (выбор количества хромосом, вероятность мутации, количество итераций). Результаты поиска наименьшего пути по указанным 15 городам на карте Краснодарского края показывают высокую эффективность применения ГА для решения транспортных задач. Практическое применение задачи коммивояжёра с использованием модифицированного ГА использовано при составлении оптимального маршрута для развоза товаров по заданным точкам на карте г. Новороссийска.

The article considers the solution of classical NP-hard traveling salesman problem (TSP) using modified genetic algorithm (GA). If in TSP the number of destinations is more than 66, then the problem becomes transcomputational (exceeds the Bremermann’s limit) and the brute force method becomes inapplicable due to high computational complexity. To solve such NP-complete optimization problems, GAs have shown high efficiency. The main feature of GA is that it analyzes not one solution, but a subset of quasi-optimal solutions (routes) called chromosomes and consisting of genes (destinations). The solution of the problem corresponds to the chromosome with best value of the objective function. In the developed GA, when implementing crossing, two options are offered: a single-point or two-point crossover. The distinctive feature of proposed modified GA is the ability to work effectively on populations with a small number of chromosomes, which reduces the computational complexity of the algorithm. The work results of modified GA on a benchmark of 70 destinations in Matlab 2021a environment are presented, obtained result shows the convergence on test set and high efficiency of GA. The solution of TSP is also implemented as a program in MS Visual Studio 2022 in Visual C# with the ability to load a geographic map and set the main characteristics of GA (selection of the number of chromosomes, mutation probability, number of iterations). The results of shortest path search for indicated 15 cities on the map of the Krasnodar region show high efficiency of GA for solving transport problems. The practical application of TSP using modified GA proposed in compiling the optimal route for delivering goods to given points on the map of Novorossiysk city.