Parallel Ant Colony Optimization for the Electric Vehicle Routing Problem

Abstract

Parallelizing metaheuristics has become a common practice considering the computation power and resources available nowadays. The aim of parallelizing a metaheuristic is either to increase the quality of the generated output, given a fixed computation time, or to reduce the required time in generating an output. In this work, we parallelize one of the best-performing ant colony optimization (ACO) algorithms and apply it to the electric vehicle routing problem (EVRP). EVRP is more challenging than the conventional vehicle routing problem, as with the consideration of electric vehicles additional hard constraints arise within the EVRP due to their limited driving range (e.g., the consideration whether electric vehicles need to visit a charging station during their daily operation). The proposed parallel ACO algorithm with several colonies also uses a migration policy to allow communication between the different colonies. From the simulation studies it is shown that parallelizing ACO algorithms, both with and without a migration policy, is highly effective.