《交巡警服务平台的设置与调度问题数学建模论文》由会员分享，可在线阅读，更多相关《交巡警服务平台的设置与调度问题数学建模论文（19页珍藏版）》请在金锄头文库上搜索。
1、1交巡警服务平台的设置与调度问题摘要本文采用图论和规划理论建立数学模型，解决交巡警服务平台的设置与调度的问题，运用 Floyd 算法在 MATLAB 软件求最短路径及最短距离矩阵作为建模和计算的基础。问题一：A 区（1）建立 0-1 规划模型分配各平台的管辖范围，发现存在未被分配的节点，再对规划模型进行改进，得到所有平台不重不漏的分配方案。（2）用任务指派模型解决交巡警服务平台警力调度，以实现全封锁的时间最短和所有平台总路程最短为目标函数，得到实现 13 个出入口快速全封锁的时间为 8.01min，调度方案：表 1 A 区平台调度方案平台 2 4 5 7 8 9 10 11 13 14 15
2、16出入口 38 62 48 29 30 16 22 24 23 21 28 14（3）建立双目标规划模型解决增加平台问题。目标一：用比例系数将工作量量化，工作量的均衡即等价为各个平台工作量的差值最小；目标二：20 个平台交巡警前往案发节点的最长路程与 3km 差值尽量小，利用 LINGO 求解得新增平台个数为 4，设置在节点 29、39、62、91。问题二：（1）定义合理性指标为任意两个平台工作量差值的绝对值，此值越小，则平台的设置越合理；反之，则越不合理。当出现不合理时，则采取在不合理区中增减平台来调节，不合理平台解决方案如下：表 2 不合理平台设置的解决方案区域 A B C D E F平
3、台总数 20 18 65 20 45 45（2）首先证明最佳围堵方案的存在性，再以 P 点为圆心，以罪犯 3 分钟逃跑的路程为半径形成一个包围圈，在包围圈内选出若干个路口，再以这些路口为圆心，10t 为半径形成若干个包围圈，交巡警赶往这些路口围堵罪犯，围堵方案如下：表 3 全市围堵方案路口 15 151 153 177 202 203 235 236 578 317173 93 95 177 175 180 16 15 485 17896 479 181平台382路口 325 328 332 362 387 418 483 541 572 264平台 324 327 380 323 100 3
4、75 478 476 484 182关键词：0-1 规划模型 任务指派模型 双目标规划 Floyd 算法 2一 问题重述为更有效地实施警察职能，需要在市区交通要道和重要部位设置交巡警服务平台，每个平台的警力配备基本相同，由于警力资源有限，如何根据某市实际情况解决以下问题：问题一：1、根据该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况及相关的数据信息。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时速为 60km/h）到达事发地。2、对于重大突发事件，如何调度全区 20 个交巡警服务平台的警力资源，对进出该区的
5、13 条交通要道实现快速全封锁。 （一个平台的警力最多封锁一个路口）3、由于现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。问题二：1、针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。2、如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给最佳围堵方案。二 模型假设1. 假设各交巡警服务平
6、台分配管辖范围的边界只为路口节点，2. 假设一个平台的警力只能封锁一个出入路口；3. 假设警察只到报案节点处理案件；4. 假设当案件发生时，交警会选择平台到案发节点之间最短的线路前往案发地；5. 假设警察出警一次只能处理一个突发案件；6. 假设每辆巡警车和犯罪嫌疑人的车行驶中速度保持匀速且车速均为60km/h；三 符号说明定义 符号说明3四 模型准备4.1 邻接矩阵 N邻接矩阵 N 中元素为 ，若 1 表示对应的平台 与节点 直接连通，ijaijivj0 表示对应的平台 与节点 未直接连通：ijaivj215267921020010vvNvLLMML4.2 最短路径矩阵 R任意两节点之间可能不
7、止一条路径，求任意两节点的最短路径是建模的基础。依据邻接矩阵 N，运用 MATLAB 软件求解出任意两点的最短路径，构建出最短路径矩阵 R，见附录 1。4.3 最短距离矩阵 D每一条最短路径对应一个路程值,我们以上述最短路径矩阵 R 为参照，构造出对应的最短距离矩阵 D，若以 A 区为例，则其最短距离矩阵 ，92()ijDsivA 区中第 i 个节点（i=1,2,3，92）ijsA 区第 i 个节点到第 j 个节点的最短路径的路程iSA 区第 i 个平台管辖范围内所有路线的路程之和A 区所有平台管辖的各线路的路程之和；v车速（10 百米/min)m第 m 个节点的发案次数（m=1,2，92）i
8、jx0-1变量处理一次突发事件的工作量等价于行驶的路程iM第 i 个平台的总工作量psp 点到全市各出口的距离4表示第 i 个节点到第 j 个节点的最短路径的路程（i，j=1,2，92） 。ijs则矩阵 D 表示如下： 01.9384.96218074.6.298071 LMM4.4 变量转换题目要求尽量能在 3 分钟内有交巡警到达事发地，将时间变量转化为路程变量。由于警车的时速为 60km/h，是固定值，即要求事发地到其所属的平台距离小于 3km。五 模型分析建立与求解5.1 问题一5.1.1 交巡警服务平台分配管辖范围的确定（1）问题分析为各交巡警服务平台分配管辖范围，使其在所管辖的范围内
9、出现突发事件时，尽量能在 3 分钟内（即最大距离为 3km）有交巡警到达事发地，结合 0-1规划模型及图论的相关知识确定各平台管辖范围。（2）规划模型决策变量：0-1 变量 ，若第 i 个平台管辖节点 j，记为 =1，否则ijx ijx=0；ijx约束条件：1. 任一个节点 m 至多由一个平台管辖，即有 ；20121,9imxL2. 到达突发事件点的时间小于 3 分钟，等价为路程小于 3km，即有， 3ijxs目标函数：平台所管辖范围之和尽量小。综上，得到 0-1 规划模型如下：52091201min3. 2,90,1ijijijimiijSxsstxL（3）模型求解参照邻接矩阵 N 和最短距
10、离矩阵 D，并利用 MATLAB 求解出各平台管辖的节点，结果如下表：表 4 各平台管辖范围初始方案分析上表可发现以下两个问题：1.共有 6 个节点任何平台都不能在 3 分钟之内到达，分别是：节点28，29，38，39，61，92，这些节点没有归入任何平台的管辖范围，是由于 3分钟内到达案发节点的约束过严。分别算出与这六个点距离最近的平台的路程，得到它们中距离最大值为 5.7。为使所有节点都有平台管理，将模型的约束条件 放大为 ；3ijxs5.7ijxs2.有些节点分布过于密集，可能被不止一个平台来进行管理，导致不知将这些节点归入哪个平台的管辖范围，例如平台 4、5 都管理节点 58，得到改进
11、6后的规划模型： 2091201min5.7.,ijijijijiijSxsxsstx至此，可以得到改进后的各平台管辖范围： 表 5 各平台管辖范围改进方案管辖节点 68 69 71 73 74 75 76 78平台 1最短路程 1.21 0.5 1.14 1.03 0.63 0.93 1.28 0.64管辖节点 40 43 44 70 72平台 2最短路程 1.91 0.8 0.95 0.86 1.61管辖节点 55 65 66平台 3最短路程 1.27 1.52 1.84管辖节点 60 62 63 64平台 4最短路程 1.74 0.35 1.03 1.94管辖节点 50 51 52 53
12、 56 58 59平台 5最短路程 0.85 1.23 1.66 1.17 2.08 2.3 1.52管辖节点 32 47 48 61平台 7最短路程 1.14 1.28 1.29 4.19管辖节点 46平台 8最短路程 0.93管辖节点 34 35 45平台 9最短路程 0.5 0.42 1.09管辖节点 26 27平台 11最短路程 0.9 1.64管辖节点 25平台 12最短路程 1.79管辖节点 21 22 23 24平台 13最短路程 2.71 0.91 0.5 2.39管辖节点 28 29平台 15最短路程 4.75 5.7管辖节点 36 37 38平台 16最短路程 0.61 1
13、.12 3.41管辖节点 41 42平台 17最短路程 0.85 0.98管辖节点 80 81 82 83平台 18最短路程 0.81 0.67 1.08 0.547管辖节点 77 79平台 19最短路程 0.98 0.45管辖节点 84 85 86 87 88 89 90 91 92平台 20最短路程 1.18 0.45 0.36 1.46 1.29 0.95 1.3 1.59 3.59（3）结果分析分析上表，发现各平台管辖范围的分配存在不公平：有些平台管理很多节点，有些平台只管理自身所在的节点。以平台 1 和平台 14 为例，平台 1 要管理21 个节点（含自身） ，且这 21 个节点每天
14、的平均发案总次数为 20.9，平台 14只管理本身节点，且它的每天发案次数为 2.5。因此，模型还需进一步改进。5.1.2 交巡警服务平台警力合理的调度方案(1) 问题分析对于重大突发事件，要设计出该区交巡警服务平台警力合理的调度方案，即调派全区 20 个平台中的某 13 个对交通要道的 13 个出入口实现快速全封锁，并做到最后一个到达出入路口的时间尽量短（或路程尽量小） ，采用任务指派模型来解决这一问题。(2) 建立模型引入 0-1 变量 ，若调派平台 i 去封锁出入口 j，记 ，否则记 。ijx 1ijx0ijx每个平台最多只能被调派到 13 个出入口之一，一个路口只能被一个平台封锁。应满
15、足两个约束条件： 1. ， ijx 13ijjx20.,1i2. ， 201iji .,i要做到快速全封锁，要求最后一个到达封锁出入口的交警平台所用时间最短。对于某个平台 i，将其调派到与它路程最短的出入口 m，此路程即为 ，ims则要求这 13 个路程中的最大值最小。目标函数： min1,20,12,4,6ixsiLL但仅在满足最后一个到达封锁出入口的平台所用时间（或路程）最短的目标下，各平台的调度方案也是不唯一的，即完成快速封锁的平均时间不一定最小，为使调度方案更加优化，要求各调度平台的总路程最短，即 in,12,4,6imxsL综上，此问题的 0-1 规划模型为： 13201min,2,
16、0,14,62,48. 1,2,19,200,imiimii imxsixst ixLL（3）模型求解利用 LINGO 软件求解上述规划模型得到了最优的调度方案(附录 3)，8将最优调度方案结果列表如下：表 7 重大事件平台的调度方案平台 调往节点 时间（min）2 38 3.984 62 0.355 48 2.487 29 8.018 30 3.069 16 1.5310 22 7.7111 24 3.813 23 0.514 21 3.2715 28 4.7516 14 6.74由上表可得实现 13 个出入口的快速全封锁的时间约为 8.01min。5.1.3 增加平台的具体个数和位置1.问题分
