AN OPTIMIZATION MODEL FOR THE FOOD DELIVERY VEHICLE ROUTING PROBLEM

Abstract

Today, restaurants derive a significant portion of their income from online food orders. Most of the orders are delivered to customers via motor couriers. While delivering the orders to the customer in the fastest way without exceeding the defined time period directly affects customer satisfaction, delivering the order to the customer in the most economical way is also important for the profitability of the company. Assigning orders to couriers in different regions and creating courier routes is a common optimization problem for restaurants. In this study, a courier vehicle routing problem is considered. A mathematical model of the problem is constructed by considering the real-time orders coming to the restaurant and the couriers in the region. In the real life problem, delivery time and transportation constraints are included in the model. The problem addressed is a single distribution center with capacity and time constraints and an open routing problem where couriers are outsourced and orders are picked up from the same restaurant. With the solution of the integer programming model, an optimum solution with the lowest courier transportation costs was obtained. Sensitivity analyses were performed to examine the effects of the number of couriers in different scenarios on order delivery time and distribution cost.

Keywords

• Courier Routing Problem
• Food Delivery
• Integer Programming

YEMEK SİPARİŞLERİ DAĞITIMI ARAÇ ROTALAMA PROBLEMİ İÇİN BİR OPTİMİZASYON MODELİ

Abstract

Günümüzde restoranlar, gelirlerinin önemli bir kısmını çevrimiçi yemek siparişlerinden elde etmektedir. Siparişlerin büyük bir kısmı motorlu kuryeler aracılığıyla müşterilere ulaştırılmaktadır. Siparişlerin tanımlanan süreyi aşmadan, en hızlı şekilde müşteriye teslim edilmesi, müşteri memnuniyetini direkt etkilerken, siparişin en ekonomik yöntemle müşteriye ulaştırılması da firmanın karlılığı açısından önem arz etmektedir. Siparişlerin farklı bölgelerdeki kuryelere atanma kararları ile kurye rotalarının oluşturulması restoranlar açısından sürekli karşılaşılan bir optimizasyon problemidir. Bu çalışmada bir kurye araç rotalama problemi incelenmiştir. Restorana gelen gerçek zamanlı siparişler ile bölgedeki kuryeler dikkate alınarak, problemin matematiksel modeli oluşturulmuştur. Gerçek hayat probleminde, teslim süresi ve taşıma ile ilgili kısıtlar modele dahil edilmiştir. Ele alınan problem, kuryelerin dış kaynak olarak kullanıldığı ve siparişlerin aynı restorandan toplandığı, tek dağıtım merkezli, kapasite ve zaman kısıtlı ve açık uçlu bir rotalama problemidir. Oluşturulan tamsayılı programlama modelinin çözümü ile kurye taşıma maliyetlerinin en düşük olduğu optimum bir çözüm elde edilmiştir. Gerçekleştirilen duyarlılık analizleri ile farklı senaryolardaki kurye sayılarının sipariş teslim süresi ve dağıtım maliyetine etkileri incelenmiştir.

Keywords

• Kurye Rotalama Problemi
• Yemek Teslimatı
• Tamsayılı Programlama

References

1. Al-Kanj, L., Nascimento, J., Powell., W. B. (2020). Approximate dynamic programming for planning a ride-hailing system using autonomous fleets of electric vehicles. European J. Oper. Res., 284(3), 1088–1106.
2. Archetti, C., Bianchessi, N., & Speranza, M. G. (2014). Branch-and-cut algorithms for the split delivery vehicle routing problem. European Journal of Operational Research, 238(3), 685- 698.
3. Baldacci, R., Mingozzi, A., Roberti, R., & Calvo, R. W. (2013). An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2), 298-314.
4. Battarra, M., Erdogan, G., & Vigo, D. (2014). Exact algorithms for the clustered vehicle routing problem. Operations Research, 62(1), 58-71.
5. Chen, X., Ulmer, M. W., Thomas., B. W. (2022). Deep Q-learning for same-day delivery with vehicles and drones. European J. Oper. Res., 298(3), 939–952.
6. Chen, Y., Qian, Y., Yao, Y., Wu, Z., Li, R., Zhou, Y., Hu, H., Xu, Y. (2019). Can sophisticated dispatching strategy acquired by reinforcement learning? In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (1395–1403. ss.). Springer.
7. Dantzig, G.B., Ramser, J.H., (1959). The truck dispatching problem. Management Science, 6(1), 80-91.
8. Jahanshahi, H., Bozanta, A., Cevik, M., Kavuk, E. M., Tosun, A., Sonuc, S. B., Kosucu B., Basar¸ A. (2022). A deep reinforcement learning approach for the meal delivery problem. Knowledge-Based Systems, 243, 108489

9. Jairo R., Montoya T., Francob, JL., Isazac, SN., Jiménezd, H.F., Herazo-Padillae, N. (2015). A literature review on the vehicle routing problem with multiple depots, Comput. Ind. Eng., 79, 115–129.
10. Keskintürk, T., Topuk, N., Özyeşil, O. (2015). Araç rotalama problemleri ile çözüm yöntemlerinin sınıflandırılması ve bir uygulama, İşletme Bilimi Dergisi, 3(2), 77-107.
11. Korablev, V., Makeev, I., Kharitonov, E., Tshukin, B., Romanov, I. (2016). Approaches to solve the vehicle routing problem in the valuables delivery domain, Procedia Computer Science, 88, 487-492.
12. Kumar, S.N., Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intell. Inf. Manage, 4, 66–74.
13. Lin, K., Zhao, R., Xu, Z., Zhou. J. (2018). Efficient large-scale fleet management via multi-agent deep reinforcement learning. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (1774–1783. pp.), New York, U.S.
14. Masoud, N., & Jayakrishnan, R. (2017). A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system. Transportation Research Part B: Methodological, 106, 218–236.
15. Novoa-Flores, G. I., Carpente, L., Lorenzo-Freire, S. (2018). A vehicle routing problem with periodic replanning. Multidisciplinary Digital Publishing Institute Proceedings, 2(18), 1192.
16. Peng, B., Wang, J., Zhang, Z. (2019). A deep reinforcement learning algorithm using dynamic attention model for vehicle routing problems. In International Symposium on Intelligence Computation and Applications (636–650. ss.). Springer.
17. Qureshi, A. G., Taniguchi, E., & Yamada, T. (2009). An exact solution approach for vehicle routing and scheduling problems with soft time windows. Transportation Research Part E: Logistics And Transportation Review, 45(6), 960-977.
18. Reyes, D., Erera, A., Savelsbergh, M., Sahasrabudhe, S., O’Neil, R. (2018). The meal delivery routing problem. Optim. Online. Erişim adresi https://optimization-online.org/?p=15139
19. Statista (2023). Online food delivery report (worldwide version). Erişim adresi https://www.statista.com/outlook/dmo/online-fooddelivery/worldwide currency=usd
20. Steever, Z., Karwan, M., Murray. C. (2019). Dynamic courier routing for a food delivery service. Comput. Oper. Res., 107, 173–188.
21. Toth, P., Vigo, D. (2002). The vehicle routing problem. Philadelphia: SIAM.
22. Ulmer, M.W., Thomas, B.W., Campbell, A.M., Woyak. N. (2021). The restaurant meal delivery problem: Dynamic pickup and delivery with deadlines and random ready times. Transp. Sci., 55(1), 75–100.
23. Ulmer, M.W., Goodson, J.C., Mattfeld, D.C., Hennig, M. (2019). Offline–online approximate dynamic programming for dynamic vehicle routing with stochastic requests. Transp. Sci., 53(1), 185–202.
24. Ulmer, M.W., Thomas, B.W., Mattfeld. D.C. (2019). Preemptive depot returns for dynamic same-day delivery. Euro J. Transp. Log., 8(4), 327–361.
25. Ulmer, M.W., Thomas. B.W. (2020). Meso-parametric value function approximation for dynamic customer acceptances in delivery routing. European J. Oper. Res., 285(1), 183–195.
26. Wei, L., Zhang, Z., Zhang, D., & Lim, A. (2015). A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 243(3), 798-814.
27. Xia, Y., Fu, Z., Pan, L., Duan, F. (2018). Tabu search algorithm for the distance-constrained vehicle routing problem with split deliveries by order. PloS One, 13(5), doi: 10.1371/journal.pone.0195457.
28. Yildiz, B., Savelsbergh. M. (2019). Provably high-quality solutions for the meal delivery routing problem. Transp. Sci., 53(5), 1372–1388.
29. Zhang, Y., Shi, L., Chen, J., Li, X. (2017). Analysis of an automated vehicle routing problem in logistics considering path interruption. Journal of Advanced Transportation, 2, 1-10.
30. Zhou, M., Jin, J., Zhang, W., Qin, Z., Jiao, Y., Wang, C., Wu, G., Yu, Y., Ye., J. (2019). Multi-agent reinforcement learning for order-dispatching via order-vehicle distribution matching. In Proceedings of the 28th ACM International Conference on Information and Knowledge Management (2645–2653. pp.). New York: The Association for Computing Machinery.