A split delivery vehicle routing problem for daily tobacco delivery

Abstract

Türkiye'nin büyük sigara üreticilerinden biri, İzmir de bulunan fabrikasından, her gün ülkenin dört bir yanındaki distribütörlerinden aldığı sigara siparişlerini, ertesi gün deposundan sevk etmektedir. İşlenmiş ve kutulara yerleştirilmiş sigaralar tırlar ve kamyonlar yardımı ile distribütörlere dağıtılmaktadır. Distribütör siparişlerinin hangi araçla ve sırayla gönderiminin planlaması, araç rotalama problemini ortaya çıkarmaktadır. Bu çalışmada, günlük sevk edilen ortalama 30.000 sigara kutusunun, 30 farklı araçla dağıtımını içeren araç rotalama planlaması problemine çözüm üretebilmek için, en uygun dağıtım rotaları belirleyen, heterojen araç filo ve bölünmüş teslimattan oluşan tamsayı karışık doğrusal programlama modeli (TKDP) geliştirildi. Matematiksel modelin amacı, yakıt maliyetlerini, her bir aracı kullanma maliyetini, distribütörü ziyaret etme maliyetini ve ekstra araç maliyetlerini (köprü veya otoyol) içeren toplam nakliye sabit ve değişken maliyetlerini en aza indirmektir. Modele ek olarak, istenilen sürede etkin bir şekilde çözülemeyen büyük örneklerini çözmek için konum tabanlı kümeleme sezgisel (KTKS) yöntem geliştirilmiştir. Sonuçlar, geliştirilen algoritmanın müşteri sayısı arttığında iyi performans gösterdiğini, daha kısa sürede kaliteli sonuçlar ürettiğini, söz konusu şirkete uygulanabilir olduğunu ve maliyet avantajı sağladığını göstermektedir.

One of the Turkey's largest cigarette manufacturer, located in Izmir, receives distributors' orders from all over Turkey every day. Processed and packed cigarettes are distributed to all distributors in different locations by trucks or trailers. The planning process includes the distribution of which vehicle and order the distributor will be sent, which means the problem of vehicle routing. In this study, a mixed integer linear programming model (MILP), consisting of heterogeneous vehicle fleet and split delivery, was developed to produce a solution to the vehicle routing planning problem involving the distribution of an average of 30,000 cigarette boxes delivered by 30 different vehicles daily. The purpose of the mathematical model is to minimize total shipping fixed and variable costs, including fuel costs, the cost of using each vehicle, the cost of visiting the distributor, and the extra vehicle costs (bridge or highway).The purpose of the mathematical model consist of heterogeneous split delivery that minimize fixed and variable costs by determining the most appropriate route of the tobacco company which is distributing cigarette to distributors. The objective of the mixed integer linear programming model (MILP) is to minimize the total transportation costs, which includes the fuel costs, fixed cost of using each vehicle, the cost of visiting a distributor and the extra vehicle costs (bridge or highway). To solve larger instances of the problem, which cannot be solved efficiently with the exact method, located based clustering heuristic algorithm is developed. Experimental results show that the developed algorithm performs well and produces quality results in shorter times and meets the performance targets of the company in question.