Kapasiteli araç rotalama problemi için değişken komşuluk iniş ve tavlama benzetimi hibrit sezgisel çözüm yaklaşımı

---

Tezin Türü: Yüksek Lisans

Tezin Yürütüldüğü Kurum: Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Türkiye

Tezin Onay Tarihi: 2024

Tezin Dili: Türkçe

Öğrenci: Hüsna TOKEL

Danışman: Ertan Güner

Özet:

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 en küçüklenmesinin amaçlandığı araç rotalama problemidir. KARP için farklı meta-sezgisel algoritmaların performanslarının birleştirilerek daha güçlü bir algoritma önerilmesi fikrinden yola çıkılarak, değişken komşu iniş ve tavlama benzetimi algoritması birleştirilerek hibrit bir sezgisel algoritma önerilmiştir. İncelemelerimize göre KARP problemleri için bu iki algoritmanın hibrit bir çözüm yaklaşımı içerisinde birleştirilerek kullanıldığı bir çalışmaya rastlanmamıştı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 çözüm yaklaşımı önerilmiştir. 22, 23, 30, 33, 51 ve 76 müşteri boyutlu problem için E veri seti DKİ-TB hibrit çözüm yaklaşımı kullanılarak çözülmüştür. Başlangıç sıcaklığı, nihai sıcaklık, soğutma oranı ve iterasyon sayısı parametrelerinin çözüm değerlerine etkisi incelenmiştir. Her bir veri seti için DKİ-TB hibrit çözüm yaklaşımı 10 kez çalıştırılarak en iyi çözüm değeri dikkate alınmıştır. Bu çözüm değerleri, KARP çözmek için kullanılan CVRP-FA ve ISA-CO algoritmalarının çözüm değerleri ile karşılaştırılmıştır. DKİ-TB hibrit çözüm yaklaşımının, literatürde mevcut olan diğer algoritmalara göre daha iyi sonuç verdiği görülmüştür. Önerilen çözüm yaklaşımının performansını incelemek amacıyla Sakarya ilinde yer alan ekmek üretimi ve dağıtımı hizmeti veren bir fırın için gerçek dünya uygulaması yapılmıştır. Uygulamada 24 ve 30 müşteri boyutlu 2 homojen araç kapasiteli mesafe kısıtlı KARP yer almaktadır. Bu problem, Tlili, Faiz ve Krichen (2014) matematiksel modeli, homojen kapasiteli mesafe kısıtlı KARP‟ e uyarlanarak çözülmüştür. Çözüm sonuçları DKİ-TB hibrit çözüm yaklaşımı sonuçları ile karşılaştırıldığında, DKİ-TB‟nin optimal çözüme yakın sonuçlar verdiği görülmüştür. 50 müşteri boyutludan büyük problemler matematiksel model kullanılarak çözülememektedir, bu durumda DKİ-TB hibrit çözüm yaklaşımı kullanılabilir.

Anahtar Kelimeler : Araç rotalama problemi, Kapasiteli araç rotalama problemi, Meta sezgisel, Değişken komşuluk Arama algoritması, Değişken komşuluk iniş algoritması, Tavlama benzetimi