2011高教社杯全国大学生数学建模竞赛B题——交巡警服务平台的设置与调度的数学优化模型

三、模型假设
1) 题目所给的数据真实可靠，所有道路均为双行道； 2) 出警时道路恒畅通（无交通事故、交通堵塞等发生） ，警车以恒定时速 （60km/h）行驶正常； 3) 警车行驶的整个路途中，通过各种交通工具，走的路程都是最短路程，转弯 处不需要花费时间； 4) 一个交巡警服务平台的警力能且只能封锁住一个路口； 5) 对于重大突发事件，接到报警后，全区（市）所有交巡警服务平台的警力在 同一时间出发赶往事发地； 6) 各个交巡警服务平台处理各案发事件的时间相等。

（5-2-1）
约束条件见正文中式（5-2-2） ，鉴于此模型难以求解，我们又建立了伪 A-13 模 型，运用匈牙利算法对其进行求解，得到合理的调度方案（见表 5-2-4） 。 针对问题 3，利用之前建立的模型，结合问题一的结果，采用逐步分析法来 解决。 首先， 依次对交巡警服务平台的工作量及出警时间进行分析， 得初步结果； 其次，结合图 5-3-1 进一步分析，得出最优方案，即需要增加平台 4 个，分别设 在节点标号为 29,39,89,69 的路口处。 针对问题 4，将设置交巡警服务平台的原则和任务进行提炼并最终归结为三 个主要的影响因素，借助 excel 数据处理工具加以分析后，对设置不合理的服务 平台提出了解决方案，见下表 5-4-3。 需增设平台的路口节点标号 504,519,204,299,315,285, 240,333,334,390,392,387 需撤掉平台的路口节点标号 322,325,372,376,377 针对问题 5，我们分两个阶段对此问题进行求解：第一阶段，在建立 3min 圈的思想的基础上，又建立 6min 圈，使问题得到了简化；第二阶段我们建立了 一个优化模型（见正文中式 5-5-1） ，最后将结果标注在了地图中，使结果显出 了较好的视觉效果。 最后，我们对双 Min 模型进行了推广，使其更具实际应用性。
表 5-1-3
平台标 号 平台所管辖 路口节点标 号 1 67 68 69 71 73 74 75 76 78 2 39 40 43 44 70 72 3 54 55 65 66 4 57 60 62 63 64 5 49 50 51 52 53 56 58 59 平台警力在路 上花费时间 （min） 0 1.6194 1.2071 0.5 1.1403 1.0296 0.6265 0.9301 1.2836 0.6403 0 3.6822 1.9144 0.8 0.9487 0.8602 1.6062 0 2.2709 1.2659 1.524 1.8402 0 1.8682 1.7392 0.35 1.0308 1.9363 0 0.5 0.8485 1.2293 1.6594 1.1708 2.0837 2.3019 1.5209 平台标 号 6 平台所管辖 路口节点标 号 6 7 30 32 47 48 61 8 33 46 9 31 34 35 45 10 11 26 27 12 25 13 21 22 23 24 14 15 28 29 16 36 37 38 17 41 42 平台警力在路 上花费时间 （min） 0 0 0.5831 1.1402 1.2806 1.2902 4.1902 0 0.8276 0.9301 0 2.0557 0.5025 0.4243 1.0951 0 0 0.9 1.6433 0 1.7889 0 2.7083 0.9055 0.5 2.3854 0 0 4.7518 5.7005 0 0.6083 1.1182 3.4059 0 0.85 0.9849
13 其中，全封锁方案有 A20 个，选择 13 个交巡警平台之后，问题就可以转化为
对 13 个平台的分配问题。可行方案可以看做是对 13 个平台到 13 个出入城区路 口节点的指派问题；同时，最优方案描述为：13 个平台的警力在同一时间各自 前往自己的目的地路口， 最后到达目的地的平台警力所花费的时间在所有方案中 最短。 2.3 问题 3 的分析 问题 3 相当于是对问题 1 所求结果的优化。 对于交巡警服务平台的工作量不均衡问题， 根据附件中的数据“各路口案发 率” ，由问题 1 的结果算出每个交巡警服务平台的总案发率，再结合各平台所管 辖的路口数，由这两个指标来衡量平台的工作量，综合分析后，得出工作量明显 大的平台，在其附近增设平台。 对于有些地方出警时间过长的问题，我们理解为其到达案发地的路程过长 （在“各个交巡警服务平台处理各案发事件的时间相等”的假设下） ，可以规定： 路上行驶时间超过 3 分钟时出警时间过长。在出警时间过长的集中地增设平台。 2.4 问题 4 的分析 交巡警服务平台设置方案的合理性包括两方面内容， 一是服务平台设置个数 的合理性，以确保工作量均衡，一是服务平台设置位置的合理性，以避免出警时 间过长。 根据设置交巡警服务平台的原则和任务， 可将影响交巡警服务平台设置的因 素归结为：交通流量、治安复杂情况、出警时间。其中，前两个因素主要影响平 台设置个数，第三个因素主要影响平台设置位置。 分别对服务平台设置个数和服务平台设置位置的合理性进行分析， 找出其明 显不合理的地方。 2.5 问题 5 的分析 当 P 点发生重大刑事案件后，城区警力尽可能快速出击，封锁交通要道，将 嫌疑人围堵在尽可能小的范围内，从而实现快速搜捕， 减少案件对市区人民生活 的影响。 首先，由于案发距报警的时间间隔是 3min，为了不出任何差错地抓捕犯罪 嫌疑人，警方必须充分考虑嫌疑人的实力，做最不利的估计，即犯罪嫌疑人以最 大时速， 沿直线逃窜， 且不会遇到交通拥堵。 以此来估计出嫌疑人最大逃逸半径， 从而可以在接到报警的时刻立即判断出犯罪嫌疑人的最大行踪范围。 其次， 由于一般出警时间为 3min， 我们需要考虑报警后 3min （即案发后 6min） 交巡警平台调用的人力资源和犯罪嫌疑人的位置。 确保犯罪嫌疑人在一个封闭的 区域内以及围堵的大致地点。 然后，根据地理的因素，我们需要决定出围堵的路口和就近的交巡警服务平 台（用来参与围堵犯罪嫌疑人的任务） 。 最后，以参加围堵的交巡警服务平台的警力能否在 3min 内到达围堵路口来 决定围堵方案。
其中， a 1,2,3，……，20； b 1,2,3，……，92。 ( 二) 对于一个路口，分配其所属的管辖平台
* TAb Min{T1b , T2b ,, T20b }
（5-1-1）
（5-1-2）
其中， b =1,2，……，92；式（5-1-2）右边的结果可将平台 A 的标号确定， 也即确定路口 b 所属的管辖平台。 5.1.3 模型的求解 [4] 利用 floyd 算法 可以求出各个路口间的最短路径上花费的时间，结果为 92 92 矩阵，从中挑选标号为 1 至 20 的列记录，结果为 20 个平台分别到 92 个 路口的最短路径上花费的时间，是 92 20 矩阵，至此得到式（5-1-1）的求解结 果，见附表 5-1-2。 [3] 利用 matlab 编程 求解式（5-1-2） ，程序见附录 5-1-1，结果见表 5-1-3。 5.1.4 结果分析 由上述结果可看出， 在案发当时交巡警服务平台即接到报警并立即派出警力 前往的情况下，仍不能保证在 3 分钟内有交巡警到达事发地的路口有 28,29,38,39,61,92 共 6 个； 管辖范围仅有本路口自己的平台有 6,10,14； 平台 20,1,5 的管辖路口数较多，分别为 10 个，10 个，9 个。 由此可看出存在交巡警服务平台的工作量不均衡和有些地方出警时间过长 的问题，我们在问题 3 中对此问题进行详细研究。
二、问题分析
2.1 问题 1 的分析 此问题属于优化聚类问题，研究此问题的目的是：当某地出现突发事件时， 尽量能在 3 分钟内有交巡警到达事发地，并且越快越好。 假设只在路口发生突发 事件，因此问题转换为：分别以 A 区的 92 个路口为研究对象，当某路口发生突 发事件时，调度该区哪一个平台的警力时可以最快到达该事发地。 解决此问题的两个优化为：20 个平台的警力分别到达 92 个路口的最短路优 化；对于一个路口，20 个警力分别走最短路到达此路口的最短路优化。在所有 警车时速恒定的情况下，最短路优化等价于最短时间优化。 2.2 问题 2 的分析 此问题类似于运筹学中的指派问题，研究此问题的目的是：找出调度该区 20 个交巡警服务平台（简称平台）警力的最佳调度方案，以求在重大突发事件 发生时能够对进出该区的 13 条交通要道（即路口）实现快速全封锁。在理想的 情况下（一个平台的警力能且只能封锁一个路口） ，问题转化为：对 20 个交巡警 平台中的 13 个进行指派，实现对进出该区的 13 个路口快速全封锁。
t ij ：从路口节点 i （或 j ）到路口节点 j （或 i ）所花费的时间；
v ：警车时速， （60km/h） ；
Tab ：从交巡警服务平台 a 到路口 b 的最短时间； Tnab ：从交巡警服务平台 a 到路口 b ，走第 n 条路所花费的时间， n 1,2，……，
m ；其中， m 为从交巡警服务平台 a 到路口 b 的总路径数；
关键词： 交巡警服务平台 优化模型 Floyd 算法 匈牙利算法
一、问题重述
“有困难找警察” ，是家喻户晓的一句流行语。警察肩负着刑事执法、治安 管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在 市区的一些交通要道和重要部位设置交巡警服务平台。 每个交巡警服务平台的职 能和警力配备基本相同。 由于警务资源是有限的， 如何根据城市的实际情况与需 求合理地设置交巡警服务平台、 分配各平台的管辖范围、 调度警务资源是警务部 门面临的一个实际课题。 根据某市设置交巡警服务平台的相关情况， 我们需要建立数学模型分析研究 如下问题： 问题 1：根据附件中该市中心城区 A 的交通网络和现有的 20 个交巡警服务 平台的设置情况示意图及相关的数据信息，为各交巡警服务平台分配管辖范围， 使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时 速为 60km/h）到达事发地。 问题 2：针对 A 区，如果发生重大突发事件，需要调度全区 20 个交巡警服 务平台的警力资源，对进出该区的 13 条交通要道实现快速全封锁，给出该区交 巡警服务平台警力合理的调度方案。 问题 3：针对 A 区，根据现有交巡警服务平台的工作量不均衡和有些地方出 警时间过长的实际情况， 拟在该区内再增加 2 至 5 个平台，确定需要增加平台的 具体个数和位置。 问题 4：针对全市（主城六区 A，B ，C，D ，E，F）的具体情况，按照设置 交巡警服务平台的原则和任务， 分析研究该市现有交巡警服务平台设置方案的合 理性。对于明显不合理的情况，需要给出解决方案。 问题 5：如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警， 犯罪嫌疑人已驾车逃跑。给出调度全市交巡警服务平台警力资 源的最佳围堵方案，以求快速搜捕嫌疑犯。