Розробка оптимізаційної моделі для динамічної маршрутизації транспортних засобів у кількох депо з урахуванням обмежень пропускної здатності та попиту, що залежать від часу
DOI:
https://doi.org/10.15587/1729-4061.2025.336781Ключові слова:
динамічна задача маршрутизації транспортних засобів у кількох депо, MINLP, попит, що залежить від часуАнотація
Об’єктом дослідження є маршрутизація транспортних засобів.
Проблема, яку потрібно вирішити, полягає в тому, що статичні плани часто перевантажують окремі депо та розподіляють затримки по маршрутах. Запропоновано модель змішаного цілочисельного нелінійного програмування для одночасного визначення призначення депо, будівництва маршруту та часу відправлення, з моніторингом пропускної здатності протягом періодів. Модель враховує нелінійні, залежні від навантаження, витрати на проїзд та використовує адаптивне скорочення можливих інтервалів обслуговування для зменшення затримок. Модель вирішується за допомогою зовнішнього наближення, що запускається пулом високоякісних маршрутів. У реалістичних багатоперіодних контрольних рівнях метод зменшує загальні витрати на розподіл та штрафи за затримку доставки порівняно з базовими рівнями одного депо та статичних кількох депо. Найбільші переваги спостерігаються, коли піки попиту локалізовані в кількох депо, оскільки перепризначення депо та перерозподіл відправлень перерозподіляють робоче навантаження без додавання транспортних засобів. Результати пояснюються двома механізмами: обліком пропускної здатності, який запобігає перевантаженню на перевантажених депо, та скоординованим контролем часу відправлення, який обмежує поширення затримки в середині дня. Порівняно з формулюваннями, які попередньо генерують поїздки або враховують мінливість лише неявно, запропонований підхід підтримує доцільність депо, оскільки попит розвивається в межах горизонту. Ключові особливості включають спільне призначення депо з рішеннями про час відправлення, відстеження пропускної здатності за періодами та нелінійне моделювання витрат у рамках точного зовнішнього наближення, сумісного з метаевристиками теплого старту. Практично, цей підхід підтримує планування в електронній комерції, фармацевтичній промисловості та дистрибуції продуктів харчування, де вікна доставки обмежені, а піки часті. Числові результати показують, що модель зменшує загальні експлуатаційні витрати на 18%, знижує штрафи за затримку доставки на 27%, покращує використання транспортних засобів на 12% та зменшує середній час очікування на 37,5% порівняно зі статичними базовими рівнями
Посилання
- Chan, Y., Carter, W. B., Burnes, M. D. (2001). A multiple-depot, multiple-vehicle, location-routing problem with stochastically processed demands. Computers & Operations Research, 28 (8), 803–826. https://doi.org/10.1016/s0305-0548(00)00009-5
- Meesuptaweekoon, K., Chaovalitwongse, P. (2014). Dynamic Vehicle Routing Problem with Multiple Depots. Engineering Journal, 18 (4), 135–149. https://doi.org/10.4186/ej.2014.18.4.135
- Wang, Y., Gou, M., Luo, S., Fan, J., Wang, H. (2025). The multi-depot pickup and delivery vehicle routing problem with time windows and dynamic demands. Engineering Applications of Artificial Intelligence, 139, 109700. https://doi.org/10.1016/j.engappai.2024.109700
- Zhang, M., Chen, A., Zhao, Z., Huang, G. Q. (2023). A multi-depot pollution routing problem with time windows in e-commerce logistics coordination. Industrial Management & Data Systems, 124 (1), 85–119. https://doi.org/10.1108/imds-03-2023-0193
- Dai, B., Li, F. (2021). Joint Inventory Replenishment Planning of an E-Commerce Distribution System with Distribution Centers at Producers’ Locations. Logistics, 5 (3), 45. https://doi.org/10.3390/logistics5030045
- Ralphs, T. K., Kopman, L., Pulleyblank, W. R., Trotter, L. E. (2003). On the capacitated vehicle routing problem. Mathematical Programming, 94 (2-3), 343–359. https://doi.org/10.1007/s10107-002-0323-0
- Mor, A., Speranza, M. G. (2022). Vehicle routing problems over time: a survey. Annals of Operations Research, 314 (1), 255–275. https://doi.org/10.1007/s10479-021-04488-0
- Zong, Z., Tong, X., Zheng, M., Li, Y. (2024). Reinforcement Learning for Solving Multiple Vehicle Routing Problem with Time Window. ACM Transactions on Intelligent Systems and Technology, 15 (2), 1–19. https://doi.org/10.1145/3625232
- Baty, L., Jungel, K., Klein, P. S., Parmentier, A., Schiffer, M. (2024). Combinatorial Optimization-Enriched Machine Learning to Solve the Dynamic Vehicle Routing Problem with Time Windows. Transportation Science, 58 (4), 708–725. https://doi.org/10.1287/trsc.2023.0107
- Wu, X., Wang, D., Wen, L., Xiao, Y., Wu, C., Wu, Y. et al. (2024). Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectives. arXiv. https://doi.org/10.48550/arXiv.2406.00415
- Cordeau, J.-F., Laporte, G., Savelsbergh, M. W. P., Vigo, D. (2007). Chapter 6 Vehicle Routing. Transportation, 367–428. https://doi.org/10.1016/s0927-0507(06)14006-2
- Cordeau, J.-F., Laporte, G., Mercier, A. (2001). A unified tabu search heuristic for vehicle routing problems with time windows. Journal of the Operational Research Society, 52 (8), 928–936. https://doi.org/10.1057/palgrave.jors.2601163
- Adamo, T., Gendreau, M., Ghiani, G., Guerriero, E. (2024). A review of recent advances in time-dependent vehicle routing. European Journal of Operational Research, 319 (1), 1–15. https://doi.org/10.1016/j.ejor.2024.06.016
- Avolio, M., Di Francesco, M., Fuduli, A., Gorgone, E., Wolfler Calvo, R. (2025). Multi-day routes in a multi-depot vehicle routing problem with intermediate replenishment facilities and time windows. Computers & Operations Research, 182, 107084. https://doi.org/10.1016/j.cor.2025.107084
- Campuzano, G., Lalla-Ruiz, E., Mes, M. (2025). The two-tier multi-depot vehicle routing problem with robot stations and time windows. Engineering Applications of Artificial Intelligence, 147, 110258. https://doi.org/10.1016/j.engappai.2025.110258
- Pak, Y.-J., Mun, K.-H. (2024). A practical vehicle routing problem in small and medium cities for fuel consumption minimization. Cleaner Logistics and Supply Chain, 12, 100164. https://doi.org/10.1016/j.clscn.2024.100164
- Wu, Z., Wang, J., Chen, N. A., Liu, Y. (2023). The load-dependent electric vehicle routing problem with time windows. International Journal of Shipping and Transport Logistics, 17 (1/2), 182–213. https://doi.org/10.1504/ijstl.2023.132674
- Mardešić, N., Erdelić, T., Carić, T., Đurasević, M. (2023). Review of Stochastic Dynamic Vehicle Routing in the Evolving Urban Logistics Environment. Mathematics, 12 (1), 28. https://doi.org/10.3390/math12010028
- Gouveia, L., Leitner, M., Ruthmair, M. (2023). Multi-Depot Routing with Split Deliveries: Models and a Branch-and-Cut Algorithm. Transportation Science, 57 (2), 512–530. https://doi.org/10.1287/trsc.2022.1179
- Cavecchia, M., Alves de Queiroz, T., Lancellotti, R., Zucchi, G., Iori, M. (2025). A Real-World Multi-Depot, Multi-Period, and Multi-Trip Vehicle Routing Problem with Time Windows. Proceedings of the 14th International Conference on Operations Research and Enterprise Systems, 112–122. https://doi.org/10.5220/0013153100003893
- Bettinelli, A., Ceselli, A., Righini, G. (2011). A branch-and-cut-and-price algorithm for the multi-depot heterogeneous vehicle routing problem with time windows. Transportation Research Part C: Emerging Technologies, 19 (5), 723–740. https://doi.org/10.1016/j.trc.2010.07.008
- Ichoua, S., Gendreau, M., Potvin, J.-Y. (2003). Vehicle dispatching with time-dependent travel times. European Journal of Operational Research, 144 (2), 379–396. https://doi.org/10.1016/s0377-2217(02)00147-9
- Baldacci, R., Bartolini, E., Mingozzi, A., Valletta, A. (2011). An Exact Algorithm for the Period Routing Problem. Operations Research, 59 (1), 228–241. https://doi.org/10.1287/opre.1100.0875
- Poikonen, S., Wang, X., Golden, B. (2017). The vehicle routing problem with drones: Extended models and connections. Networks, 70 (1), 34–43. https://doi.org/10.1002/net.21746
- Bektaş, T., Laporte, G. (2011). The Pollution-Routing Problem. Transportation Research Part B: Methodological, 45 (8), 1232–1250. https://doi.org/10.1016/j.trb.2011.02.004
- Schneider, M., Stenger, A., Goeke, D. (2014). The Electric Vehicle-Routing Problem with Time Windows and Recharging Stations. Transportation Science, 48 (4), 500–520. https://doi.org/10.1287/trsc.2013.0490
- 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. https://doi.org/10.1016/j.ejor.2012.08.015
- Petris, M., Archetti, C., Cattaruzza, D., Ogier, M., Semet, F. (2024). A heuristic with a performance guarantee for the commodity constrained split delivery vehicle routing problem. Networks, 84 (4), 446–464. https://doi.org/10.1002/net.22238
- Rivera, J. C., Murat Afsar, H., Prins, C. (2016). Mathematical formulations and exact algorithm for the multitrip cumulative capacitated single-vehicle routing problem. European Journal of Operational Research, 249 (1), 93–104. https://doi.org/10.1016/j.ejor.2015.08.067
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2025 Zainal Azis, Tua Halomoan Harahap, Muliawan Firdaus, Herman Mawengkang
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Закріплення та умови передачі авторських прав (ідентифікація авторства) здійснюється у Ліцензійному договорі. Зокрема, автори залишають за собою право на авторство свого рукопису та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons CC BY. При цьому вони мають право укладати самостійно додаткові угоди, що стосуються неексклюзивного поширення роботи у тому вигляді, в якому вона була опублікована цим журналом, але за умови збереження посилання на першу публікацію статті в цьому журналі.
Ліцензійний договір – це документ, в якому автор гарантує, що володіє усіма авторськими правами на твір (рукопис, статтю, тощо).
Автори, підписуючи Ліцензійний договір з ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР», мають усі права на подальше використання свого твору за умови посилання на наше видання, в якому твір опублікований. Відповідно до умов Ліцензійного договору, Видавець ПП «ТЕХНОЛОГІЧНИЙ ЦЕНТР» не забирає ваші авторські права та отримує від авторів дозвіл на використання та розповсюдження публікації через світові наукові ресурси (власні електронні ресурси, наукометричні бази даних, репозитарії, бібліотеки тощо).
За відсутності підписаного Ліцензійного договору або за відсутністю вказаних в цьому договорі ідентифікаторів, що дають змогу ідентифікувати особу автора, редакція не має права працювати з рукописом.
Важливо пам’ятати, що існує і інший тип угоди між авторами та видавцями – коли авторські права передаються від авторів до видавця. В такому разі автори втрачають права власності на свій твір та не можуть його використовувати в будь-який спосіб.
