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

Abstract

In this thesis, a Revised Multiple Ant Colony System (RMACS) approach is applied to the Vehicle Routing Problem with Time Windows (VRPTW). Our primary objective is to minimize the number of vehicles and the secondary objective is to minimize the total travel distance. Two artificial ant colonies, where one minimizes the number of vehicles and the other the total travel time, cooperate with each other through pheromone update to optimize the 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 six different problem types, each containing 8-12 100-node problems. Although the best solutions could not be improved, in many instances the number of the vehicles is the same with the best results or 1-2 near to them. However, the travel distance %30 far from the best benchmark solutions in some of the problem instances.