Kapasite kısıtlı araç rotalama probleminin paralel genetik algoritma ile çözümü

Abstract

Bu çalışmada kapasiteleri kısıtlı araçlar ile farklı sayıda talebe sahip müşterilere bu taleplerinin ulaştırılması için kullanılan rota maliyetlerinin paralel genetik algoritma tekniklerinin kullanılarak optimize edilmesi gerçekleştirilmiştir. Genetik popülâsyonun ilk nesli oluşturulurken tasarruf algoritmasının geliştirilmiş bir haliyle kromozomlar ürettik. Geri kalan kromozomlar ise rastgele üretilmiştir. CUDA versiyon 5 özellikli Nvidia Titan X ekran kartı vasıtasıyla GPU Paralelleştirme kullandık. Genetik algoritmaya ait çaprazlama ve mutasyon işlemleri için uygulanan bu GPU paralelleştirmesi ile çok sayıda yeni çözümü hızlı bir şekilde üreterek optimum değeri bilinen problem setlerinin optimum çözümüne kısa sürede ulaştık. Optimum değerlerine ulaşılamayan problem setlerinde ise paralel algoritmanın seri algoritmaya göre daha iyi sonuçlar ürettiğini gözlemledik. Her bir problem seti için algoritma 10 kez çalıştırılarak testler gerçekleştirilmiştir. Test sonuçları aynı problem setlerini kullanarak çözüm üreten diğer algoritmalar ile karşılaştırılmıştır. Bu karşılaştırma sonucunda paralel genetik algoritmanın optimum sonuçlara etkili biçimde kısa sürede ulaştığı tespit edilmiştir. Çok sayıda müşteri içeren problem setlerindeki etkisi algoritmanın etkinliğini daha iyi göstermektedir.

In this study, we consider the Vehicle Routing Problem (VRP) in which vehicles departure from one or more depot(s), visit customers with known demands and finally return to the depot(s). Generally, VRP aims to minimize the total distance of the vehicles routes and therefore decrease transportation costs. The VRP has many variants with various features and constraints such as hard time windows, soft time windows, dynamic allocation of swap containers, configurable vehicle capacities or pick-up and delivery. In this thesis, we consider the capacitated vehicle routing problem (CVRP) with vehicles of the same capacity based at a central depot. We improveda parallel genetic algorithm working on a graphical processing unit (GPU) using NVIDIA's CUDA to solve the CVRP. For the initial population, some chromosomes were generated by an enhancement of the Clarke and Wright savings heuristic and the others were generated randomly.We used three crossover operators PMX, OX and NWOX and three mutation methods Insertion, Swap and Inversion.We tested our serial and parallel genetic algorithms with benchmark instances and compared it with some other heuristics in the literature.We performed 10 independent runs for all implementations to get reliable statistical results.Experimental results showed that the proposed parallel genetic algorithm is competitive in terms of the quality of the solutions obtained.