Parallel Delivery Operations Modelling

Рассматривается некоторая схема организации доставки. Ключевым моментом является принцип распараллеливания маршрутов с использованием нескольких перевозчиков одновременно, причем эти вспомогательные перевозчики могут базироваться на основном перевозчике. Примером такой системы доставки может быть фургон, перевозящий несколько автономных перевозчиков, которые, в свою очередь, могут осуществлять одновременные так называемые параллельные доставки. Маршруты доставки определяются на основе координат клиентов, определения приемлемых точек старта для вспомогательных перевозчиков, технических и энергетических ограничений основных и вспомогательных перевозчиков, а также минимизации количества времени, затрачиваемого на операции доставки. Разработанный алгоритм решения задачи маршрутизации доставки с использованием первичных и вторичных перевозчиков позволяет сократить время и ресурсы доставки. Алгоритм реализован на языке Python с использованием библиотек обработки и визуализации траекторий и других пространственно-временных данных, пакетов для извлечения, моделирования, анализа и визуализации уличных сетей на примере города Екатеринбурга.

Ключевые слова

исследование операций; задача маршрутизации; задача коммивояжера; алгоритм ближайшего соседа; служба доставки.

Литература

1. van Duin J.H.R., Vlot T.S., Tavasszy L.A., Duinkerken M.B., van Dijk B. Smart Method for Self-Organization in Last-Mile Parcel Delivery. Transportation Research Record, 2021, vol. 2675, no. 4, pp. 260-270.
2. Zhang J., Campbell J.F., Sweeney II D.C., Hupman A.C. Energy Consumption Models for Delivery Drones: A Comparison and Assessment. Transportation Research, 2021, Part D, vol. 90, article ID: 102668.
3. Zavalishchin D., Vakolyuk K. Algorithm for Parallel Parcels Delivery Service. 2021 Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology, 2021, pp. 0367-0370. DOI: 10.1109/USBEREIT51232.2021.9455068
4. Euchi J., Sadok A. Hybrid Genetic-Sweep Algorithm to Solve the Vehicle Routing Problem with Drones. Physical Communication, 1959, vol. 44, pp. 269-271.
5. Tamke F., Buscher U. A Branch-And-Cut Algorithm for the Vehicle Routing Problem with Drones. Transportation Research, 2021, Part B, vol. 144, pp. 174-203.
6. Chung S.H., Sah B., Lee J. Optimization for Drone and Drone-Truck Combined Operations: A Review of the State of the Art and Future Directions. Computers and Operations Research, 2020, no. 123, article ID: 105004.
7. Dijkstra E.W. A Note on Two Problems in Connexion with Graphs. Numerical Mathematics, vol. 1, issus 1, 1959, pp. 269-271.
8. Macrina G., Pugliese L.D.P., Guerriero F., Laporte G. Drone-Aided Routing: a Literature Review. Transportation Research, 2020, Part C, no. 120, article ID: 102762144.
9. Boeing G. OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks. Computers, Environment and Urban Systems, 2017, vol. 65, no. 9, pp. 126-139.
10. Hunter J.D. Matplotlib: a 2D Graphics Environment. Computing in Science and Engineering, 2007, vol. 9, no. 3, pp. 90-95.
11. Timofeeva G.A., Martynenko A.V. Analysis of Transport Network Development via Probabilistic Modelling. Proceedings of 14th International Conference Stability and Oscillations of Nonlinear Control Systems, 2018, article ID: 8408407.
12. Zavalishchin D.S., Timofeeva G.A. Dynamic Approach to Transportation Planning under Uncertainty. AIP Conference Proceedings, 2017, article ID: 070018.