A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems

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

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

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 languageEnglish
Title of host publicationGECCO '23 Companion
Subtitle of host publicationProceedings of the Companion Conference on Genetic and Evolutionary Computation
PublisherAssociation for Computing Machinery (ACM)
Pages45–46
Number of pages2
ISBN (Electronic)9798400701207
DOIs
Publication statusPublished - 24 Jul 2023
EventGECCO '23: Genetic and Evolutionary Computation Conference - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023
https://dl.acm.org/conference/gecco

Publication series

NameGECCO: Genetic and Evolutionary Computation Conference

Conference

ConferenceGECCO '23: Genetic and Evolutionary Computation Conference
Abbreviated titleGECCO '23
Country/TerritoryPortugal
CityLisbon
Period15/07/2319/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

Fingerprint

Dive into the research topics of 'A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems'. Together they form a unique fingerprint.

Cite this