This paper introduces an extension to the Orienteering Problem (OP), called Clustered Orienteering Problem with Subgroups (COPS). In this variant, nodes are arranged into subgroups, and the subgroups are organized into clusters. A reward is associated with each subgroup and is gained only if all of its nodes are visited; however, at most one subgroup can be visited per cluster. The objective is to maximize the total collected reward while attaining a travel budget. We show that our new formulation has the ability to model and solve two previous well-known variants, the Clustered Orienteering Problem (COP) and the Set Orienteering Problem (SOP), in addition to other scenarios introduced here. An Integer Linear Programming (ILP) formulation and a Tabu Search-based heuristic are proposed to solve the problem. Experimental results indicate that the ILP method can yield optimal solutions at the cost of time, whereas the metaheuristic produces comparable solutions within a more reasonable computational cost.

本论文介绍了一种 Orienteering Problem（OP）的扩展，被称为 Clustered Orienteering Problem with Subgroups (COPS)。在这个变种中，节点被分成子组，并且子组被组织成簇。每个子组都与奖励相关，只有当访问其所有节点时才能获得奖励；然而，每个簇最多只能访问一个子组。目标是在旅行预算下最大化总奖励收集。我们展示了我们的新模型有能力模拟和解决之前已知的两个变种，即 Clustered Orienteering Problem (COP) 和 Set Orienteering Problem (SOP)，以及其他在本文中介绍的情境。我们提出了一个整数线性规划（ILP）模型和一个基于 Tabu 搜索的启发式方法来解决这个问题。实验结果表明，ILP 方法可以得到最优解，但时间开销较大，而元启发式方法在更合理的计算成本内产生可比较的解。

子群对聚类导航问题的研究