go back

Benchmarking Dynamic Capacitated Arc Routing Algorithms Using Real-World Traffic Simulation

Hao Tong, Leandro Minku, Stefan Menzel, Bernhard Sendhoff, Xin Yao, "Benchmarking Dynamic Capacitated Arc Routing Algorithms Using Real-World Traffic Simulation", IEEE Congress on Evolutionary Computation, 2022.


The combinatorial optimization of the dynamic capacitated arc routing problem (DCARP) targets to re-schedule the service plans of agents, such as vehicles in a city scenario, when dynamic events deteriorate the quality of the current schedule. Various algorithms have been proposed to solve DCARP instances in different dynamic scenarios. However, most existing work in literature developed algorithms and evaluated their performance based on artifi cially constructed dynamic environments instead of using more advanced traffic simulations which are built on actual traffic data. In this paper, we constructed a novel DCARP optimization framework based on the Simulation of Urban MObility (SUMO) transportation simulation software, which allows to include actual traffic environments for generating a set of DCARP instances from dynamic events, such as road congestion or task changes. The flexibility of the framework allows to develop DCARP optimization algorithms and evaluate their effectiveness. We use the benchmarking framework to generate 12 different dynamic instances using real-world traffic data of Dublin City. They are used to compare a recently proposed hybrid local search algorithm (HyLS) with one state-of-the-art meta-heuristic optimization algorithm. The generated benchmark scenarios indicate that HyLS is a very effective optimizer on DCARP scenarios with real traffic data for reducing the total service cost as well as the value of our DCARP optimization framework for the development and benchmarking of optimization algorithms in this domain.

Download Bibtex file Per Mail Request