An Investigation of Adaptive Operator Selection in Solving Complex Vehicle Routing Problem

Pei, Jiyuan1; Mei, Yi2; Liu, Jialin1; Yao, Xin1

10.1007/978-3-031-20862-1_41

2022

19th Pacific Rim International Conference on Artificial Intelligence (PRICAI)

0302-9743

1611-3349

978-3-031-20861-4

LECT NOTES ARTIF INT

13629

NOV 10-13, 2022

null,Shanghai,PEOPLES R CHINA

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

Search operators play an important role in meta-heuristics. There are typically a variety of search operators available for solving a problem, and the selection and order of using the operators can greatly affect the algorithm performance. Adaptive operator selection (AOS) has been proposed to select operators during optimisation dynamically and adaptively. However, most existing studies focus on real-value optimisation problems, while combinatorial optimisation problems, especially complex routing problems, are seldom considered. Motivated by the effectiveness of AOS on real-value optimisation problems and the urgent need of efficiency in solving real routing problems, this paper investigates AOS in complex routing problems obtained from real-world scenarios, the multi-depot multi-disposal-facility multi-trip capacitated vehicle routing problems (M3CVRPs). Specifically, the stateless AOS, arguable the most classic, intuitive and commonly used category of AOS approaches, is integrated into the region-focused local search (RFLS), the state-ofthe-art algorithm for solving M3CVRPs. Unexpectedly and yet within understanding, experimental results show that the original RFLS performs better than the RFLS embedded with stateless AOS approaches. To determine the causes, a novel neighbourhood analysis is conducted to investigate the characteristics of M3CVRP and the factors that affect the performance of the AOS. Experimental results indicate that the momentum assumption of stateless AOS, good operators in history will also work well in current stage, is not satisfied within most of the time during the optimisation of the complex problem, leading to the unstable performance of operators and the failure of stateless AOS.

Adaptive operator selection Vehicle routing problem Neighbourhood analysis Local search Meta-heuristics

First ; Corresponding

English

CPCI-S

National Natural Science Foundation of China[61906083] ; Shenzhen Science and Technology Program[KQTD2016112514355531] ; Shenzhen Fundamental Research Program[JCYJ20190809121403553] ; Guangdong Provincial Key Laboratory[2020B121201001] ; Marsden Fund of New Zealand Government[VUW1614]

Computer Science

Computer Science, Artificial Intelligence ; Computer Science, Interdisciplinary Applications ; Computer Science, Theory & Methods

WOS:000897031800041

Web of Science

1.Southern Univ Sci & Technol SUSTech, Dept Comp Sci & Engn, Shenzhen 518055, Peoples R China
2.Victoria Univ Wellington, Sch Engn & Comp Sci, Wellington 6012, New Zealand

Pei, Jiyuan,Mei, Yi,Liu, Jialin,et al. An Investigation of Adaptive Operator Selection in Solving Complex Vehicle Routing Problem[C]. GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND:SPRINGER INTERNATIONAL PUBLISHING AG,2022.