A revised multiple ant colony system for vehicle routing problems with time windows

Abstract

Bu çalışma, Zaman Kısıtlı Araç Rotalama Problemini Karınca Kolonisioptimizasyonuna dayalı bir yaklaşımla çözmeyi amaçlamaktadır. Problemdeki birinciamacımız araç sayısını, ikinci amacımız ise toplam katedilen yolu minimize etmektir. Buminimizasyon problemini çözmek üzere biri araç sayısını, diğeri ise toplam katedilen yoluminimize etmeye odaklı iki karınca kolonisi feromen seviyeleri vasıtasıyla haberleşerek biryardımlaşma anlayışı içerisinde çalışırlar. Algoritma C++ programında kodlanmış olup,Solomon'un (1987) 56 problem örneği üzerinde test edilmiştir. Herbiri 8-12 100 noktalıproblem içeren bu problem örnekleri 6 değişik problem setine karşılık gelmektedir. Buçalışma sonucunda araç sayısında literatürdeki en iyi sonuçlara karşın bir geliştirmesağlanamamış olmasına karşın, en iyi sonuçlara maksimum 2 araç sayısı uzaklıkta sonuçlarbulunmuştur. Fakat katedilen yol miktarı bazı problem örneklerinde literatürdeki en iyisonuçlardan %30 daha uzak sonuçlar vermektedir.

In this thesis, a Revised Multiple Ant Colony System (RMACS) approach is applied tothe Vehicle Routing Problem with Time Windows (VRPTW). Our primary objective is tominimize the number of vehicles and the secondary objective is to minimize the total traveldistance. Two artificial ant colonies, where one minimizes the number of vehicles and theother the total travel time, cooperate with each other through pheromone update to optimizethe corresponding objectives. The developed approach is coded in C++ and tested on the well-known 56 benchmark instances of Solomon (1987). These instances are composed of sixdifferent problem types, each containing 8-12 100-node problems. Although the best solutionscould not be improved, in many instances the number of the vehicles is the same with the bestresults or 1-2 near to them. However, the travel distance %30 far from the best benchmarksolutions in some of the problem instances.