The multi-visit team orienteering problem with precedence constraints

• Published in: European journal of operational research 2020-04, Vol.282 (2), p.515-529
• Main Authors: Hanafi, Saïd, Mansini, Renata, Zanotti, Roberto
• Format: Article
• Language: English
• Subjects: Branch-and-cut; Computer Science; Kernel search; Precedence constraints; Routing; Team orienteering problem
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2019.09.045

•A new variant of the Team Orienteering Problem is introduced.•Two branch-and-cut algorithms are proposed to solve the problem.•A variant of Kernel Search is developed as an effective heuristic approach.•The proposed algorithms are also effective for the Team Orienteering Problem. 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.