Heuristic approaches for a new variant of the team orienteering problem

In this paper, we tackle the team orienteering problem (TOP) with service times, mandatory nodes and incompatibilities arising from two real-world healthcare applications. We propose two heuristic algorithms: a variable neighbourhood descent algorithm and a matheuristic based on a cut separation approach. For the latter, we also provide a multi-threaded version exploiting its intrinsic capability to be parallelised. Both algorithms include a specific heuristic routine to provide a starting feasible solution, since finding a feasible solution has been proven to be NP-complete. The results of our heuristic algorithms are compared with an exact cutting plane approach and have complementary strengths and weaknesses. They are also evaluated on existing TOP benchmarks against state-of-the-art TOP algorithms, demonstrating their competitiveness on general grounds.