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

Global Optimum Maximal Coverage Scheduling Strategy for Police Patrol Cars Deployment

作　　者：吴思远[1] 

机构地区：[1]重庆邮电大学计算机科学与技术学院,重庆400065

出　　处：《广西师范大学学报（自然科学版）》2010年第1期96-99,共4页Journal of Guangxi Normal University:Natural Science Edition

基　　金：重庆市自然科学基金资助项目(2006BB2374);重庆邮电大学自然科学基金资助项目(A2009-35)

摘　　要：针对警车的配置和巡逻区域覆盖问题,通过引入k-means聚类算法、最小顶点覆盖和遗传算法等,提出一种警车优化配置和全局最优的巡逻区域最大覆盖调度方案。利用k-means聚类算法生成的N个中心点作为警车初始位置的参考点,完成警车初始化配置。接着采用遗传算法优化选取出全局最优的巡逻参考路线,进而引入Dijkstra算法计算出满足要求的巡逻部署线路,同时给出了任意两个交叉路口间的最短路径和警车在某一时刻所在位置的计算方法,以及警车巡逻的区域覆盖率和行车时间。通过详细的模拟实验验证了其有效性,实验结果表明该方案优化选取得到的巡逻路线具有较好的鲁棒性,可有效提高巡逻效果的显著性,且巡逻路线保持多变,具有较好的隐蔽性。By introducing the ideas of k-means clustering,genetic algorithm and minimum vertex cover,a global optimal police patrol car configuration and deployment for the department of traffic police is proposed. In this setting,k-means clustering is used to generate N center points based on the density of the intersections and completed the police patrol ear initialization configuration. Then the 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 any moments ,as well as regional coverage and travel time of the N police patrol cars. To verify 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.

关 键 词：区域覆盖 K-MEANS聚类 调度Dijkstra算法 遗传算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]