Solution Of Capacitated Vehicle Routing Problem For A Food Delivery Company With Heuristic Methods

Yıl 2023, Cilt: 11 Sayı: 1, 1 - 16, 24.07.2023

Nurhayat Tok , Şerife Özkar

https://doi.org/10.18825/iremjournal.1174543

Öz

A food delivery company operates in Balıkesir performs to the distribution for the products of a certain brand from the central warehouse to the customers located in the central districts of Altıeylül and Karesi by using two vehicles with high capacity. The company visits customers on certain routes to meet their daily demands and is able to meet all demands at the end of the day. In this study, the distribution of the company's products was considered as a Vehicle Routing Problem, and it was aimed to reconstruct the distribution routes of the vehicles with the help of various algorithms and to provide cost savings in terms of the distance traveled. In order to solve the problem, first of all, an appropriate capacity assumption was made for the vehicles by considering the daily demand amounts of the customers. Under this assumption, first new customer groups to be visited in daily periods were created, and then new routes were obtained for the relevant customer groups. In this process, the problem was designed as a Capacity Constrained Vehicle Routing Problem, and the results obtained using Fisher and Jaikumar's Algorithm and Clarke and Wright's Savings Algorithm were evaluated. When the results obtained are compared with the current route status of the company, it has been determined that it is possible to achieve a high rate of improvement by using the routes determined by algorithms.

Anahtar Kelimeler

Vehicle routing problem, Capacitated Vehicle Routing Problem, Fisher and Jaikumar algorithm, Clarke and Wright’s savings algorithm, Nearest neighbor algorithm

Solution Of Capacitated Vehicle Routing Problem For A Food Delivery Company With Heuristic Methods

Öz

Balıkesir'de faaliyet gösteren bir gıda dağıtım şirketi, belirli bir markanın ürünlerinin merkez depodan Altıeylül ve Karesi merkez ilçelerinde bulunan müşterilere yüksek kapasiteli iki araçla dağıtımını gerçekleştirmektedir. Şirket, müşterilerin günlük taleplerini karşılamak için belirli rotalarda onları ziyaret etmekte ve gün sonunda taleplerin hepsini karşılayabilmektedir. Bu çalışmada, firmaya ait ürünlerin dağıtımı Araç Rotalama Problemi olarak ele alınmış, araçların dağıtım rotalarının çeşitli algoritmalar yardımı ile yeniden oluşturulması ve alınan yol açısından maliyet tasarrufu sağlamak hedeflenmiştir. Problemi çözmek amacıyla öncelikle müşterilerin günlük talep miktarları göz önünde bulundurularak araçlar için uygun bir kapasite varsayımı yapılmıştır. Bu varsayım altında, önce günlük periyotlarda ziyaret edilecek yeni müşteri grupları oluşturulmuş, ardından ilgili müşteri grupları için yeni rotalar elde edilmiştir. Bu süreçte problem Kapasite Kısıtlı Araç Rotalama Problemi olarak dizayn edilmiş, Fisher ve Jaikumar Algoritması ve Clarke ve Wright'ın Tasarruf Algoritması kullanılarak ulaşılan sonuçlar değerlendirilmiştir. Elde edilen sonuçlar şirketin mevcut rota durumu ile karşılaştırıldığında, algoritmalarla belirlenen rotaları kullanarak yüksek oranda iyileşme sağlamanın mümkün olduğu tespit edilmiştir.

Anahtar Kelimeler

Araç rotalama problemi, Kapasiteli Araç Rotalama Problemi, En Yakın Komşu Algoritması, Fisher ve Jaikumar algoritması, Clarke ve Wright’ın tasarruf algoritması

Kaynakça

• Baldacci, R., Mingozzi, A. & Roberti, R. (2012). Recent exact algorithms for solving the vehicle routing problem under capacity and time window constraints. European Journal of Operational Research, 218(1): 1-6.
• Bozyer, Z., Alkan, A. & Fığlalı, A. (2014). Kapasite kısıtlı araç rotalama probleminin çözümü için önce grupla sonra rotala merkezli sezgisel algoritma önerisi. Bilişim Teknolojileri Dergisi, 7(2): 29-37.
• Caccetta, L., Alameen, M. & Abdul-Niby, M. (2013). An improved Clarke and Wright algorithm to solve the capacitated vehicle routing problem. Engineering, Technology & Applied Science Research, 3(2): 413-415.
• Christofides, N. (1976). The vehicle routing problem. Revue française d'automatique, informatique, recherche opérationnelle. Recherche opérationnelle, 10(V1): 55-70.
• Clarke, G. & Wright, J.W. (1964). Scheduling of vehicles from a central depot to a number of delivery points. Operations Research, 12(4): 568-581.
• Cordeau, J.F., Gendreau, M., Laporte, G., Potvin, J.Y. & Semet, F. (2002). A guide to vehicle routing heuristic. Journal of the Operational Research Society, 53(5): 512-522.
• Dantzig, G.B. & Ramser, J.H. (1959). The truck dispatching problem. Management Science, 6(1): 80-91.
• Fisher, M.L. & Jaikumar, R. (1981). A generalized assignment heuristic for vehicle routing. Networks, 11(2): 109–124.
• Hashi, E. K., Hasan, M. R., & Zaman, M.S.U. (2015, November). A heuristic solution of the Vehicle Routing Problem to optimize the office bus routing and scheduling using Clarke & Wright's savings algorithm. In 2015 international conference on computer and information engineering (ICCIE) IEEE, 13-16.
• 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.
• Kosif, B. & Ekmekçi, İ. (2012). Araç rotalama sistemleri ve tasarruf algoritması uygulaması, İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 11(21): 41-51.
• Laporte, G., Gendreau, M., Potvin, J.Y. and Semet, F. (2000). Classical and modern heuristics for the vehicle routing problem. International Transactions in Operation Research, 7(4-5): 285-300.
• Lysgaard, J. (1997). Clarke & Wright’s savings algorithm. Department of Management Science and Logistics, The Aarhus School of Business, 44: 1–7.
• Solomon, M.M. (1987). Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research, 35(2): 254–265.
• Sultana, T., Akhand, M. A. H., & Rahman, M. H. (2017, May). A variant Fisher and Jaikuamr algorithm to solve capacitated vehicle routing problem. In 2017 8th International Conference on Information Technology (ICIT) IEEE, 710-716.
• Toth, P. & Vigo, D. (2002). Models, relaxations and exact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics, 123(1-3): 487-512.
• Ulutaş, A., Bayrakçıl, A.O. & Kutlu, M.B. (2017). Araç rotalama probleminin tasarruf algoritması ile çözümü: Sivas'ta bir ekmek fırını için uygulama. Cumhuriyet Üniversitesi İktisadi ve İdari Bilimler Dergisi, 18(1): 185-197.
• https://www.movable-type.co.uk/scripts/latlong.html, (07.09.2022).