LOJİSTİK PLANLAMA VE MODELLEME Dersi Düğüm Tabanlı Araç Rotalama Problemleri soru detayı:
SORU:
Araç Rotalama Problemi İçin En Yakın Komşuluk Algoritması (Talepler Bölünemez Kabulü Varken) adımları nelerdir?
CEVAP:
• 0. Adım:Eldeki serim seyrek ise düğümler arası karşılıklı enkısa yolları bularak serimi tam bağlı hâle çevir.
• 1. Adım: Merkez düğümü başlangıç noktası olarak seç.
• 2. Adım: Seçilen düğümden gidilebilir ve henüz uğranmamış diğer düğümler arasından enkısa mesafeli olanı belirle. Gidilecek düğümün talebi aracın boş kalan kapasitesini aşmıyorsa ilgili düğüme git, o düğümü seçilen düğüm olarak işaretle ve 3. adıma geç. Gidilecek düğümün talebi kalan kapasiteyi aşıyorsa ikinci enkısa mesafeli yolu, o da olmuyorsa sırayla diğerlerini dene. Hiçbirinin talebi kalan kapasiteye sığmıyorsa bu araç daha fazla yüklenemez. Aracı o düğümden merkeze geri gönder ve 4. adıma geç.
• 3. Adım: Bütün düğümlere uğrandı mı? Cevap evet ise dur, hayır ise 2. adıma dön.
• 4. Adım: Talebi karşılanan düğümleri serimden çıkar, kalan düğümler için yeni bir araç hazırla, merkez düğümü başlangıç düğüm olarak seç ve 2. adıma git.
Bu algoritma 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 aynı mantığın kullanılması mümkündür.