An effective multi-level memetic search with neighborhood reduction for the clustered team orienteering problem

Mu He, Qinghua Wu, Una Benlic, Yongliang Lu and Yuning Chen

European Journal of Operational Research, 2024, vol. 318, issue 3, 778-801

Abstract: The Clustered Team Orienteering Problem (CluTOP) extends the classic Clustered Orienteering Problem by considering the use of multiple vehicles. The problem is known to be NP-hard and can be used to formulate many real-life applications. This work presents a highly effective multi-level memetic search for CluTOP that combines a backbone-based edge assembly crossover to generate promising offspring solutions with an effective bilevel synergistic local search procedure at both cluster and customer levels to improve offspring solutions. Other novel features of the proposed approach include a joint use of three specific hash functions to identify the tabu status of candidate solutions at the cluster level, a multi-neighborhood search with inter-route and intra-route optimization at the customer level, a pre-processing neighborhood reduction strategy to avoid examining non-promising candidate solutions, and a strategy for controlled exploration of infeasible solutions. Extensive experimental results on 1848 benchmark instances convincingly demonstrate high competitiveness of the approach in terms of both solution quality and computational time, compared to the state-of-the-art heuristics from the literature. In particular, the proposed algorithm improves upon the existing best-known solutions for 294 instances, while matching the previous best-known results for all but 3 of the remaining instances. To gain further insights into the algorithm’s performance, additional experiments are conducted to analyze its main components.

Keywords: Heuristics; Orienteering problem; Neighborhood reduction; Memetic search (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221724004636
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:318:y:2024:i:3:p:778-801

DOI: 10.1016/j.ejor.2024.06.015

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 ().