  The capacitated arc routing problem (CARP) is a challenging combinatorial
optimisation problem abstracted from typical real-world applications, like
waste collection and mail delivery. However, few studies considered dynamic
changes during the vehicles' service, which can make the original schedule
infeasible or obsolete. The few existing studies are limited by dynamic
scenarios that can suffer single types of dynamic events, and by algorithms
that rely on special operators or representations, being unable to benefit from
the wealth of contributions provided by the static CARP literature. Here, we
provide the first mathematical formulation for dynamic CARP (DCARP) and design
a simulation system to execute the CARP solutions and generate DCARP instances
with several common dynamic events. We then propose a novel framework able to
generalise all existing static CARP optimisation algorithms so that they can
cope with DCARP instances. The framework has the option to enhance optimisation
performance for DCARP instances based on a restart strategy that makes no use
of past history, and a sequence transfer strategy that benefits from past
optimisation experience. Empirical studies are conducted on a wide range of
DCARP instances. The results highlight the need for tackling dynamic changes
and show that the proposed framework significantly improves over existing
algorithms.
