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
|
