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

doi:10.1145/3512290.3528756

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 Proceedings › Conference paper (refereed) › Research › peer-review

2 Citations (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 language	English
Title of host publication	GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference
Publisher	Association for Computing Machinery, Inc
Pages	305-313
Number of pages	9
ISBN (Print)	9781450392372
DOIs	https://doi.org/10.1145/3512290.3528756
Publication status	Published - 8 Jul 2022
Externally published	Yes

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

Access to Document

10.1145/3512290.3528756

Cite this

@inproceedings{43558225e80346d09776cc086bf1f168,

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

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. {\textcopyright} 2022 ACM.",

keywords = "Dynamic CARP, Dynamic Events, Fitness Landscape Analysis, Local Search Algorithm",

author = "Hao TONG and MINKU, {Leandro L.} and Stefan MENZEL and Bernhard SENDHOFF and Xin YAO",

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

year = "2022",

month = jul,

day = "8",

doi = "10.1145/3512290.3528756",

language = "English",

isbn = "9781450392372",

pages = "305--313",

booktitle = "GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery, Inc",

}

What Makes The Dynamic Capacitated Arc Routing Problem Hard To Solve: Insights From Fitness Landscape Analysis. / TONG, Hao; MINKU, Leandro L.; MENZEL, Stefan et al.
GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference. Association for Computing Machinery, Inc, 2022. p. 305-313.

Research output: Book Chapters | Papers in Conference Proceedings › Conference paper (refereed) › Research › peer-review

TY - GEN

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

AU - TONG, Hao

AU - MINKU, Leandro L.

AU - MENZEL, Stefan

AU - SENDHOFF, Bernhard

AU - YAO, Xin

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

PY - 2022/7/8

Y1 - 2022/7/8

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

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

KW - Dynamic CARP

KW - Dynamic Events

KW - Fitness Landscape Analysis

KW - Local Search Algorithm

UR - http://www.scopus.com/inward/record.url?scp=85135225653&partnerID=8YFLogxK

U2 - 10.1145/3512290.3528756

DO - 10.1145/3512290.3528756

M3 - Conference paper (refereed)

SN - 9781450392372

SP - 305

EP - 313

BT - GECCO 2022 - Proceedings of the 2022 Genetic and Evolutionary Computation Conference

PB - Association for Computing Machinery, Inc

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this