《交巡警服务平台的设置与调度优化问题》由会员分享,可在线阅读,更多相关《交巡警服务平台的设置与调度优化问题(27页珍藏版)》请在金锄头文库上搜索。
1、交巡警服务平台的设置与调度优化问题Last updated at 10:00 am on 25th December 2020题目 交巡警服务平台的设置与调度优化问题摘要问题一,第一个子问题要求合理分配A区的交巡警服务平台的管理范围,可根据各个 路口到交巡警服务平台的距离建立最短路径模型,利用Floyd算法,结合Matlab得出最终 的各个路口到交巡警服务平台最短距离。在得到的合理分配方案中,部分交巡警服务平台 管理路口较大,最大需要管理10个路口,部分管理路口数较少,最少的为1个路口。具 体结果见正文表 1。第二个子问题要求给出调配警力快速封锁重要通道得调度方案,就需要调配所用时间 最少,而
2、警车的速度是一定的,在解决问题时可以将其转化为交巡警服务平台到13个封 锁路口总的距离最短。因此建立0 1整数规划模型,判断封锁路口是否由交巡警服务平台 Q 进行封锁,列出目标方程和约束条件,目标函数为:i利用 Lingo 软件编程求解,给出了该区交巡警服务平台警力合理的调度方案,完整结 果见正文。第三个子问题要求增设交巡警服务平台,结合出警时间过长以及交巡警服务台工作量 大的问题,提出增设条件,利用Matlab进行模拟,可得到需要在路口编号为28、40、 48、89 增设新的见巡警服务平台。问题二,第一个子问题,要求评判该市现有交巡警服务平台设置方案,可利用改进后 的模糊综合评判方法进行评价
3、,设置3km路口溢出率L等项目为指标,得出全市的交巡警 k服务平台的设置方案不合理的结论,并给出在A、D、F区增加交巡警服务平台的结局方 案。第二个子问题,要求对犯罪嫌疑人设计最佳的围堵方案,需要考虑犯罪嫌疑人在3分 钟及交巡警服务台封锁A区的时间内能否逃出A区,因此需要分类讨论。在封锁全市出口 的情况下,为保证成功抓捕犯罪嫌疑人因满足的条件为:通过Floyd算法,建立0-1规划模型,可得到编号B4交巡警服务台封锁路口 151, 编号B7交巡警服务台封锁路口 153编号为F5交巡警服务台封锁路口 178,最快的封锁 时间为。关键词:Floyd算法Mat lab模拟改进模糊综合评判法0-1整数规
4、划、问题重述背景分析恩格斯在家庭私有制和国家的起源中曾指出:文明国家的一个最微不 足道的警察,都可能比氏族社会拥有更大的“权威”,所以一个国家是不能没 有警察的9。当前我国正处于经济社会转型的变革时期,尽管在总体上看我国社会稳 定,人民安居乐业,但影响国家安全和经济稳定的不确定因素在不断增加本社 会转型所带来的诸多矛盾没有得到及时有效的疏导、缓解和消除。面对这些新 情况、新问题,大力提高我国警力资源效率,是当前公安工作的一个非常突出 问题。而解决这个问题的出路,就是在于最大程度地科学合理配置警力资源。王铁岭、福州市公安局课题组等个人及组织都对此问题进行过研究。而本 文结合前人的思考,给出合理的
5、交巡警服务平台的设置以及优化。问题重述为了更有效地贯彻实施警察的职能,需要在市区的一些交通要道和重要部 位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由 于警务资源是有限的,如何根据城市的实际情况与需求合理地设置交巡警服务 平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课 题。试就某市设置交巡警服务平台的相关情况,建立数学模型分析研究下面的 问题:1、为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件 时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。 对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对 进出该
6、区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封 锁一个路口,给出该区交巡警服务平台警力合理的调度方案。 根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际 情况,拟在该区内再增加2 至5个平台,请确定需要增加平台的具体个数和 位置。2、针对全市的具体情况,按照设置交巡警服务平台的原则和任务,分析研究 该市现有交巡警服务平台设置方案的合理性。如果有明显不合理,请给出解 决方案。如果该市地点P (第32个节点)处发生了重大刑事案件,在案发3分钟 后接到报警,犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯,请给出调度全 市交巡警服务平台警力资源的最佳围堵方案。二、问题分析对
7、于问题一的分析问题一主要分为 3 小问:第 1 小问是合理分配 A 区的交巡警服务平台的管 理范围;第 2 小问是调配警力快速封锁重要通道;第 3 小问是改变现在交巡警 服务平台分布问题,进行增设交巡警服务平台。对于第1小问,可以利用题目所提供的数据画出A区交通网络与交巡警服务平台的分布图。交巡警服务平台管理范围合理也就是交巡警服务平台能在3 分钟内尽快赶到事发路口,相当与 92个路口到 20 个交巡警服务平台求最短距 离。根据最短距离划分交巡警服务平台的管理范围。在本题中利用Matlab软件 编程和Floyd算法就可以算出最短距离,利用所算便可以进行问题的求解。对于第 2小问,要求交巡警服务
8、平台在最快的时间内封锁13个交通要道, 鉴于时间最少,而警车的速度是一定的,只要最后到达封锁路口的警车所经过 的路程最短最小即可,但是所有警车经过的路程与最后一个警车到达封锁路口 的结果是一致的。在解决问题时可以从交巡警服务平台到13个封锁路口的最短 综合距离这方面考虑。利用 0-1 规划,判断封锁路口是否由交巡警服务平台 Qi 进行封锁,列出目标方程和约束条件即可以解决本题。对于第 3小问,增加25个交巡警服务平台的标准可以从2个方面考虑: 一是警车是否能3 分钟到达;二是,能否使交巡警服务平台工作量下降,也就 是降低交巡警服务平台管理范围下的总发案率。本问中可以列出超出管理范围 的路口和高
9、总发案率的地区,根据数据进行分析,并且设定相应的评判标准, 利用Matlab编写相应代码进行求解。对于问题二的分析问题一主要分为2小问,第1小问是根据设置交巡警服务平台的原则和任 务,评判该市现有交巡警服务平台设置方案;第2小问是地点P发生重大事 故,设计最好的围堵方案。对于第 1 小问,因为要评价该市的交巡警服务平台的设置方案,因此可以建立评价模型,不过在现有的模型下,无法寻找合适的评价模型进行求解。而且一些评价具有主观性,因此需要改进现有的模型进行求解。分析发现,评价指标很大程度上就可以表现交巡警服务平台的设置方案是否合理。因此在本文 中,利用改进后的综合评价模型进行评价交巡警服务平台的设
10、置方案是否合 理。对于第2 小问,需要设计最佳的围堵方案,需要考虑两种情况,一是犯罪 嫌疑人在A区被截住,一种就是犯罪嫌疑人在全市被截住,因此需要进行分类 讨论。追捕犯罪嫌疑人的原则是不管动用多大的人力物力都要追捕到犯罪嫌疑 人,在这个前提下考虑如何节省资源。通过查询犯罪嫌疑人所在区域的监控等 方式了解犯罪嫌疑人的车速。根据车速可以判断犯罪嫌疑是否在 A 区。进而利 用0-1 整数规划,建立目标函数可以得到如何在全市快速封锁全市出口。封锁全 市避免了仅仅封锁A区导致犯罪嫌疑人逃掉,同时,在设置约束条件的时候需 要考虑到群众是在3min之后报警的。在这段时间内民警是本可以行动3000m 的,而事
11、实上这段时间是犯罪嫌疑人逃跑的时间,是交巡警服务平台未行动的 时间。综合上诉分析,确立最佳的方案需要考虑多方面因素,既要考虑如何不 让犯罪嫌疑人逃掉,也要考虑如何节省物力和人力。三、模型假设结合本题实际,为了确保模型求解的准确性和合理性,我们排除了一些特 殊因素的干扰,提出以下几点假设:1、警车和犯罪嫌疑人的行车车速恒;2、出警时间只与交巡警服务平台与所发生事故的路口距离有关;3、各个区的交巡警服务平台只管理自己区的路口;4、行车时路况正常,不存在突发意外。四、符号说明为了便于问题的求解,我们给出以下符号说明:各区的各交巡警服务平台承担平均发案率表示交巡警服务平台所在路口节点标号表示需要封锁的
12、交通要道的路口标号超出3km的路口该区总路口全区面积交巡平台编号3 km路口溢出率各区单位面积上人口分布率交巡警平台i到封锁道路j的距离犯罪嫌疑人不能逃走的某一段时间交巡警服务平台最优管理范围内交巡警服务平台到路口的距离五、模型的建立与求解经过以上的分析和准备,我们将逐步建立以下数学模型,进一步阐述模型 的实际建立过程。问题一的建立与求解合理分配交巡警服务平台分配管辖范围A区交巡警服务平台的管辖范围通过A区的路口节点表示,为使管辖范围 合理,就需要考虑各交巡警服务平台到各路口节点距离最短,尽量保证警员可 以在三分钟之内赶到,如果路口节点距离最近的交巡服务平台超过3km,依旧 认为该交巡警服务平
13、台分配为最佳管辖分配。在进行A区管理划分是时,需要画出A区各个路口以及交巡警服务平台 的分布图,根据图像有利于问题的进一步分析。同时需要考虑每两个节点之间 的距离,这方便与后面题目得求解。两点之间的距离公式为:根据两点间的距离公式可以得到A区各个相连路口的距离,并且可以通过 相连路口的距离得到各个交巡警服务平台到各个路口的距离,因此可以得到本 问的最优规划方案。在附件中Excel中全市交通路口节点数据找到1关于A区各个路口的位置 关系,利用Mat lab可以画出A区交通网络与交巡警服务平台的分布图,其中实 心点“ ”表示交叉路口的节点,没有实圆点的交叉线为道路立体相交;星号 “ * ”表示出入
14、城区的路口节点;圆圈“o ”表示现有交巡警服务平台的设置 点。利用Mat lab软件所画图像如下图所示(图1)。图1 A区交通网络与交巡警服务平台的分布图通过上图可以发现部分区域超出交巡警服务平台 3 可到达区域,该部分区域按照就近原则进行分配。为计算各交巡警服务平台到各路口节点的最短距离,利用Floyd算法求解 各路口节点到交巡警服务平台的最短距离,在通过判断各路口节点到交巡警服 务平台的最短距离进行排序,即可得到交巡警服务平台的管辖范围。Floyd算法是计算赋权图中各对顶点之间最短路径,用Dijkstra算法每次以 不同的顶点作为起点,计算从该点出发到其余顶点的最短路径,反复执行n -1
15、次这样的操作,就可以得到从每一个顶点到其他路径的最短路径。先建立无向图,以A区路口节点为图G的顶点,各节点之间为图G相应两 顶点间的边,得图G。对G的每一边e,赋以一个实数w(e),w(e)表示节点之 间的距离,称为e的权,得到赋权图G。赋权图G中指定的两个顶点u ,v间一定存在最小的轨,它的权叫做u ,vi i00间的距离,记作 d (u , v )00赋权图G权的邻接矩阵A:0来存放w(e)。a =g表示i到j没有直接的边相连。ija = w表示i到j的边的长度。ij ij以下为Floyd关于本题的算法步骤:St epl:初始时,S只包含源点,v的距离为0, U包含除v外的其他顶点,U中顶点 u 距离为边上的权;Step2:从U中选取一个距离v最小的顶点k,把k加入S中(该选定的距离就是V到k的最短路径长度);Step3:以k为重新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点 u的距离(经过顶点k )比原来距离(不经过顶点k)短,则修改顶点u的 距离值,修改后的距离值的顶点k的距离加上边上的权;Step4:重复步骤第二步和第三步知道所有顶点都包含在S中。通过Floyd算法,利用mat lab软件得到在3分钟尽量赶到事发地,各个交巡警服务平台管辖的最佳范围,20个交巡警服务平台管辖的路口见下表(表l):表1 20个交巡警服务平台管辖的