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

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

摘要

本文解决的是交巡警服务平台的设置与调度问题，根据城区具体的地理位置，案发率以及面积人口等所给的信息数据，针对不同的具体问题分别应用不同的算法建立不同的模型，给出了合理的交巡警服务平台的设置和调度方案。

问题一，题中A城区20个交巡警服务平台的分配管辖范围问题，建立服务平台在3分钟内抵达所管辖路口节点覆盖率最大化的目标函数模型，求解得到A城区20个服务平台具体的管辖的路口节点（见表5-1），此时在服务平台所管辖的路口节点中有6个路口节点的抵达时间超过了3分钟，整体有效的覆盖率达到了93.48%。

问题二，对于进出A城区的13条交通要道的封锁问题，建立了针对每个服务平台的最远距离最小化目标函数和整体封锁时间最优的多目标非线性函数，运行MATLAB求解得出封锁进出A城区13条交通要道的最短时间为8.015分钟，其中1至13个交通要道分别对应A城区12、14、16、21、22、23、24、28、29、30、38、48、62路口节点，对应的交巡警服务平台为12、16、9、14、10、13、11、15、7、8、2、5、4这13个服务平台进行封锁，路径最优，封锁时效最强（8.015分钟）。

问题三，题中考虑到各平台工作量的均衡及出警时间，需要增加交巡警服务平台的个数及位置问题。将各平台所管辖范围内的发案数的和来衡量其工作量大小，在此基础上建立了一个对每个节点的出警时间不超过3分钟的条件约束的数学模型，求解得到可在本区增加节点28、39、48、87这4个服务平台，此时各服务平台的管辖路口节点见表7-1，各交巡警服务平台的工作量较原来有较好的优化改进。

问题四，设计A城区A1和A11这两个服务平台对城区A最优的巡逻路线，采用模拟退火算法建立以两个服务平台巡逻路线距离最短的目标优化决策模型，求解得出了服务平台A1的巡逻路线依次为1、74、71、72、73、83、84、85、20、86、87、92、91、88、89、90、82、81、18、80、79、19、78、77、76、75最后回到平台1；剩下的路口节点则均由服务平台A11巡逻，其具体的先后巡逻路径见表8-2，此时两个平台巡逻路径的最短距离为图上距离1278mm，也即实际距离127.8km。

问题五，分析找出主城六区交巡警服务平台的不合理之处，结合各个城区的面积与人口等相关因素，分别考虑各区工作量情况以及各区3分钟出警覆盖率两大方面分析A、B、C、D、E、F六个城区交巡警服务平台的合理性，再在问题三的基础上对各城区不合理情况进行模型优化，并得到结果D、E、F区分别增加平台数1个、2个，3个，分别增加在节点353、408、463、503、521以及556，此时各区工作量以及3分钟出警率更加平衡。

关键词：Floyd算法 多目标非线性规划模型 模拟退火算法

1

1 问题重述

1.1问题背景

中国经济的快速发展带动人民生活水平的提高，公共安全保障问题也受到民众和政府的重视，警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。由于警务资源是有限的，根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源对于提高交巡警应急联动能力，快速高效的处理道路交通突发事件具有较实际的现实意义。 1.2需要解决的问题

由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

问题一：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。 问题二：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。

问题三：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。

问题四：现要求编号为A1和A11的两个交巡警平台各派出一队交巡警，对城区A各路口进行巡逻，巡逻后返回各自平台。请规划好这两队交巡警的最佳巡逻路线。

问题五：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。

2 问题分析

此题是研究交巡警的合理分配和调度的数学建模问题。需要通过建立合理的数学模型，进行多目标优化决策，实现对交巡警服务平台进行合理分配管辖范围。首先对市区的网络图通过MATLAB进行数据预处理，得到相邻两节点的领接距离矩阵。基于Floyd的编程思想，借助于MATLAB软件进行编程，得到任意两点最短路径的距离矩阵，随后针对具体不同问题进行深入分析。

针对问题一，我们已知A城区92个路口节点（其中也包括现有的20个交巡警服务平台）的坐标，在所给的节点坐标数据中，绘制出A城区92个路口节点的交通网络图。然后采用Floyd算法计算现有的20个交巡警服务平台与路口节点的最短路径的距离，在不考虑服务平台工作负荷的情况下，满足20个服务平台到所管辖的路口节点的距离不超过3公里，同时对于每一个路口节点都有一个距离最优的交巡警服务平台相对应。

2

针对问题二，要实现A城区20个交巡警服务平台对进出该区的13条交通要到进行快速全封锁。考虑到一个交巡警服务平台的警力最多只能封锁一个路口，所以需要进行平台到13个交间决定的，所以我们首先需要对单个平台到交通要道的可以先对每个平台单独交通要道的最优距离计算。因为最终的封锁时间是由平台到交通要道最远距离的那个时虑，建立单个平台“最远距离的最小化”优化模型。根据实行封锁的时间的要求，可引用“短板效应”来考虑出警时间，因为在封锁13条交通要道过程中，所消耗时间的长短取决于封锁单条要道所耗时间最长的那一个，在此基础上在建立一个总体的距离最优化模型。

针对问题三，20个交巡警服务平台所管辖的路口节点的个数不同，每个路口节点的案发率也不同，因此工作量并不均衡，工作量可以通过该平台管辖范围内发案率的累积量来评判，工作量均衡则可以通过各平台到所管辖路口节点的距离来衡量。考虑到出警时间过长的实际情况，为了保证及时出警，还需要平台到路口节点的距离来限制约束。此外增加服务平台必然存在一定的成本，增加的平台越多成本也将越高，在尽可能小的成本条件下，我们考虑在满足服务平台覆盖率、各平台管辖路口节点的工作量、及时出警的条件下增加尽量少的交警服务平台，在以此作为边界条件，建立优化决策模型，最后与增设平台前工作量做分析比较，以此检验增设后的优化效果。 针对问题四，设计A城区A1和A11这两个服务平台对城区A最优的巡逻路线，我们采用模拟退火算法的原理考虑到这两个节点从各自的平台出发，巡逻完后也要回到各自的平台，对此确定了相应的条件约束，建立了以两个服务平台巡逻路线距离最短的目标优化决策模型，以此设计出最优的巡逻路线方案。

针对问题五，分析找出主城六区交巡警服务平台的不合理之处，结合各个城区的面积与人口等相关因素，分别考虑各区工作量情况（发案率）以及各区3分钟出警覆盖率两大方面分析A、B、C、D、E、F六个城区交巡警服务平台的合理性，再在问题三的基础上对各城区不合理情况进行模型优化，最后对比优化前后效果。

3 基本假设和符号说明

3.1基本假设

假设1：同一管辖范围内，同一时间发生两起案件的可能性很小，只考虑同

一时间只处理一个案件的情况。

假设2：出警时警车速度恒定，不会出现堵车等特殊情况。

假设3：假设接到报案后，交巡警可以立即出发，准备时间忽视不计。 假设4：整个模型以节点作为划分交巡警服务平台管辖范围的基本单位。 假设5：假设案件都发生在节点上，不考虑发生早在两个节点之间的问题。 3.2 符号说明

符号 i 符号说明 A城区第i个交巡警服务平台 A城区第j个路口节点 A城区从第i个交巡警平台到第j个路口节点的时间 A城区从第i个交巡警平台到第j个路口节点平台的最短距离 3

j tij dij

xij k ? yi yij平台i到路口节点j的距离dij是否超过3km的决策变量 第j个路口节点是否属于第i个服务平台管辖的决策变量 区别于服务平台i以外的服务平台 服务平台在3分钟内抵达路口节点的覆盖率 表示是否在第i个节点处设立为交巡警服务平台的决策变量 表示A城区服务平台A1平台是否从i节点巡逻到j节点 表示A城区服务平台A11平台是否从i节点巡逻到到j节点 Aij Bij 4 数据分析和处理

4.1 A城区各节点间的坐标数据处理

根据附录2中92个路口节点的横纵坐标，用MATLAB（程序见附录一）编程计算标出每个节点标号与之相连的关系，更直观的呈现各节点相对应的空间地理位置关系，效果见图：

4006158380483073134032338463537361645393840476505159525564953576062485208684899088918763766475656668677719807983821881923605455334929281015447816974737071722434217413201227300242801323260200222511261421250300350400450

图4-1：92个路口节点位置关系平面图

由图4-1可以很直观的看到现有的20个交巡警服务平台以及要分配管辖的路口节点的平面地理位置，也可以辅助对问题一建立的严谨模型计算结果的主观检验。

4.2 A城区92个路口节点的距离分析

由上图知A城区92个路口节点的平面布局图，根据题目给出的坐标数据，采用Floyd算法（编程代码见附录二），计算A城区92个路口节点相互之间最短路径的距离，计算的结果矩阵如下（完整的数据见附录三）

1 2 3

表4-2:A城区92个路口节点相互之间的最短距离 1 2 3 … 90 91 0 18.9874 38.8388 … 45.1713 49.9147 18.9874 0 21.1165 … 63.3732 68.1166 38.8388 21.1165 0 … 78.4747 83.2181 4

92 69.9397 80.7279 101.8444