Advancing optimization and evaluation for dynamic capacitated arc routing problems

Tong, Hao ORCID: 0000-0003-4881-8701 (2024). Advancing optimization and evaluation for dynamic capacitated arc routing problems. University of Birmingham. Ph.D.

Preview

Tong2024PhD.pdf
Text - Accepted Version
Available under License All rights reserved.
Download (11MB) | Preview

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 needs 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 dynamic 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 solution. In particular, we provide the following main contributions in this thesis:

1. We provide the first mathematical formulation of DCARP in the literature and developed a simulator to emulate the behavior of vehicles’ service processes in the real world. This simulator offers a novel research platform for generating DCARP benchmarks to support DCARP studies.

2. We propose 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. Experimental results demonstrate that the proposed framework was able to significantly improve over state-ofthe- art dynamic optimization algorithms in terms of total costs of the final solution.

3. We perform a fitness landscape analysis on various DCARP instances to understand which factors make a DCARP instance harder to solve. Empirical studies reveal that cost-related dynamic events had 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 propose 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. The proposed framework was able to improve the DCARP optimization for new DCARP instances in terms of total costs of initial solutions and convergence speed 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 derive 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. The evaluation based on the derived lower bound indicates that there is still room for improvement between the lower bound and the optimized result.

6. To analyze the performance of proposed algorithms on real-world applications, we develop 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 evaluating the proposed algorithms to these scenarios for performance analysis. The evaluation demonstrates that dynamic optimization for CARP is necessary in real-world applications. Moreover, empirical studies also indicate that the adopted artificial DCARP benchmarks were sufficient for measuring the performance of optimization algorithms.

Type of Work:

Thesis (Doctorates > Ph.D.)

Award Type:

Doctorates > Ph.D.

Supervisor(s):

Supervisor(s)	Email	ORCID
Yao, Xin	UNSPECIFIED	orcid.org/0000-0001-8837-4442
Minku, Leandro L.	UNSPECIFIED	orcid.org/0000-0002-2639-0671
Menzel, Stefan	UNSPECIFIED	UNSPECIFIED
Sendhoff, Bernhard	UNSPECIFIED	UNSPECIFIED