Ant Colony optimization with Heuristic Repair for the Dynamic Vehicle Routing Problem

Abstract

Ant colony optimization (ACO) algorithms have proved to be suitable for solving dynamic optimization problems. The intrinsic characteristics of ACO algorithms enables them to transfer knowledge from past optimized environments via their pheromone trails to shorten the optimization process in the current environment. In this work, change-related information is also utilized when a dynamic change occurs. The dynamic vehicle routing problem is addressed where nodes are removed, representing customers that have already been visited, or added, representing customers that placed a new order and need to be visited. These change-related information are used to heuristically repair the solution of the previous environment, based on effective moves of the unstringing and stringing operator. Experimental results show that utilizing change-related information is beneficial in the generated dynamic test cases.