Решение задачи маршрутизации транспортных средств с несколькими центрами и динамическим добавлением целевых объектов
Аннотация
задача маршрутизации транспортных средствВ статье рассматривается задача маршрутизации транспортных средств с чередованием объектов двух типов и несколькими центрами сбора. Отличительной особенностью этой задачи является появление новых целевых объектов в процессе посещения существующих. При этом расстояние до новых целевых объектов становится известно только после их фактического появления, что требует гибкого подхода к построению маршрутов транспортных средств. Составлена математическая модель задачи с учетом всех входных данных и ограничений. Для решения задачи предложены четыре эвристических алгоритма решения: «жадный» (т. е. принимающий локально оптимальные решения на каждом шаге) алгоритм без смены центра сбора, «жадный» алгоритм со сменой центра сбора, алгоритм с учетом потерь и алгоритм на основе расчета привлекательности центров сбора. Для каждого из предложенных алгоритмов представлено их пошаговое описание, а также разработаны их программные реализации, что позволило протестировать их на множестве входных данных различной размерности и выполнить детальное сравнение результатов работы алгоритмов. Также было предложено несколько способов генерации входных данных для тестирования: случайный и «кластерный» алгоритмы для генерации расположений целевых объектов, а также последовательный и «групповой» алгоритмы для генерации моментов появления целевых объектов. В заключительной части проведен сравнительный анализ разработанных алгоритмов и оценена эффективность их применения для решения задач маршрутизации транспортных средств с динамическим добавлением целевых объектов с входными данными различного размера и характера.
Скачивания
Литература
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.
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).