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

谭 巍

（西安理工大学自动化与信息工程学院，陕西西安 710048）

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

谭 巍

（西安理工大学自动化与信息工程学院，陕西西安 710048）

文章以2011年全国大学生数学建模竞赛B题中的数据和假设为基础，根据图论中的Floyd算法和运筹学中的指派模型，研究了如何对现有交巡警服务平台的管辖范围进行合理地分配．建立对现有平台管辖的综合评价模型，并结合出警时间尽可能短的原则，对模型进行了优化，得到了交巡警服务平台管辖范围的合理分配方案．

0-1规划；Floyd算法；综合评价模型；夹角余弦法

警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能．为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台．每个交巡警服务平台的职能和警力配备基本相同．由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题．

1 基本假设

1.1 假设发案率只在节点上发生，不用考虑在本区之外的情况．

1.2 在出入城区路口所设的交巡警服务平台堵住该路口的时间为零．

1.3 所有道路都是双向且畅通无阻的，警车由最短路径到达事发地点．

1.4 相邻两个交叉路口之间的道路近似认为是直线．

1.5 警车以60km/h的速度匀速行驶，不考虑车辆的调头、启动、停止时的加减速过程．

2 符号说明

A0：存放各个节点之间的距离的邻接矩阵；μ：A区所有平台案发率的平均值；α：A区单位平台总发案率；tij：从i到j的时间矩阵；z1：表示从所有交巡台出发到达指定路口的距离；αij：从i到j的距离矩阵．

3 模型的建立与求解

3.1 问题一

3.1.1 模型的建立与求解

根据城市交通路口的路线，利用Floyd算法[3]求出对应点之间的最短时间路径．由Floyd算法得到的结果对20个平台管辖分配建立了一个整数规划模型：

由LINGO编程求解出管辖范围，从结果中看出，除标号28、29、38、61、92这个6点外，93.5%的路口都能在3分钟到达．将结果整理，得到各交巡警平台管辖路口标号及其总案发案率（如表1）．

表1 各交巡警服务平台管辖路口标号及其总案发案率

3.1.2 模型的建立与求解

对于将二十个交巡警分配到十三个路口封堵，我们建立一个双目标整数规划模型：

设用

z2：表示从交巡台出发到指定路口的时间和．

通过LINGO程序求解得出满足条件的最小时间为8.055分钟，与之相对应的调度方案如表2．

表2 A区快速封锁交通要道的最佳分配方案

3.1.3 模型的建立与求解

警务部门在增设平台时，主要考虑优化的两个因素是出警速度和工作量均衡度．参考信息得知，我国很多大中城市都对市区发生事故有出警时间的硬指标，故此处出警速度以最长出警时间tmax衡量；工作量均衡度以所有平台各自管辖区域内总发案率的方差衡量．[1]

采用宽容分层序列法，[1]来分析这两个指标．缩短出警时间是警务部门增设服务平台的首要目标，当出警时间被缩短到一定范围内时，我们可以近似地将落在这个范围内的出警时间看作是无差异的．若假设范围上限为T，则[0，T]内的出警速度都是可以接受的．采用第一小问中的要求，取T=3.在确定增设的平台数量后，枚举所有可能的位置，求出tmax的下界．（如图1）其中使得解落在[0，3]内的最小增设平台数为4．

图1 出警速度与增设平台数的关系

现在来调整4个新增平台的具体位置来最优化工作量均衡度．假设l21,l22,l23,l24为4个新增平台

的位置，ri表示平台i(1≤i≤24)管辖区域内的总发案率，表示各平台管辖区域内总发案率的平均值，则工作量均衡度的最优化模型可以表示为：

由于未设平台的路口有72个，采用模拟退火算法[3]求近似最优解．

图2 A区新增平台位置示意图

用模拟退火算法得到最优工作量均衡度为2.4111，与之对应的新增平台的具体位置为28，40，48，91（如图2）．新增平台后各个平台的管辖路口标号及总发案率数据见表2.

表3 增设平台后A区各平台管辖路口标号及总发案率

为了验证我们上诉4个平台增加的合理性，画出新增平台后管辖区总发案率（图3）和各个平台的贡献度（图4）．

图3 各个平台管辖区内总发案率

图4 各个平台总发案率对方差的贡献度

从图4中可以明显看出有4个平台对方差的贡献度较大，分别是A10，A13，A14及A21．其中A10，A14和A21均因离其他路口较远，管辖的路口数较少导致总发案率偏低，造成不可避免的较大的方差贡献度．A13的方差贡献度大则是因为它所管辖的路口发案率都较高，在资源条件允许的情况下，可以考虑在附近路口再增设一个平台来减轻A13的工作量，具体取舍要依实际情况而定．但我们在A13附近搜索第五个平台的位置，总体方差下降并不显著，故选择增设四个平台作为最终方案．

3.2 问题二的模型

3.2.2 全市平台的合理性

3.2.2.1 综合评价模型

从出警速度的角度考虑，假设所有路口均按照模型一匹配到最近的平台，将此时的出警速度作为评判一个区的平台设置在时间上的合理性．

由上提出以下3个评价指标：

（1）出警时间达标率η

出警时间的达标率是指达标路口数占该区总路口数的百分比，一定程度上可以反映该区平台设置的整体合理程度．以A区为例，设A区总路口数为NA，其中达标路口数为，不达标路口数为则

（2）平均超出时间

平均超出时间是指某区不达标路口的出警时间超出规定时间（3分钟）部分的平均值．以A区来说，有

平均超出时间越大，该区的设置越不合理．

（3）平均工作量

先忽略区域内工作量要平均的要求，取而代之的是区与区之间工作量的平均程度，这样做的根据是区内的平均程度可以容易地通过平台的调整、增加以及算法二的安排来优化．平均工作量是指某区所有平台处理事件数的平均值．以A为例，设A区平台数为nA，则为A去第i平台的发案率．根据各区之间平均工作量的比较结果，可以为工作量大的城区增加平台．

（4）确定指标权重

指标权重的合理确定是综合评价结果是否可信的一个核心问题，为了避免主观性因素的影响，我们采用客观赋权法来确定权重．考虑到每个指标的大小是否合理要与该市整体的实际情况相联系，而夹角余弦法很好地满足了这种要求，故采用夹角余弦法.[3]

具体步骤如下：

Step1：求出理想的最佳方案R和最劣方案T．

Step2：计算效益型矩阵B 和相对偏差矩阵．

Step3：利用列向量夹角定权W并计算分数向量Q．

通过对模型求解，最后计算分数向量

Q=(0.9321 0.7940 0.3036 0.3875 .05080 0.4491)T看出六个城区交巡警服务平台设置相对合理度的高低为ABEFDC，A，B两区的综合分数远远高于其他各区；同样地，利用成本型矩阵，可以得到六个城区平台设置相对合理度的高低为ABEDFC．从综合评价值结果与排序可以看出A，B两区的平台设置方案相对合理，而其余四区存在明显问题．

D，E两区小，但是出警速度却很慢，通过观察发现，在平台的设置上，有一些点明显不合理，针对这种现象，我们的做法是将这些明显不合理的点删去，再加入等量多的平台，使其出警速度得以优化．对于重新加入的平台位置选择，采用枚举法加快出警速度，对所有η、到一定指标的方案进行人工删选，并在位置固定后用模型三安排每个平台服务的节点．得出结果如下：

D 增加点 329 333 370删除点 322 325 328 E 增加点 388 464删除点 373 376

C，F两区大，警力明显不足，警速度也很慢，而且在平台的设置上，也有一些点明显不合理，针对这种现象，我们先将这些明显不合理的点删去，再加入比所删平台数量更多的平台，多增加的平台数目主要由确定，使其平均工作量降到与其他四区大概相等的水平．在数目确定的情况下，枚举所有可能选择，对所有η、达到一定指标的方案进行人工删选，并在位置固定后用算法三安排每个平台服务的节点．

由于C区点数过多，枚举所有可能情况不切实际，且C区的发案率分布较为均匀，我们将已经设置的平台的周围节点从枚举范围中除去，运行速度大大提升．在实际操作中，取η=0.8，=0.5规定平台周围的节点据平台直线距离小于1公里．

得出结果如下：

C增加点 209 239 258 287 313删除点 166 169 F增加点 507 520 527删除点 483

4 模型评价

通过建立两个不同的整数优化模型，得到各个交巡警的管辖范围和发生突发事件后的调动发案；采用夹角余弦法的综合评价法，量化全市的平台设置方案．模型简单方便，具有很强的实用型、推广性，可以用来解决类似的城市的紧急服务设施，如医疗救护中心、消防中心、110报警中心等等的优化设置和合理设置的问题．

[1]朱茵，江越.城市道路交通应急警力配置模型研究[J].中国安全科学学报，2010（11）.

[2]袁新生，邵大宏，郁时练.LINGO和EXCEL在数学建模中的应用[M].北京：科学出版社，2007.

[3]刘卫国.MATLAB程序设计与应用[M].北京：高等教育出版社，2006.

（责任编辑：于开红）

Abstract:Based on data and assumptions in the 2011 National Mathematical Contest in Modeling Problem B is assigned according to the Floyd algorithm in graph theory and operations research model to study the how the jurisdiction of the existing Traffic Patrol service platform rational allocation. The establishment of a comprehensive evaluation model under the jurisdiction of the existing platform, combined with the principle of police time is as short as possible; the model is optimized and rational allocation of program service platform under the jurisdiction of the Traffic and Patrol Police.

Keywords:0-1 planning; Floyd algorithm; evaluation model; cosine method

Traffic Patrol service platform settings and scheduling

TAN Wei
(Xi'an University of Technology Automation and Information Engineering, Xi'an, Shanxi 710048, China)

O29

A

1009-8135（2012）03-0106-05

2012-01-20

谭 巍（1990-），男，重庆万州人，西安理工大学自动化与信息工程学院学生．