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

王小霞 林俊杉 伍兆榔 王海波

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

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

中图分类号：F502    文献标志码：A

DOI：10.13714/j.cnki.1002-3100.2024.13.003

Abstract： This article presented a patrol configuration and location method based on the regional division under the characteristics of the road network to improve the efficiency of patrols in the target area. The author quantitatively analyzed the road network density of the research area and quantified the layout structure of the road network based on the centrality evaluation index to achieve the division of the research area. Then， a planning model was constructed with the optimal number of patrol vehicles as the target and the total area patrol coverage rate as the constraint. Finally， the author used a location greedy algorithm to solve and obtain the sub-area coverage rate and the number of patrol vehicle configurations. The results show that the patrol coverage rate is positively correlated with the benefits brought by the improvement of the sub-area road network level and patrol vehicle speed. This method provides an effective way to solve the problem of patrol configuration and location.

Key words： road network centrality; road network density; regional division; patrol car configuration; greedy algorithm

0  引  言

巡逻部署是一种在指定区域内进行巡逻安排[1]，并考察最大覆盖率及巡逻路线问题[2]的调度布置，其广泛应用于高速公路[3]、飞机航线[4]和工业园区[5]等重要区域。巡逻部署有影响因素多、区域复杂的特点，相关研究也主要从这两方面开展。如，学者提出的基于多种因素权重的巡逻综合评价模型[6]，实现了对多目标的定量研究，但精确获取权重的难度较大；部分研究人员进一步针对“安全性需求、暴露时间、热点地区”等因素对巡逻配置问题的研究[7]，发现安全性需求对巡逻资源分配的影响比重最高。此外，为探究投诉数量与巡逻资源之间的潜在关系，Lau H等[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时刻整个路网被巡逻车辆覆盖到的路段总长度；CvgG，i，t为给定路网G在t时刻第i辆巡逻车覆盖范围内路段长度，如式（4）所示：

CvgG，i，t=fG，xt，yt，T，t                                     （4）

OvpG，i，t在给定路网G中，在t时刻，第i辆巡逻车与其它巡逻车覆盖范围的重叠路段长度，如式（5）所示：

OvpG，i，t=fCvgG，i，t，CvgG，j，t                                 （5）

式中：fCvg，Cvg表示任意两辆巡逻车覆盖范围重叠部分的路段长度。另外在对约束条件（2）配置方案构建如下：

MinDisG，xt，yt，X，Y≤vT                                     （6）

式中：DisG，xt，yt，X，Y为在给定路网G中，在t时刻，在位置xt，yt的第i辆巡逻车距离第j个重点部位位置X，Y的距离；v表示巡逻车辆出行速度，T表示规定时间2min。

1.3  基于巡逻车选址的贪心算法

假设巡逻路线的起点均位于结点上，采用贪心算法不断从未被巡逻车覆盖的结点中，依次选取较优点作为巡逻车的起始点。同时，把该巡逻车于指定时间T内可达的结点和路段的状态标注为已被覆盖。该算法用于每新增一辆巡逻车时确定该巡逻车的初始位置。算法具体为创建用于临时存放区域内未被覆盖结点的三级结点集V、V、V，运算过程如图2所示，未被覆盖的结点筛选并存放在三级结点。

筛选原则：优先筛选满足度数dv>2的结点进入一级结点集V，且在该点分配巡逻车后，新增的覆盖范围与原有覆盖范围的重叠部分比例小于0.6；其次满足度数1

2  实例研究

2.1  研究区域

本文选取的某大型产业园区，区域面积约为28.9km2，所包含的道路总长度约为76.6km，如图3所示。其大部分区域的交通网络基本形式为方格网式，交通网络呈自由式分布，整个园区道路网密度为约2.65km/km2。

2.2  区域划分

2.2.1  路网布局结构分析

研究区域按路网密度差异分布大致划分为三个部分。各分区所占面积、路网长度和密度，如表1所示。

十字交叉口越多的区域（即度数等于4的节点），路网的连接性能越好。对交叉口度数统计如表2所示，在该园区路网共231个交叉口节点中，低度数（小于4）及高度数（大于等于4）节点分别为165个（71.4%）和66个（28.6%）。从度数节点分布情况看，高度数节点在园区中呈局部集中分布的状态。其中度数大于4的节点均分布在主园区，这也影响了该区域的整体中间中心度水平。相反由于东部地区和西南角路网分布节点连接能力差，导致道路网的中间中心度为仅2.98。

2.2.2  基于路网布局结构的区域划分

根据不同节点中心度分布区域特征，依据园区布局中密度高且度数大于4的节点作为对象选取了三个重点部位，如图4黑点所示。综合考虑路网密度、中心度和路网布局结构呈局部枢纽性的特点，把整个园区分为四个子区域。其中区域二和区域三分别为路网布局结构等级最低和次低的子区域；区域四为路网等级次高；区域一为整个园区核心，道路网络密度和中心度最大，为路网布局结构等级最高的子区域。

2.2.3  模型求解及分析

采用基于选址改进的贪心算法对目标规划模型进行求解。结果显示，当巡逻车速为30km/h时，覆盖及配置情况如图5所示。粗线段部分为巡逻车三分钟内覆盖道路，覆盖率90%以上，同时也满足两分钟内到达重点部位的约束条件。与传统方法相比，该方法未产生巡逻不均的问题，同时模型考虑减少重复覆盖率，最大程度避免巡逻资源的浪费。

为了研究不同速度下各子区域覆盖率及巡逻车配置变化情况，设置不同巡逻速度如表3所示。对比数据发现巡逻车平均速度从30km/h提高到40km/h时，巡逻车最小配置数量从14辆减少到10辆，节约了28.6%的巡逻车资源，同时整体覆盖率增加1.0%；在巡逻车速提高33.3%的情况下，区域二和区域三巡逻车数量最低配置数量只减少一辆，这是由于该地区路网通达性较差，路网密度低，导致提高巡逻车速对增加路网覆盖率效果不明显；对比区域一和区域四，巡逻提速33%，巡逻车最低数量配置从7辆减少到4辆，节约42.8%巡逻车资源。对比发现路网等级高的地区节省巡逻车资源的效果更显著。

如表3和图6所示，巡逻平均速度设为30km/h的情况下，区域一和区域四覆盖率较高，分别为98.2%和95.6%；区域二和区域三覆盖率略低，分别为83.8%和85.4%；子区域覆盖率从小到大排序为：区域二、区域三、区域四、区域一，各子区域路网等级也依次逐级升高。同样的情况也出现在平均速度为40km/h的情况下。这表明各区域巡逻覆盖率受路网布局结构等级影响：区域路网等级差异程度与覆盖率差异相关，即路网等级差异较大的子区域覆盖率相差较大；路网布局结构等级较高的区域巡逻覆盖率明显更高。这是由于区域中心度高导致通达性更好，在规定时间内巡逻车到达区域更广。

3  结  论

本文提出一种基于路网特征划分的巡逻车配置选址方法。首先定量分析了区域路网密度，并提出以中心度评价指标量化路网布局结构，综合划分出重点部位和路网等级差异的四个子区域；然后以总区域覆盖率为约束，以巡逻车配置数量为优化目标，并基于对路网数据分析建立目标规划模型；最后基于巡逻车选址改进的贪心算法求解并得出各子区域覆盖率及巡逻车配置数量。结果显示，在满足约束条件的前提下，路网等级较高的区域一和区域四巡逻覆盖率要高出路网等级较低的区域二和区域三约12个百分点；且就提速带来的效益，路网等级高的区域要比等级低的区域收益更高。

参考文献：

[1]  SAMANTA S， SEN G， GHOSH S K. A literature review on police patrolling problems[J]. Annals of Operations Research， 2022，316：1063-1106.

[2]  KESKIN B B， STEIL D， SPILLER S. Analysis of an integrated maximum covering and patrol routing problem[J]. Transportation Research Part E Logistics and Transportation Review， 2012，48（1）：215-232.

[3] 项芮，朱默宁，徐丽. 多无人机高速公路巡逻任务规划方法[J]. 无线电工程，2022，52（7）：1222-1230.

[4] 毛杰，张昊，李海燕. 基于Lazy Theta*算法的反潜巡逻飞机航路规划研究[J]. 舰船电子工程，2020，40（12）：40-43，47.

[5] 吕淑贤，黄锰钢，崔真源. 基于建筑空间模型的大型工业园区内保安巡逻系统研究[J]. 土木建筑工程信息技术，2011，3（1）：6-12.

[6]  WILSON O W. Wilson police planning[M]. 2nd ed. Charles C： Thomas Publisher， 1958.

[7]  CARR H R. Developing a robust resource allocation formulae for police[J]. Policing and Society： An International Journal， 2000，10（3）：235-261.

[8]  LAU H， HO G， YI Z， et al. Optimizing patrol force deployment using a genetic algorithm[J]. Expert Systems with Applications， 2010，37（12）：8148-8154.

[9]  CHELST K. An algorithm for deploying a crime directed （tactical） patrol force[J]. Management Science， 1978， 24（12）：1314-1327. [10]  DORMONT P， CHAIKEN J M. A patrol car allocation model： Capabilities and algorithms[J]. Management Science， 1978，24（12）：1291-1300.

[11]  FENIMORE D M. Mapping harmspots： An exploration of the spatial distribution of crime harm[J]. Applied Geography， 2019，109：102034.

[12]  ZENG M L， MAO Y Y， WANG C. The relationship between street environment and street crime： A case study of Pudong New Area， Shanghai， China[J]. Cities， 2021，112：103143.

[13] 冯健，黄琳珊，董颖，等. 城市犯罪时空特征与机制——以北京城八区财产类犯罪为例[J]. 地理学报，2012，67（12）：1645

-1656.

[14]  LE A V， NHAN N H K， MOHAN R E. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots[J]. Sensors， 2020，20（2）：445.

[15]  SHIN Y C， MOON I. Robust building evacuation planning in a dynamic network flow model under collapsible nodes and arcs[J]. Socio-economic Planning Sciences. 2023，86：101455.