Araç Rotalama Probleminin Genetik Algoritma ile Çözümü

Yıl 2020, Cilt: 20 Sayı: 3, 227 - 254, 29.09.2020

Ebru Okur Mahmut Atlas

https://doi.org/10.18037/ausbd.801768

Cited By: 4

Öz

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.

Anahtar Kelimeler

Genetik Algoritma, Araç Rotalama Problemi, Meta-Sezgisel Teknikler

Kaynakça

• Acar, E. (2014). Yatırım problemlerinin değerlendirilmesinde evrimsel algoritma kullanımı yap işlet devret modeli altyapı projesi üzerine bir uygulama (Tez Numarası. 357356). [Doktora Tezi. Eskişehir: Anadolu Üniversitesi Sosyal Bilimler Enstitüsü]. YÖK Tez Merkezi.
• Chen, T. & Chen, C., (1997). Improvements of simple genetic algorithm in structural desing. International. Journal for Numerical Methods in Engineering, 40, 1323–1334. Christofides, N., (1976). The vehicle routing problem. Recherche Operationnelle, 10 (2), 55-70.
• Çeyrekoğlu, S., (2017). Araç rotalama problemine genetik algortima yaklaşımı ve örnek bir uygulama (Tez Numarası. 461711).[Yüksek Lisans Tezi. İstanbul: İstanbul Üniversitesi Fen Bilimleri Enstitüsü]. YÖK Tez Merkezi.
• Çolak, S., (2010). Genetik algoritmalar yardımı ile gezgin satıcı probleminin çözümü üzerine bir uygulama. Çukurova Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, 19 (3), 423-438.
• Dasgupta, D. & Michalewicz, Z., (1997). Evolutionary algorithmsın engineering applications, Germany: Springer.
• Demircioğlu, M., (2009). Araç rotalama probleminin sezgisel bir yaklaşım ile çözümlenmesi üzerine bir uygulama (Tez Numarası. 241435). [Doktora Tezi. Adana: Çukurova Üniversitesi Sosyal bilimler Enstitüsü]. YÖK Tez Merkezi.
• Dreo, J., Siarry, P., Petrowski, A., & Taillard, E., (2006). Metaheuristics for hard optimization. Germany:Springer-Verlag, 978-3-540-23022-9.
• Duman, C., (2007). Genetik algoritma ile tesis yerleşimi tasarımı ve bir uygulama (Tez Numarası.213245). [Yüksek Lisans Tezi. İstanbul: Yıldız Teknik Üniversitesi Fen Bilimleri Enstitüsü.]. YÖK Tez Merkezi.
• Düzakın, E. ve Demircioğlu, M., (2009). Araç rotalama problemleri ve çözüm yöntemleri. Çukurova Üniversitesi İİBF Dergisi, 13 (1), 68-87.
• Eksioglu, B., Vural, A.V. & Reisman, A., (2009). The vehicle routing problem: A taxonomicreview. Computers & Industrial Engineering, 57, 1472–1483. Elmas, Ç., (2007). Yapay zeka uygulamaları, Ankara: Seçkin.
• Emel, G.G., ve Taşkın, Ç., (2002). Genetik algoritmalar ve uygulama alanları. Bursa: Uludağ Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, XXI (1), 129-152.
• Er, H., Çetin, M. ve İpekçi Çetin, E. (2005). Finansta evrimsel algoritmik yaklaşımlar: Genetik algoritma uygulamaları. Akdeniz İ.İ.B.F. Dergisi, 10, 73-94.
• Fisher, M. L. & Jaikumar, R., (1981). Ageneralized assignment heuristic for vehicle routing, Networks, 11, 109-124.
• Gomez, P. A. & Hougen, D. F., (2007). Initial population for genetic algorithms: A metric approach. International Conference on Genetic and Evolutionary Methods. LasVegas, Nevada, USA, 25-28 Haziran.
• Gupta, S.M. & Imtanavanich, P. (2010). Evolutionary computational approach for disassembly sequencing in a multiproduct environment. Biomedical Soft Computing and Human Sciences. 15 (1), 71-76.
• Günay, N.S. (2013). Genetik algoritma ile araç rotalama problemlerinin çözümü için görsel rotalama yazılımı geliştirme (Tez Numarası. 337103). [Yüksek Lisans Tezi. İstanbul: İstanbul Üniversitesi Fen Bilimleri Enstitüsü.]. YÖK Tez Merkezi.
• Haupt, R. L. & Haupt, S.E. (2004). Practical genetic algorithms (Second Edition), New Jersey: John Wiley&Sons.
• Karaova, M., Smarkov, V. & Penev, S. (2005). Genetic operators crossover and mutation in solving the TSP problem. International Conference on Computer Systemsand Technologies – CompSysTech, - IIIA (20), 1-6.
• Keskintürk, T., Topuk, N. ve Ö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.
• Kırda, K., (2013). Evsel ilaç atıklarının toplanması projesindeki tersine lojistik sürecinin modellenmesi için genetik algoritmaların kullanılması (Tez Numarası. 337587). [Doktora Tezi. İzmir: Dokuz Eylül Üniversitesi Sosyal Bilimler Enstitüsü]. YÖK Tez Merkezi.
• Koza, J. R., (1998). Genetic Programming: On the programming of computers by means of natural selection. London: The MIT Press, 0-262-11170-5.
• Özkan, B., (2008). Dinamik gezgin satıcı probleminin çözümü için bir eniyileme kütüphanesinin tasarımı ve görsel yazılım geliştirme ortamı ile birlikte gerçekleştirimi (Tez Numarası. 216130). [Yüksek Lisans Tezi. İzmir: Ege Üniversitesi Fen Bilimleri Enstitüsü]. YÖK Tez Merkezi.
• Öztürk, A. (2011). Yöneylem araştırması. Bursa: Ekin.
• Rothlauf, F., (2006). Representations for genetic and evolutionary algorithms. Springer-Verlag, Netherlands, 978-3-540-25059-3.
• Sivanandam, S.N. & Deepa, S.N., (2008). Introduction to genetic algorithms. Berlin: Springer Science& Business Media.
• Şen, Z., (2004). Genetik algoritmalar ve eniyileme yöntemleri. İstanbul: Su Vakfı.
• Toth, P. & Vigo, D., (2002a). Models, relaxations and rxact approaches for the capacitated vehicle routing problem. Discrete Applied Mathematics 123, 487 – 512.
• Yücel, A., (2016). Mesafe kısıtlı çok yönlü kümelenmiş açık araç rotalama probleminin genetik algoritma ile çözümü. (Tez Numarası.465573). [Doktora Tezi. İstanbul: İstanbul Üniversitesi Sosyal bilimler Enstitüsü]. YÖK Tez Merkezi.