ENGINEERING JOURNAL CHIANG MAI UNIVERSITY

Volume 25, No. 03, Month DECEMBER, Year 2018, Pages 199 - 208

Comparing the multi colony ant system and ant system methods for solving the capacitated vehicle routing problem

Udom Janjarassuk and Kittirod Santithayee

Abstract Download PDF

This research presents a new method called Multi Colony Ant System (MCAS) to solve the Capacitated Vehicle Routing Problem (CVRP). The objective is to test the new algorithm and compare the results with the traditional Ant System (AS) approach. The MCAS algorithm uses multiple colonies of ants to find routes, which increases the chance of obtaining better solutions. Our method also employs the 2-Opt local search to improve the solutions. The algorithm was implemented in C++. Experiments were conducted to test the effectiveness of the algorithm by using 20 CVRP instances from literature. The results were compared to those from AS and the known optimal solutions. From the results, our proposed MCAS method provides significant improvement over the traditional AS approach, with an average optimality gap of only 0.68% compared to 2.24% of the traditional AS approach.

Keywords

Vehicle Routing Problem, Multi Colony Ant System, 2-Opt local search

---