The multi-visit team orienteering problem with precedence constraints

Saïd Hanafi, Renata Mansini and Roberto Zanotti

European Journal of Operational Research, 2020, vol. 282, issue 2, 515-529

Abstract: We study a new variant of the Team Orienteering Problem (TOP) where precedence constraints are introduced. Each customer has a set of tasks that have to be accomplished according to a predefined order by an heterogeneous fleet of vehicles. If a customer is selected, then all the tasks have to be completed by possibly different vehicles. To tackle the problem, we propose an enhancement of the Kernel Search (KS) framework that makes use of different sorting strategies and compare its performance to a Branch-and-Cut algorithm embedding the dynamic separations of different valid inequalities and the use of a simplified KS as primal heuristic. The Branch-and-Cut strongly improves the performance of Gurobi when used to solve the compact problem formulation, whereas the variant of KS comes up to be an extremely effective approach also as primal heuristic embedded into a MIP solver. New benchmark instances and corresponding best known values are provided. Both solution approaches have also been tested on instances of the special case TOP providing extremely good results.

Keywords: Routing; Team orienteering problem; Precedence constraints; Kernel search; Branch-and-cut (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221719308021
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:282:y:2020:i:2:p:515-529

DOI: 10.1016/j.ejor.2019.09.045

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