logo资料库

数学建模交巡警服务平台的设置与调度.pdf

发布时间：2022-05-30 发布人：admin 分类：说明书 资料大小：0.54M 资料格式：pdf 举报 版权申诉
第1页 / 共24页
第2页 / 共24页
第3页 / 共24页
第4页 / 共24页
第5页 / 共24页
第6页 / 共24页
第7页 / 共24页
第8页 / 共24页
资料共24页，剩余部分请下载后查看
    交巡警服务平台的设置与调度 摘要 本文将全市交巡警服务平台的设置抽象为图论的 0-1 整数规划表述，对交巡警平台 的调度抽象为图论的最短路径表述。根据不同的需求建立多目标，利用 MATLAB、 LINGO、EXCEL 分析处理数据、建立并求解模型，最终以图表的形式给出最优方案。 问题一，为 20 个交巡警平台合理分配管辖范围，合理性体现在两个方面：一是让 各个平台到管辖路口的出警时间尽量短，二是让各个交巡警平台的工作量（每个平台所 管辖范围内各路口发生报警案件的次数）尽量均衡。 为了解决这个问题，首先根据实际数据，利用邻接矩阵和 floyd 算法计算出各路口 节点间的最短路矩阵。以每个平台到所管辖路口节点的最长时间最小为主要目标，兼顾 各平台的工作量尽量均衡的目标，约束条件包括每个平台尽量三分钟到达等。 问题二，要求要求给出一个合理的封锁方案，完成对 13 个目标路口的全封锁，即 在交通网络赋权图中选择恰当的交巡警平台，对目标节点进行封锁，使全封锁时间最短。 为了实现全封锁时间最短，建立两个目标，一是实现全封锁的最长时间最小，二是 各个平台完成各自封锁任务的总时间最短，建立指派模型，从而得出最优的方案。 问题三，要求合理的增设 2-5 个交巡警平台，并重新对整个 A 区的平台管辖范围进 行分配。增设平台的目的是尽量实现交巡警 3 分钟内到达所管辖的路口节点，同时使各 平台的出警工作量尽量均衡。这样就建立了一个基于 0-1 规划和多目标规划的模型，但 由于数据量比较大，数据处理时间较长。 问题四，将全市六个区的交巡警平台和所有的路口节点视为一个大的交通网络，解 决方法与 A 区类似。事实上，在全市的 582 个路口节点中共有 138 个是不可能在 3 分钟 内到达的路口节点，并且出警工作量不均衡，所以现有的平台设置不尽合理。 为此，我们进一步分析，通过增设平台并重新分配管辖范围，使问题合理解决。通 过图表可以看出增设平台前后的合理性。 问题五，考虑到案发三分钟后接到报警，同时考虑到制定调度方案和实施封锁相应 的路口也需要一定的时间。为此，我们首先找出接到报警时嫌疑犯可能到达的路口，再 通过进一步分析，确定应该封锁的出入口。然后调动全市 80 个交巡警平台对这些出入 口进行封锁，并给出了封锁方案。 对每一个模型，每一个解决问题的思路，我们都分析了优缺点和改进的方向。 关键词：Floyd 算法 0-1 规划 正负偏差 指派问题 多目标 1
    一、 问题重述 “有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、 交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交 通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相 同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平 台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： （1）附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服 务平台的设置情况示意图，相关的数据信息见附件 2。请为各交巡警服务平台分配管辖 范围，使其在所管辖的范围内出现突发事件时，尽量能在 3 分钟内有交巡警（警车的时 速为 60km/h）到达事发地。 对于重大突发事件，需要调度全区 20 个交巡警服务平台的警力资源，对进出该区 的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出 该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟 在该区内再增加 2 至 5 个平台，请确定需要增加平台的具体个数和位置。 （2）针对全市（主城六区 A，B，C，D，E，F）的具体情况，按照设置交巡警服 务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理 性。如果有明显不合理，请给出解决方案。 如果该市地点 P（第 32 个节点）处发生了重大刑事案件，在案发 3 分钟后接到报警， 犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资 源的最佳围堵方案。 二、 问题分析 本文主要是合理设置交巡警服务平台，各个交巡警平台的合理管辖范围，以及快速 封锁时的合理调度方案。联系到生活中的实际我们需要考虑交巡警平台封锁出入口路的 时间快，所经过的总路径最短，以确定合理的搜索路径。再次考虑到各个交巡警平台管 辖各路口的距离与个数的合理分配，最终判定最合理平台设置方案。最后通过各个交巡 警平台的工作分配不同合理设置和调节平台的位置。 假设交巡警出警时速相同时，各平台到各节点的路径长度长短与其所用时间长短等 价，使交巡警尽量能在 3 分钟内到达事发地，也是寻求路径最短的线路，此外还需考虑 到实际情况中的均衡警力分配以确定交巡警平台的管辖范围。 在一个交巡警平台只封锁一个出入口节点的前提下，A 区的全面快速封锁就是用尽 可能短的时间完成警力的调度。由于各平台是同时移动，所以完成调度的时间是交巡警 平台最后一个到达指定节点时间，最优方案就是这些时间中最短的所对应的方案，同上 由于题目中警车时速不变，那么时间的最优解便变成了距离上的最优解。 对 A 区现有交巡警平台协调管辖范围后，仍有节点不能被相应平台在 3 分钟内抵达， 各平台的工作量也有一些不同，再联系实际增设平台需要资金支持与增加警力配合，故 此我们适当增设新的交巡警服务平台，并对所有平台的管辖范围进行重新分配。 在分析研究全市现有交巡警服务平台设置方案的合理性时。我们将全市六区的交巡 警服务平台和所有路口节点视为一个大的交通网络图，仍旧考虑工作量尽量均衡和距离 最近的原则，其解决方法与 A 区类似。 2
    三、 模型假设 [1]. 假设交通事故只发生在节点，不用考虑本区之外的情况； [2]. 假设每条节点线路只能属于一个交警巡台； [3]. 假设所有道路都是双向且畅通无阻的，警车由最短路径到达事发地点； [4]. 假设相邻两个交叉路口之间的道路近似认为是直线； [5]. 假设每一个交巡警平台的警力只能封锁一个出入口； [6]. 假设警车时速不变，忽略启动时速和制动时速。 四、 符号说明 Djd_ 所有相邻节点之间的距离的 92 阶矩阵。 Ak(i,j) 从节点 i 到节点 j 的路径上所经过的顶点序号不大于 k 的最短路径长度 p2kij 交巡警服务平台 i 到出入口 j 的可行距离 五、 模型一（问题一） 5.1.1 模型一的建立与求解 首先提取出 A 区所有节点的坐标，在没有任何限制下求出任意相邻两节点间的距离， 记为矩阵 d。然后考虑节点之间是否有道路，建立邻接矩阵 ， 考虑这两点之后，建立表示所有相邻节点之间的距离的 92*92 阶矩阵 Djd, (1.1.1) (1.1.2) 其中， (1.1.3) 为了求出任意两节点之间的最短路线，我们采用 Floyd 算法。Floyd 算法的基本思想是： 递推产生一个矩阵序列 ，其中 表示从节点 i 到节点 j 的路径上 所经过的顶点序号不大于 k 的最短路径长度。计算时用迭代公式： (1.1.4) k 是迭代次数，i，j，k=1,2，…，n。 最后，当 k=n 时，An 即是各节点之间的最短通路值。 利用 Floyd 算法，综合以上考虑，得出任意 A 区两节点之间的最短路径，存放于新的矩 3 ijm1,ij(,)0ijmij节点与有道路，节点与无道路111212122212nnnnnnddddddDjdddd…………………的最短路径j与i，相邻节点w没有道路j与i，节点，0ijjidij12,,,,,knAAAA(,)kAij111(,)min((,),(,)(,))kkkkAijAijAikAkj
    阵 Djd 中，此时 (1.1.5) 并且利用矩阵 path 用来存放每对顶点之间最短路径上所经过的顶点的序号。 根据“任意两节点之间的距离小于等于 30”，经计算发现有的节点巡警在 3 分钟内 无法到达，有的节点有多个节点的巡警能够在 3 分钟内到达。再根据节点距离哪个交巡 警平台近就归哪个管辖。 因为 A 区交巡警服务平台即为节点 1-20，所以取矩阵 Djd 的前 20 行记为矩阵 Djd1， 利用 MATLAB 求出 Djd1 每列的非零最小值，找出该值和其所在的行，所在的行就表示属 于哪个交巡警服务平台，存于矩阵 I 中。同时根据现实，节点 1-20 归本身管辖。 （程序详见附录一） 节点分配表 平 台 号 节 点 号 平 台 号 节 点 号 1 2 3 4 5 6 7 8 9 10 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 6 7 30 32 47 48 61 8 33 46 9 31 34 35 45 10 11 12 13 14 15 16 17 18 19 20 11 26 27 12 25 13 21 22 23 24 14 15, 28 29 16 36 37 38 17 41 42 表 5.1.1 工作量分配图 18 80 81 82 83 19 77 79 20,84 85,86 87,88 89,90 91,92 4 路径任意两节点之间的最短，0,ijijwjid
    图 5.1.1 所以虽然能够保证每个节点有距离其最近的巡警平台管辖，但由表 5.1.1 折线浮动 很大看出，各平台的工作量分配很不均衡。 5.1.2 模型一的评价 优点：利用 Floyd 算法，能够容易地算出任意两节点之间的最短距离，代码简单明 确。 缺点：按出警时间最短，即距离最短来分配节点，没有考虑到各巡警服务平台的工 作量是否均衡分配等。 5.2.1 模型一的改进 模型一的计算结果虽然能够回答题中所提问题，但是在解决现实生活中的实际问 题时还是会有一些不足之处。例如：各个交巡警平台的工作量很不均衡。对此，我们对 模型进行改进，利用 LONGO 再一次增加限制条件使得交巡警平台所负责的节点数不大于 7，不小于 3，并改为如下三个目标： 1）尽量在三分钟之内到达； (1.2.6) 2）最长出警时间最短； min max( ) (1.2.7) 3）工作量尽量均衡。 (1.2.8) 约束条件： 5 各平台工作量024681012141234567891011121314151617181920平台序号总发案率1234567891011121314151617181920921jminjtpijijtf201miniiqgmgp
    模型说明： (1.2.6)极小化时间的正偏差，以尽量使得巡警平台在三分钟内到达指定节点； (1.2.7)使得一个交巡警平台到一个节点的最长出警时间最短； (1.2.8)希望保持等式，则同时极小化正、负偏差 gp、gm； (1.2.9)交巡警平台向本身移动是不需要花费时间，属于自己的管辖范围； (1.2.10)交巡警服务平台所负责的节点数不大于 7，不小于 3； (1.2.11)每个节点有且仅有一个巡警平台管辖； (1.2.12)交巡警平台尽量三分钟到达管辖范围的节点； (1.2.13)使得工作量尽量均衡，1.35 是平均工作时间。 tp 、tm ——平台时间最短时间的正、负偏差； gp 、gm ——为使工作量均衡的的正负偏差 ； ——交巡警服务平台 i 是否管辖节点 j； ——交巡警服务平台 i 到节点 j 所需最短时间； ——节点 j 的案发率。 （程序详见附录二） 1 2 3 改进模型节点分配表 4 5 6 1 44 65 79 80 2 39,40 67 74 75 76 78 4 57 60 62 63 66 3 43 54 55 64 68 70 5,49 6 48 50 51 52 56 58 53 59 6 平 台 号 节 点 号 7 8 9 10 7 30 31 61 8 35 37 47 9 32 45 10 33 34 921201201921）13.2.1—（—35.1)12.2.1—（———，3)11.2.1—（—————————1）10.2.1—（———————37）9.2.1（————————，1jiijijijjijijiijijjijgpgmfaanftptmtfffjifjjiiijfijtjfaan
    平 台 号 节 点 号 11 12 13 14 15 16 17 18 19 20 12 25 27 13 23 24 14 21 36 15 28 29 16 38 46 17 41 42 11 22 26 20,82 86 90 91,92 19 69 71 73 81 83 18 77 84 85 87 88 89 表 5.2.1. 改进模型工作量分配图 图 5.2.1. 5.2.2 模型一的评价： 该模型能进一步优化模型，从图 5.2.1.看中的折现平稳，可以看出工作量分配均衡， 并且实现了尽量三分钟内到达，是比较好的优化模型。 六、 模型（问题二） 6.1 模型的建立与求解： 首先通过 MATLAB 将所有平台到每个出入口的最短路径矩阵从各个节点间最短路径 矩阵中提取出来并存储在 Akou.txt 中。 在全面封锁 A 区时，考虑平台警力问题所以一个平台警力只能封锁一个节点，故以 下入 0-1 变量。 (2.1) 对全区的快速封锁即是选择恰当的平台对所有出入口进行封锁时使得全封锁的时 间最短，让完成全封锁的时间最小化即是此问题的优化目标。全封锁时间最短主要通过 以下两个方面衡量： 一是让实现全封锁可能方案的最长时间最小，这是对封锁方案中所有交巡警平台的 要求； 二是在保证实现全封锁可能方案的最长时间最小的条件下，优化调度方案，是的各 个平台完成各自封锁任务的平均时间或是总时间最短。 当这两个层面的优化目标都实现时，对应的封锁方案才是最优方案。我们通过直接 7 工作量051015135791113151719平台序号总发案率系列1).13,1(),20,1(,个出入口节点移动j个平台不向第，第0个出入口节点移动j个平台向第i，第1jijfij
    建立双目标的 0-1 规划，将两个目标加权求和化为单目标的 0-1 规划。 巡警出警时时速不变，所以目标中的时间最短也就是求路径最短。 建立模型如下： (2.1) (2.2) s.t. 模型说明： （2.3）每个平台的约束,表示每个平台的交巡警至多可以抵达一个出入口。 （2.4）每个出入口的约束，表示每个出入口有且只有一个平台的交巡警抵达。 ——交巡警平台 i 是否封锁路口 j: ——交巡警平台 i 到出入口 j 的可行距离. 利用 LINGO 编程求解后，模型（2）的最优值为 542.04 ,其中一次调度的线路距离和 是 461.89，单独一个平台到出入口的最长距离是 80.15. （程序详见附录三） 取值为一的变量 模型的最优调度方案 调度线路距离/mm 39.82 3.50 24.76 80.15 30.60 15.33 8 调度线路 2-40-39-38 4-62 5-47-48 7-30-29 8-33-32-7-30 9-35-36-16 201131}2{miniijjijfkp)}2(maxmin{)13,1(),20,1(ijijjifkp）5.2—（———————}1，0{）4.2（———13,1对,1)3.2（———20，，1i对,1201131ijiijjijfjffijfijkp238,2x62,4x48,5x29,7x30,8x16,9x
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料