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

doi:10.1145/3512290.3528756

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

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

159 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 language	English
Title of host publication	GECCO '22
Subtitle of host publication	Proceedings of the Genetic and Evolutionary Computation Conference
Editors	Jonathan E. Fieldsend
Place of Publication	New York
Publisher	Association for Computing Machinery (ACM)
Pages	305-313
Number of pages	9
ISBN (Electronic)	9781450392372
DOIs	https://doi.org/10.1145/3512290.3528756
Publication status	Published - 8 Jul 2022
Event	GECCO '22: Genetic and Evolutionary Computation Conference - Boston, United States Duration: 9 Jul 2022 → 13 Jul 2022

Publication series

Name	GECCO: Genetic and Evolutionary Computation Conference

Conference

Conference	GECCO '22: Genetic and Evolutionary Computation Conference
Abbreviated title	GECCO 2022
Country/Territory	United States
City	Boston
Period	9/07/22 → 13/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

Access to Document

10.1145/3512290.3528756

TongH2022WhatmaAccepted author manuscript, 1.91 MB
TongH2022Whatma_SupplAccepted author manuscript, 149 KB

Cite this

Tong, H., Minku, L., Menzel, S., Senhoff, B., & Yao, X. (2022). What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis. In J. E. Fieldsend (Ed.), GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference (pp. 305-313). (GECCO: Genetic and Evolutionary Computation Conference). Association for Computing Machinery (ACM). https://doi.org/10.1145/3512290.3528756

Tong, Hao ; Minku, Leandro ; Menzel, Stefan et al. / What makes the dynamic capacitated arc routing problem hard to solve : insights from fitness landscape analysis. GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference. editor / Jonathan E. Fieldsend. New York : Association for Computing Machinery (ACM), 2022. pp. 305-313 (GECCO: Genetic and Evolutionary Computation Conference).

@inproceedings{148b7bdcd9b846ffaa92cf15f2f39e25,

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

keywords = "Fitness landscape analysis, dynamic CARP, dynamic event, local search algorithm, Local Search Algorithm, Dynamic CARP, Dynamic Events, Fitness Landscape Analysis",

author = "Hao Tong and Leandro Minku and Stefan Menzel and Bernhard Senhoff and Xin Yao",

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: {\textcopyright} 2022 ACM.; GECCO '22: Genetic and Evolutionary Computation Conference, GECCO 2022 ; Conference date: 09-07-2022 Through 13-07-2022",

year = "2022",

month = jul,

day = "8",

doi = "10.1145/3512290.3528756",

language = "English",

series = "GECCO: Genetic and Evolutionary Computation Conference",

publisher = "Association for Computing Machinery (ACM)",

pages = "305--313",

editor = "Fieldsend, {Jonathan E.}",

booktitle = "GECCO '22",

address = "United States",

}

Tong, H, Minku, L, Menzel, S, Senhoff, B & Yao, X 2022, What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis. in JE Fieldsend (ed.), GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference. GECCO: Genetic and Evolutionary Computation Conference, Association for Computing Machinery (ACM), New York, pp. 305-313, GECCO '22: Genetic and Evolutionary Computation Conference, Boston, Massachusetts, United States, 9/07/22. https://doi.org/10.1145/3512290.3528756

What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis. / Tong, Hao; Minku, Leandro; Menzel, Stefan et al.
GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference. ed. / Jonathan E. Fieldsend. New York: Association for Computing Machinery (ACM), 2022. p. 305-313 (GECCO: Genetic and Evolutionary Computation Conference).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - What makes the dynamic capacitated arc routing problem hard to solve

T2 - GECCO '22: Genetic and Evolutionary Computation Conference

AU - Tong, Hao

AU - Minku, Leandro

AU - Menzel, Stefan

AU - Senhoff, Bernhard

AU - Yao, Xin

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

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.

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.

KW - Fitness landscape analysis

KW - dynamic CARP

KW - dynamic event

KW - local search algorithm

KW - Local Search Algorithm

KW - Dynamic CARP

KW - Dynamic Events

KW - Fitness Landscape Analysis

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

U2 - 10.1145/3512290.3528756

DO - 10.1145/3512290.3528756

M3 - Conference contribution

T3 - GECCO: Genetic and Evolutionary Computation Conference

SP - 305

EP - 313

BT - GECCO '22

A2 - Fieldsend, Jonathan E.

PB - Association for Computing Machinery (ACM)

CY - New York

Y2 - 9 July 2022 through 13 July 2022

ER -

Tong H, Minku L, Menzel S, Senhoff B, Yao X. What makes the dynamic capacitated arc routing problem hard to solve: insights from fitness landscape analysis. In Fieldsend JE, editor, GECCO '22: Proceedings of the Genetic and Evolutionary Computation Conference. New York: Association for Computing Machinery (ACM). 2022. p. 305-313. (GECCO: Genetic and Evolutionary Computation Conference). doi: 10.1145/3512290.3528756

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

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this