Решение задачи маршрутизации транспортных средств с несколькими центрами и динамическим добавлением целевых объектов

Аннотация

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