Constructing selection hyper-heuristics for open vehicle routing with time delay neural networks using multiple experts

Tyasnurita, Raras; Özcan, Ender; Drake, John H.; Asta, Shahriar

Abstract

Hyper-heuristics are general purpose search methods for solving computationally difficult problems. A selection hyper-heuristic is composed of two key components: a heuristic selection method and move acceptance criterion. Under an iterative single-point search framework, a solution is modified by selecting and applying a predefined low-level heuristic, with a decision then taken to accept or reject the resulting solution. Designing a selection hyper-heuristic is an extremely challenging task. In this study, we investigate computer-aided design of a selection hyper-heuristic for the open vehicle routing problem. A time delay neural network is used as an offline apprenticeship learning method. Our approach first observes the search behaviour of multiple expert human-designed selection hyper-heuristics on a selected sample of training instances, before automatically generating a selection hyper-heuristic capable of solving unseen instances effectively. The proposed approach is tested on open vehicle routing problem instances of different sizes to examine the performance and generality of the selection hyper-heuristics generated. Improved performance is demonstrated over a set of well-known benchmarks from the literature when compared to using the existing expert systems directly.

Citation

Tyasnurita, R., Özcan, E., Drake, J. H., & Asta, S. (2024). Constructing selection hyper-heuristics for open vehicle routing with time delay neural networks using multiple experts. Knowledge-Based Systems, 295, Article 111731. https://doi.org/10.1016/j.knosys.2024.111731

• Journal Article Type: Article
• Acceptance Date: Mar 30, 2024
• Online Publication Date: Apr 18, 2024
• Publication Date: Jul 8, 2024
• Deposit Date: May 12, 2024
• Publicly Available Date: May 15, 2024
• Journal: Knowledge-Based Systems
• Print ISSN: 0950-7051
• Electronic ISSN: 1872-7409
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 295
• Article Number: 111731
• DOI: https://doi.org/10.1016/j.knosys.2024.111731
• Keywords: Combinatorial optimisation, Metaheuristics, Vehicle routing, Apprenticeship learning, Machine learning
• Public URL: https://nottingham-repository.worktribe.com/output/34632998
• Publisher URL: https://www.sciencedirect.com/science/article/pii/S0950705124003666?via%3Dihub
• Additional Information: This article is maintained by: Elsevier; Article Title: Constructing selection hyper-heuristics for open vehicle routing with time delay neural networks using multiple experts; Journal Title: Knowledge-Based Systems; CrossRef DOI link to publisher maintained version: https://doi.org/10.1016/j.knosys.2024.111731; Content Type: article; Copyright: © 2024 The Author(s). Published by Elsevier B.V.