Решение задачи маршрутизации транспорта с чередованием объектов с определением местоположения центров на основе алгоритмов кластеризации

Аннотация

В статье рассматривается задача маршрутизации транспорта с несколькими центрами и чередованием объектов двух видов, особенностью которой является отсутствие исходной информации о местоположении центров. Задача состоит в поиске координат центров и в определении порядка посещения объектов с целью минимизации общей длины маршрута. Предложены математическая модель задачи с разными типами переменных и алгоритм решения поставленной задачи. Его основная идея состоит в кластеризации объектов для нахождения координат центров и последующем определении порядка посещения кластеров. В статье рассматриваются два алгоритма кластеризации: k-means и подход, основанный на применении муравьиных стратегий. Объекты типа центр предлагается располагать в центры масс полученных кластеров. Далее предлагается способ задания матрицы расстояний между кластерами, что позволяет перейти к решению задачи коммивояжера для формирования искомого маршрута. В заключении проведен анализ применяемых алгоритмов кластеризации и сделаны выводы по целесообразности их использования в рамках поставленной задачи. Также проведено сравнение предложенного в статье алгоритма с точным методом решения. Оценена эффективность процедуры поиска местоположения центров.