An Evolutionary Approach to Solving the Problem of Vehicle Routing

Рассматривается задача маршрутизации транспортных средств, являющаяся обобщением задачи коммивояжера. Существует несколько основных моделей маршрутизации, каждая из которых характеризуется наличием дополнительных условий (по грузоподъемности, транспортному парку,  времени доставки, количеству баз и т. д.) и описывает группу реальных  задач транспортной логистики. Эта задача относится к классу NP-трудных, а наличие дополнительных условий еще более усложняет ее решение. В работе описан двухэтапный подход к организации оптимальной маршрутизации: на первом этапе все пункты доставки распределяются на географические районы методами нечеткой кластеризации, а на втором − для каждого района и каждого транспортного средства с помощью генетического алгоритма  рассчитывается оптимальный маршрут. При этом все имеющиеся в задаче ограничения учитываются при вычислении фитнес-функции и определяют допустимость и приспособленность особей популяции. В большинстве практических задач необходимо иметь сбалансированное распределение потребителей по различным маршрутам для равномерной загрузки транспортного парка и снижения общего времени доставки, поэтому  в представленном алгоритме после предварительной оценки продолжительности всех маршрутов предусмотрена дополнительная процедура выравнивания кластеров. Реализованный алгоритм успешно использовался для получения решения задачи маршрутизации в масштабах города и в условиях реальной транспортной сети.