Applying the Population-Based Ant Colony Optimization to the Dynamic Vehicle Routing Problem

Abstract

The population-based ant colony optimization (P-ACO) algorithm is a variant of the ant colony optimization metaheuristic specifically designed to address dynamic optimization problems. Whenever a change in the environment occurs, P-ACO repairs the pheromone trails affected by the change using previous solutions maintained in a population-list. Typically, change-related information are utilized for repairing these solutions. The change-related information for this dynamic vehicle routing problem (DVRP) case are the nodes removed and inserted when a change in the environment occurs. In this chapter, the operators of the unstringing and stringing (US) heuristic are utilized for repairing the solutions. Experimental results demonstrate that P-ACO embedded with the US heuristic outperforms other peer methods in a series of DVRP test cases.