LOJİSTİK PLANLAMA VE MODELLEME Dersi Düğüm Tabanlı Araç Rotalama Problemleri soru detayı:

CEVAP:

• 1. Adım: 1. düğümden bütün diğer düğümlere git-gel şeklinde tanımlanabilecek ve T={1,i,1}şeklinde gösterilebilecek olan uygun olmayan ilk turları türet. (Başlangıçta n-1 tane tur türetilmiş olacaktır). Amaç fonksiyonu değerini hesapla. 

• 2. Adım: sij değerlerini hesapla. 

• 3. Adım: Olabilir bağlantılar arasından enbüyük sij değerine karşı gelen (i,j) ayrıtını seçerek turu T={1-i-j-1} şekline dönüştür. Amaç fonksiyonu değerini güncelle. 

• 4. Adım: Var olan tur için 1 ile i arasına ve j ile 1 arasına girebilecek (Turun başına ve sonuna eklenebilecek) henüz tura eklenmemiş alternatif düğümleri belirleyerek, bunlara karşı gelen kazanım değerleri arasından enbüyük olanı seç. Yeni eklenecek düğümün talebi, elde kalan kapasiteyi aşmıyorsa uygun bağlantıyı yap. Turu ve amaç fonksiyonu değerini güncelle. 5. adıma geç. Eklenecek yeni düğümün talebi elde kalan kapasiteyi aşıyorsa, bir sonraki enbüyük kazanım değerli durumu incele. O da olmuyorsa sırayla hepsine bak. Hiçbiri uymuyorsa aracı daha fazla doldurmak mümkün değildir. Aracı merkeze gönder ve 6. adıma geç. 

• 5. Adım: Bütün düğümlerin talebi karşılandı mı? Cevap evet ise dur, hayır ise 4. adımı tekrar et. 

• 6. Adım: Talebi karşılanan düğümleri serimden çıkararak serimi güncelle, yeni bir araç için 1. adımdan başlayarak algoritmayı uygula. 

Kazanım algoritması ile araç kapasiteleri aşılmadan ve araç rotaları da kesişmeyecek şekilde turlar belirlenir. Özel bir durum olarak taleplerin kısmi karşılanmasına izin verilirse, algoritmada düzeltme yapılarak ve müşteri talebinin en fazla kaç parçada karşılanmasına izin verilebileceği belirlenip aynı mantığın kullanılması mümkündür.