基于择路因子的警车信息物理融合系统部署调度方法

摘要

本发明给出一种基于择路因子的警车信息物理融合系统部署调度方法，该方法首先初始化信息处理单元，将地图信息进行加工；然后信息处理单元在加工后的地图数据上利用贪心算法部署物理单元最后；信息处理单元引入择路因子调度物理单元。该方法通过贪心算法部署警车，在警车巡逻过程中引入择路因子，以保证警车在均匀分布的基础上有着较高的见警率，使警车在巡逻过程中能更广泛地震慑到犯罪分子，同时，择路因子的引入还能使警车的巡逻规律具有一定的隐蔽性(不可预见性)。

说明书

技术领域

本发明涉及一种基于择路因子的警车信息物理融合系统部署调度方法，主要用于解决智 能交通系统中警车均匀分布和提高城市道路中见警率的问题，属于信息物理融合系统和智能 交通系统的交叉技术应用领域。

背景技术

信息物理融合系统被认为是继计算机、互联网之后世界信息技术的第三次浪潮。信息物 理融合系统可以理解为基于嵌入式设备的高效网络化智能信息系统，是具有高度自主感知、 自主判断、自主调节和自治能力，能够实现虚拟世界和现实物理世界互联与协同的下一代智 能系统。信息物理融合系统在功能上主要考虑性能优化，是集计算(Computation)、通信 (Communication)与控制(Control)3C于一体的智能技术。现在，信息物理融合系统技术 已经得到了国际工商业界和许多大型国际公司的高度关注，发展速度极为迅速，已被应用于 交通、医疗、能源等多个重要发展领域，具有广阔的应用前景。

智能交通系统是一种典型的信息物理融合系统，它将先进的信息技术、数据通讯传输技 术、电子传感技术、控制技术及计算机技术等有效地集成运用于整个地面交通管理系统而建 立的一种在大范围内、全方位发挥作用的，实时、准确、高效的综合交通运输管理系统。ITS (Intelligent Transportation System)可以有效地利用现有交通设施、减少交通负荷和环境污染、 保证交通安全、提高运输效率，因而，日益受到各国的重视。21世纪将是公路交通智能化的 世纪，人们将要采用的智能交通系统，是一种先进的一体化交通综合管理系统。在该方法中， 车辆靠自己的智能在道路上自由行驶，公路靠自身的智能将交通流量调整至最佳状态，借助 于这个系统，管理人员可以掌握对道路、车辆行踪等情况。

警车部署调度系统是智能交通系统的一种典型应用，智能化的警车部署调度系统将充分 利用有限的警力资源，使配备有GPS(Global Positioning System)卫星定位系统及先进通讯 设备的警车在所辖范围内按照优化的方案进行巡逻，加快了接处警(接受报警并赶往现场处 理事件)时间，提高了反应时间，使警车以较高的频率(见警率)出现在市区内的各个区域， 在一定程度上对违法犯罪分子起到震慑作用，减少潜在案件的发生，增加市民的安全感，为 社会和谐提供了有力的保障。

贪心算法(又称贪婪算法)是指，在对问题求解时，总是做出在当前看来是最好的选择。 也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。用贪心 算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作为最优选择，而不 考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它 采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为 一个规模更小的子问题，通过每一步贪心选择，贪心算法能对范围相当广泛的许多问题产生 整体最优解或者是整体最优解的近似解。

择路因子是在警车巡逻调度过程中为了提高其在市区内的各个区域出现的频率(见警率) 而引入的一个参数。择路因子是一个整型数组，市区内的每条路段对应一个数组元素。各条 路段上每当有警车经过时，对应该路段的择路因子就加1，而当警车巡逻到达交叉路口时， 就通过判断该交叉路口上各路段择路因子的大小，进入择路因子值较小的路段。择路因子的 引入能够保证在警车均匀分布的基础上有着较高的见警率，使警车在巡逻过程中能更广泛地 震慑到犯罪分子，减少潜在案件的发生，增加市民的安全感。

随着信息物理融合系统的提出和智能交通技术的迅速发展，警车部署调度系统引起了多 领域专家的关注，提出了很多新颖的方法。总的来看，有两类基本思路：第一种思路就是固 定分区，按照警车在接警后三分钟内赶到现场的比例不低于90％的要求作区域划分，每个区 域固定一辆警车巡逻；另一种思路则是动态分区，按各警车的接处警能力来划分区域，在调 度过程中保证警车均匀分布。

发明内容

技术问题：本发明的目的是提供一种基于择路因子的警车信息物理融合系统部署调度方 法，该方法通过贪心算法部署警车，在警车巡逻过程中引入择路因子，以保证警车在均匀分 布的基础上有着较高的见警率，使警车在巡逻过程中能更广泛地震慑到犯罪分子，同时，择 路因子的引入还能使警车的巡逻规律具有一定的隐蔽性(不可预见性)。

技术方案：本发明所述的基于择路因子的警车信息物理融合系统部署调度方法，通过贪 心算法来部署警车，参考择路因子来调度警车。本发明以警车所能覆盖的路段总长为贪心准 则来部署车辆，使警车能够尽可能的均匀分布；警车调度过程中选择择路因子最小的路段作 为巡逻的目标路段。

本发明所述的信息物理融合系统由若干物理单元(这里指警车)和一个信息处理单元(这 里指警车部署调度系统)组成，其中所述的物理单元接收来自信息处理单元的位置和方向数 据，并向信息处理单元反馈当前的位置和方向作为确认；所述信息处理单元(这里指警车部 署调度系统)用于接收并存储物理单元发送的确认数据，并对这些数据进行分析和处理，向 物理单元发送控制数据。

基于择路因子的警车信息物理融合系统部署调度方法的实现包括以下步骤：

步骤1)将用户提供的城市地图中长度不一的原始路段进行等距划分(划分间距由用户 指定)，计算所有交叉路口与交叉路口、交叉路口与划分点、划分点与划分点间的最短距离得 最短距离表；

步骤2)由警车速度和用户要求的处警时间得警车的处警半径，依据步骤1)得到的最短 距离表，以用户指定的重点位置为中心划分重点区域；

步骤3)依次在用户指定的重点位置部署警车，具体步骤如下：

步骤3.1)信息处理单元将位置和方向信息发送给物理单元，在重点位置部署一个物 理单元；

步骤3.2)物理单元将位置和方向信息反馈给信息处理单元；

步骤3.3)信息处理单元计算物理单元所能覆盖到的交叉路口和划分点个数，并标记 这些能被覆盖到的交叉路口和划分点；

步骤3.4)信息处理单元计算当前被物理单元覆盖的交叉路口和划分点的总数；

步骤3.5)物理单元数加1；

步骤4)在普通区域用贪心算法部署警车。具体步骤如下：

步骤4.1)信息处理单元遍历所有未被覆盖的交叉路口和划分点，计算以当前交叉路 口/划分点为中心，以处警能力为半径所能覆盖到的交叉路口/划分点的总数，将覆盖总数最多 的中心点作为物理单元的部署点；

步骤4.2)信息处理单元将位置和方向信息发送给物理单元；

步骤4.3)物理单元将位置和方向信息反馈给信息处理单元；

步骤4.4)信息处理单元计算当前被覆盖交叉路口和划分点的总数；

步骤4.5)物理单元数加1；

步骤5)判断当前交叉路口和划分点覆盖率是否达到用户指定的覆盖率，若覆盖率小于 用户指定的覆盖率，则返回到步骤4)，再部署一辆新的警车。所述覆盖率是指已被物理单元 覆盖的交叉路口和划分点数与所有路口和划分点总数之比；

步骤6)信息处理单元依次判断各物理单元当前所处位置是否是交叉路口。若是，则选 取择路因子最小的路段作为前进方向，计算下一时刻的位置；若不是，则直接计算下一时刻 的位置；

步骤7)信息处理单元将位置和方向信息发送给物理单元；

步骤8)物理单元将位置和方向信息反馈给信息处理单元；

步骤9)判断当前交叉口覆盖率是否能达到用户指定的覆盖率，若不是，则返回到步骤4)， 再部署一辆新的警车；

步骤10)判断累计稳定运行时间是否大于用户指定的警察换班时间；若不是，则返回到 步骤7)。

有益效果：本发明所述的基于择路因子的警车信息物理融合系统部署调度方法，通过贪 心算法来部署警车，参考择路因子来调度警车。本发明以警车所能覆盖的路段总长(最长) 为贪心准则来部署车辆，使警车能够尽可能的均匀分布；警车调度过程中选择择路因子最小 的路段作为巡逻的目标路段。

(1)以警车所能覆盖的路段总长(最长)为贪心准则来部署车辆，使警车能够尽可能的 均匀分布；

(2)警车调度过程中选择择路因子最小的路段作为巡逻的目标路段，平衡了城市道路中 见警率；

(3)择路因子的引入，加上原始路段长度的差异性，使警车的巡逻规律具有了一定的隐 蔽性；

(4)择路因子设置简单，计算快捷，系统代价小；

(5)复杂计算都放在步骤1信息处理单元初始化中，系统实时性好；

(6)系统采用了模块化的设计思想，有着较好的可扩展性和可维护性。

附图说明

图1是基于择路因子的警车信息物理融合系统部署调度方法模型图，

图2是实例部分地图，

图3是基于择路因子的警车信息物理融合系统部署调度方法流程图。

具体实施方式

本发明所述的基于择路因子的警车信息物理融合系统部署调度方法，通过贪心算法来部 署警车，参考择路因子来调度警车。本发明以警车所能覆盖的路段总长(最长)为贪心准则 来部署车辆，使警车能够尽可能的均匀分布；警车调度过程中选择择路因子最小的路段作为 巡逻的目标路段。

本发明所述的信息物理融合系统由苦干物理单元和一个信息处理单元组成，其中所述的 物理单元即警车，用于接收位置和方向这样的控制数据，并当前的位置和方向数据作为确认； 所述信息处理单元即警车部署调度系统，用于接收并存储物理单元发送的确认数据，并对这 些数据进行分析和处理，向物理单元发送控制数据。

基于择路因子的警车信息物理融合系统部署调度方法的实现包括以下步骤：

1、将用户提供的城市地图中长度不一的原始路段进行等距划分(划分间距由用户指定)， 计算所有交叉路口与交叉路口、交叉路口与划分点、划分点与划分点间的最短距离得最短距 离表；

2、由警车速度和用户要求的处警时间得警车的处警半径，依据步骤1)得到的最短距离 表，以用户指定的重点位置为中心划分重点区域；

3、依次在用户指定的重点位置部署警车。具体步骤如下：

3.1、信息处理单元将位置和方向信息发送给物理单元，在重点位置部署一个物理单 元；

3.2、物理单元将位置和方向信息反馈给信息处理单元；

3.3、信息处理单元计算物理单元所能覆盖到的交叉路口和划分点个数，并标记这些 能被覆盖到的交叉路口和划分点；

3.4、信息处理单元计算当前被物理单元覆盖的交叉路口和划分点的总数；

3.5、物理单元数加1；

4、在普通区域用贪心算法部署警车。具体步骤如下：

4.1、信息处理单元遍历所有未被覆盖的交叉路口和划分点，计算以当前交叉路口/划 分点为中心，以处警能力为半径所能覆盖到的交叉路口/划分点的总数，将覆盖总数最多的中 心点作为物理单元的部署点；

4.2、信息处理单元将位置和方向信息发送给物理单元；

4.3、物理单元将位置和方向信息反馈给信息处理单元；

4.4、信息处理单元计算当前被覆盖交叉路口和划分点的总数；

4.5、物理单元数加1；

5、判断当前交叉路口和划分点覆盖率是否达到90％，若覆盖率小于90％，则返回到步 骤4)，再部署一辆新的警车。其中，覆盖率是指已被物理单元覆盖的交叉路口和划分点数与 所有路口和划分点总数之比，90％的覆盖率由用户指定；

6、信息处理单元依次判断各物理单元当前所处位置是否是交叉路口。若是，则选取择路 因子最小的路段作为前进方向，计算下一时刻的位置；若不是，则直接计算下一时刻的位置；

7、信息处理单元将位置和方向信息发送给物理单元；

8、物理单元将位置和方向信息反馈给信息处理单元；

9、判断当前交叉口覆盖率是否能达到90％，若不是，则返回到步骤4)，再部署一辆新 的警车；

10、判断累计稳定运行时间是否大于4小时(4小时为警察换班时间，由用户指定)。若 不是，则返回到步骤7)。