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规划、 模拟退火法 、平台的设置与调度、 图论、追捕 2 1、 问题背景 现代社会中，要保证社会的良性运行，人民警察扮演着重要的角色。他们肩负着刑事执法
5、、治安管理、交通管理、服务群众的重要职能 ，在保障人民财产安全面前起着举足轻重的作用。为了更有效地实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。这些交巡警服务平台的职能和警力配备基本相同，共同维护着社会的治安，保证城市的安全。 在交巡警服务平台的设置中我们要充分考虑到警察所担负的 社会职责：刑事执法、治安管理、交通管理、服务群众。在保证人民群众人身与财产安全的前提下还要尽量把服务工作做好做到位，让人民群众满意，因此，交巡警服务平台的设置是关键还要考虑到调度上的方面与快捷。 而现实中由于警务资源的限制，同时考虑到社会资源的高效分配，不可能在每个交通要到和重要部位都设置这些交
6、巡警服务平台。因而，如何根据城市的实际情况和需求合理的配置 有限的 交巡警服务平台、分配平台的管辖范围、调度警务资源是警务部门面临的一个实际而重要的问题。 2、问题重述 就某市设置交巡警服务平台的相关情况，建立数学模 型分析研究下面的问题： 附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图，相关的数据信息见附件 2。 全市（主城六区 A， B， C， D， E， F）的 交巡警服务平台的设置的 具体情况 与其他这些城市的情况见附件 2。 问题 1： 请为 A区 各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在
7、3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。 问题 2： 对于重大突发事件，需要调度 A 区 20 个交巡警服务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁。实际中一 个平台的警力最多封锁一个路口 。请给出 遇到重大突发事件时的 警力合理的调度方案。 问题 3： 根据 A区 现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2至 5个平台，请确定需要增加平台的具体个数和位置。 问题 4： 针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。 问
8、题 5： 如果该市地点 P（第 32个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给 出调度全市交巡警服务平台警力资源的最佳围堵方案。 3、基本假设 现针对问题做必要的假设： 1、 发生突发事件后，警察在接到报警时能立刻出警，时间上的消耗主要考虑到在路上所花的时间。 3 2、 警察出警时，在去案发现场的路上道路通畅（不发生堵车等现象），警车行驶正常。 3、交巡警服务平台的工作量主要由于出警所引起，而在现场或服务平台处理案件的工作量忽略。 4、任何事故都发生在市 区道路的节点上。 5、警察出警到达事发地点走最短距离，而且警车始终保持匀速行驶
9、。 6、犯罪嫌疑人驾驶车辆出逃时，只能通过联通市区与外界的节 点逃出市区。 7、交巡警服务平台一般不能跨区管理，除非是一些重大事故。 8、 一般地， 驾车逃跑的嫌疑犯不会走回路，而且想尽量离出事地点越远越好。 9、嫌疑犯逃跑的车速是恒定的。 4、符号说明 表 1 符号 数学解释 in 路口（节点）的发案率 ijd ,ij两节点之间的距离 iw i 节点处交巡警服务平台的工作量 it i 节点处的出警时间 is 标准差 v 警车的行驶速度 u 嫌疑犯逃跑车速 5、 问题分析 5.1 问题 1 的分析 分配交巡警服务平台 管辖范 围的目的是当其所管辖的范围内发生突发事件时，尽量能在 3分钟之内有交
10、巡警到达事发地。根据实际生活中的经验，人们 当然 也 希 望突发事件发生时交巡警能够能尽快到达事发地处理事件。因而，在确定每个服务平台的管辖范围时，应 根据 “ 就近原则 ” 节点距离某个服务平台最近就属于那个服务平台管辖。可以考虑借助 “ Floyd-Warshall 最短路径 算法 ” 解决这个问题。 5.2 问题 2 的分析 当发生重大突发事件时要调度全区 20个交巡警服务平台的警力资源 对 13条进出该区的交通要道实现全面快速的封锁 。其中时间是关键因素，我们希望封锁完 成得越快越好 ，而全封锁的最终完成以最后一个交通要道的封锁实现为标志。从而 只须要求封锁最慢的那个交通要道的封锁时间
11、最短即可。 5.3 问题 3 的分析 之所以要增加 2至 5个平台，是为了 解决现有 交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际问题。 由于管辖范围的划分是依据出警时间来确定的，因此在这里我们首先应该考虑工作量均衡问题，然后再以出警时间作为辅助来检验增加的服务平台的合理性。 而一般说来， 出警时间 与工作量具有一定的正相关性，因此在出警时4 间较长的节点或其附近增加 交巡警服务平台 可以在一定程度上协调解决这 两个问题。 由于工作量既与出警路程有关，又与案件发生频率有关，所以可用案件发生频率与路程的积来表征工作量的大小，于是对每一个服 务平台都有一个相应的工作量；同时又可用方差来
12、表征工作均衡的程度 。 因此，通过添加服务平台，可以调整管辖范围 ， 从而不但可以确保出警时间，也能 调整工作量大小 ，以方差大小来衡量 其均 衡程度，最终可得 一个添加方案。 整个过程主要采用模拟退火算法，由于此题距离较远的节点 出警时间不一定能保证 ，且 工作量相对较大 ，故可从距离入手来添加服务平台。依据该算法原理，采用逐步寻优的手段 ， 以工作量方差为检验标准， 温度下降时工作量以较大概 率 趋于均衡， 最终将得到一个较为合理的平台设置方案。 5.4 问题 4 的分析 根据设置交巡警服 务平台的原则与任务 刑事执法、治安管理、交通管理与服务群众，同时结合题目的要求 可知平台设置的效果
13、： 第一 是 保证 接到 报警后出警时间不能过长； 第二 是各个服务平台 的工作量大致均衡。 接下来主要依据这两个方面对服务平台的设置进行优化。 对于第一点，依据题意，不管在哪个区，出现突发事件时，尽量在相对短的时间内有巡警到达，基于这一点，我们可以对各个区内巡警服务平台的管辖范围进行划分。这就是说，范围的划分是为 了保证出警时间不是太长。但考虑到现实中交巡警一般不能跨区管理，并且每个区的面积、人口密度、服务平台数目也不相同，因此要对不同区分开考虑，故不同区的出警最长时间的设定标准是不同的。 对于第二条，由上面划分的管辖范围，依据问题 3 中的方法算出各个服务平台的工作量， 通过比较，我们可以
14、直观的发现其中的不合理的地方 一些服务平台之间的工作量相差太大，有些节点的出警时间的相对较长，可 以 分 如下情况进行优化： （ 1）某个服务平台的工作量很大，若将其中某些节点划给其它服务平台管理则可达相对均衡状态，但划出的这些节点归为其他服 务平台则会导致出警时间过长，也即该服务平台附近没有其他工作量较小的服务平台，两种矛盾无法调和，此时应该考虑添加一个服务平台。 （ 2）某几个服务平台较为集中，且各自工作量相对较小，而将这些平台管辖区域外的节点调给它时又会导致出警时间过长， 此时可以考虑撤消 （或转移）某一个或几个服务平台来平衡工作量。 通过以上两方面的调整，采用模拟退火算法思想，通过添加
15、和撤消 服务平台，最终工作量的方差达到最小且基本不变，而且每个节点的出警时间均不会有太大差异，这样就得到一个相对较为合理的设置方案。 5.5 问题 5 的分析 当发生 重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点 。我们根据假设，嫌疑犯希望里出事地点 P节点越来越远，而且嫌疑犯所走的路线不会出线回路。这时，我们将 P点当作根，嫌疑犯可能的逃跑路线构成一个树。交巡警便可以根据逃跑路线所构成的树对嫌疑犯进行围堵。 根据图论的知识，借助 MATLAB 与 LINGO 编程便可以得到一个围堵方案。 5 6、模型的建立与
16、分析 6.1 问题 1 的求解 6.1.1 模型的建立与求解 根据“就近原则” 的要求只需要确定 距离每个节点最近的交巡警服务平台是哪个，从而 就可以确定每个交巡警服务平台的管辖范围。 这里我们用到 “ Floyd-Warshall 最短路径算法 1” 。这个算法 通过不停地加入中间点进行矩阵的迭代， 从而 解决有向图中每对顶点的最短路径问题，当我们把每个节点看作顶点时，我们便可以求得每个服务平台的管辖范围 管辖的节点。 由 MATLAB 编程（见附录 1），利用 Floyd-Warshall 最短路径算法 可以得到 A 区 20个服务平台的管辖范围，即每个服务平台所管辖的节点编号。 A 区服
17、务平台的工作量见表 2， 结果见表 3： 表 2 A 区交巡警平台编号 A 区交巡警平台的位置编号 A区交巡警平台的工作量 A1 1 84.7033 A2 2 128.7231 A3 3 58.4864 A18 18 97.9036 A19 19 92.9778 A20 20 38.7462 表 3 A区交巡警平台编号 A 区交巡警平台位置编号 每个交巡警平台所管辖节点编号 A1 1 1、 67、 68、 69、 71、 73、 74、75、 76、 78 A2 2 2、 39、 40、 43、 44、 70、 72 A3 3 3、 54、 55、 65、 66 A4 4 4、 57、 60、
18、 62、 63、 64 A5 5 5、 49、 50、 51、 52、 53、 56、58、 59 A6 6 6 A7 7 7、 30、 32、 47、 48、 61 A8 8 8、 33、 46 A9 9 9、 31、 34、 35、 45 A10 10 10 A11 11 11、 26、 27 A12 12 12、 25 A13 13 13、 21、 22、 23、 24 A14 14 14 6 A15 15 15、 28、 29 A16 16 16、 36、 37、 38 A17 17 17、 41、 42 A18 18 18、 80、 81、 82、 83 A19 19 19、 77、
19、 79 A20 20 20、 84、 85、 86、 87、 88、 89、90、 91、 92 A区各个交巡警平台的相应的管辖范围如图 1所示 （ MATLAB 程序见附录 2） : 图 1（不同管辖范围用不同的颜色标识） 6.1.2 模型的分析 从结果中 可以很直观地看到不同交巡警平台所管辖的周围的节点个数是不同的，从而管辖范围不同，他们的工作量当然也不相同。例如平台 A20 要管辖 10 个节点，而平台 A6 仅管辖 1 个节点，这显然是不合理的 利用最短路径的思想划分的管辖范围会使得服务平台的工作量的不均衡。 6.2 问题 2 的 求解 6.2.1 模型的建立与求解 当遇到突发事件需要
20、对 A 区进行全封锁时， 合理的调度方案应该是使出警时间最长的节点处的出警时间达到最小值，其余的节点处出警时间尽量减小。又由于 警车匀速行驶，所以 路程的长短反映出出警时间的长短 ，故可 用距离来代替时间 考虑。 由于 20个服务平台的交巡警封锁 13个路口，每个路口要有一个平台的交巡警负责，每个交巡警平台最多只 能封锁一个路口， 可以 考虑 用 0-1 规划来解决 。目标函数为 13个路口到各个服务平台的距离的集合，求解目标函数就是对这些距离进行搜索 ， 找出达7 到 13 个一一对应时 的最小距离， 也就是说对所有可选的调度方案，找出每个方案的最大距离，然后从这些最大距离中取出最小值。对于
21、取出的方案， 由于前 12 个对应距离均比这个距离小，所以这个对应就表示完成封锁所需时间的最小值。 借助计算机编程可得结果。 其 LINGO 程序见附录 3，运行结果如下： 以 A7服务平台封锁 29 号出口节点即可找到符合题意的 一种封锁方案 ，并且这个 方案 中的最大距离是所有 可行方案 中最小的，所以说这个结果是最佳的。而其 余的 封锁 时间均比完成该封锁 用时 短，故 只用保证第 29 号出口节点由 A7 服务平台负责封锁， 其余的节点处 可 有不止一 种选择，这里我们 给出一种 相对较佳的 方案作参考 ，见表 4： 表 4 路口号 12 14 16 21 22 23 24 28 29
22、 30 38 48 62 平台号 A10 A16 A9 A14 A11 A13 A12 A15 A7 A6 A2 A5 A4 6.2.2 模型分析 LINGO 程序的最终结果显示只需要将 29号路口由 A7 来封锁，其余路口 在保证 选择与他们距离短于 A7-29 之间的距离的平台的情况下， 尽量选较短距离。即便如此，调度方案也不唯一，这里仅 给出一个 相对较佳的 可行方案。 6.3 问题 3 的 求解 6.3.1 模型建立与求解 为 解决服务平台 工作量 的 不均衡和有些地方的出警时间过长的实际问题，可以考虑添加新的服务平台 来分摊工作量 较大 的服务平台的工作量 ，又由于工作量大小和出警时
23、间在一定程度上有正相关性，故一般也可 同时 减少 出 警时间过长 节点的出警时间。 每个服务平台都有一定的工作量，我们定义工作量函数 i ij jjw d n其表示标号为 i 的服务平台的工作量， jn 为其管辖的节点处的发案率。 节点 i 处的出警时间为 iji dt v 由于 v 不变， it 仅与 ijd 成正相关关系，距离长的地方出警时间相应会长。 ijd 为 节点与管辖其的服务平台之间的距离。 各个服务平台的工作量的均衡程度由各个服务平台的工作量之间的方差 s 来决定。 当我们计划增加 2 至 5个服务平台时，我们最终要使得方差 s 达到最小值时的工作量达到最均衡的状态。 这时便可以
24、确定所增加的服务平台的个数与位置。 对此，我们运用“模拟退火算法 2” 对其进行求解。 该算法 是寻求各个状态点之间的一个均衡的状态。而我们正是要通过增加服务平台的个数使得更个服务平台的工作量达到基本均衡，同时使 得出警时间过长的节点的出警时间得到有效缩短。 MATLAB 程序 见附录 4，运行结果表 5： 8 表 5 新增 服务平台个数 新增服务平台所在节点标号 5 21、 24、 28、 38、 92 5 21、 24、 28、 39、 92 新增平台如图 2： 图 2（其中青色加号 表示新增平台） 6.3.2 模型分析 根据程序运行的结果， 可知在 38 或 39 号节点处增加新的服务平
25、台所得结果差异不大，因此都可以当作 供选方案。 由于退火模型存在普遍的缺陷， 根据所选的“退火系数”t的不同，得到的结果可以有一定的差异，但对问题没有本质上的影响。如 t取不同值时 ， 92这个节点也可不添加服务平台，但也符合时间限制，对工作量均衡也无显著影响，只是上面的添加方案可以更加有效，工作量也相对较小， 即这是一个较佳方案， 故选之。 6.4 问题 4 的 求解 6.4.1 模型的建立与 求解 对现有交巡警服务平台设置的合理性的讨论主要有两个指标来确定 各服务平台的工作量的差异与各个节点的出警时间的长短。 现实生活中不同区的警力管辖范围仅限于该区，只有发生特殊事件时才有跨区合作的机会，
26、因此我们将全市六区分开考虑，每个区的服务平台的管辖范围仅限于该区，那么问题的解 决思路与问题 3有很多类似的地方。 问题的解决过程如下： （ 1）计算各区的服务平台的工作量，及它们的方差大小。计算各个节点处的出警时9 间。 （ 2）根据问题三的方法对每个区的服务平台进行优化。 （ 3）对于服务平台集中且各个服务平台的工作量都不大的情况考虑撤销一个服务平台节约警力资源。 根据求解以上问题的思路，我们把全市划分为 6各区，各个区由 Floyd-Warshall最短路径算法 求得各个服务平台的管辖范围，先通过直观地观察撤销一些明显的工作量过少的的平台，然后由模拟退火算法通过增加服务平台的个数来均衡各
27、个平台的工 作量。 由 MATLAB 编程运行 得到各个服务平台的工作量如表 6,得到结果如表 7： 表 6 交巡警平台编号 交巡警平台的位置标号 交巡警平台的工作量 A1 1 84.7033 A2 2 128.7231 A3 3 58.4864 F9 483 97.9036 F10 484 92.9778 F11 485 38.7462 表 7 增加与撤销平台如图 3 所示： （其中蓝色表示原服务平台，青色加号表添加新平台，红色叉号表撤消平台） 图 3 区号 新增平台所在节点的标号 撤销平台所在节点的标号 A 21、 24、 28、 38或 39、 92 B 120、 147 97、 99
28、C 205、 240、 261、 281、 301、 313 166、 169、 179、 178 D 333、 362 322、 325 E 391、 409、 417、 452 372、 376、 377 F 493、 515 484 10 6.4.2 模型的分析 原方案的设计从时间和工作量上来讲 绝大部分是合理的，只是有些地方设置不太科学。事实上，考虑时间因素和工作量因素占不同比重时 优化 方案也会不同。此处先考虑的是时 间因素，对各个区域的服务平台管辖范围进行划分，然后采用问题 3 中方法给出工作量并得出撤消 和添加 的服务平台 ，然后再以时间限制进行优化检验。当然，采取不同的均衡标准
29、与时间限制也可以有不同的优化方案。 6.5 问题 5 的 求解 6.5.1 模型的建立与 求解 当发生重大案件需要全市的交巡警联合围堵时，交巡警需要对嫌疑犯有可能经过的道路提前进行围堵。将全市的交通网看作一个图，把各个节点看作顶点。根据假设，嫌疑犯希望 离 出事地点 P 节点越远 越好 ，而且嫌疑犯所走的路线不会 出现 回路。因此 ， 与同一个 顶 点相连的 任意两个顶 点不会连通 （即 无圈） ，这样可以 将 P 点当作 树 根， 而 嫌疑犯可能的逃跑路线 则 构成一个树 ，这个树采用广度优先搜索 BFS 的方法得到的 (附录5)。 下面我们用图论的知识对 这个围堵 问题进行求解 3： 假设嫌疑犯可能的逃跑路线所构成的树为 T ，我们的算法如下： （ 1） 把 T 的全部叶删除，得到子树 1T ；若 1T 是一个顶点组成的 ， 算法终 止； 否则转（ 2）。 （ 2）用 1T 替换 T ，转（ 1）。 （ 3）反复执行（ 1）和（ 2）。 对于示意图如下图 3的树，我们先从 2 3 4 6 7 1 0 1 1 1 2 1 3v v v v v v v v v、 、 、 、 、 、 、 、点出发，分
