1 Genelleştirilmiş Araç Rotalama Problemi için Modeller ve Dal-Kesi Algoritmaları YAEM 2010Tolga Bektaş, Southampton UniversityGüneş Erdoğan, Özyeğin ÜniversitesiStefan Røpke, Technical University of Denmark
3 Problem Tanımı Tüm serim G = (V, E) ; V = {0,1,…,n} Nokta kümesinin alt kümeleri : salkımlarV = C0 C1 … CmHer salkıma ait bir talep miktarıDepodan çıkan Q kapasiteli K araçHer salkımdan bir noktaya uğrayıp, depoya dönüşAmaç : Toplam seyahat mesafesinin enküçüklenmesi
6 YazınGhiani ve Improta (2000), GARP’ı Kapasiteli Ark Rotalama Problemine dönüştürerek çözmeyi önerdi ve uyguladı.Kara and Bektaş (2003), GARP için Miller- Tucker-Zemlin kısıtları kullanan polinom boyutlu bir formülasyon önerdi ve uyguladı.Bautista ve diğerleri (2008), GARP’ın özel bir halini Karınca Kolonisi Sezgisel Yöntemini kullanarak çözdü.
7 YazınBaldacci, Bartolini ve Laporte (2010), GVRP’nin olası uygulamaları üzerine bir çalışma yaptı.Moccia, Cordeau ve Laporte (2010), zaman kısıtlı GARP için bir tabu araması algoritması önerdi ve uyguladı.
16 Teorik AnalizTeorem: F1 modelinin, Doğrusal Programlama alt modelinin bulduğu alt sınırlar, F2 modelinden her zaman daha kuvvetlidir.Deneysel çalışma, F2 modelinin azaltılmış değişken sayısının bazı durumlarda çözüm süresini kısalttığını göstermiştirTeorem: F4 modelinin, Doğrusal Programlama alt modelinin bulduğu alt sınırlar, F3 modelinden her zaman daha kuvvetlidir.
18 Önişleme Algoritması Eğer i ve j noktaları, j ∈ C(i), j i her iki a ve b noktası, a, b ∈ V \ C(i); (a) (b) için cai + cib ≥ caj +cjb ve q(i) +q(a) +q(b) ≤ Q koşullarını ve c0i ≥ c0j koşulunu sağlıyorsa, j noktası i noktasından üstündür.Bu durumda, i noktasının problem verisinden çıkartılması, en iyi çözümü etkilemez.Naif çözüm karmaşıklığı : O(n4)İyileştirilmiş karmaşıklığı : O(n3)
19 Geçerli Eşitsizlikler Teorem: Her salkımın tek bir noktaya toparlandığı serimde, Kapasiteli Araç Rotalama Problemi için geçerli olan her kısıt, F1, F2, F3 ve F4 için de geçerlidir.Ayrıştırma algoritması:Modelin Doğrusal Programlama alt modelini çözÇözümü her salkımı bir noktaya toparlayacak şekilde işleKARP için literatürde var olan kısıtları işlenmiş çözümden ayrıştır ve modele ekle
20 Hesapsal DeneylerDeneysel veri, Fischetti vd yılında Gezgin Satıcı Probleminden, Genelleştirilmiş Gezgin Satıcı Problemi için veri oluşturma yöntemi kullanılarak oluşturuldu.Kullanılan ham veri:Salkım sayısı, nokta sayısının yarısı ve üçte biri olarak belirlendi ve her iki durum için hesapsal deneyler yapıldı.
21 Hesapsal Deneyler CPLEX 10.0 ve 2.4 GHz AMD Opteron 250 CPU kullanıldı Tüm deneylerde F4 hem çözüm süresinde hem de alt sınır kuvveti açısından en yüksek başarımı sergiledi.Nokta sayısı arasında iken, iki saatlik hesap süresi sınırı dahilinde, 148 problem enstantanesinin tümünde en iyi çözüm bulunduNokta sayısı arasında iken, altı saatlik hesap süresi sınırı dahilinde, 10 problem enstantanesinin 3 tanesinde en iyi çözüm bulundu
22 Sonuç GARP için dört Tamsayısal Programlama modeli oluşturuldu Modeller kendi aralarında teorik ve deneysel olarak karşılaştırıldıÖnişleme algoritması ile enstantane boyutu küçültüldüLiteratürde KARP için var olan kısıtların GARP’a uyarlanabileceği gösterildiDal-kesi algoritması uygulandıDeneysel olarak 101 nokta ve 51 / 34 salkımlık iki enstantane iki saat içinde çözülebildi
23 Genelleştirilmiş Araç Rotalama Problemi için Modeller ve Dal-Kesi Algoritmaları YAEM 2010Tolga Bektaş, Southampton UniversityGüneş Erdoğan, Özyeğin ÜniversitesiStefan Røpke, Technical University of Denmark