What Makes The Dynamic Capacitated Arc Routing Problem Hard To Solve: Insights From Fitness Landscape Analysis

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

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

1 Citation (Scopus)

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. © 2022 ACM.
Original languageEnglish
Title of host publicationGECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
PublisherAssociation for Computing Machinery, Inc
Pages305-313
Number of pages9
ISBN (Print)9781450392372
DOIs
Publication statusPublished - 8 Jul 2022
Externally publishedYes

Bibliographical note

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).

Keywords

  • Dynamic CARP
  • Dynamic Events
  • Fitness Landscape Analysis
  • Local Search Algorithm

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