A Multiple Ant Colony System for the Electric Vehicle Routing Problem with Time Windows

Abstract

Ant colony optimization (ACO) has been found to be useful on several vehicle routing problem variations. In this work, ACO is applied to the electric vehicle routing problem with time windows (E-VRPTW). The E-VRPTW has a hierarchical multiple objective function, which is to minimize the number of electric vehicles and the total distance traveled. A multiple ACO is applied to E-VRPTW in which two colonies cooperate to minimize the objectives in parallel. A local search is embedded in ACO to improve the quality of the output. The experimental results on a set of benchmark instances show that the multiple ACO is competitive with existing methods.