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

1、1交巡警服务平台的设置与调度【摘要】警察是现代社会中不可或缺的社会角色，肩负着执法、治安与服务群众等重要职能。为了更好地履行这些职能，交巡警服务平台要合理地分布在城市的各个地区，这样不仅可以及时响应出警到达案发现场，在遇到突发事件时也可以通过联合调度高效地行动起来。该论文就交巡警服务平台的设置与调度等实际问题，针对所提出的 5 个问题分别给出具体的解决方案并给出结果：对于问题 1 要给 A 区的每个服务平台分配管辖范围，即分配其管辖的节点。我们根据“就近原则”来分配管辖的节点，保证尽量在 3 分钟内有交巡警到达事发地。对此，借助 MATLAB 编程采用“Floyd 最短路径算法”确定距离每个节

2、点最近的服务平台，从而得到每个服务平台的管辖范围。对于问题 2 的合理的调度方案的确定，我们在“快速封锁”的原则下，通过调度警力使得 A 区在最短时间内被全封锁。20 个服务平台对 13 个路口进行全封锁，而且每个服务平台最多封锁一个路口，这可划归于一个 0-1 规划问题，因此可用 LINGO 编程求得各种可选调度方案中 13 个路口封锁时间的最大值取值最小时的调度情况。对于问题 3 增加平台的个数与位置的确定，我们的目的是使各个服务平台的工作量达到均衡状态而且出警时间过长的问题得到有效解决。为此，我们在出警时间过长的节点或附近尝试增加新的服务平台，然后计算方差来衡量工作量的均衡程度，比较增加

3、 2 至 5 个服务平台时的方差，以此确定方差最小的情况为最后的可选方案。这个过程仍然借助 MATLAB 程序来完成，采用“模拟退火法”来确定工作量达到均衡时新增平台的个数与位置。对于问题 4 对全市服务平台设置方案的合理性的讨论，我们借助问题 1 和问题 3的解决方法来确定各区服务平台的管辖范围与新增服务平台的个数与位置。同时对模型进行优化，考虑到有些服务平台的工作量过少的情况，撤消一些现有的服务平台。借助 MATLAB 程序，可以给出一个较合理的解决方案，即给出各个分区的服务平台的调整方案。对于问题 5 围堵方案的确定，可将全市的交通网看作一张图，各个节点看作顶点。同时根据必要的假设：嫌疑

4、犯一直朝远离事发点 P 点的方向逃跑，而且不走回路。这时，将 P 点看作树根，嫌疑犯的可能的逃跑路线便成为一个树，有可能经过的节点便是枝和叶。这样，就能根据图论的知识，通过 MATLAB 与 LINGO 程序，利用“追捕算法”来对各个分支道路进行有序的封锁排查，进而求得最佳的围堵方案。关键词：Floyd 最短路径算法、0-1 规划、模拟退火法、平台的设置与调度、图论、追捕21、问题背景现代社会中，要保证社会的良性运行，人民警察扮演着重要的角色。他们肩负着刑事执法、治安管理、交通管理、服务群众的重要职能，在保障人民财产安全面前起着举足轻重的作用。为了更有效地实施这些职能，需要在市区的一些交通要道

5、和重要部位设置交巡警服务平台。这些交巡警服务平台的职能和警力配备基本相同，共同维护着社会的治安，保证城市的安全。在交巡警服务平台的设置中我们要充分考虑到警察所担负的社会职责：刑事执法、治安管理、交通管理、服务群众。在保证人民群众人身与财产安全的前提下还要尽量把服务工作做好做到位，让人民群众满意，因此，交巡警服务平台的设置是关键还要考虑到调度上的方面与快捷。而现实中由于警务资源的限制，同时考虑到社会资源的高效分配，不可能在每个交通要到和重要部位都设置这些交巡警服务平台。因而，如何根据城市的实际情况和需求合理的配置有限的交巡警服务平台、分配平台的管辖范围、调度警务资源是警务部门面临的一个实际而重要

6、的问题。2、问题重述就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件 2。全市（主城六区A，B，C，D，E，F）的交巡警服务平台的设置的具体情况与其他这些城市的情况见附件 2。问题 1：请为 A 区各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。问题 2：对于重大突发事件，需要调度 A 区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速

7、全封锁。实际中一个平台的警力最多封锁一个路口。请给出遇到重大突发事件时的警力合理的调度方案。问题 3：根据 A 区现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。问题 4：针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。问题 5：如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。3、基本

8、假设3现针对问题做必要的假设：1、发生突发事件后，警察在接到报警时能立刻出警，时间上的消耗主要考虑到在路上所花的时间。2、警察出警时，在去案发现场的路上道路通畅（不发生堵车等现象） ，警车行驶正常。3、交巡警服务平台的工作量主要由于出警所引起，而在现场或服务平台处理案件的工作量忽略。4、任何事故都发生在市区道路的节点上。5、警察出警到达事发地点走最短距离，而且警车始终保持匀速行驶。6、犯罪嫌疑人驾驶车辆出逃时，只能通过联通市区与外界的节点逃出市区。7、交巡警服务平台一般不能跨区管理，除非是一些重大事故。8、一般地，驾车逃跑的嫌疑犯不会走回路，而且想尽量离出事地点越远越好。9、嫌疑犯逃跑的车速是

9、恒定的。4、符号说明表 1符号 数学解释in路口（节点）的发案率jd两节点之间的距离,ijiw节点处交巡警服务平台的工作量t节点处的出警时间iis标准差v警车的行驶速度u嫌疑犯逃跑车速5、问题分析5.1 问题 1 的分析分配交巡警服务平台管辖范围的目的是当其所管辖的范围内发生突发事件时，尽量能在 3 分钟之内有交巡警到达事发地。根据实际生活中的经验，人们当然也希望突发事件发生时交巡警能够能尽快到达事发地处理事件。因而，在确定每个服务平台的管辖范围时，应根据“就近原则”节点距离某个服务平台最近就属于那个服务平台管辖。可以考虑借助“Floyd-Warshall 最短路径算法”解决这个问题。5.2

10、问题 2 的分析当发生重大突发事件时要调度全区 20 个交巡警服务平台的警力资源对 13 条进出该区的交通要道实现全面快速的封锁。其中时间是关键因素，我们希望封锁完成得越快越好，而全封锁的最终完成以最后一个交通要道的封锁实现为标志。从而只须要求封锁最慢的那个交通要道的封锁时间最短即可。5.3 问题 3 的分析之所以要增加 2 至 5 个平台，是为了解决现有交巡警服务平台的工作量不均衡和4有些地方出警时间过长的实际问题。由于管辖范围的划分是依据出警时间来确定的，因此在这里我们首先应该考虑工作量均衡问题，然后再以出警时间作为辅助来检验增加的服务平台的合理性。而一般说来，出警时间与工作量具有一定的正

11、相关性，因此在出警时间较长的节点或其附近增加交巡警服务平台可以在一定程度上协调解决这两个问题。由于工作量既与出警路程有关，又与案件发生频率有关，所以可用案件发生频率与路程的积来表征工作量的大小，于是对每一个服务平台都有一个相应的工作量；同时又可用方差来表征工作均衡的程度。因此，通过添加服务平台，可以调整管辖范围，从而不但可以确保出警时间，也能调整工作量大小，以方差大小来衡量其均衡程度，最终可得一个添加方案。整个过程主要采用模拟退火算法，由于此题距离较远的节点出警时间不一定能保证，且工作量相对较大，故可从距离入手来添加服务平台。依据该算法原理，采用逐步寻优的手段，以工作量方差为检验标准，温度下降

12、时工作量以较大概率趋于均衡，最终将得到一个较为合理的平台设置方案。5.4 问题 4 的分析根据设置交巡警服务平台的原则与任务刑事执法、治安管理、交通管理与服务群众，同时结合题目的要求可知平台设置的效果：第一是保证接到报警后出警时间不能过长；第二是各个服务平台的工作量大致均衡。接下来主要依据这两个方面对服务平台的设置进行优化。对于第一点，依据题意，不管在哪个区，出现突发事件时，尽量在相对短的时间内有巡警到达，基于这一点，我们可以对各个区内巡警服务平台的管辖范围进行划分。这就是说，范围的划分是为了保证出警时间不是太长。但考虑到现实中交巡警一般不能跨区管理，并且每个区的面积、人口密度、服务平台数目也

13、不相同，因此要对不同区分开考虑，故不同区的出警最长时间的设定标准是不同的。对于第二条，由上面划分的管辖范围，依据问题 3 中的方法算出各个服务平台的工作量，通过比较，我们可以直观的发现其中的不合理的地方一些服务平台之间的工作量相差太大，有些节点的出警时间的相对较长，可以分如下情况进行优化：（1）某个服务平台的工作量很大，若将其中某些节点划给其它服务平台管理则可达相对均衡状态，但划出的这些节点归为其他服务平台则会导致出警时间过长，也即该服务平台附近没有其他工作量较小的服务平台，两种矛盾无法调和，此时应该考虑添加一个服务平台。（2）某几个服务平台较为集中，且各自工作量相对较小，而将这些平台管辖区域

14、外的节点调给它时又会导致出警时间过长，此时可以考虑撤消（或转移）某一个或几个服务平台来平衡工作量。通过以上两方面的调整，采用模拟退火算法思想，通过添加和撤消服务平台，最终工作量的方差达到最小且基本不变，而且每个节点的出警时间均不会有太大差异，这样就得到一个相对较为合理的设置方案。5.5 问题 5 的分析当发生重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点。我们根据假设，嫌疑犯希望里出事地点 P 节点越来越远，而且嫌疑犯所走的路线不会出线回路。这时，我们将 P 点当作根，嫌疑犯可能的逃跑路线构成一个树。交巡警便可以

15、根据逃5跑路线所构成的树对嫌疑犯进行围堵。根据图论的知识，借助 MATLAB 与 LINGO 编程便可以得到一个围堵方案。6、模型的建立与分析6.1 问题 1 的求解6.1.1 模型的建立与求解 根据“就近原则”的要求只需要确定距离每个节点最近的交巡警服务平台是哪个，从而就可以确定每个交巡警服务平台的管辖范围。这里我们用到“Floyd-Warshall 最短路径算法 1”。这个算法通过不停地加入中间点进行矩阵的迭代，从而解决有向图中每对顶点的最短路径问题，当我们把每个节点看作顶点时，我们便可以求得每个服务平台的管辖范围管辖的节点。由 MATLAB 编程（见附录 1） ，利用 Floyd-War

16、shall 最短路径算法可以得到 A 区 20个服务平台的管辖范围，即每个服务平台所管辖的节点编号。A 区服务平台的工作量见表 2，结果见表 3：表 2A 区交巡警平台编号 A 区交巡警平台的位置编号A 区交巡警平台的工作量A1 1 84.7033A2 2 128.7231A3 3 58.4864 A18 18 97.9036A19 19 92.9778A20 20 38.7462表 3A 区交巡警平台编号A 区交巡警平台位置编号 每个交巡警平台所管辖节点编号A1 1 1、67、68、69、71、73、74、75、76、78A2 2 2、39、40、43、44、70、72A3 3 3、54、5

17、5、65、66A4 4 4、57、60、62、63、64A5 5 5、49、50、51、52、53、56、58、59A6 6 6A7 7 7、30、32、47、48、61A8 8 8、33、46A9 9 9、31、34、35、45A10 10 106A11 11 11、26、27A12 12 12、25A13 13 13、21、22、23、24A14 14 14A15 15 15、28、29A16 16 16、36、37、38A17 17 17、41、42A18 18 18、80、81、82、83A19 19 19、77、79A20 20 20、84、85、86、87、88、89、90、91、

18、92A 区各个交巡警平台的相应的管辖范围如图 1 所示（MATLAB 程序见附录 2）:图 1（不同管辖范围用不同的颜色标识）6.1.2 模型的分析从结果中可以很直观地看到不同交巡警平台所管辖的周围的节点个数是不同的，从而管辖范围不同，他们的工作量当然也不相同。例如平台 A20 要管辖 10 个节点，而平台 A6 仅管辖 1 个节点，这显然是不合理的利用最短路径的思想划分的管辖范围会使得服务平台的工作量的不均衡。6.2 问题 2 的求解6.2.1 模型的建立与求解当遇到突发事件需要对 A 区进行全封锁时，合理的调度方案应该是使出警时间最长的节点处的出警时间达到最小值，其余的节点处出警时间尽量减

19、小。又由于警车匀7速行驶，所以路程的长短反映出出警时间的长短，故可用距离来代替时间考虑。由于 20 个服务平台的交巡警封锁 13 个路口，每个路口要有一个平台的交巡警负责，每个交巡警平台最多只能封锁一个路口，可以考虑用 0-1 规划来解决。目标函数为 13 个路口到各个服务平台的距离的集合，求解目标函数就是对这些距离进行搜索，找出达到 13 个一一对应时的最小距离，也就是说对所有可选的调度方案，找出每个方案的最大距离，然后从这些最大距离中取出最小值。对于取出的方案，由于前 12 个对应距离均比这个距离小，所以这个对应就表示完成封锁所需时间的最小值。借助计算机编程可得结果。其 LINGO 程序见

20、附录 3，运行结果如下：以 A7 服务平台封锁 29 号出口节点即可找到符合题意的一种封锁方案，并且这个方案中的最大距离是所有可行方案中最小的，所以说这个结果是最佳的。而其余的封锁时间均比完成该封锁用时短，故只用保证第 29 号出口节点由 A7 服务平台负责封锁，其余的节点处可有不止一种选择，这里我们给出一种相对较佳的方案作参考，见表 4：表 4路口号12 14 16 21 22 23 24 28 29 30 38 48 62平台号A10 A16 A9 A14 A11 A13 A12 A15 A7 A6 A2 A5 A46.2.2 模型分析LINGO 程序的最终结果显示只需要将 29 号路口由

21、 A7 来封锁，其余路口在保证选择与他们距离短于 A7-29 之间的距离的平台的情况下，尽量选较短距离。即便如此，调度方案也不唯一，这里仅给出一个相对较佳的可行方案。6.3 问题 3 的求解6.3.1 模型建立与求解为解决服务平台工作量的不均衡和有些地方的出警时间过长的实际问题，可以考虑添加新的服务平台来分摊工作量较大的服务平台的工作量，又由于工作量大小和出警时间在一定程度上有正相关性，故一般也可同时减少出警时间过长节点的出警时间。每个服务平台都有一定的工作量，我们定义工作量函数 iijwdn其表示标号为 的服务平台的工作量， 为其管辖的节点处的发案率。i j节点 处的出警时间为 ijitv由

22、于 不变， 仅与 成正相关关系，距离长的地方出警时间相应会长。 为节点与vitijd ijd管辖其的服务平台之间的距离。各个服务平台的工作量的均衡程度由各个服务平台的工作量之间的方差 来决定。s8当我们计划增加 2 至 5 个服务平台时，我们最终要使得方差 达到最小值时的工作s量达到最均衡的状态。这时便可以确定所增加的服务平台的个数与位置。对此，我们运用“模拟退火算法 2”对其进行求解。该算法是寻求各个状态点之间的一个均衡的状态。而我们正是要通过增加服务平台的个数使得更个服务平台的工作量达到基本均衡，同时使得出警时间过长的节点的出警时间得到有效缩短。MATLAB程序见附录 4，运行结果表 5：

23、表 5新增服务平台个数 新增服务平台所在节点标号5 21、24、28、38、925 21、24、28、39、92新增平台如图 2：图 2（其中青色加号表示新增平台）6.3.2 模型分析根据程序运行的结果，可知在 38 或 39 号节点处增加新的服务平台所得结果差异不大，因此都可以当作供选方案。由于退火模型存在普遍的缺陷，根据所选的“退火系数”t 的不同，得到的结果可以有一定的差异，但对问题没有本质上的影响。如 t 取不同值时，92 这个节点也可不添加服务平台，但也符合时间限制，对工作量均衡也无显著影响，只是上面的添加方案可以更加有效，工作量也相对较小，即这是一个较佳方案，故选之。6.4 问题

24、4 的求解6.4.1 模型的建立与求解9对现有交巡警服务平台设置的合理性的讨论主要有两个指标来确定各服务平台的工作量的差异与各个节点的出警时间的长短。现实生活中不同区的警力管辖范围仅限于该区，只有发生特殊事件时才有跨区合作的机会，因此我们将全市六区分开考虑，每个区的服务平台的管辖范围仅限于该区，那么问题的解决思路与问题 3 有很多类似的地方。问题的解决过程如下：（1）计算各区的服务平台的工作量，及它们的方差大小。计算各个节点处的出警时间。（2）根据问题三的方法对每个区的服务平台进行优化。（3）对于服务平台集中且各个服务平台的工作量都不大的情况考虑撤销一个服务平台节约警力资源。根据求解以上问题的

25、思路，我们把全市划分为 6 各区，各个区由 Floyd-Warshall最短路径算法求得各个服务平台的管辖范围，先通过直观地观察撤销一些明显的工作量过少的的平台，然后由模拟退火算法通过增加服务平台的个数来均衡各个平台的工作量。由 MATLAB 编程运行得到各个服务平台的工作量如表 6,得到结果如表 7：表 6交巡警平台编号 交巡警平台的位置标号 交巡警平台的工作量A1 1 84.7033A2 2 128.7231A3 3 58.4864 F9 483 97.9036F10 484 92.9778F11 485 38.7462表 7增加与撤销平台如图 3 所示：（其中蓝色表示原服务平台，青色加号

26、表添加新平台，红色叉号表撤消平台）区号 新增平台所在节点的标号 撤销平台所在节点的标号A 21、24、28、38 或 39、92B 120、147 97、99C 205、240、261、281、301、313166、169、179、178D 333、362 322、325E 391、409、417、452 372、376、377F 493、515 48410图 36.4.2 模型的分析原方案的设计从时间和工作量上来讲绝大部分是合理的，只是有些地方设置不太科学。事实上，考虑时间因素和工作量因素占不同比重时优化方案也会不同。此处先考虑的是时间因素，对各个区域的服务平台管辖范围进行划分，然后采用问题

27、 3 中方法给出工作量并得出撤消和添加的服务平台，然后再以时间限制进行优化检验。当然，采取不同的均衡标准与时间限制也可以有不同的优化方案。6.5 问题 5 的求解6.5.1 模型的建立与求解当发生重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点。根据假设，嫌疑犯希望离出事地点 P 节点越远越好，而且嫌疑犯所走的路线不会出现回路。因此，与同一个顶点相连的任意两个顶点不会连通（即无圈） ，这样可以将 P 点当作树根，而嫌疑犯可能的逃跑路线则构成一个树，这个树采用广度优先搜索 BFS 的方法得到的(附录 5)。下面我们用图论的知识对这个围堵问题进行求解 3：假设嫌疑犯可能的逃跑路线所构成的树为 ，我们的算法如下：T（1） 把 的全部叶删除，得到子树 ；若 是一个顶点组成的，算法终止；T1否则转（2） 。