В статье рассматривается задача маршрутизации нескольких транспортных средств, особенностью которой является требование чередования объектов двух видов в результирующих маршрутах. При этом объекты загрузки должны быть обязательно посещены ровно один раз, а центры разгрузки могут входить в маршруты транспортных средств неограниченное число раз. Необходимо минимизировать максимальную из длин маршрутов транспортных средств, то есть, другими словами, сократить разброс длин полученных маршрутов. Для решения поставленной задачи предлагается использовать генетический алгоритм. С этой целью способ построения хромосом, операторы отбора особей, скрещивания и мутации модернизируются с учетом специфики задачи, причем каждая хромосома включает маршруты всех транспортных средств. Основная часть статьи посвящена исследованию и настройке параметров предложенного алгоритма решения. Для разных размерностей решаемых задач оцениваются длины полученных маршрутов транспортных средств в зависимости от размера популяции, числа итераций алгоритма, а также значения коэффициента мутации. На основе проведенного исследования разработаны рекомендации по применению предложенного алгоритма в рамках поставленной задачи. Также проводится оценка работоспособности и результативности алгоритма в сравнении с точным методом решения. Показано, что предложенный алгоритм позволяет получать решения, близкие к оптимальному, за существенно меньшее время.
This article considers a multi-vehicle routing problem requiring alternating two types of objects in the resulting routes. Loading facilities must be visited exactly once, while unloading centers can be included in vehicle routes an unlimited number of times. It is necessary to minimize the maximum length of vehicle routes, or, in other words, to reduce the variance in the lengths of the resulting routes. A genetic algorithm is proposed for solving this problem. To this end, the chromosome construction method, individual selection operators, crossovers, and mutations are optimized to address the specifics of the problem, with each chromosome including the routes of all vehicles. The main part of the article is devoted to the study and tuning of the parameters of the proposed solution algorithm. For different problem dimensions, the lengths of the resulting vehicle routes are estimated depending on the population size, the number of algorithm iterations, and the mutation coefficient. Based on the conducted research, recommendations for applying the proposed algorithm to the given problem are developed. The algorithm's performance and effectiveness are also evaluated in comparison with an exact solution method. It is shown that the proposed algorithm allows obtaining solutions close to optimal in significantly less time.
The authors declare that there are no conflicts of interest present.