Solving Capacitated Vehicle Routing Problem (CVRP) for the Environments with Circular Obstacles

Authors : Mehmet KARAKOÇ, Aybars UGUR

Pages : 283-296

Doi:10.19113/sdufenbed.817282

View : 24 | Download : 13

Publication Date : 2021-08-20

Article Type : Research Paper

Abstract :Kapasiteli araç rotalama probleminde insert ignore into journalissuearticles values(KARP);, belirli kapasitedeki bir araç filosu merkezî bir depodan harekete geçer ve en düşük maliyetli en uygun rota kümesini kullanarak birtakım müşterilere hizmet verip bu başlangıç noktasına geri döner. Gerçek hayatta ise ortamlar farklı büyüklüklerdeki delik, makine veya ağaç gibi engeller içerebilmektedir. Bu çalışmada, klasik KARP’nin çeşitli büyüklüklerdeki dairesel engeller içeren ortamlar için genişletilmiş bir biçimi önerilmektedir. Bu problemi çözmek için yerel arama ile iyileştirilmiş genetik algoritmalar tabanlı melez bir üst-sezgisel algoritma geliştirilmiştir. Ek olarak, çalışma uzayına engeller ve konumlar yerleştirmek için bir görsel benzetim aracı tasarlanmıştır. Geliştirilen algoritma ortam üzerinde çeşitli engel doluluklarıyla farklı müşteri-engel sayıları ve engel büyüklükleri için sınanmıştır. Elde edilen sonuçlar sunulmuş ve problemin potansiyel uygulamaları tartışılmıştır.
Keywords : Kapasiteli araç rotalama problemi KARP, Dairesel engeller, Üst sezgi, Genetik algoritmalar, Yerel arama, Benzetim