The multi-visit team orienteering problem with precedence constraints - Université Polytechnique des Hauts-de-France Accéder directement au contenu
Article Dans Une Revue European Journal of Operational Research Année : 2020

The multi-visit team orienteering problem with precedence constraints

Résumé

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.
Fichier non déposé

Dates et versions

hal-03400340 , version 1 (25-10-2021)

Identifiants

Citer

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

Altmetric

Partager

Gmail Facebook X LinkedIn More