A solution approach to the orienteering problem with time windows and synchronisation constraints

The orienteering problem with time windows and synchronisation constraints, known as the Cooperative Orienteering Problem with Time Windows (COPTW), is a class of problems with some important applications such as in home health care and emergency logistics management, and yet has received relatively little attention. In the COPTW, a certain number of team members are required to collect the associated reward from each node simultaneously and cooperatively. This requirement to have one or more team members simultaneously available at a vertex to collect the reward poses a challenging task. It means that while multiple paths need to be determined as in the team orienteering problem with time-windows (TOPTW), there is the additional requirement that certain paths must meet at some of the vertices. Exact methods are too slow for operational purposes and they are not able to handle large scale instances of the COPTW. In this paper, we address the problem of finding solutions to the COPTW in times that make the approach suitable for use in certain emergency response situations. This is achieved by developing new merit-based heuristics as elements of an Adaptive Large Neighbourhood Search (ALNS) algorithm. We validate the performance of this new approach through an extensive computational study. The computational results show that the proposed method is effective in obtaining high quality solutions in times that are suitable for operational purposes.