广西师范大学学报（自然科学版） ›› 2010, Vol. 28 ›› Issue (1): 96-99.

• • 上一篇    下一篇

全局最优警车巡逻区域最大覆盖调度策略

吴思远   

  1. 重庆邮电大学计算机科学与技术学院,重庆 400065
  • 收稿日期:2009-12-20 出版日期:2010-03-20 发布日期:2023-02-07
  • 通讯作者: 吴思远(1974—),男,湖北汉阳人,重庆邮电大学讲师,硕士。E-mail:wusy@cqupt.edu.cn
  • 基金资助:
    重庆市自然科学基金资助项目(2006BB2374);重庆邮电大学自然科学基金资助项目(A2009-35)

Global Optimum Maximal Coverage Scheduling Strategy for Police Patrol Cars Deployment

WU Si-yuan   

  1. College of Computer Science and Technology,Chongqing University of Posts and Telecommunications, Chongqing 400065,China
  • Received:2009-12-20 Online:2010-03-20 Published:2023-02-07

摘要： 针对警车的配置和巡逻区域覆盖问题,通过引入k-means聚类算法、最小顶点覆盖和遗传算法等,提出一种警车优化配置和全局最优的巡逻区域最大覆盖调度方案。利用k-means聚类算法生成的N个中心点作为警车初始位置的参考点,完成警车初始化配置。接着采用遗传算法优化选取出全局最优的巡逻参考路线,进而引入Dijkstra算法计算出满足要求的巡逻部署线路,同时给出了任意两个交叉路口间的最短路径和警车在某一时刻所在位置的计算方法,以及警车巡逻的区域覆盖率和行车时间。通过详细的模拟实验验证了其有效性,实验结果表明该方案优化选取得到的巡逻路线具有较好的鲁棒性,可有效提高巡逻效果的显著性,且巡逻路线保持多变,具有较好的隐蔽性。

关键词: 区域覆盖, k-means聚类, 调度, Dijkstra算法, 遗传算法

Abstract: By introducing the ideas of k-means clustering,genetic algorithm andminimum vertex cover,a global optimal police patrol car configuration and deployment for the department of traffic police is proposed.In this setting,k-meansclustering is used to generate N center points based on the density of the intersections and completed the police patrol car initialization configuration.Thenthe genetic algorithm is adopted to receive a global optimal patrol route as reference and finally the Dijkstra algorithm is employed to calculate the patrol deployment routes.Meanwhile,the calculation methods of the shortest path is given between any two intersections and the location of police cars at anymoments,as well as regional coverage and travel time of the N police patrol cars.Toverify its validity,sensitivity analysis on the budget,the number of patrol cars is performed to identify the possible solutions.Experimental results show this method is robust and can effectively improve the effectiveness of patrol deployment and the routes kept varied with good property of concealment.

Key words: regional coverage, k-means algorithm, scheduling, Dijkstra algorithm, genetic algorithm

中图分类号: 

  • TP301.6
[1] DINESH K S,DEBASIS G,AVINASH G.Lexicographic goal programming model for police patrol cars deployment in metropolitan cities[J].Information andManagement Sciences,2007,18(2):173-188.
[2] ARTHUR D,VASSILV S.How slow is the k-means method?[C]//Proceedings of the 2006 Symposium on Computational Geometry (SoCG).New York:ACM Press,2006:144-153.
[3] SCHMIT T,LOTHAR M.Theory of genetic algorithms Ⅱ:models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling[J].Theoretical Computer Science,2004,310:181-231.
[4] THOMAS H C,CHARLES E L,RONALD L R,et al.Introduction to algorithms[M].2nd ed.Cambridge,MA:MIT Press and McGraw-Hill,2001:595-601.
[5] YARUSHKINA N G.Genetic algorithms for engineering optimization:theory and practice[C]//Proceedings of the 2002 IEEE International Conference onArtificial Intelligence Systems.Washington,DC:IEEE Computer Society,2002:407-410.
[1] 肖飞, 康增彦, 王维红. 两种算法用于预测A2/O工艺脱氮条件[J]. 广西师范大学学报（自然科学版）, 2022, 40(6): 173-184.
[2] 朱恩文, 朱安麒, 王洁丹, 刘玉娇. 基于EEMD-GA-BP模型的风电功率短期预测研究[J]. 广西师范大学学报（自然科学版）, 2022, 40(1): 166-174.
[3] 胡竣涛, 时小虎, 马德印. 基于均值漂移和遗传算法的护工调度算法[J]. 广西师范大学学报（自然科学版）, 2021, 39(3): 27-39.
[4] 许伦辉, 曹宇超, 林培群. 基于融合免疫优化和遗传算法的多应急物资中心选址与调度[J]. 广西师范大学学报（自然科学版）, 2020, 38(6): 1-13.
[5] 包剑飞, 张杜鹃. 旅游产业与区域经济耦合协调度研究——以长江三角洲城市群为例[J]. 广西师范大学学报（自然科学版）, 2020, 38(3): 117-127.
[6] 叶青, 黄强, 聂斌, 李欢. 一种自适应的高维离群点识别方法[J]. 广西师范大学学报（自然科学版）, 2020, 38(2): 107-114.
[7] 许伦辉,尹诗德,刘易家. 基于模拟退火的自适应布谷鸟算法求解公交调度问题[J]. 广西师范大学学报（自然科学版）, 2018, 36(2): 1-7.
[8] 梁晓萍,罗晓曙. 基于遗传自适应的维纳滤波图像去模糊算法[J]. 广西师范大学学报（自然科学版）, 2017, 35(4): 17-23.
[9] 周秀丹, 胡志华, 魏晨. 自动化集装箱码头成组直接中转的岸桥作业调度[J]. 广西师范大学学报（自然科学版）, 2016, 34(2): 81-89.
[10] 刘伟铭, 李荣荣, 王超, 黄玲. 高速公路通行卡调拨问题的遗传算法[J]. 广西师范大学学报（自然科学版）, 2016, 34(1): 1-8.
[11] 刘宏, 王其涛, 夏未君. 基于量子遗传算法的WSN三维定位方法[J]. 广西师范大学学报（自然科学版）, 2015, 33(4): 49-54.
[12] 乐美龙, 高金敏. 轮辐式航线网络下机型分配与舱位控制的协同优化研究[J]. 广西师范大学学报（自然科学版）, 2014, 32(3): 33-40.
[13] 赵新超, 吴召军. 求解背包问题的多位极贪婪遗传算法[J]. 广西师范大学学报（自然科学版）, 2013, 31(4): 41-47.
[14] 曹永春, 邵亚斌, 田双亮, 蔡正琦. 一种基于免疫遗传算法的聚类方法[J]. 广西师范大学学报（自然科学版）, 2013, 31(3): 59-64.
[15] 蒋晓峰, 许伦辉, 朱悦. 基于SVM短时交通流量预测[J]. 广西师范大学学报（自然科学版）, 2012, 30(4): 13-17.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 陈永淇, 白克钊, 邝华, 孔令江, 刘慕仁. 教室内布局对人员疏散影响的研究[J]. 广西师范大学学报（自然科学版）, 2011, 29(1): 1 -4 .
[2] 许伦辉, 叶凡. 基于横、轴、竖加速度干扰模型的行车舒适性评价[J]. 广西师范大学学报（自然科学版）, 2011, 29(1): 5 -9 .
[3] 阳丽, 孔令江. 微纳米球形颗粒之间的毛细力研究[J]. 广西师范大学学报（自然科学版）, 2012, 30(1): 1 -4 .
[4] 贺青, 刘剑, 韦联福. 微弱电磁信号的物理极限检测:单光子探测器及其研究进展[J]. 广西师范大学学报（自然科学版）, 2022, 40(5): 1 -23 .
[5] 白克钊, 罗旭东, 孔令江, 刘慕仁. 开放边界条件下一种数据传输元胞自动机模型[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 1 -4 .
[6] 许伦辉, 廖燃火昆. 基于车流轨迹的交叉口相位相序优化[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 5 -9 .
[7] 王修信, 秦丽梅, 农京辉, 梁宗经, 朱启疆. 利用单窗算法反演喀斯特城市地表温度[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 10 -14 .
[8] 黎玉芳, 张军舰. NA样本回归函数估计的强相合性[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 15 -19 .
[9] 贾保华. 一个不满足中心极限定理的严平稳相伴随机序列[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 20 -23 .
[10] 陈翠玲, 李明, 梁家梅, 李略. Wolfe线搜索下一类新的共轭梯度法及其收敛性[J]. 广西师范大学学报（自然科学版）, 2010, 28(3): 24 -28 .
版权所有 © 广西师范大学学报（自然科学版）编辑部
地址：广西桂林市三里店育才路15号　邮编：541004
电话：0773-5857325　E-mail: gxsdzkb@mailbox.gxnu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发