A memetic algorithm for the Orienteering Problem with Mandatory Visits and Exclusionary Constraints

Yongliang Lu, Una Benlic and Qinghua Wu

European Journal of Operational Research, 2018, vol. 268, issue 1, 54-69

Abstract: The Orienteering Problem with Mandatory Visits and Exclusionary Constraints (OPMVEC) is to visit a set of mandatory nodes (locations) and some optional nodes, while respecting the compatibility constraint between nodes and the maximum total time budget constraint. It is a variation of the classic orienteering problem that originates from a number of real-life applications. We present a highly effective memetic algorithm (MA) for OPMVEC combining: (i) a dedicated tabu search procedure that considers both feasible and infeasible solutions by constraint relaxation, (ii) a backbone-based crossover, and (iii) a randomized mutation procedure to prevent from premature convergence. Experiments on six classes of 340 benchmark instances from the literature demonstrate highly competitive performance of MA – it reports improved results for 104 instances compared with the existing heuristic approach, while finding matching best-known results for the remaining cases. Additionally, MA can be used to produce a starting point for an exact solver (e.g., CPLEX), leading to an increased number of problem instances that are solved to optimality. We further investigate the contribution of the key algorithmic elements to the success of the proposed approach.

Keywords: Heuristics; Orienteering Problem; Memetic algorithm; Infeasible local search (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718300377
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:268:y:2018:i:1:p:54-69

DOI: 10.1016/j.ejor.2018.01.019

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