基于特征区域划分的巡逻配置及选址方法研究.docx

基于特征区域划分的巡逻配置及选址方法研究

摘?要：为提高目标区域的巡逻效率，文章提出一种基于路网特征下区域划分的巡逻配置及选址方法。首先，定量分析研究区域路网密度，并基于中心度评价指标量化路网布局结构，实现研究区域划分；然后以总区域巡逻覆盖率为约束，构建以最优巡逻车数量配置为目标的规划模型；最后基于选址贪心算法求解并得出子区域覆盖率及巡逻车配置数量。结果显示，巡逻覆盖率与子区域路网等级和巡逻车速度提高带来的收益呈正相关关系。该方法可为巡逻配置及选址问题的解决提供有效途径。

关键词：路网中心度；路网密度；区域划分；巡逻车配置；贪心算法

0?引?言

巡逻部署是一种在指定区域内进行巡逻安排[1]，并考察最大覆盖率及巡逻路线问题[2]的调度布置，其广泛应用于高速公路[3]、飞机航线[4]和工业园区[5]等重要区域。巡逻部署有影响因素多、区域复杂的特点，相关研究也主要从这两方面开展。如，学者提出的基于多种因素权重的巡逻综合评价模型[6]，实现了对多目标的定量研究，但精确获取权重的难度较大；部分研究人员进一步针对“安全性需求、暴露时间、热点地区”等因素对巡逻配置问题的研究[7]，发现安全性需求对巡逻资源分配的影响比重最高。此外，为探究投诉数量与巡逻资源之间的潜在关系，LauH等[8]基于遗传算法使用线性回归方法进行研究，确定增加巡逻部署是降低投诉的关键；Chelst通过整数线性规划建立最优投诉导向巡逻模型[9]为高风险地区分配固定巡逻车，该方法实现了目标区域优化的效果，但也导致巡逻布置严重不均；Chaiken等基于有哪些信誉好的足球投注网站算法提出程序化巡逻分配模式（PCAM），在满足巡逻诉求的同时确定最小巡逻车数，并且处理重复巡逻和巡逻车辆分布不均的问题[10]。也有学者基于犯罪案件的空间聚集性[11]、区域类型属性[12]以及各类型空间格局之间共同性与差异性[13]，探讨了警车巡逻配置的问题。此外，还有学者提出全覆盖路径规划问题（CCPP）[14]，即从全路径路覆盖角度出发，基于旅行商问题的遗传算法（GA）和蚁群优化算法（ACO）进行优化。

上述针对巡逻部署问题的研究已取得不少成果，但仍存在仅重视单目标优化而忽视实际情况复杂性的弊端。因此本文提出一种基于路网特征下区域划分的巡逻配置及选址的方法。基于总区域巡逻覆盖率约束，建立以最优巡逻车配置为目标的规划模型，并采用基于巡逻车选址的贪心算法进行求解，多方面考察子区域覆盖率及巡逻车配置数量的效果，来提高区域的巡逻效率。

1?基于特征区域划分的配置及选址方法

本文提出基于特征区域划分的配置及选址方法流程如图1所示。

首先对研究区域网络道路进行分析，分别根据路网密度和中心度指标量化路网布局结构后，依据路网布局结构差异进行区域划分；然后依据节点-弧段模型进行路网拓扑信息分析，建立路网数据模型，并以总区域巡逻车覆盖率为约束构建以最优巡逻车数量配置为目标的规划模型；最后使用基于巡逻车选址的贪心算法对模型求解并得出子区域覆盖率及配置情况。

1.1?基于路网中心度的评价指标方法

本文基于多中心性评价中的邻近度、中间性和直达性测度道路交通网络中心性，提炼出度数中心度和中间中心度对路网布局结构进行度量。度数中心度C表达如下：

C=X????????????????????????????????????????????????（1）

其中：表示与点A直接相连的其他点个数。

中间中心度测度节点对于网络的整体控制程度，其表达式如下：

C=bi?????????????????????????????????????????????（2）

其中：bi=gi/g;C为节点i的中间中心度；bi为节点i处于节点j和k之间的最短路径上的概率；gi为节点j和k之间存在的经过节点i的最短数目；g为节点j和节k之间存在的最短路径数目。

1.2?巡逻车配置目标规划模型

1.2.1?路网数据模型构建

采用有向图表述道路网络，以结点-弧段模型[15]为基础，建立面向巡逻建模需求的路网数据模型。本文提及的结点主要为拓扑结点，即由道路相交而产生的结点、或道路的起点及终点。路网数据模型里包含以下信息：（1）结点及邻近结点集用来确定相交弧段；（2）弧段的长度用于计算距离。

1.2.2?车辆巡逻配置建模

在路网数据模型基础上，模型满足以下约束：（1）巡逻车辆于三分钟内可覆盖不小于0.9倍的路网总长。（2）在两分钟内满足对重点部位路段的全覆盖。基于上述两个约束条件并考虑最少车辆数量配置作为目标函数。为满足巡逻约束条件（1），构建目标规划模型如下：

fG，N，t=≥0.9，i=1，2，…，N?????????????????????????（3）

式中：N为给定车辆数；G为规定路网；∑L为给定路网G的总长度；fG，N，t为t时刻整个路网被巡