An effective hybrid evolutionary algorithm for the clustered orienteering problem

Qinghua Wu, Mu He, Jin-Kao Hao and Yongliang Lu

European Journal of Operational Research, 2024, vol. 313, issue 2, 418-434

Abstract: In this paper, we study a variant of the orienteering problem called the clustered orienteering problem. In this problem, customers are grouped into clusters. A profit is associated with each cluster and is collected if and only if all customers in the cluster are served. A single vehicle is available to visit the customers. The goal is to maximize the total profits collected within a maximum travel time limit. To address this NP-hard problem, we propose the first evolutionary algorithm that integrates a backbone-based crossover operator and a destroy-and-repair mutation operator for search diversification and a solution-based tabu search procedure reinforced by a reinforcement learning mechanism for search intensification. The experiment results indicate that our algorithm outperforms the state-of-the-art algorithms from the literature on a wide range of 924 well-known benchmark instances. In particular, the proposed algorithm obtains new records (new lower bounds) for 14 instances and finds the best-known solutions for the remaining instances. Furthermore, a new set of 72 large instances with 50 to 100 clusters and at least 400 vertices is generated to evaluate the scalability of the proposed algorithm. Results show that the proposed algorithm manages to outperform three state-of-the-art COP algorithms. We also adopt our algorithm to solve a dynamic version of the COP considering stochastic travel time.

Keywords: Heuristics; Clustered orienteering problem; Tabu search; Hybrid evolutionary algorithm; Reinforcement learning (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221723006100
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:313:y:2024:i:2:p:418-434

DOI: 10.1016/j.ejor.2023.08.006

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().