РЕШЕНИЕ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТНЫХ СРЕДСТВ С НЕСКОЛЬКИМИ ЦЕНТРАМИ, ДИНАМИЧЕСКИМ ДОБАВЛЕНИЕМ ЦЕЛЕВЫХ ОБЪЕКТОВ И ДИРЕКТИВНЫМИ СРОКАМИ НА ИХ ПОСЕЩЕНИЕ
DOI:
https://doi.org/10.17308/sait/1995-5499/2025/4/47-60Ключевые слова:
задача маршрутизации транспортных средств, динамическая задача, директивные сроки, алгоритм с учетом потерь, эвристический алгоритм, сравнительный анализ, NP-трудная задача, теория расписанийАннотация
В статье рассматривается задача маршрутизации транспортных средств с чередованием объектов двух типов и несколькими центрами сбора. Задача определена как динамическая, то есть целевые объекты появляются не все одновременно, а по про шествии некоторого заранее заданного времени с момента начала передвижения мобильных объектов. Кроме того, для них заданы директивные сроки — моменты времени, до которых желательно посетить целевые объекты. Рассмотрено четыре целевые функции, направленные на минимизацию следующих показателей: время завершения посещения всех целевых объектов, количество нарушений директивных сроков, максимальное по длительности нарушение директивных сроков и суммарные временные затраты по всем маршрутам транспортных средств. Предложено четыре алгоритма решения поставлен ной задачи, а именно алгоритм на основе группировки целевых объектов, «жадный» алгоритм со сменой центра сбора, алгоритм с учетом потерь и алгоритм на основе расчета привлекательности центров сбора. Алгоритм на основе группировки целевых объектов учитывает при решении задачи директивные сроки объектов, остальные три основываются только на информации о местоположении объектов. В рамках исследования проведен вычислительный эксперимент для задач разных размерностей, выполнен сравнительный анализ предложенных алгоритмов в зависимости от выбранного критерия оптимальности, а также проведена оценка времени работы каждого из алгоритмов. Для алгоритма на основании расчета привлекательности центров сбора приведены результаты тестирования для двух значений гиперпараметра.
Библиографические ссылки
Akhmetbek Y. Stochastic dynamic vehicle routing problem survey / Y. Akhmetbek, T. Mustakhov // SDU Bulletin: Natural and Technical Sciences. – 2023. – Vol. 62, No 2. – P. 75–87.
Cabuk S. Solving Dynamic Full-Truckload Vehicle Routing Problem Using an Agent-Based Approach / S. Cabuk, R. Erol // Mathematics. – 2024. – Vol. 12, No 13. – P. 2138.
Alvarenga G. B. A hybrid approach for the dynamic vehicle routing problem with time windows / G. B. Alvarenga, R. M. de Abreu Silva, G. R. Mateus // Fifth International Conference on Hybrid Intelligent Systems. – 2005. – P. 7.
de Oliveira S. M. A solution of dynamic vehicle routing problem with time window via ant colony system metaheuristic / S. M. de Oliveira, S. R. de Souza, M. A. L. Silva // 10th Brazilian Symposium on Neural Networks. – 2008. – P. 21–26.
Fabri A. On dynamic pickup and delivery vehicle routing with several time windows and waiting times / A. Fabri, P. Recht // Transportation Research Part B: Methodological. – 2006. – Vol. 40, No 4. – P. 335–350.
Liu Y. A Quick Pheromone Matrix Adaptation Ant Colony Optimization for Dynamic Customers in the Vehicle Routing Problem / Y. Liu, Z. Wang, J. Liu // Journal of Marine Science & Engineering. – 2024. – Vol. 12, No 7.
Konovalenko A. Optimizing a Dynamic Vehicle Routing Problem with Deep Reinforcement Learning: Analyzing State-Space Components / A. Konovalenko, L. M. Hvattum // Logistics. – 2024. – Vol. 8, No 4. – P. 96.
Baty L. Combinatorial optimization-enriched machine learning to solve the dynamic vehicle routing problem with time windows / Baty L. [et al.] // Transportation Science. – 2024. – Vol. 58, No 4. – P. 708–725.
Pan W. Deep reinforcement learning for the dynamic and uncertain vehicle routing problem / W. Pan, S. Q. Liu // Applied Intelligence. – 2023. – Vol. 53, No 1. – P. 405–422.
Bertsimas D. J. Stochastic and dynamic vehicle routing in the Euclidean plane with multiple capacitated vehicles / D. J. Bertsimas, G. Van Ryzin // Operations Research. – 1993. – Vol. 41, No 1. – P. 60–76.
Darwish S. M. Game theory based solver for dynamic vehicle routing problem / S. M. Darwish, B. E. Abdel-Samee // The International Conference on Advanced Machine Learning Technologies and Applications. – 2020. – P. 133142.
Xu H. A hybrid ant colony optimization for dynamic multidepot vehicle routing problem / H. Xu, P. Pu, F. Duan // Discrete Dynamics in Nature and Society. – 2018. – Vol. 2018, No 1.
Есаков О. А. Решение задачи маршрутизации транспортных средств с несколькими центрами и динамическим добавлением целевых объектов / О. А. Есаков, О.А. Медведева // Вестник ВГУ. Серия: Системный анализ и информационные технологии. – 2024. – № 4. – С. 35–52.
Загрузки
Опубликован
Выпуск
Раздел
Лицензия
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
