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

Ключевые слова: задача маршрутизации транспортных средств, динамическая задача, «жадный» алгоритм, алгоритм с учетом потерь, эвристический алгоритм, сравнительный анализ, NP-трудная задача

Аннотация

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

Скачивания

Данные скачивания пока не доступны.

Биографии авторов

Олег Алексеевич Есаков, Воронежский государственный университет

студент 2-го курса магистратуры кафедры вычислительной математики и прикладных информационных технологий факультета прикладной математики, информатики и механики Воронежского государственного университета

Ольга Александровна Медведева, Воронежский государственный университет

канд. физ.-мат. наук, доц., доцент кафедры вычислительной математики и прикладных информационных технологий факультета прикладной математики, информатики и механики Воронежского государственного университета

Литература

1. Hasle G., Lie K. A. and Quak E. (2007) Geometric modelling, numerical simulation, and optimization. Heidelberg: Springer. Vol. 54. P. 398.
2. Velarde M., Litvinchev I. S. and Cedilio G. (2017) Integrated model of vehicle routing and construction of service zones. Izvestia of the Russian Academy of Sciences. Theory and control systems. No 6. P. 74–79.
3. Yusupova N. I. and Valeev R. S. (2020) About one routing problem for delivery of homogeneous product to different clients by automobile transport means. Modern science-intensive technologies. No 4. P. 84–88.
4. Wang Y. [et al.] (2020) Collaborative two-echelon multicenter vehicle routing optimization based on state–space–time network representation. Journal of Cleaner Production. Vol. 258. P. 120590.
5. Medvedev S., Sorokina A. and Medvedeva O. (2019) The vehicle routing problem for several agents among the objects of two types. XXI International Conference Complex Systems: Control and Modeling Problems. P. 535–540.
6. Medvedev S. N. [et al.] (2019) Formulation and algorithmization of the interleaved vehicle routing problem. Journal of Physics: Conference Series. Vol 1203, No 1. P. 012053.
7. Medvedev S. N. (2021) Mathematical model and algorithm for solving the problem of routing vehicles with several centers with alternation and a single collection point. Vestnik VSU. Series: System Analysis and Information Technologies. No 1. P. 21–32.
8. Montemanni R. [et al.] (2003) A new algorithm for a dynamic vehicle routing problem based on ant colony system. Second international workshop on freight transportation and logistics. P. 27–30.
9. Gendreau M. [et al.] (1999) Parallel tabu search for real-time vehicle routing and dispatching. Transportation science. Vol 33, No 4. P. 381–390.
10. Haghani A. and Jung S. (2005) A dynamic vehicle routing problem with time-dependent travel times. Computers & operations research. Vol 32, No 11. P. 2959–2986.
11. Pavone M. [et al.] (2009) A stochastic and dynamic vehicle routing problem with time windows and customer impatience. Mobile Networks and Applications. Vol 14. P. 350–364.
12. Gladkov L. A. and Gladkova N. V. (2014) Features and new approaches to the solution of dynamic transportation problems with time constraints. Izvestia of the Southern Federal University. Technical Sciences. No 7 (156). P. 178–187.
Опубликован
2025-01-27
Как цитировать
Есаков, О. А., & Медведева, О. А. (2025). Решение задачи маршрутизации транспортных средств с несколькими центрами и динамическим добавлением целевых объектов. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (4), 35-52. https://doi.org/10.17308/sait/1995-5499/2024/4/35-52
Раздел
Математические методы системного анализа, управления и моделирования

Наиболее читаемые статьи этого автора (авторов)