Solution of capacitated vehicle routing problem for a food delivery company with heuristic methods

Abstract

A food delivery company operating in Balıkesir performs distribution of the products for 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 traveled distance. 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 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.

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.