Kapasite Kısıtlı Araç Rotalama Problemi için Melez Bir Algoritma


Babayiğit B. , Yıldız K.

3rd International Symposium on Innovative Approaches in Scientific Studies, Ankara, Türkiye, 19 - 21 Nisan 2019, cilt.4, no.1, ss.508-513

  • Cilt numarası: 4
  • Basıldığı Şehir: Ankara
  • Basıldığı Ülke: Türkiye
  • Sayfa Sayıları: ss.508-513

Özet

Son yıllarda yaşanan ekonomik daralma sonucunda üretim maliyetlerini azaltmak ve kar marjlarını arttırmak firmalar için

önemli bir hedef haline gelmiştir. Özellikle lojistik ve dağıtım şirketlerinin operasyonel işlemleri araç rotalama problemi olarak

ele alınarak değerlendirilmesi gerekmektedir. Araç rotalama problemi (ARP) kombinasyonel optimizasyon problemlerindendir

ve NP-Zor sınıfında yer almaktadır. ARP’nin temel amacı belirli sayıda müşteriye hizmet vermek koşuluyla minimum mesafeli

rotaları oluşturmaktır. Problem kapasite, zaman penceresi, mesafe gibi kısıtlar eklenerek farklı türlere ayrılabilmektedir. Kapasite

kısıtlı ARP’nde bir rotada yer alan müşteri talepleri toplamının araç kapasitesini aşmaması gerekmektedir. Literatürde problemin

çözümünde kesin, sezgisel ve metasezgisel çözüm yöntemleri mevcut olmakla birlikte bu çalışmada kapasite kısıtlı araç rotalama

probleminin çözümü için en yakın komşu algoritması, Yapay Arı Koloni (YAK) algoritması ve 2-opt algoritmalarının birlikte

kullanıldığı melez bir yapı önerilmiştir. Önerilen algoritmada başlangıç çözümlerinin yarısı rassal diğer yarısı ise en yakın komşu

yöntemi ile oluşturulmuştur. Başlangıç çözümlerine uygulanan YAK algoritması ile elde edilen en iyi çözüme 2-opt algoritması

uygulanarak tur maliyetleri azaltılmıştır. Önerilen algoritma literatürde halihazırda var olan test problemleri üzerinde denenmiş

ve karşılaştırmalı sonuçları elde edilmiştir. Önerilen algoritmanın en iyi çözümlere yakın değerler ürettiği gözlemlenmiştir. Bu

çalışmada sunulan çözüm yöntemi literatüre önemli katkılar sağlayabilir ve çok çeşitli kombinasyonel optimizasyon

problemlerinin çözümünde kullanılabilir.