基于强化学习的距离约束的最大加权目标覆盖问题研究
A Reinforcement Learning Framework for Solving the Maximum Weighted Target Cover Problem with Distance Limitations
摘要: 距离约束的最大加权目标覆盖问题(MaxWTCDL)是一个NP-难组合优化问题。传统的启发式和近似算法在处理此问题时，往往容易陷入局部最优，难以求解。为了解决这些挑战，我们提出了一种基于强化学习的方法来求解MaxWTCDL问题。首先，我们将该问题重新表述为最大预算分组集合覆盖问题(MaxBGSC)的一个特例。我们将该问题建模为马尔可夫决策过程，并采用Q-learning算法来学习有效的传感器移动策略。实验结果表明，所提出的强化学习方法相比传统算法取得了更优越的性能，突显了其在高效解决带有距离约束的复杂覆盖问题方面的潜力。
Abstract: The Maximum Weighted Target Cover Problem with Distance Limitations (MaxWTCDL) is an NP-hard combinatorial optimization problem. Traditional heuristic and approximation algorithms often struggle with this problem due to a tendency to converge to local optima. To address these challenges, we propose a reinforcement learning-based approach for solving the MaxWTCDL problem. Specifically, we reformulate the problem as a special case of the Maximum Budgeted Group Set Cover Problem (MaxBGSC). We model the problem as a Markov Decision Process and employ the Q -learning algorithm to learn effective sensor movement strategies. Experimental results demonstrate that the proposed reinforcement learning method achieves superior performance compared to traditional algorithms, highlighting its potential in efficiently solving complex coverage problems with distance constraints.
文章引用：梁泳劲, 何伟骅. 基于强化学习的距离约束的最大加权目标覆盖问题研究[J]. 应用数学进展, 2026, 15(3): 23-33. https://doi.org/10.12677/aam.2026.153084

参考文献

[1] Mois, G., Folea, S. and Sanislav, T. (2017) Analysis of Three IoT-Based Wireless Sensors for Environmental Monitoring. IEEE Transactions on Instrumentation and Measurement, 66, 2056-2064. [Google Scholar] [CrossRef] 
[2] Lombardo, L., Corbellini, S., Parvis, M., Elsayed, A., Angelini, E. and Grassini, S. (2018) Wireless Sensor Network for Distributed Environmental Monitoring. IEEE Transactions on Instrumentation and Measurement, 67, 1214-1222. [Google Scholar] [CrossRef] 
[3] Li, X., Li, D., Wan, J., Vasilakos, A.V., Lai, C. and Wang, S. (2015) A Review of Industrial Wireless Networks in the Context of Industry 4.0. Wireless Networks, 23, 23-41. [Google Scholar] [CrossRef] 
[4] Liang, J., Liu, M. and Kui, X. (2014) A Survey of Coverage Problems in Wireless Sensor Networks. Sensors & Transducers, 16, 240-248.
[5] Chaturvedi, P. and Daniel, A.K. (2021) A Comprehensive Review on Scheduling Based Approaches for Target Coverage in Wsn. Wireless Personal Communications, 123, 3147-3199. [Google Scholar] [CrossRef] 
[6] Wang, B. (2011) Coverage Problems in Sensor Networks. ACM Computing Surveys, 43, 1-53. [Google Scholar] [CrossRef] 
[7] Wu, W., Zhang, Z., Lee, W. and Du, D.-Z. (2020) Optimal Coverage in Wireless Sensor Networks, Volume 162 of Springer Optimization and Its Applications. Springer International Publishing.
[8] Somasundara, A.A., Ramamoorthy, A. and Srivastava, M.B. (2007) Mobile Element Scheduling with Dynamic Deadlines. IEEE Transactions on Mobile Computing, 6, 395-410. [Google Scholar] [CrossRef] 
[9] Tan, R., Xing, G., Wang, J., et al. (2010) Exploiting Reactive Mobility for Collaborative Target Detection in Wireless Sensor Networks. IEEE Transactions on Mobile Computing, 9, 317-332. [Google Scholar] [CrossRef] 
[10] Liao, Z., Wang, J., Zhang, S., Cao, J. and Min, G. (2015) Minimizing Movement for Target Coverage and Network Connectivity in Mobile Sensor Networks. IEEE Transactions on Parallel and Distributed Systems, 26, 1971-1983. [Google Scholar] [CrossRef] 
[11] Chen, Z., Gao, X., Wu, F. and Chen, G. (2016) A PTAS to Minimize Mobile Sensor Movement for Target Coverage Problem. IEEE INFOCOM 2016—The 35th Annual IEEE International Conference on Computer Communications, San Francisco, 10-14 April 2016, 1-9. [Google Scholar] [CrossRef] 
[12] Wongwattanakij, N., Phetmak, N., Jaikaeo, C., et al. (2023) An Improved PTAS for Covering Targets with Mobile Sensors. arXiv:2305.03946.
[13] Quan, L.V., Hanh, N.T., Binh, H.T.T., Toan, V.D., Ngoc, D.T. and Lam, B.T. (2023) A Bi-Population Genetic Algorithm Based on Multi-Objective Optimization for a Relocation Scheme with Target Coverage Constraints in Mobile Wireless Sensor Networks. Expert Systems with Applications, 217, Article 119486. [Google Scholar] [CrossRef] 
[14] Jin, J., Ran, Y. and Zhang, Z. (2024) Approximation Algorithms for Maximum Weighted Target Cover Problem with Distance Limitations. Journal of Combinatorial Optimization, 47, Article No. 60. [Google Scholar] [CrossRef] 
[15] Applegate, D.L., Bixby, R.E., Chvátal, V. and Cook, W.J. (2006) The Traveling Salesman Problem: A Computational Study. Princeton University Press.
[16] Perboli, G. and Rosano, M. (2019) Parcel Delivery in Urban Areas: Opportunities and Threats for the Mix of Traditional and Green Business Models. Transportation Research Part C: Emerging Technologies, 99, 19-36. [Google Scholar] [CrossRef] 
[17] Li, Y., Chu, F., Feng, C., Chu, C. and Zhou, M. (2019) Integrated Production Inventory Routing Planning for Intelligent Food Logistics Systems. IEEE Transactions on Intelligent Transportation Systems, 20, 867-878. [Google Scholar] [CrossRef] 
[18] Brouer, B.D., Alvarez, J.F., Plum, C.E.M., Pisinger, D. and Sigurd, M.M. (2014) A Base Integer Programming Model and Benchmark Suite for Liner-Shipping Network Design. Transportation Science, 48, 281-312. [Google Scholar] [CrossRef] 
[19] Golden, B., Bodin, L., Doyle, T. and Stewart, W. (1980) Approximate Traveling Salesman Algorithms. Operations Research, 28, 694-711. [Google Scholar] [CrossRef] 
[20] Mazyavkina, N., Sviridov, S., Ivanov, S. and Burnaev, E. (2021) Reinforcement Learning for Combinatorial Optimization: A Survey. Computers & Operations Research, 134, Article 105400. [Google Scholar] [CrossRef] 
[21] Bello, I., Pham, H., Le, Q.V., Norouzi, M. and Bengio, S. (2016) Neural Combinatorial Optimization with Reinforcement Learning. arXiv:1611.09940.
[22] Barrett, T., Clements, W., Foerster, J. and Lvovsky, A. (2020) Exploratory Combinatorial Optimization with Reinforcement Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 34, 3243-3250. [Google Scholar] [CrossRef] 
[23] Chen, M., Liu, S. and He, W. (2024) Learn to Solve Dominating Set Problem with GNN and Reinforcement Learning. Applied Mathematics and Computation, 474, Article 128717. [Google Scholar] [CrossRef] 
[24] Wang, Q. and Tang, C. (2021) Deep Reinforcement Learning for Transportation Network Combinatorial Optimization: A Survey. Knowledge-Based Systems, 233, Article 107526. [Google Scholar] [CrossRef] 
[25] Wang, D. (2023) Reinforcement Learning for Combinatorial Optimization. In: Wang, J., Ed., Encyclopedia of Data Science and Machine Learning, IGI Global Scientific Publishing, 2857-2871. [Google Scholar] [CrossRef] 
[26] Khalil, E., Dai, H., Zhang, Y., Dilkina, B. and Song, L. (2017) Learning Combinatorial Optimization Algorithms Over graphs. Advances in Neural Information Processing Systems, 30, 6348-6358.
[27] Hu, Y., Yao, Y. and Lee, W.S. (2020) A Reinforcement Learning Approach for Optimizing Multiple Traveling Salesman Problems over Graphs. Knowledge-Based Systems, 204, Article 106244. [Google Scholar] [CrossRef] 
[28] Wang, C., Han, C., Guo, T. and Ding, M. (2022) Solving Uncapacitated P-Median Problem with Reinforcement Learning Assisted by Graph Attention Networks. Applied Intelligence, 53, 2010-2025. [Google Scholar] [CrossRef] 
[29] Guo, W., Xu, Y. and Jin, Y. (2023) Swap-Based Deep Reinforcement Learning for Facility Location Problems in Networks. arXiv:2312.15658.

为你推荐