Abstract
The capacitated arc routing problem (CARP) aims at scheduling a fleet of vehicles with limited capacities to serve a set of tasks in a graph. The dynamic CARP (DCARP) optimization focuses on updating the vehicles’ service routes when unpredicted dynamic events happen and deteriorate the current service plan. Due to the outside vehicles are still being in their service when dynamic events happen and being located at different positions of the graph with different remaining capacities, the optimization algorithms for static CARP are unsuitable for solving the DCARP instance. However, in the existing literature, almost all proposed algorithms for DCARP were designed only for specific dynamic events instead of generic dynamic events such as the changing of traversing costs, the changing of the task’s demand, and the changing of the task’s number. Moreover, these algorithms are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this work, we proposed a novel generalized meta-heuristic framework which enables all algorithms designed for static CARP to be capable of solving DCARP instances. Our experimental results demonstrated that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms in terms of the quality of obtained solution within the limited computational time.
Original language | English |
---|---|
Title of host publication | GECCO '23 Companion |
Subtitle of host publication | Proceedings of the Companion Conference on Genetic and Evolutionary Computation |
Publisher | Association for Computing Machinery (ACM) |
Pages | 45–46 |
Number of pages | 2 |
ISBN (Electronic) | 9798400701207 |
DOIs | |
Publication status | Published - 24 Jul 2023 |
Event | GECCO '23: Genetic and Evolutionary Computation Conference - Lisbon, Portugal Duration: 15 Jul 2023 → 19 Jul 2023 https://dl.acm.org/conference/gecco |
Publication series
Name | GECCO: Genetic and Evolutionary Computation Conference |
---|
Conference
Conference | GECCO '23: Genetic and Evolutionary Computation Conference |
---|---|
Abbreviated title | GECCO '23 |
Country/Territory | Portugal |
City | Lisbon |
Period | 15/07/23 → 19/07/23 |
Internet address |
Bibliographical note
Acknowledgments:Hao Tong gratefully acknowledges the financial support from Honda Research Institute Europe (HRI-EU). Part of this work was done while the first author was a visiting PhD student at SUSTech.
Keywords
- Dynamic Capacitated Arc Routing Problem
- Meta-heuristic Algorithms
- Routing Optimization
- Evolutionary Algorithms