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

Hao Tong, Leandro Minku, Stefan Menzel, Bernard Sendhoff, Xin Yao

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The dynamic capacitated arc routing problem
(DCARP) aims at re-scheduling 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 evaluated their algorithms’
performance based on artificially constructed dynamic environments
instead of using more realistic traffic simulations which
are built on actual traffic data. In this paper, we constructed a
novel DCARP benchmarking framework based on the Simulation
of Urban MObility (SUMO) transportation simulation software,
which allows to include real-world 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 more comprehensively. We use the benchmarking
framework to generate 12 different dynamic instances using
real-world traffic data of Dublin City. We then demonstrate the
value of our framework by using these instances to compare
our previously proposed hybrid local search algorithm (HyLS)
with a 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. They also demonstrate the
importance of our DCARP benchmarking framework for the
development and benchmarking of optimization algorithms in
more realistic scenarios.
Original languageEnglish
Title of host publicationIEEE Congress on Evolutionary Computation (IEEE CEC 2022)
Publication statusAccepted/In press - 26 Apr 2022

Fingerprint

Dive into the research topics of 'Benchmarking Dynamic Capacitated Arc Routing Algorithms Using Real-World Traffic Simulation'. Together they form a unique fingerprint.

Cite this