Reinforcement learning based hyper-heuristics for many-objective pickup and delivery problem

Adeem Ali Anwar*, Xuyun Zhang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

Abstract

The pickup and delivery problem (PDP) is considered one of the key optimization problems. PDP is an NP-Hard problem; consequently, researchers tried to solve it using evolutionary algorithms. In literature, different variations of the problem have been studied using evolutionary algorithms. In this paper, we consider the many-objective variation of the PDP known as MaOPDP with six objectives as it is similar to real-life PDP. To solve the problem, we considered 15 different low-level heuristics (LLHs) divided between perturbation and local search phases and optimized the search between LLHs using a cross-domain technique known as Hyper-heuristics (HHs). To effectively solve MaOPDP, a q-learning-based HH named Reinforcement learning-based Selection Hyper-heuristic (RL_SHH) is proposed. According to our knowledge, the considered version of MaOPDP has not been optimized using HHs in the literature. A high-level selection criterion covering exploration and exploitation is proposed to choose between LLHs. To prove the effectiveness of our approach, benchmark data sets have been taken in small, medium, and large sizes and contrasted with state-of-the-art HHs and meta-heuristics. RL-SHH has produced significantly better results on 69 out of 72 instances while using Hypervolume (HV). Additionally, μ norm mean values (a cross-domain indicator) have been taken into consideration, and RL-SHH has dominated a state-of-the-art HH known as HH-ILS by 646.7% and 100% using HV and Additive Epsilon Indicator (AEI) respectively.

Original languageEnglish
Title of host publication23rd IEEE International Conference on Data Mining ICDM 2023
Subtitle of host publicationproceedings
EditorsGuihai Chen, Latifur Khan, Xiaofeng Gao, Meikang Qiu, Witold Pedrycz, Xindong Wu
Place of PublicationPiscataway, NJ
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages924-929
Number of pages6
ISBN (Electronic)9798350307887
ISBN (Print)9798350307894
DOIs
Publication statusPublished - 2023
Event23rd IEEE International Conference on Data Mining, ICDM 2023 - Shanghai, China
Duration: 1 Dec 20234 Dec 2023

Publication series

Name
ISSN (Print)1550-4786
ISSN (Electronic)2374-8486

Conference

Conference23rd IEEE International Conference on Data Mining, ICDM 2023
Country/TerritoryChina
CityShanghai
Period1/12/234/12/23

Fingerprint

Dive into the research topics of 'Reinforcement learning based hyper-heuristics for many-objective pickup and delivery problem'. Together they form a unique fingerprint.

Cite this