A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems

The capacitated arc routing problem (CARP) aims at scheduling a fleet of vehicles with limited capacities to serve a set of tasks in a graph. The dynamic CARP (DCARP) optimization focuses on updating the vehicles’ service routes when unpredicted dynamic events happen and deteriorate the current service plan. Due to the outside vehicles are still being in their service when dynamic events happen and being located at different positions of the graph with different remaining capacities, the optimization algorithms for static CARP are unsuitable for solving the DCARP instance. However, in the existing literature, almost all proposed algorithms for DCARP were designed only for specific dynamic events instead of generic dynamic events such as the changing of traversing costs, the changing of the task’s demand, and the changing of the task’s number. Moreover, these algorithms are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this work, we proposed a novel generalized meta-heuristic framework which enables all algorithms designed for static CARP to be capable of solving DCARP instances. Our experimental results demonstrated that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms in terms of the quality of obtained solution within the limited computational time.