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