Roozbeh Iman, Hearne John W, Pahlevani Delaram
School of Science, RMIT University, Melbourne, Australia.
Heliyon. 2020 Jun 20;6(6):e04202. doi: 10.1016/j.heliyon.2020.e04202. eCollection 2020 Jun.
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.
带时间窗和同步约束的定向越野问题，即带时间窗的协同定向越野问题（COPTW），是一类具有重要应用的问题，如家庭医疗保健和应急物流管理等领域，但受到的关注相对较少。在COPTW中，需要一定数量的团队成员同时协作从每个节点获取相关奖励。要求有一个或多个团队成员同时在一个顶点获取奖励是一项具有挑战性的任务。这意味着虽然如同带时间窗的团队定向越野问题（TOPTW）一样需要确定多条路径，但还有额外要求，即某些路径必须在一些顶点处会合。精确方法对于实际操作来说太慢，并且无法处理大规模的COPTW实例。在本文中，我们解决了在适合某些应急响应情况的时间内找到COPTW解决方案的问题。这是通过开发新的基于价值的启发式算法作为自适应大邻域搜索（ALNS）算法的元素来实现的。我们通过广泛的计算研究验证了这种新方法的性能。计算结果表明，所提出的方法能够在适合实际操作的时间内有效地获得高质量的解决方案。
