Carnegie Mellon University in Qatar, Doha, Qatar.
PLoS One. 2022 Jul 22;17(7):e0271751. doi: 10.1371/journal.pone.0271751. eCollection 2022.
The Orienteering Problem is a routing problem that commonly appears in mapping, transportation, distribution, and scheduling scenarios. The Orienteering Problem is a challenging NP-hard problem, such that obtaining optimal or near optimal solutions usually requires a significant amount of computation for large and even moderately large instances. As a result, existing algorithms cannot effectively be utilized for solving large Orienteering Problems in an online setting, which is often required in real-world applications where a plan has to be iteratively computed. For instance, a planner might need to adapt to changes in the scenario or in the environment (e.g., this is common in goods delivery, as well as in mobile robotic scenarios for coverage, monitoring, and surveillance). Motivated by these limitations, we propose a multi-stage clustering-based metaheuristic for tackling large Orienteering Problems in an effective, strategically controlled amount of computation time. The metaheuristic starts by decomposing the problem into smaller, independent sub-problems that are efficiently solved using an algorithm of choice, sequentially or in parallel. The obtained solutions are then merged to form a solution for the original problem, and then further optimized and processed to ensure feasibility. The metaheuristic aims to dramatically improve the computation time of a given Orienteering Problem algorithm without a significant decrease in the solution quality of that algorithm, especially for large Orienteering Problems. We have validated the effectiveness of the proposed metaheuristic design through a set of computational experiments. In particular, using a state-of-the-art heuristic and an exact algorithm, we have shown that it is significantly beneficial to use the Orienteering Problem algorithm plugged into our metaheuristic, as opposed to using it as a standalone algorithm. This was found to be especially true for large problems. As a result, large instances of Orienteering Problems can be effectively tackled within reasonable time bounds even for online application scenarios.
定向问题是一种常见于地图绘制、交通、配送和调度场景中的路径规划问题。定向问题是一个具有挑战性的 NP 难问题，因此获得最优或近似最优的解决方案通常需要大量的计算，尤其是对于大型甚至中等规模的实例。因此，现有的算法不能有效地用于在在线环境中解决大型定向问题，而在线环境通常是现实世界应用程序所需要的，这些应用程序需要迭代计算计划。例如，规划者可能需要适应场景或环境中的变化（例如，在货物配送中以及移动机器人的覆盖、监控和监视场景中，这是很常见的）。受这些限制的启发，我们提出了一种基于多阶段聚类的元启发式算法，用于在有效的、战略性控制的计算时间内解决大型定向问题。该元启发式算法首先将问题分解为更小的、独立的子问题，然后使用选择的算法有效地解决这些子问题，顺序或并行地解决。然后将获得的解决方案合并为原始问题的解决方案，然后进一步优化和处理以确保可行性。该元启发式算法旨在显著提高给定定向问题算法的计算时间，而不会显著降低该算法的解决方案质量，尤其是对于大型定向问题。我们已经通过一系列计算实验验证了所提出的元启发式设计的有效性。特别是，我们使用最先进的启发式算法和精确算法表明，将定向问题算法插入到我们的元启发式算法中使用，而不是单独使用该算法，这是非常有益的。对于大型问题尤其如此。因此，即使在在线应用场景中，也可以在合理的时间内有效地解决大型定向问题的实例。
