Composite ant colony algorithms for transportation problems


Thesis Type: Postgraduate

Institution Of The Thesis: Marmara University, Institute for Graduate Studies in Pure and Applied Sciences, Department of Industrial Engineering (Eng), Turkey

Approval Date: 2010

Thesis Language: English

Student: MERVE ER

Consultant: Ercan Öztemel

Abstract:

ULAŞIM PROBLEMLERİNDE KARINCA KOLONİSİ ALGORİTMALARI Literatürde Karınca Kolonisi Optimizasyonu (KKO) algoritmaları için çeşitli paralelleştirme stratejileri önerilmiştir. Şimdiye kadarki en iyi sonuçlar algoritmanın farklı işlemcilere atanan birkaç koloni içerdigi iri taneli (coarse-grained) paralelleştirme stratejileriyle elde edilmiştir. Bu nedenle, bu tezde sıralı KKO algoritmalarının performansını arttırmak için geliştirilen çok kolonili yaklaşımlar üzerinde durulmuştur. Literatürde çok kolonili KKO yaklaşımları ile ilgili birkaç araştırma bulunmaktadır. Bu amaçla geliştirilmiş olan paralelleştirme stratejilerinin çoğu tezin içerisinde kısaca açıklanmıştır. Bunun yanında, KKO algoritmaları için birleşik bir yapı önerilmiş ve böyle karma bir yapı ile KKO algoritmalarının problem çözme yeteneklerini geliştirme olanağı araştırılmıştır. Önerilen algoritma Java’da kodlanmış ve Solomon’un Zaman Pencereli Araç Rotalama Problemi kıyaslama örneklerinden C tipi kıyaslama problemlerini çözmede kullanılmıştır. Sonuçlar karşılaştırmalı olarak yorumlanmıştır. ABSTRACT COMPOSITE ANT COLONY ALGORITHMS FOR TRANSPORTATION PROBLEMS There are various parallelization strategies for Ant Colony Optimization (ACO) algorithms in the literature. The best-so-far results are gained by coarse-grained parallelization strategies in which the algorithm contains several colonies assigned to different processors. Consequently, in this thesis it is dwelled upon the multi colony approaches that are developed to enhance the performance of the sequential ACO algorithms. There are a few researches in the literature about multi colony ACO approaches. Most of the parallelization strategies are briefly explained within the thesis. Furthermore, a composite structure for ACO algorithms is proposed and the possibility of enhancing the problem solving capability of the ACO algorithms with such a combined manner is investigated. The proposed algorithm is coded in Java and utilized in solving the C type benchmark problems of the Vehicle Routing Problem with Time Windows benchmark instances of Solomon. The respective comparison is provided.