Skip to Main content Skip to Navigation
Journal articles

The multi-visit team orienteering problem with precedence constraints

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.
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03400340
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Monday, October 25, 2021 - 8:29:30 AM
Last modification on : Wednesday, November 3, 2021 - 5:24:23 AM

Identifiers

Collections

Citation

Said Hanafi, Renata Mansini, Roberto Zanotti. The multi-visit team orienteering problem with precedence constraints. European Journal of Operational Research, Elsevier, 2020, 282 (2), pp.515-529. ⟨10.1016/j.ejor.2019.09.045⟩. ⟨hal-03400340⟩

Share

Metrics

Record views

9