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 language | English |
|---|---|
| Title of host publication | 2022 IEEE Congress on Evolutionary Computation (CEC) |
| Publisher | IEEE |
| Number of pages | 8 |
| Volume | 2022 |
| ISBN (Electronic) | 978-1-6654-6709-4 |
| ISBN (Print) | 978-1-6654-6708-7 |
| DOIs | |
| Publication status | E-pub ahead of print - 6 Sept 2022 |
| Event | 2022 IEEE Congress on Evolutionary Computation - Padua, Italy Duration: 18 Jul 2022 → 23 Jul 2022 |
Publication series
| Name | Congress on Evolutionary Computation |
|---|---|
| Publisher | IEEE |
Conference
| Conference | 2022 IEEE Congress on Evolutionary Computation |
|---|---|
| Abbreviated title | IEEE CEC 2022 |
| Country/Territory | Italy |
| City | Padua |
| Period | 18/07/22 → 23/07/22 |
Access to Document
- TongH2022Benchmarking
This is the authors' accepted manuscript (AAM) for an article published in 2022 IEEE Congress on Evolutionary Computation (CEC) by IEEE as 10.1109/CEC55065.2022.9870399. © 2022 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works.