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.