当前位置:文档之家› 2011年数学建模大赛优秀论文

2011年数学建模大赛优秀论文

交巡警服务平台的设置与调度的数学模型摘要针对交巡警服务平台的设置与调度问题,本文主要考虑出警速度和各服务平台的工作量来建立合理方案。

对于A区的20个交巡警服务平台分配管辖范围的问题,我们采用Dijkstra算法,分别求得在3分钟内从服务台可以到达的路口。

根据就近原则,每个路口归它最近的服务台管辖。

对进出A区的13个交通要道进行快速全封锁,我们采用目标规划进行建模,运用MATLAB软件编程,先找出13个交通要道到20个服务台的所有路径。

然后在保证全封锁时间最短的前提下,再考虑局部区域的封锁效率,即总封锁时间最短,封锁过程中总路程最小,从而得到一个较优的封锁方案。

为解决前面问题中3分钟内交巡警不能到达的路口问题,并减少工作量大的地区的负担,这里工作量以第一小问中20个服务台覆盖的路口发案率之和以及区域内的距离的和来衡量。

对此我们计划增加四个交巡警服务台。

避免有些地方出警时间过长和服务台工作量不均衡的情况。

对全市六个区交警平台设计是否合理,主要以单位服务台所管节点数,单位服务台所覆盖面积,以及单位服务台处理案件频率这些因素进行研究分析。

以A 区的指标作为参考,来检验交警服务平台设置是否合理。

对于发生在P点的刑事案件,采用改进的深度搜索和树的生成相结合的方法,对逃亡的犯罪嫌疑人进行可能的逃逸路径搜索。

由于警方是在案发后3分钟才接到报警,因此需知道疑犯在这3分钟内可能的路线。

要想围堵嫌疑犯,服务台必须要在嫌疑犯到达某节点之前到达。

用MATLAB编程,搜索出嫌疑犯可能逃跑的路线,然后调度附近的服务台对满足条件的节点进行封锁,从而实现对疑犯的围堵。

关键词:Dijkstra算法;目标规划;搜索;一、问题重述近十年来,我国科技带动生产力不断发展,我国的经济实力不断增强,而另一方面安全生产形式却相当严峻。

每年因各类生产事故造成大量的人员伤亡、经济损失。

尤其是一些大目标点,作为人类经济、政治、文化、科技信息的中心,由于其“人口集中、建筑集中、生产集中、财富集中”的特点,一旦发生重大事故,将会引起惨重的损失。

为保障生产安全、预防各类事故。

我国正在各省市目标点逐步建立交巡警服务平台。

由于警力资源有限,则需要根据城市的具体情况合理地设置交巡警服务台、分配各平台的管辖范围、调度警力资源。

就某市中心城区A 的交通网络和现有的交巡警服务台分布的实际情况,为各交巡警服务平台分配管辖范围,使其在所管辖范围内出现突发事件时,尽量在3分钟内有交巡警到达事发地点(警车的时速为60Km/h )。

如果发生重大突发事件,要调用全区20个交巡警服务台的警力资源,对进出该区的13个要道进行全速封锁,以防罪犯逃走。

其中一个交巡警服务台的警力资源只能封锁一个路口,建立数学模型,给出一套合理调度交巡警服务台警力资源的方案!在现有的交巡警服务台中出现了个服务台的工作量不均衡和有的地方出警时间过长等情况,警务部门计划在该区增加2至5个服务平台,避免出现服务台工作量不均衡和有的地方出警时间过长等情况!就此为警务部门确定要增加平台的个数及位置!根据全市六个城区的具体情况,按设置服务台任务和原则,分析现已设置的交巡警服务台的合理性。

如不合理,给出合理的方案!若在该市的P 点发生重大刑事案件,案发3分钟后警方才接到报警,犯罪嫌疑人已经驾车逃亡。

为了快速收铺疑犯,建立数学模型,利用现有的警力资源,给出一套最优的围堵方案!二、模型的假设1)警车在赶往事发地点途中,交通无阻塞。

2)在各个平台的管辖范围内,在较短时间内最多发生一起突发案件。

3)交巡警在赶往案发地点途中,道路转弯处不影响警车速度。

4)如果案发地点不在道路上,假设该案发地点在离它最近的道路上。

5)在整个路途中,通过各种通讯设备,走的路径都是最短路径。

6)犯罪嫌疑人驾车逃跑时速和警车时速相同。

7)服务台一接到报警就出警,中间没有时间耽搁。

三、符号说明),,(W E V G :该市的道路网络赋权图,其中,V :图的顶点集合;E :图的边集合;W :图的邻接矩阵。

),...,2,1(n i V i :赋权图的第i 个节点标号。

),(i i y x :i V 点的坐标。

),...,2,1(m i E i = :赋权图的第i 条边),(k j i v v e :赋权图中第i 条边的向量坐标ij d :第i 个节点到第j 个节点的长度(i 节点和j 节点相邻)j i Path ,:i 节点到j 节点的路径v :警车行驶时速(h Km /)四、模型的建立与分析4.1.1 管辖范围确定本问题要求根据中心城区A 的交通网络和20个交巡警服务台的位置,对这20个交巡警的管辖范围进行配置,寻找满足条件的路口节点。

将道路网图中,每个路口看作节点,将道路看作图中对应节点的边,各条道路的长度看作对应边的权,所给的城市道路网就转化成了图论中的加权网络图,问题就转化为一个图论问题,即在给定的加权网络图中寻找各服务台在指定时间内能到达的节点,这些节点及以内的区域就是该服务台的管辖范围。

Dijkstra (迪杰斯特拉)算法是典型的单源最短算法,用于计算一个节点到其他所有节点的最短路径。

主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。

本问题就是运用Dijkstra 算法,从交巡警服务台节点出发,收索满足条件的节点。

Dijkstra 基本思想:若使),...,,(10n u u u 最短,就要使),...,,(110-n u u u 最短,即保证从0u 开始到以后各点的路都是最短的。

由图),,(W E V G , 设集合V S i ⊆,i i S V S -= 令n V =||,=i S {u |从0u 到u 的最短路已求出} =i S '{'u |从0u 到'u 最短路未求出}基本步骤如下:第一步:根据附录表中所给的各个服务台与节点的坐标数据,在示意图中标示出来,如图1所示:第二步:考虑到服务台可以管理该服务台自身所在节点,故而1到20号节点就由相应位置所在的服务台管理.第三步:以下计算均以题目所给的表格数据计算,由公式=d )()(j i j i y y x x -+- 求出i 、j 两点间的距离。

根据已知条件,可以求出满足条件的管辖范围为:在保证出警时道路畅通,警车行驶正常的情况下,由题意可知,车速恒为v 千米/小时,出警时间不超过t 分钟,则从交巡警平台到出事地所行使的最大路程为:60/)0(vt L =由题目所给的数据3=t 分钟,60=v 千米/小时。

可得:Km L 3)0(=所以,要使事故发生后3分钟内达到事发地点,则交巡警服务台的管辖范围不应超过3Km ,对于任何一个服务台在3分钟以内都无法到达的节点,稍后另作讨论。

运用MATLAB 求出除自身以外在3分钟以内只有一个服务台可以赶到的节点。

第四步:在3分钟之内有多个服务台可以赶到的节点,取离节点最近的服务台管理该节点,结果如表一所示:第五步:在3分钟没有任何服务台可以赶到的节点,取离节点最近的服务台管理该节点。

具体情况如表二所示:表二3分钟不能到达的路口三分钟不能到达的路口取最近的服务台28 1529 1538 1639 2(16)61 4、6、792 18、204.1.2 要道全封锁方案针对本问题我们在设置方案时,首先考虑时间问题,即要使服务平台尽可能快地封锁13条交通要道。

在分配任务时,充分调动全区20个交巡警服务平台的警力资源,首先考虑全局总体效率最高,封锁总时间最短,即在所有的封锁路线中的最大距离尽可能的短。

再考虑局部效率较高,则必须使服务平台到各自封锁节点的长度和最短。

为此,我们采用目标规划的基本建模思想对此问题进行求解。

第一步:通过MATLAB编程找出13个路口到20个服务平台的映射路径,具体内容见表三。

从中筛选出路程最短的4个服务平台。

为下一步任务分配做准备。

表三距离要道最短的四个服务台交通要道服务台服务台服务台服务台备注12 9 8 7 3 本身有服务台14 13 16 9 11 本身有服务台16 9 8 7 3 本身有服务台21 13 14 11 1222 13 11 14 1223 13 11 14 1224 13 12 11 1028 15 7 9 829 15 7 8 530 7 8 5 638 16 2 9 1748 7 5 6 862 4 3 1 19第二步:因要对进出该区的13条交通要道实现快速全封锁,故我们必须先保证出警时间最短,然后再保证总路程最短,同时还要使各个服务平台的工作量均衡。

经过对表十表数据的分析比较可以得出:28、29号路口较为偏远。

具体情况如表四所示:表四距28,29要道最近的服务台及距离交通要道标号服务台标号距离d28 15 4751.84128 7 8570.21829 15 5700.52529 7 8015.456由于一个服务台的警力只能封锁一个路口,从上表可以看出,调度15号服务台封锁28号路口,7号服务台封锁29号路口,为较优的封锁方案,可以保证总封锁时间最短,总的封锁时间为:vt/=d由以上数据可知m8015=d456.可得时间为:mint。

=015.8其次考虑到局部封锁效率,使服务平台到各自封锁要道的长度和最短。

这就是第三步考虑的问题。

第三步:在前两步的基础上,要想得到服务台到各自封锁要道的路程和最短,就要使服务台到各自封锁要道的路程最短。

但由于一个服务台的警力资源只能封锁一个交通要道,故而服务台标号不能重复。

通过对表三和表十的分析比较,得出一个较优的调度方案,如表五所示:表五调度方案服务平台标号交通要道标号路程(m)路径10 12 7586.585 10-26-27-1216 14 6741.661 16-149 16 1532.540 9-35-36-1614 21 3264.965 14-2111 22 3269.556 11-2213 23 500 13-2312 24 3591.630 12-25-2415 28 4751.8417 15-287 29 8015.456 7-30-298 30 3060.819 8-33-32-7-302 38 3982.185 2-40-39-385 48 2475.825 5-47-484 62 350 4-62总长49123.074.1.3 平台增加个数及位置确定从问题一的第四步我们可以看出A区现有交巡警服务平台设置方案的不合理性,针对现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,我们确定需要增加4个服务平台,具体方案如表六所示:表六平台设置设置平台位置原因28或29 28和29出警时间长39 38和39出警时间长,由39点出警比从2号出警时间短,可以帮2号服务台减少工作量61 出警时间长91 既可以使第92点的出警时间在3分钟内,又可以有效的减少20号服务平台的工作量4.2.1全区服务台合理性分析交巡警服务台设置的原则主要有警情主导警务原则、快速处警原则、方便与安全原则。

相关主题