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

Tong，Hao1; Minku，Leandro L.1; Menzel，Stefan2; Sendhoff，Bernhard2; Yao，Xin3,4,5,6

10.1145/3512290.3528756

2022-07-08

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

305-313

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.

Dynamic CARP Dynamic Events Fitness Landscape Analysis Local Search Algorithm

Corresponding

English

EI

20223112528680

Routing algorithms

Computer Software, Data Handling and Applications:723 ; Optimization Techniques:921.5

2-s2.0-85135225653

Scopus

1.School of Computer Science,University of Birmingham,Birmingham,United Kingdom
2.Honda Research Institute Europe,Offenbach,Germany
3.Department of Computer Science and Engineering,SUSTech,Shenzhen,China
4.Research Institute of Trustworthy Autonomous Systems (RITAS),SUSTech,China
5.Guangdong Key Laboratory of Brain-inspired Intelligent Computation,SUSTech,China
6.School of Computer Science,University of Birmingham,United Kingdom

Tong，Hao,Minku，Leandro L.,Menzel，Stefan,et al. What Makes The Dynamic Capacitated Arc Routing Problem Hard To Solve: Insights From Fitness Landscape Analysis[C],2022:305-313.