Reinforcement Learning based Hyper-heuristics for Many-objective Pickup and Delivery Problem
Adeem Ali Anwar, Xuyun Zhang · 2023
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, $\mu$ 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.