Araç rotalama probleminin genetik algoritma ile çözümü

Abstract

Bu çalışmada, çözülmesi zor problemler sınıfında yer alan araç rotalama problemi ele alınmıştır. Araç rotalama problemi kısaca, müşteri taleplerini karşılayacak ürün dağıtımına ait optimum rotaların tasarlanması problemidir. Toplam kat edilen mesafenin en küçüklenmesi problemin temel amacını oluşturmaktadır. Günümüz iş hayatında ürün dağıtım maliyetleri toplam lojistik maliyetlerinin önemli bir kısmını oluşturmaktadır. Bu çalışmada meta-sezgisel çözüm tekniklerinden birisi olan genetik algoritma kullanılarak Eskişehir Halk Ekmek A.Ş.’nin tüm müşteri taleplerini karşılayacak araç rota mesafesini iyileştirmek amaçlanmaktadır. Bu amaçla, genetik algoritmanın hem zor ve büyük ölçekli problemleri etkin bir şekilde çözebilmesi, hem de kısa sürede optimuma yakın çözümler üretebilmesi özelliğinden yararlanılarak Eskişehir Halk Ekmek A.Ş.’nin dağıtım araçlarının, satış büfelerine en kısa mesafeden rota hesaplamasına optimum çözüm aranmıştır ve mevcut durum ile karşılaştırma yapılmıştır. Ekmekler, tek bir üretim tesisinde üretilerek 51 adet satış büfesi aracılığıyla halka ulaştırılmaktadır. Üretim tesisinin satış büfelerine olan uzaklıkları “Google Maps” üzerindeki konumlarından sağlanmıştır. Ele alınan problem için genetik algoritma 2000 kez çalıştırılmıştır ve yaklaşık olarak 25 saniye (sn) gibi kısa bir sürede sonuca ulaşılmıştır. Genetik algoritma ile belirlenen araç rotalama işlemi sonucunda Eskişehir Halk Ekmek İşletmesi’nin mevcut olarak kullandığı rotasyon iyileştirilerek daha iyi bir sonuç elde edilmiştir. Çalışma öncesinde, Eskişehir Halk Ekmek İşletmesi rotalarının oluşturulmasında 17 yıllık tecrübesinden yararlanarak 3 aracın toplam kat ettiği mesafeyi 236,54 km olarak belirlediği görülmektedir. Genetik algoritma ile hesaplama sonucunda ise 3 aracın toplam kat ettiği mesafe 210,24 km olarak hesaplanmıştır. Bu durumda, günlük olarak hesaplanan değerde 26,3 km’lik bir iyileşme sağlanmaktadır. Aylık olarak düşünüldüğünde, bir ay için yaklaşık olarak 790 km’lik bir iyileşme sağlamaktadır. Maliyet bazında bakıldığında, kullanılan araçlar şehir içinde gidilen her km’de ortalama 1,6 TL/lt yakıt harcamaktadır ve aylık olarak düşünüldüğünde işletme için 1.264 TL’lik bir yakıt tasarrufu ile maliyette azalma sağlanmaktadır. Bu çalışma sonucunda işletmeye ait 51 adet satış büfesi için tüm talepleri karşılayacak bir rotasyon oluşturularak araçlarının hem zamandan tasarruf etmesini hem de maliyetin düşürülmesini sağlayan bir çözüm sunulmuştur.

In this study, vehicle routing problem which is in the class of hard to solve problems is addressed. The vehicle routing problem is, in short, the problem of designing optimal routes for product distribution to meet customer demands. The main objective of the problem is to minimize the total distance traveled. In today's business world, product distribution costs constitute an important part of total logistics costs. In this study, it is aimed to improve vehicle route distance to meet all customer demands of Eskişehir Public Bread Company Company using genetic algorithm, which is one of the meta-heuristic solution techniques. For this purpose, by using the genetic algorithm to solve difficult and large-scale problems effectively and to produce solutions that are close to optimum in a short time, Eskişehir Public Bread Company distribution vehicles are searched for the optimum solution for the route calculation to the sales points from the shortest distance and a comparison was made with the current situation. Breads are produced in a single production center and delivered to the public through 51 sales buffets. The distances of the production facility from the sales buffets are determined from their location on "Google Maps". The genetic algorithm was run 2000 times for the problem under consideration, and the result was reached in a short period of approximately 25 seconds (sec). As a result of the vehicle routing process determined by the genetic algorithm, a better result was obtained by improving the rotation used by Eskişehir Public Bakery Company. Before the study, it is seen that Eskişehir Public Bread Company determined the total distance traveled by 3 vehicles as 236.54 km, benefiting from 17 years of experience in the creation of routes. Considered on a monthly basis, it provides an improvement of approximately 790 km for a month. On the basis of cost, the vehicles used consume 1.6 TL / lt of fuel per km traveled in the city, and when considered monthly, a reduction in cost is achieved with a fuel saving of 1.264 TL for the business. As a result of this study, a solution was created to meet all demands for 51 sales buffets belonging to the enterprise, thus saving both time and cost for their vehicles.