Building Blocks as Experiences in Dynamic Capacitated Arc Routing Problems

The dynamic capacitated arc routing problem (DCARP) aims to update the service paths of vehicles in the capacitated arc routing problem when uncertain factors deteriorate the current schedule of vehicles' services. A DCARP scenario comprises a series of DCARP instances that share similarities with each other. Therefore, optimisation experience gained from solving the former DCARP instance can potentially facilitate the optimisation for a new DCARP instance. However, existing optimisation algorithms for solving DCARP seldom consider such optimisation experience and instead re-optimise the DCARP instance from scratch. This paper proposes a dynamic optimisation framework with a solution building block adaptation strategy (DO-SBBA) that extracts the optimisation experience from the former optimisation process to facilitate the optimisation of the next DCARP instance. The framework introduces the concept of building blocks for extracting the valuable experience contained in historical solutions. The building block-based constructive heuristic is proposed to handle DCARP scenarios with cost- or task-changing dynamic events, and an insertion heuristic is proposed to handle task-changing dynamic events. Experimental studies demonstrate the effectiveness of DO-SBBA for extracting and utilising optimisation experience in DCARP scenarios, significantly improving the performance of dynamic optimisation compared to state-of-the-art DCARP methods.