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

Jiyuan PEI, Yi MEI, Jialin LIU*, Xin YAO

*Corresponding author for this work

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

1 Citation (Scopus)

Abstract

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-of-the-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. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
Original languageEnglish
Title of host publicationPRICAI 2022: Trends in Artificial Intelligence : 19th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2022, Shanghai, China, November 10–13, 2022, Proceedings, Part I
EditorsSankalp KHANNA, Jian CAO, Quan BAI, Guandong XU
PublisherSpringer Science and Business Media Deutschland GmbH
Pages562-573
Number of pages12
ISBN (Electronic)9783031208621
ISBN (Print)9783031208614
DOIs
Publication statusPublished - 2022
Externally publishedYes
Event19th Pacific Rim International Conference on Artificial Intelligence - Shanghai, China
Duration: 11 Oct 202213 Oct 2022

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume13629
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference19th Pacific Rim International Conference on Artificial Intelligence
Abbreviated titlePRICAI 2022
Country/TerritoryChina
CityShanghai
Period11/10/2213/10/22

Bibliographical note

This work was supported by the National Natural Science Foundation of China (Grant No. 61906083), the Shenzhen Science and Technology Program (Grant No. KQTD2016112514355531), the Shenzhen Fundamental Research Program (Grant No. JCYJ20190809121403553), the Guangdong Provincial Key Laboratory (Grant No. 2020B121201001), and Marsden Fund of New Zealand Government (VUW1614).

Keywords

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

Fingerprint

Dive into the research topics of 'An Investigation of Adaptive Operator Selection in Solving Complex Vehicle Routing Problem'. Together they form a unique fingerprint.

Cite this