最小最大圈覆盖问题的精确算法 袁森.pdf

: .
网络首发时间：2022-06-09 16:49:54
网络首发地址or the min-max cycle cover problem (in Chinese). Sci Sin Inform,
2022, doi: -2021-0444
⃝c 2022 《中国科学》杂志社 : 最小最大圈覆盖问题的精确算法
7 7
8 8
2 2
4 4
1 1
6 6
9 9
3 3
5 5
10 10
(a) (b)
图 1 不平衡的 (a) 和平衡的 (b) 数据收集路径示例
Figure 1 An example of the unbalanced (a) and balanced (b) data gathering route
最小最大圈覆盖问题是组合优化问题的典型代表, 其应用广泛, 应用领域包括物流配送 [3]、车辆路
径规划 [4]、无人机灾难救援 [5, 6]、无线传感器网络 [7, 8] 等. 例如, 在无线传感器网络中, 传感器之间距离
较远, 无法直接相互通信, 因此如何从传感器收集数据就成为一个基本的问题. 解决该问题的一个有效
的方法是, 调度多个移动接收器来收集来自传感器的数据. 每一个移动接收器收集完数据后都需要回
到它出发的位置, 因此移动接收器的路径是一个圈. 由于移动接收器的工作时间是受到它所携带的电
能的约束的, 我们希望平衡不同数据收集路径的长度, 以便尽快收集传感数据. 例如, 图 1(a) 和 (b) 表
示了在由 10 个无线传感器组成的网络上, 有两种不同的数据收集路径. 图上的边表示移动接收器在
数据收集途中的移动路径. 显然, 收集数据的完成时间取决于最大圈的长度. 图 1(a) 是不平衡的数据
收集路径的例子, 其收集完成时间长; 图 1(b) 是平衡的数据收集路径的例子, 其收集完成时间短. 因
此, 在无线传感器网络的数据收集问题中, 我们希望数据收集路径的最大长度最短, 这恰好就得到