Kapasiteli araç rotalama problemi (KARP), bir depodan, sabit kapasiteli araçlar ile farklı coğrafik bölgelerde bulunan müşterilerin önceden belirlenen taleplerinin karşılanması için en uygun rotalar belirlenerek hizmet verildiği, toplam tur uzunluğunun minimize edilmesinin amaçlandığı araç rotalama problemidir. Literatürde, KARP çözmek için çok sayıda sezgisel ve meta-sezgisel algoritma mevcuttur. Bu çalışmada, farklı meta-sezgisel algoritmaların performanslarının birleştirilerek daha güçlü bir algoritma önerilmesi fikrinden yola çıkarak, değişken komşu iniş (DKİ) ve tavlama benzetimi (TB) algoritması birleştirilerek hibrit sezgisel algoritma önerilmiştir. Değişken komşu aramanın bir çeşidi olan DKİ algoritması, yerel arama algoritması ile arama yaparken farklı komşuluk mekanizmaları kullanarak küresel minimuma ulaşmayı amaçlar. Çözümde iyileşme olduğunda, aynı komşuluk yapısı ile arama yaparak aramayı yoğunlaştırır. Eğer çözümde iyileşme olmazsa, farklı komşuluk arama mekanizmaları ile arama yaparak çözümü çeşitlendirir. TB algoritmasında, arama sürecinde sıcaklık bir fonksiyona bağlı olarak azaltılır, sıcaklık azaltıldıkça çözüm optimum çözüme yaklaşır. Arama sürecinde çözümde iyileşme olmadığında, belli kriterlere bağlı olarak kötü çözümlerde kabul edilerek yerel minimuma takılmayı önlemek amaçlanmaktadır. Bu iki algoritmanın avantajları birleştirilerek, çözümde iyileşme olduğunda aramayı yoğunlaştıran, çözümde iyileşme olmadığında belli oranda kötü çözümleri kabul ederek yerel minimuma takılmayı önleyen ve yeni çözüm kabul edilemediği durumda farklı komşuluk yapıları ile arama yapılarak çözümü çeşitlendiren bir çözüm yaklaşımı önerilmiştir. Önerilen hibrit çözüm yaklaşımı, literatürde sıklıkla kullanılan veri seti ile test edilmiştir. Çözüm sonuçları, literatürde karşılaşılan diğer algoritmaların sonuçları ile karşılaştırılmıştır. Karşılaştırma sonucunda, önerilen DKİ-TB hibrit sezgiselinin, farklı boyutlu veri setleri için daha iyi performans gösterdiği görülmüştür. Gelecek çalışmalarda, daha büyük boyutlu problemler için daha iyi performans gösterdiğinin kanıtlanması hedeflenmektedir. ORCID NO: 0009-0003-8665-6798
Anahtar Kelimeler: Kapasiteli araç rotalama problemi, hibrit sezgisel, değişken komşu arama, değişken komşu iniş, tavlama benzetimi
|
