@phdthesis {pub5536,
	title = {Advancing Optimization and Evaluation for Dynamic Capacitated Arc Routing Problems},
	author = {Hao Tong},
	year = {2024},
	month = {May},
	abstract = {The Capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from real-world applications, such as waste collection and road gritting. It aims at scheduling a fleet of vehicles, each with a limited capacity, to serve a series of tasks in a graph spending the lowest possible total cost. In real applications, unexpected dynamic changes usually occur when vehicles are in their service, which potentially cause the current schedule of vehicles become worse or even infeasible. For example, the road may be closed or congested due to an accident, or new tasks might emerge after vehicles have already started their service. Consequently, the current schedule is required to be updated ensuring efficient service continuity, taking into account the different locations and various remaining capacities of the vehicles currently still in services. This adaptive scenario is regarded as dynamic CARP (DCARP). Within this context, the information including the updated graph, the new set of tasks and the status of all vehicles is denoted as the DCARP instance which requires optimization to ensure an updated and efficient schedule.

This thesis mainly focuses on investigating the characteristics of the DCARP and proposing efficient optimization algorithms for its resolution. In particular, we provide the following main contributions in this thesis:
1. We provide the first mathematical formulation of DCARP in the literature and architect a simulator to emulate the behavior of vehicles{\textquoteright} service processes in the real world. This simulator offers a novel research platform for generating DCARP benchmarks to support DCARP studies.
2. We proposed a novel generalized meta-heuristic framework based on a virtual-task strategy for DCARP optimization. It enables all meta-heuristic algorithms designed for solving static CARP to be capable of effectively solving DCARP instances.
3. We performed the fitness landscape analysis on various DCARP instances to investigate which factors make DCARP instance harder to solve. Empirical studies reveal that cost-related dynamic events have almost no effect on the difficulty of DCARP instances, while introductions of new tasks are the main factor making DCARP instances harder to solve. 
4. We proposed an experience-assisted optimization framework based on a novel solution building block strategy to deal with the DCARP scenario. A DCARP scenario comprises a series of DCARP instances that share similarities with each other, and the proposed framework promotes the DCARP optimization for new DCARP instances by leveraging optimization experiences extracted from the former DCARP instances.
5. To evaluate the efficacy of proposed algorithms in comparison to the theoretical global optimum, we derived a node matching lower bound for DCARP instances as the theoretical global optimum is always unknown for most DCARP instances. The deviations between the lower bound and DCARP solutions are calculated to measure the performance of our algorithms.
6. To analysis the performance of proposed algorithms within real-world applications, we developed a DCARP benchmarking system based on SUMO (Simulation of Urban Mobility) integrated with real-traffic conditions. A series of DCARP scenarios with different settings are generated based on the proposed SUMO-based system using real-traffic data, thereby applying the proposed algorithms to these scenarios for further performance analysis from a more practical perspective.},
	publisher = {University of Birmingham},
	booktitle = {University of Birmingham}
}