What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis

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

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

104 Downloads (Pure)

Abstract

The Capacitated Arc Routing Problem (CARP) aims at assigning vehicles to serve tasks which are located at different arcs in a graph. However, the originally planned routes are easily affected by different dynamic events like newly added tasks. This gives rise to Dynamic CARP (DCARP) instances, which need to be efficiently optimized for new high-quality service plans in a short time. However, it is unknown which dynamic events make DCARP instances especially hard to solve. Therefore, in this paper, we provide an investigation of the influence of different dynamic events on DCARP instances from the perspective of fitness landscape analysis based on a recently proposed hybrid local search (HyLS) algorithm. We generate a large set of DCARP instances based on a variety of dynamic events and analyze the fitness landscape of these instances using several different measures such as fitness correlation length. From the empirical results we conclude that cost-related events have no significant impact on the difficulty of DCARP instances, but instances which require more new vehicles to serve the remaining tasks are harder to solve. These insights improve our understanding of the DCARP instances and pave the way for future work on improving the performance of DCARP algorithms.
Original languageEnglish
Title of host publicationGECCO '22
Subtitle of host publicationProceedings of the Genetic and Evolutionary Computation Conference
EditorsJonathan E. Fieldsend
Place of PublicationNew York
PublisherAssociation for Computing Machinery (ACM)
Pages305-313
Number of pages9
ISBN (Electronic)9781450392372
DOIs
Publication statusPublished - 8 Jul 2022
EventGECCO '22: Genetic and Evolutionary Computation Conference - Boston, United States
Duration: 9 Jul 202213 Jul 2022

Publication series

NameGECCO: Genetic and Evolutionary Computation Conference

Conference

ConferenceGECCO '22: Genetic and Evolutionary Computation Conference
Abbreviated titleGECCO 2022
Country/TerritoryUnited States
CityBoston
Period9/07/2213/07/22

Bibliographical note

Funding Information:
Hao Tong gratefully acknowledges the financial support from Honda Research Institute Europe (HRI-EU). This work was also support by Research Institute of Trustworthy Autonomous Systems (RITAS), the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), the Program for Guangdong Introducing Innovative and Enterpreneurial Teams (Grant No. 2017ZT07X386), the Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531).

Publisher Copyright:
© 2022 ACM.

Keywords

  • Fitness landscape analysis
  • dynamic CARP
  • dynamic event
  • local search algorithm
  • Local Search Algorithm
  • Dynamic CARP
  • Dynamic Events
  • Fitness Landscape Analysis

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Theoretical Computer Science

Fingerprint

Dive into the research topics of 'What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis'. Together they form a unique fingerprint.

Cite this