A Novel Generalized Metaheuristic Framework for Dynamic Capacitated Arc Routing Problems

Hao TONG, Leandro L. MINKU, Stefan MENZEL, Bernhard SENDHOFF, Xin YAO

Research output: Book Chapters | Papers in Conference ProceedingsConference paper (refereed)Researchpeer-review

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. © 2023 Copyright held by the owner/author(s).
Original languageEnglish
Title of host publicationGECCO 2023 Companion : Proceedings of the 2023 Genetic and Evolutionary Computation Conference Companion
EditorsSara SILVA, Luís PAQUETE
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
Pages45-46
Number of pages2
ISBN (Print)9798400701207
DOIs
Publication statusPublished - 15 Jul 2023
Externally publishedYes
EventGenetic and Evolutionary Computation Conference 2023 - Lisbon, Portugal
Duration: 15 Jul 202319 Jul 2023

Conference

ConferenceGenetic and Evolutionary Computation Conference 2023
Abbreviated titleGECCO’23 Companion
Country/TerritoryPortugal
CityLisbon
Period15/07/2319/07/23

Bibliographical note

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
  • Evolutionary Algorithms
  • Meta-heuristic Algorithms
  • Routing Optimization

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