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

吴思远

doi:10.16088/j.issn.1001-6600.2010.01.034

广西师范大学学报（自然科学版） ›› 2010, Vol. 28 ›› Issue (01) : 96 -99. DOI: 10.16088/j.issn.1001-6600.2010.01.034

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

吴思远

作者信息 +

Author information +

文章历史 +

PDF

摘要

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