交巡警服务平台的设置与调度

宁楠楠 李国宁 李恒宇 宋一苇

摘要：文章研究在警力资源有限的情况下，根据城市的实际情况与需求，利用图论、目标规划、优化搜索等數学模型与算法，给出合理设置交巡警服务平台、分配各平台的管辖范围、调度警务资源方案。

关键词：图论；Floyd算法； 0-1整数规划；双目标规划；优化搜索

一、基于Floyd算法的交巡警服务平台管辖范围的分配模型

服务平台的管辖范围划分依据为其能在有突发事件情况下，能在规定时间内到达事发现场，在已知警车速度的条件下，转化为服务平台与其负责的管辖范围最短距离是否满足要求。因此，首先需求得各个路口节点的彼此最短路径矩阵，然后对路口节点的性质进行分析，最终确定其归属服务平台。

（一）管辖范围分配模型

目标矩阵：M={mij}20×92，其中：mij=0 路口j由服务平台i管辖1 路口j不由服务平台i管辖

约束条件：

Step3：按一定分配原则对各个路口节点分配其所对应的交巡警服务平台，分配原则如表2所示。

求解以上模型最后得到如表3的分配方案。

二、基于0-1整数规划的警力调度模型

警力调度可转化为20个服务平台中选择13个服务平台的0-1整数规划问题。因各交巡警平台的警察视为同时出动，则对全区全封锁所需时间可用各出动的服务平台中完成对应线路封锁所需时间最长的来刻画，即maxTime，因此目标函数即为所需最长的时长最短min（maxTime），时间问题可转化为距离问题。

（一）模型建立与求解

（二）封锁调度结果

利用MATLAB和Lingo进行求解，步骤如下。

1.同模型一的最短路径矩阵求解方法，MATLAB中使用Floyd算法求解出20个服务平台与13条交通要道间的最短路径dij。

2.按交巡警服务平台及交通要道进行对应的标号，引入决策变量xij，根据模型二0～1规划模型，利用Lingo进行规划求解。经过求解后得到如表4的警力封锁调度方案。

三、基于双目标优化的服务平台调整模型

由于出警时间过长及工作量不均衡，需对全区平台进行调整，即增加一定数量的服务平台。同时两个因素必须考虑。

1.考虑投入则不能为减少平均工作量而过多的建设平台。

2.平台建设是需要解决目前存在的出警时间和工作量两方面问题。因此该问题是一个双目标规划问题。

（一） 模型建立与求解

记交巡警服务平台i的工作量为：wi=∑pij

式中，pij为服务平台i管辖范围内的路口节点j的发案率。接着对现有交巡警服务平台情况进行分析。

1.出警时间：由模型一的结果，标号为28，29，38的6个路口节点因任何服务平台都无法在规定时间内到达，存在出警时间过长的问题。

2.工作量的平衡：由定义的工作量计算模型一分配方案中各交巡警服务平台的工作量。

由图1可知，有些服务平台的管辖范围与工作量均较大，如1，7，13，20；而10，12，14服务平台则相对较小。存在交巡警资源浪费和工作量过负荷等问题，故A区服务平台的设置不合理。可由新增加服务平台来平衡各服务平台的工作量，为此建立如下双目标优化模型。

3.决策变量：引入覆盖矩阵T描述路口节点i是否满足出警时长规定，即该节点与相应路口节点j的最短路径dij是否在3km内，组成元素tij为决策变量：tij=1 dij≤3km0 dij≥3km

4.描述路口节点i建立服务台，引入决策变量ki=1 i建立服务平台0 i不建立服务平台 i=21，…，92

（二）平台调整结果

直接求解该双目标规划模型难度较大，故将其转化为单目标问题求解。

Step1：根据目标函数一，确定可增加服务平台的路口节点候选集E，以及所需增加的服务平台的最低数目N。

MATLAB求解得路口节点候选集E={28，29，38，39，61，92}；最低需求数目N=4。

Step2：将Step1中求解的结果作为新的约束条件，结合最低需求数目N，进行遍历搜索，找出工作量方差最低的方案去求解目标函数二。具体求解方案如表5所示。

步骤1：同模型一的求解过程，求得交巡警服务平台与路口节点的最短路径矩阵D={dij}24×92；并按I，II类对各路口节点进行划分，此时不存在III类节点。

步骤2：I类节点仍直接分配给唯一符合要求的交巡警服务平台；II类路口节 点，综合就近原则与工作量的均衡两方面，即首先考虑距路口i最近的交巡警服务平台j，计算该服务平台的工作量wj，及此时的平均工作量w′。若wj≤w′，则将该路口 节点归为该服务平台管辖；否则选择次短距离的服务平台，进行同样的考虑。最终得到相应的分配方案。

四、基于优化搜索的最佳围堵方案模型

假设逃犯对全区线路熟悉，即逃犯不会驶向有交巡警服务平台的路口节点。若想在路口节点成功围堵逃犯，则相应的服务平台的警方必须比逃犯先到达该路口节点，因警方是在逃犯出逃3分钟后接到通知，则成功围堵的条件为t逃犯-i≥t警方-i+3。同时采用优化搜索的思想进行迭代计算。，若能将逃犯所有的出逃路线都围堵成功，那么该方案即为最佳方案。

（一）模型建立与求解

结合围堵成功的约束条件：t逃犯-i≥t警方-i+3，确定逃犯3分钟内可到达的节点集E={e1，e2，…，en}，此时E为逃犯可活动范围；找出与E中节点相连通的节点集合E′={e1′，e2，′…，en′}，该集合中的节点即为逃犯下一步可能出逃的路线节点；并且E中与之相连的节点集合为G={g1，g2，…，gn}，即逃犯可以从gi出发到达下一个出逃节点ei′。当G=？覫时，表明此时逃犯没有可以选择出逃的路线，即围堵成功。接着进行如下计算过程：

Step1：取gi和ei′，满足gi与ei′直接相连；

Step2：计算逃犯和距离ei′最近的交巡警服务平台与ei′的最短距离d逃犯，d警方。若d逃犯≤d警方，则ei′加入E和G，表明此时ei′为逃犯可活动范围；若d逃犯≥d警方，则ei′将从E′中删除，即逃犯不可逃往该节点。

Step3：判断gi是否仍与E′连通。若不存在这样的节点，则将gi从G中删除，即逃犯不可从节点gi出逃。

Step4：判断是否成立。若G=？覫成立，则结束该过程求解；若不成立则重复Step1。

（二）最佳围堵方案

最终得到如表6围堵方案。

参考文献：

[1]杨丰梅，华国伟，邓猛，等.选址问题研究的若干进展[J].运筹与管理，2005（06）.

[2]李帮义，姚恩瑜.关于最短路问题的一个双目标优化问题[J].运筹学学报，2001（04）.

[3]祁荣宾，冯汝鹏.求解一类0-1整数规划问题的新方法——混沌搜索算法[J].控制与决策，2003（06）.

（作者单位：宁楠楠、李恒宇、宋一苇，南京邮电大学；李国宁，兰州理工大学）