帮写交巡警服务平台的设置与调度的设计方案数学建模论文

xs 742 0

摘要

由于平面区域不能用圆来不重不漏地覆盖,我们采用正六边形来覆盖,但根据道路口疏密状况和人口数量、区域面积的差异,最后决定对于不同区域采用不同尺寸的正六边形,来覆盖城区各道路的方法来进行各个交巡警服务平台的管辖范围的初次预分配,对于初次预分配的结果按各个道路口到各服务平台的最短路的里程乘以发案率的和,得到各个服务平台的总工作量。按相邻区域内服务平台工作量相当的标准进行调整,用Dijkstra算法求得那些重复包含和漏掉的路口,及那些距离邻近的路口节点重新分配到邻近的正六边形内,从而得到最终的管理范围。由于要力求工作量均衡,就目前的服务平台而言数量不足,通过采用最短路的选址方法来确定,应就需再增加3个服务平台,具体位置分别在标号为

29、

72、90的三个路口。

对于重大突发事件,需要调整全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁,采用最优化及规划法得到了调度方案。

根据六个区人口密度,交通路口的疏密程度不同的现状。采用与A区相同的方法来计算,发现多个区的不同交巡警服务平台的工作量相差悬殊,极不平衡。这说明若仅考虑路程和发案率及仅坚守自己的城区的调度方案是不合理的,应将六个区的各个服务平台的管辖范围适时作出调整,既有分工又要注意合作,协同作战,要有全市全局的思想和行动。

如果该市地点P处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。我们可以求得一个半径为2km、P点为圆心的圆域,对于这个区域内的服务平台,要求采用追的办法,赶向P点,对于圆周外的服务平台,要求其派车堵住相应的路口,采用堵的策略。

本文的方案是静态的,而警车始终在服务平台内,没有考虑到实际警车在返程途中的情形。可以采用GPS定位与先进的通讯手段,采取动态发布出警信息给警车,让其根据自己所处的位置,随时调整出警的路线,这样更能高效地完成自己的职责。

关键词

服务平台、初次预分配、Dijkstra算法、调度

1一、 问题重述

已知:“有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能,需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的,如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

求解:

(1)附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图,相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警(警车的时速为60km/h)到达事发地。

对于重大突发事件,需要调度全区20个交巡警服务平台的警力资源,对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口,请给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况,拟在该区内再增加2至5个平台,请确定需要增加平台的具体个数和位置。

(2)针对全市(主城六区A,B,C,D,E,F)的具体情况,按照设置交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案(参见附件)的合理性。如果有明显不合理,请给出解决方案。

如果该市地点P(第32个节点)处发生了重大刑事案件,在案发3分钟后接到报警,犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯,请给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二、 模型假设

1. 假设出现突发事件时,警车总是在交巡警服务平台内,即出发地总是交巡警服务平

台;

2. 平台内有足够的警车可供调用(A区每个服务平台有5辆警车,B区有9辆等);

3. 本模型中仅考虑出警的问题没有考虑到达了事发地处理时间和返程等问题;

4. 假设突发事件在各个道路上的发案率就是其路口的发案率;

5. 假设交巡警在接到报警后,以最短路径到达事发地点。

三、符号说明

d: 表示任意两点(xm,ym)、(xn,yn)之间的距离;

wi: 第i个服务平台的工作量,(i1,2,,20);

ci: 第i节点的发案率;

wj: 第j个交叉路口到它管辖的平台的最短路;

Bi: 第i个服务平台的总工作量;

Lvi: 与它连通道路中的两个节点之间的距离;

tmax: 13个交通要道全部被封锁所需的最大时间;

2Q(i): 第i个服务平台所覆盖的节点集合。

C(i): 集合Q(i)中元素之和;

L(k): 第k个区域内所有节点,kA,B,C,D,E,F。

四、问题分析

对于问题

(1),如何为A区交巡警服务平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在3分钟内有交巡警到达事发地。

我们按常规思考方法是:以服务平台为中心,以3分钟警车所走的路程为半径画圆,由题意知警车速度为60km/h,即D=3km,即以各个服务平台为中心以D=3为半径划分管辖范围(见图一),

这种作法没有实际意义,重复率太高,另外也没有考虑每个路口的发案率.我们必须另找办法,从相关知识有,对于平面内的一区域,若用圆来划分是无法实现的,我们可以用正六边形来划分. 图1 用圆来初步覆盖区域图

图3

图2

但由于具有地理位置和道路的变化,发案率的不同,我们不可能在A区(全市范围)用完全大小尺寸的六边形来划分,我们可以根据到路口的疏密程度在不同的地域选用不同大小的六边形来划分。

3由附件2中的数据,经过20个平台之间的直线距离的计算,从而确定了以稠密区域以2km为半径作六边形,在稀疏区仍以3km为半径作六边形初次预分配得到图4。

图4.以正六边形为半径覆盖各个节点

这样便产生如下的问题:

(A).同一个路口包含在两个以上的六边形中,我们称为重点;

(B).某些路口不包含在任何一个六边形,我们称为漏点.

如何解决这两个问题呢?对于问题(A)我们采用dijkstra算法分别来求这些重点到包含它的六边形中心(平台)的最短路,比较大小后取最小的值则为其所管辖的范围,对于(B)我们求出那些漏点与它邻近的正六边形的中心(平台)的最短路值的比较,选最小为其所管辖范围。

五、模型准备

首先我们对A区域交通网图进行处理,假如以各个服务平台为正六边形中心,以3cm为半径画正六边形,对A区交通网内的节点进行初次预分配,将每个平台覆盖的节点运用dijkstra算法求最短路,首先假使每个平台都可以处理任意大的工作量,将每个节点划分到离它最近的那个平台内。划分之后结果发现某些平台的工作量过大,而有些平台则是闲置的。对此我们将某些工作量过大的平台内的节点向周围工作量小的节点进行调配,在调配之后使其每个服务平台的工作量都相当,对于划分过程中所漏掉的一些地方,则可将其强行划分归其相邻且工作量未达到饱和状态的平台。

我们在案发率高、人口稠密,且工作量已达饱和状态的平台附近增加平台,因为这里的原有服务平台已无暇顾及周围的某些区域,还有再将3分钟内交巡警所到达不了的节点附近增加交巡警服务平台。

六、模型建立与求解

问题一:

5.1交巡警服务平台分配管辖范围问题

用公式:

(1)

计算出A区内相邻两点之间的距离d,从而得到各路线的权值。

4 d(xmxn)2(ymyn)2

Dijkstra算法用于求指定两点间的最短路,或从指定点到其余各点的最短路。以各个平台为六边形的中心,分别以半径为3厘米和半径为2厘米在题目中给出的附表1中作正六边形,得到以平台为中心的覆盖图(见图4)。用Dijkstra算法(我们用matlab编写的函数Dijkstra(w,start,MAX)来具体实现,程序见附件)计算出每个六边形内各点到平台的最短路。在图中有许多点被多个平台覆盖,我们将这些点分配到离它最近的那一个平台内。我们用公式

Biwj*cj(n为该平台包含的节点数) …

(2)

j1n

得到各个平台的管理区域(见附表2)。

由表中数据可见划分之后结果发现某些平台的工作量过大,而有些平台则是闲置的。对此我们将某些工作量过大的平台内的节点向周围工作量小的节点进行调配,在调配之后使相邻的几个服务平台的工作量大致相当,得到下表的分配方案:

5.2对A区的13个进出该区的节点进行堵截问题

首先对13个节点进行分析,利用任意两节点间的距离公式

(3)可计算出每一个出口到他周围的几个平台间的最短路。为了遵循在最短时间内封锁A区的13个进出口节点原则,但是每一个平台最多封锁一个出口,所以要选出13个平台和他所封锁的节点为13对。我们为了使这13组中相距最远的一组所需时间最短,利用特定的程序可以得出以下的结果:

5

表二:最优堵截方案表

出口节点标号 12 14 16 21 22 23 24

最优堵截平台标号 10 16 9 14 11 13 12 堵截所花时间(分) 7.587 6.742 1.533 3.265 3.27 0.5 3.592

出口节点标号 28 29 30 38 48 62

最优堵截平台标号 7 15 5 2 6 4 堵截所花时间(分) 8.867 6.13 3.213 3.982 2.506 1.05 由以上结果得出:tmax8.867分钟

5.3增加平台使其设置方案更加具有合理性

在问题1.1中为了尽量平衡各个平台的工作量,进行调整之后任然有几个平台的工作量过大的情况出现。可以利用特定的方法加入几个平台使其各个平台工作量趋于平衡,

图5 察

P*(vi,v69),P*(vi,v71),P*(vi,v72),P*(vi,v73),P*(vi,v74),把这5个距离中最大的数称为顶点vi的最大服务距离,即为L(vi)。 V,E,可以看出图5是一个连通无向图,记为G任取,viV(i69,71,72,73,74) 考vi与V中其它顶点间的最短(也称为距离):

求出图5中各点间的距离,如图6所示,这样就可以把每个顶点vi对应的最大服务距离L(vi)求出来。

69到各顶点的距离就是表第一行各数,它们中的最大的是19.4,所以L(v69)19.4,其实他各点的最大距离为:

L(v71)13,L(v72)11.4,L(v73)19.4,L(v74)12.5

6

由于i,所以把平台建立在节点72(418,347)上。

用同样的方法计算可得在节点90(440.5,381.5)和节点29(246,337)处也应建立平台。通过数据分析得出在此节点上建立平台后它的工作量与周围各平台相比趋于平衡。

即应在A区再加3个交巡警服务平台,分别为29(246,337),72(418,347),90(440.5,381.5)。在图6中的红色五角星即为新增平台。

min{L(v)}11.4i

图六:新增加的三个服务平台 注:上图中红色五角星所在的区域,就是要增加交巡警服务平台的区域

问题二:

5.4全市交巡警服务平台合理性分析

根据交巡警服务平台的原则和任务,可以得出A区的管辖效果指标:

1.覆盖率

一段时间,第i个交巡警平台所覆盖的节点集合为Q(i),该交巡警服务平台的覆盖率f(i)为该平台覆盖的节点之和C(i)与该区域内所有节点L(k)的百分比:

C(i)f(i)

L(k)

7

对比A,B,C,D,E,F区的覆盖率,可以发现B,C,F区的覆盖率高,即区域内交巡警服务平台的数量少,则每个平台覆盖的节点个数多,此方案就不合理。

2.范围

任意一个交巡警平台(i1,2,,20)I能在规定时间内,由当前位置出发,所能覆盖的节点集合Q(I),Q(I)中所有直道的长度之和称为该平台的覆盖范围,其值可以由平台与区域面积的比来权衡。可以分析比较A,B,C,D,E,F区的覆盖范围的大小。

区。即就是相对于各区域内的区域面积,其内的平台个数远远小于A区。考虑到D区和E区的人口数量多,在其内更容易发生事故和各种案件,因此此交巡警平台设置方案不合理。

有上述两种情况的分析可得解决方案:应该在B,C,D,E,F区增加相当数量的交巡警平台。

5.5对P点进行围堵方案

由于警车在行驶中,有警鸣声开路,即行驶过程中的阻碍减少,道路畅通(阻碍可以忽略不计)。但是逃犯由于心理因素,车辆因素和道路的阻碍原因。在分析此问题时,我们假设出警时的反应速度相对于影响逃犯逃跑的负面因素对逃跑造成的时间影响可以忽略不计。即警车的速度是大于逃犯的逃跑速度的,由警车的速度为60公里每小时假设逃犯的逃跑速度为40公里每小时。

在3分钟内,逃犯已经跑出的路程为2千米,即我们在图中以2厘米为半径,以32点为圆心画圆得到下图:

由图可知发案3分钟后接到报警,嫌疑犯最远能逃跑的点在图中的圆内,他不可能出到圆外的点。即在接到报警后各平台立即出警对与圆相接的各线路进行有效地堵截。

图七 由上图可以看出在29,15,10,5,6,3这些平台处就地进行封锁。在封锁之后逃犯的逃窜

路线只有从36和48节点处逃出包围圈。

当他从36节点逃窜时用离36最近的平台16处派调警力对其封锁

4*1000.4(分钟) w364他所用的时间为t1000

即在接案后0.4分钟警方就可以到达36节点进行堵截。逃犯从32点到36点的最短路为26.3,他所用的时间为3.9分钟。由于3.9-3=0.9>0.4所以16平台可以在逃犯赶到之前到达36点进行堵截。

当他从48节点逃窜时用离48最近的平台4处派调警力可对其封锁。

即当逃犯从48出来经过61,66,62进行逃窜时平台4经62到61处进行堵截,经过 8

计算逃犯到60所用时间为4.15分钟,平台4经62到61处进行堵截所用时间为0.99分钟。所以4平台可以在逃犯赶到之前到达61点进行堵截。

即最佳堵截方案为平台29,15,10,5,6,3这些平台处就地进行封锁,用平台16封锁36节点,用平台4封锁61节点为最佳堵截方案。在圈内的点用7,8,9三个平台的警力进行围追。即在大的范围内进行围追堵截,最终将逃犯所在的范围缩小到最小。

七、模型的误差分析

1.本模型只考虑了事故发生在节点的情况,忽略了在两个节点中间发生事故时的情况。

2.此模型只考虑了静态的情况,而没有考虑在处理完前一事件的返程中又接到新的报警时的情况。

3.本模型都是以最短路来考虑解决问题,实际当中警车可能做不到按最短路来进行出警,从而产生误差。

八、模型的推广与评价

该模型不仅适用于交巡警的巡逻方案,对社会治安防控、国庆治安巡逻方案,和我们对旅游路线的规划、公交线路规划都具有指导作用。该模型能够对已知相关数据的城市路网,进行合理行车区域规划,合理选用给出的优化算法,可以实现高效行车,使车辆与城区均得到较好的交通效果。

本文在建立模型时,首先较为深入地分析了模型本身涉及到的一些量和关键因素,在此基础上,建立一个理论模型来入手,建立了此模型。

当然,本文也有较多的改进之处,模型忽略了较多因素,是在理想情况下获得的近似解;并且在对图形区域划分中限定了较为苛刻的划分标准,从而影响了模型的推广性,;同时,许多模型都是自己独立建立的,可能求解效果并不明显,仍然存在一些误差,但总的来说,还是具有较好的实际操作价值和科学指导意义的。

九、参考文献

[1]徐晓丽,浅谈交巡警执法规范化的重要性及其路径思考,法制与社会,2011.08。

[2]张俭,大城市建立街面动态管理巡逻勤务机制的思考与探索,公安研究,2001,第3期。

[3]姜启源,谢金星,叶俊.数学模型(第三版)[M].高等教育出版社,2003

[4]西工大数模委员会.数学建模简明教程[M].北京高等出版社,2008

[5]王景存,张晓彤,陈彬,陈和平.一种基于Dijkstra算法的启发式最优路径搜索算法[J],《北京科技大学学报》,2007.3

[6]刘锋,数学建模,南京大学出版社,2005

[7]胡运权,运筹学教程(第三版),清华大学出版社,2007.4

十、附件

附表1:相邻两节点间的距离(道路的长)

9

10

附表2:初次预分配的各平台工作量

11

12


标签: 帮写交巡警服务平台的设置与调度的设计方案数学建模论文

发布评论 0条评论)

还木有评论哦,快来抢沙发吧~

客服微信:jie5527c点击复制并跳转微信