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

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.© 2020 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. I. S. Bonilha, M. Mavrovouniotis, F. M. Muller, G. Ellinas, M. Polycarpou. Ant colony optimization with heuristic repair for the dynamic vehicle routing problem. 2020 IEEE Symposium Series on Computational Intelligence (SSCI), Canberra, Australia, pp. 313-320, 2020. doi: 10.1109/SSCI47803.2020.930815