基于时间切片叠加的警车巡逻路线规划  

Routine-design for Police Wagons’ Patrol Based on Time-slices Overlay Algorithm

作　　者：汪淼[1] 徐海洋[2] 杜睿[2] 

机构地区：[1]国防科学技术大学计算机学院,湖南长沙410073 [2]国防科学技术大学光电工程学院,湖南长沙410073

出　　处：《数学的实践与认识》2010年第15期201-207,共7页Mathematics in Practice and Theory

基　　金：国防科技大学数学建模创新实践基地学员创新基金

摘　　要：在城市中，有效的安排警车巡逻对于降低犯罪率，预防潜在犯罪案件发生和及时处理案件具有十分重要的意义．通过一些必要简化首先确定了巡逻方案应当满足的条件以及方案的评价体系．通过随机贪心算法求解足够多的可行静态解，并引入时间片叠加的思想在静态解的基础上应用深度优先搜索算法，将求解动态巡逻问题转化为在有向连通图中寻找使目标函数达到最大的约束环路的问题，最终求得动态巡逻方案．最后，通过实例对模型进行了验证和评价．To design police wagons＇ patrol routine effectively in the city is meaningful for reducing crimes, preventing potential crimes and dealing with the cases in time. The paper firstly determines the conditions that the patrol routine should satisfy and defines an evaluation system for the solution. A sufficient number of feasible static solutions can be got by random greedy algorithm and based on that we introduce time-slices overlay algorithm to find out the dynamic solution applying DFS. The time-slices overlay algorithm changes the problem into finding out a constrained circle which will maximize the objective function in a directed graph. At last, the model is tested and evaluated through an example.

关 键 词：时间切片叠加 静态解 动态解 警车巡逻 

分 类 号：O224[理学—运筹学与控制论]