Удосконалення методу динамічної маршрутизації з часовими вікнами автомобільних перевезень сільськогосподарської продукції
DOI:
https://doi.org/10.31734/agroengineering2021.25.072Ключові слова:
автомобільні вантажні перевезення, динамічна маршрутизація, сумісність замовленьАнотація
Стаття присвячена вдосконаленню методу динамічної маршрутизації автомобільних перевезень транспортних засобів. Розглядається дрібногуртова доставка на кільцевих маршрутах магістральної транспортної мережі вантажів, які швидко псуються. Головним критерієм якості перевезення обрано мінімальну гарантовану тривалість доставки вантажів з усієї сукупності замовлень на перевезення. Обмеження стосуються горизонту прогнозування, а також часових вікон на доставку вантажів. Іншим обмеженням є інтенсивність використання автомобільних транспортних засобів. Поставлено вимогу залучення мінімальної кількості автомобільних транспортних засобів із наявних. Зроблено огляд та аналіз відомих методів динамічної маршрутизації, який показав, що при зростанні кількості замовлень, особливо незапланованих, вони стають неефективними за якістю результатів. З’ясовано, що застосування попередньої класифікації є способом, який покращує результат маршрутизації. У цій роботі як класифікаційну ознаку використано сумісність окремих операцій транспортного процесу, які виконуються послідовно, в єдиному потоці. Кожна з таких операцій стосується доставки дрібногуртових вантажів за одним замовленням. Попередня класифікація замовлень на перевезення дає змогу сформувати з них оптимальні кільцеві розвізні або збірні маршрути. Крім того, для планування доставки на кільцевих маршрутах вантажів, які швидко псуються, було вперше застосовано складання розкладу виконання транспортних операцій. Для цього розглядались часові зв’язки, які виникають між кожною парою заданих замовлень на перевезення. На основі вивчених зв’язків побудовано модель у вигляді орієнтованого графа. Впорядкування такого графа дає змогу розробити активний, найменш тривалий розклад виконання транспортного процесу. Такий метод дає змогу застосувати лінійне програмування при пошуку оптимального розкладу та метод гілок і меж при маршрутизації. Динамічні зміни дорожніх і транспортних умов не погіршують якості попередньо виконаної маршрутизації. Було виконано апробацію методики на тестових вхідних даних. Порівняння результатів, отриманих за запропонованим методом і відомим методом границь і меж, показав покращання щонайменше на 11 % показників якості розроблених маршрутів і розкладів.
Посилання
Anderluh, A., Larsen, R., Hemmelmayr, V. C., & Nolz, P. C. (2020). Impact of travel time uncertainties on the solution cost of a two-echelon vehicle routing problem with synchronization. Flexible Services and Manufacturing Journal, 32(4), 806–828.
Buelvas Padilla, M. P., Nisperuza Canabal, P. A., López Pereira, J. M., & Hernández Riaño, H. E. (2018). Vehicle routing problem for the minimization of perishable food damage considering road conditions. Logistics Research, 11(2), 1–18.
Chen, J., Gui, P., Ding, T., Na, S., & Zhou, Y. (2019). Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on tabu search. Sustainability, 11(23), 65–84.
Çimen, M., & Soysal, M. (2017). Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm. Transportation Research Part D: Transport and Environment, 54, 82–98.
Filina-Dawidowicz, L., & Stankiewicz, S. (2021). Organization and Implementation of Intermodal Transport of Perishable Goods: Contemporary Problems of Forwarders. In Sustainable Design and Manufacturing 2020 (рр. 543–553). Springer, Singapore.
Ichoua, S., Gendreau, M., & Potvin, J.-Y. (2006). Exploiting knowledge about future demands for real-time vehicle dispatching. Transportation Science, 40(2), 211–225.
Jaillet, P., & Wagner, M. R. (2008). Online vehicle routing problems: A survey. In The Vehicle Routing Problem: Latest Advances and New Challenges (рр. 221–237). Boston MA: Springer.
Okulewicz, M., & Mańdziuk, J. (2017). The impact of particular components of the PSO-based algorithm solving the Dynamic Vehicle Routing Problem. Applied Soft Computing, 58, 586–604.
Oliskevych, M. (2019). Dynamic scheduling of highway cargo transportation. In ICCPT 2019: Current Problems of Transport: Proceedings of the 1st International Scientific Conference, May, 28-29, 2019 (pp. 141–151). Ternopil, Ukraine.
Oliskevych, M. S., Mastykash, O. L., & Roi, M. P. (2020). Zalezhnist efektyvnosti diialnosti i kooperatsii pereviznyka vid vkhidnoho potoku zamovlen. Transport development, 1 (6), 103–115.
Pillac, V., Gendreau, M., Guéret, C., & Medaglia, A. L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Research, 225(1), 1–11.
Potvin J-Y., Xua Y., Benyahiac, I. (2009). Vehicle routing and scheduling with dynamic travel times. Computers & Operations Research, 33, 1129–1137. doi:10.1016/j.cor.2004.09.015.
Psaraftis, H. N. (2019). Ship routing and scheduling: the cart before the horse conjecture. Maritime Economics & Logistics, 21(1), 111–124.
Ramamoorthy, M., & Syrotiuk, V. R. (2020). Online re-routing for vehicle breakdown in residential waste collection. In 2020 IEEE 92nd Vehicular Technology Conference (рр. 1–5).
Ritzinger, U., Puchinger, J., & Hartl, R. F. (2016). A survey on dynamic and stochastic vehicle routing problems. International Journal of Production Research, 54(1), 215–231.
Shramenko, N., Muzylyov, D., & Shramenko, V. (2020). Methodology of costs assessment for customer transportation service of small perishable cargoes. International Journal of Business Performance Management, 21(1-2), 132–148.
Skovron, I. Ya., Dorosh, A. S., Demchenko, Ye. B., Bolvanovska, T. V., & Malashkin, V. V. (2020). Pidvyshchennia efektyvnosti dostavky zbirnykh vantazhiv avtomobilnym transportom. Transportni systemy ta tekhnolohii perevezen, 20, 36–43.
Tanaev, V. S., Sotskov, Yu. N., & Strusevych, V. A. (1989). Teoryia raspysanyi: Mnohostadyinie systemi. Moskva: Nauka.
Zhi, L., Zhou, X., & Zhao, J. (2020). Vehicle Routing for Dynamic Road Network Based on Travel Time Reliability. IEEE Access, 8, 190596-190604.
