ЭВОЛЮЦИОННЫЙ ПОДХОД К РЕШЕНИЮ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ - Тененев, В. А.; Шаура, А. С.; Шаура, Д. С. (Интеллектуальные системы в производстве, 2020)
Рассматривается задача маршрутизации транспортных средств, являющаяся обобщением задачи коммивояжера. Существует несколько основных моделей маршрутизации, каждая из которых характеризуется наличием дополнительных условий (по грузоподъемности, транспортному парку, времени доставки, количеству баз и т. д.) и описывает группу реальных задач транспортной логистики. Эта задача относится к классу NP-трудных, а наличие дополнительных условий еще более усложняет ее решение. В работе описан двухэтапный подход к организации оптимальной маршрутизации: на первом этапе все пункты доставки распределяются на географические районы методами нечеткой кластеризации, а на втором − для каждого района и каждого транспортного средства с помощью генетического алгоритма рассчитывается оптимальный маршрут. При этом все имеющиеся в задаче ограничения учитываются при вычислении фитнес-функции и определяют допустимость и приспособленность особей популяции. В большинстве практических задач необходимо иметь сбалансированное распределение потребителей по различным маршрутам для равномерной загрузки транспортного парка и снижения общего времени доставки, поэтому в представленном алгоритме после предварительной оценки продолжительности всех маршрутов предусмотрена дополнительная процедура выравнивания кластеров. Реализованный алгоритм успешно использовался для получения решения задачи маршрутизации в масштабах города и в условиях реальной транспортной сети.