A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties

Yuchang Zhang, Ruibin Bai, Rong Qu, Chaofan Tu, Jiahuan Jin

Research output: Journal PublicationArticlepeer-review

64 Citations (Scopus)

Abstract

In the past decade, considerable advances have been made in the field of computational intelligence and operations research. However, the majority of these optimisation approaches have been developed for deterministically formulated problems, the parameters of which are often assumed perfectly predictable prior to problem-solving. In practice, this strong assumption unfortunately contradicts the reality of many real-world problems which are subject to different levels of uncertainties. The solutions derived from these deterministic approaches can rapidly deteriorate during execution due to the over-optimisation without explicit consideration of the uncertainties. To address this research gap, a deep reinforcement learning based hyper-heuristic framework is proposed in this paper. The proposed approach enhances the existing hyper-heuristics with a powerful data-driven heuristic selection module in the form of deep reinforcement learning on parameter-controlled low-level heuristics, to substantially improve their handling of uncertainties while optimising across various problems. The performance and practicality of the proposed hyper-heuristic approach have been assessed on two combinatorial optimisation problems: a real-world container terminal truck routing problem with uncertain service times and the well-known online 2D strip packing problem. The experimental results demonstrate its superior performance compared to existing solution methods for these problems. Finally, the increased interpretability of the proposed deep reinforcement learning hyper-heuristic has been exhibited in comparison with the conventional deep reinforcement learning methods.

Original languageEnglish
Pages (from-to)418-427
Number of pages10
JournalEuropean Journal of Operational Research
Volume300
Issue number2
DOIs
Publication statusPublished - 16 Jul 2022

Keywords

  • 2D packing
  • Container truck routing
  • Deep reinforcement learning
  • Hyper-heuristics
  • Transportation

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'A deep reinforcement learning based hyper-heuristic for combinatorial optimisation with uncertainties'. Together they form a unique fingerprint.

Cite this