Kapasite kısıtlı araç rotalama probleminin paralel genetik algoritma ile çözümü
Solving the capacitated vehicle routing problem using a parallel genetic algorithm
- Tez No: 459306
- Danışmanlar: YRD. DOÇ. DR. HAKAN KUTUCU
- Tez Türü: Yüksek Lisans
- Konular: Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol, Computer Engineering and Computer Science and Control
- Anahtar Kelimeler: Araç yönlendirme problemi, Vehicle routing problem
- Yıl: 2017
- Dil: Türkçe
- Üniversite: Karabük Üniversitesi
- Enstitü: Fen Bilimleri Enstitüsü
- Ana Bilim Dalı: Bilgisayar Mühendisliği Ana Bilim Dalı
- Bilim Dalı: Bilgisayar Mühendisliği Bilim Dalı
- Sayfa Sayısı: Belirtilmemiş.
Özet
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.
Özet (Çeviri)
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.
Benzer Tezler
- Kapasite kısıtlı araç rotalama problemi ve çözüm yöntemleri
Capacitated vehicle routing problem and solution approaches
ZEYNEP BİRECİK
Doktora
Türkçe
2023
Endüstri ve Endüstri MühendisliğiYıldız Teknik ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. DOĞAN ÖZGEN
- Kapasite kısıtlı araç rotalama probleminin yabani ot ve hibrit metasezgisel algoritmalarla çözümü
Solution of capacitated vehicle routing problem with invasive weed and metaheuristic algorithms
ÜMİT YILDIRIM
Yüksek Lisans
Türkçe
2019
Endüstri ve Endüstri MühendisliğiÇukurova ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DR. ÖĞR. ÜYESİ YUSUF KUVVETLİ
- Kümeleme ve genetik algoritma destekli yaklaşımlarla kapasite kısıtlı araç rotalama probleminin çözümü: perakende zincirinde uygulanması
Solution of the capacity constraint vehicle routing problem with cluster and genetic algorithm based approach: a retail chain application
TOLGA ŞEN
Yüksek Lisans
Türkçe
2014
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
DOÇ. DR. HARUN REŞİT YAZĞAN
- Bulanık C ve K-ortalamalarla başlangıç çözümü oluşturulmuş tavlama benzetimi hibrit algoritması ile kapasite kısıtlı araç rotalama probleminin çözümü
Solution of capacitated vehicle routing problem with simulated annealing hybrid algorithm with initial solution created with fuzzy C and K-means algorithm
AHMET FATİH EKER
Yüksek Lisans
Türkçe
2020
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. İBRAHİM ÇİL
- Kapasite kısıtlı yerleştirme rotalama probleminin bir melez karınca kolonisi algoritması ile çözümü
Solution of capacitated location routing problem with hybrid ant colony algorithm
SÜMEYYE GİZEM ÇAKAR
Yüksek Lisans
Türkçe
2021
Endüstri ve Endüstri MühendisliğiSakarya ÜniversitesiEndüstri Mühendisliği Ana Bilim Dalı
PROF. DR. HARUN REŞİT YAZĞAN