当前位置:首页 >> 理学 >>

数学建模解决交巡警服务平台的设置与调度问题


渤海大学本科毕业论文(设计)
数学建模解决交巡警服务平台的设置与调度 问题
Mathematical modeling to solve JiaoXunJing service platform set and scheduling problems

学 院(系): 专 学 业: 号:

数理学院 信息与计算科学 09020153 王希伟 2009、9 朱凤娟 2013 年 05 月 14 日

学 生 姓 名: 入 学 年 度: 指 导 教 师: 完 成 日 期:

渤海大学
Bohai University

数学建模解决交巡警服务平台的设置与调度问题





警察在当今社会扮演着不可或缺的角色,尽管如此由于警务资源有限。现实生活 中还是存在这诸多问题,如何合理设置交巡警服务平台、分配各平台的管辖范围,以 及调度警务资源仍是重中之重亟待解决的问题。首先,我们通过长度覆盖原则、概率 平均原则等的方法有效的解决管辖范围,其前提是在规定时间 t 及时速 v 的情况下达 到的方法, 通过两点间的距离公式或分类讨论其覆盖问题, 也达到了令人满意的答案。 其次,我们通过邻接矩阵模型将合理调度问题转化成为最优路径问题,并通过矩阵求 其值。 再次, 通过人为设定条件, 运用模糊数学方法, 在所加平台尽可能少的前提下, 使其有效覆盖面积达到最大值,又因为 A 区域的面积一定,这样两者之比的比例越 大,才是我们想要的最优方案。接下来,此题的分布合理性主要是以覆盖率最大化和 到达事故现场的最短时间为主。建立优化模型,以“至少需要警务员平台 13 个”作 为一个约束条件,以所有警务人员赶赴险情现场所经过路程的总和最短为目标函数, 以实现警员赶赴险情现场所需时间的总和最少, 从而做到更合理地安排警务人员的执 勤平台位置。最后,主要是缩小搜索罪犯所在范围的方法来找到这些犯罪地点发生的 “重采用这种插值方法道路离散后,将直线上的无穷多个点转化有限个点,便于分析 问题和实现相应的算法,所取得的整体离散效果还是比较理想的。 关键词:长度覆盖原则;概率平均原则;邻接矩阵;最优路径;模糊数学式

- I -

数学建模解决交巡警服务平台的设置与调度问题

Mathematical modeling to solve JiaoXunJing service platform set and scheduling problems Abstract
Police plays an indispensable role in today's society, however because of police resources co., LTD. Or in real life, there exist many problems, how to reasonably set up JiaoXunJing service platform, the distribution of the jurisdiction of the platform, and the scheduling of police resources is still the top priority problem to be solved. First of all, we through the length of coverage of methods, such as principle, the principle of probability and average effective solve the jurisdiction, the premise is that within the prescribed time t and the speed of v method, under the condition of the distance between two points by formula or classification to discuss its coverage, also reached a satisfactory answer. Second, we will through the adjacency matrix model reasonable scheduling problem into an optimal path problem, and its value by using matrix. Again, by using fuzzy mathematics method, set conditions is platform under the premise of as little as possible, make the effective coverage area reaches the maximum, and since the area of A region must have, so that both the ratio of the percentage, the greater the optimal solution is what we want. Next, distribution in the rationality of this topic is based on maximum coverage and arrived at the scene of the accident in the shortest time. Optimization model is set up to 13 "police officer" at least need platform as a constraint condition, after all police officers to danger the scene as the sum of the shortest distance as objective function, the sum of time needed for dangerous situations for police officers rushed to the scene at least, to be more reasonable to arrange place of police officers on duty platform. Finally, mainly to reduce the search area to find these crimes of place "after heavy use this road discrete interpolation method, linear transformation of an infinite number of points on a finite number of points, facilitate analysis problems and the corresponding algorithm, obtained the integral discrete effect is ideal. Key Words:Length of coverage principle;Average probability principle;Adjacency matrix ;The optimal path ;Fuzzy mathematics

- II -

数学建模解决交巡警服务平台的设置与调度问题


摘 引 1 1.1



要 ................................................................................................................................ I 言 ............................................................................................................................... 1 问题的提出和假设 ................................................................................................. 2 问题的重述与分析 .............................................................................................. 2 1.1.1 1.1.2 1.2 2 2.1 2.2 2.3 2.4 2.5 3 3.1 3.2 3.3 问题的重述 ............................................................................................... 2 问题的分析 ............................................................................................... 2

Abstract ................................................................................................................................. II

问题的假设 .......................................................................................................... 3 模型的建立与求解 ................................................................................................. 5 问题一的求解: .................................................................................................. 5 问题二的求解: .................................................................................................. 6 问题三得求解: .................................................................................................. 8 问题四的求解: .................................................................................................. 9 问题五的求解: ................................................................................................ 12 模型的评价与改进 ............................................................................................... 15 模型的评价 ........................................................................................................ 15 模型的优点: .................................................................................................... 15 模型的不足: .................................................................................................... 16

参考文献: ......................................................................................................................... 16 附件一 ................................................................................................................................. 17 附件二 ................................................................................................................................. 18

- III -

数学建模解决交巡警服务平台的设置与调度问题





“有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、 交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能,需要在市区的一些 交通要道和重要部位设置交巡警服务平台。 每个交巡警服务平台的职能和警力配备基 本相同。由于警务资源是有限的,如何根据城市的实际情况与需求合理地设置交巡警 服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。 警察是现代社会不可或缺的角色,肩负着执法、治安、提供社会服务等重要职责。为 了更好更有效的实现这些只能,必须设立交巡警服务平台。这些平台需要合理地分布 在城市的各个地区和交通要道,这样不仅可以及时响应出警到达案发现场,在遇到重 要的或者突发的事件时也能高效的通过联合调度行动起来。

–1–

数学建模解决交巡警服务平台的设置与调度问题

1

问题的提出和假设

1.1 问题的重述与分析
1.1.1 问题的重述 “有困难找警察”,是家喻户晓的一句流行语。警察肩负着刑事执法、治安 管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能,需要在市区 的一些交通要道和重要部位设置交巡警服务平台。 每个交巡警服务平台的职能和警力 配备基本相同。由于警务资源是有限的,如何根据城市的实际情况与需求合理地设置 交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际 课题。 试就某市设置交巡警服务平台的相关情况, 建立数学模型分析研究下面的问题: 问题 1:附件 1 中的附图 1 给出了该市中心城区 A 的交通网络和现有的 20 个交巡警服务平台的设置情况示意图,相关的数据信息见附件 2。请为各交巡警服务 平台分配管辖范围,使其在所管辖的范围内出现突发事件时,尽量能在 3 分钟内有交 巡警(警车的时速为 60km/h)到达事发地。 问题 2:对于重大突发事件,需要调度全区 20 个交巡警服务平台的警力资 源,对进出该区的 13 条交通要道实现快速全封锁。实际中一个平台的警力最多封锁 一个路口,请给出该区交巡警服务平台警力合理的调度方案。 问题 3:根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长 的实际情况,拟在该区内再增加 2 至 5 个平台,请确定需要增加平台的具体个数和位 置。 问题 4:针对全市(主城六区 A,B,C,D,E,F)的具体情况,按照设置 交巡警服务平台的原则和任务,分析研究该市现有交巡警服务平台设置方案的合理 性。如果有明显不合理,请给出解决方案。 问题 5:如果该市地点 P(第 32 个节点)处发生了重大刑事案件,在案发 3 分钟 后接到报警,犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯,请给出调度全市交巡警 服务平台警力资源的最佳围堵方案。 1.1.2 问题的分析 警察的存在大大提高了居民的安全感, 当然如何去提高处理各类事件的效率 以及降低犯罪率是极为重要的问题,只有统筹全面合理调配,才能为我们的生活增添 浓墨重彩的一笔。

–2–

数学建模解决交巡警服务平台的设置与调度问题

问题一分析:城市的巡逻警车时速在 60km/h,在发生突发状况的时候要求尽量 能在 3 分钟内有巡警到达事发地。 对于重大突发事件,就 A 区而言,要求调度 A 区 20 个巡警服务平台,对 13 个 要道实行快速全面封锁。其合理化调度方案。 若在 A 区增加 2—5 个服务平台,确定一下平台的个数为多少才是最佳方案。 问题二分析:如果针对全市六个城区(主要城区有六个:A、B、C、D、E、F) 的具体情况,按巡警服务平台原则和任务设置方案,在某处若有明显的不合理之处可 加以改进,做出合理化解决问题的方案。 若在 A 区的 P 点发生重大刑事案件,在案发 3 分钟后接到报警,为快速追捕嫌 疑犯,给出最佳围堵方案。也可给出其他需要考虑的因素给出相应的解决方案。

1.2 问题的假设
1)警务人员在出警过程中速度不变,不考虑因缺油或车辆转弯时速度的损失。 2)由于警车有先进的通达设备及 GPS 卫星定位,可以清楚的知道案发位置,并 对事件做出迅速反应。 3)警车到事发地之间道路通畅,不会出现因堵车或绕路等问题浪费时间。 4)由题目的设定知,警车应在有限的时间内到达案发现场。三分钟内为最宜。 5)警务人员都能忠于职守,按时出警。 6)题目所提供的数据为真实数据。 7)警员必须沿着图中的路线走。 8)各相关地点不会同时出现突发事件。 1.3 符号说明

x :是在 A 区突发事件所在地的横坐标
y :是在 A 区突发事件所在地的纵坐标
xi :是 A 区平台的横坐标 yi :是 A 区平台的纵坐标

xj yj
zi

:是A区结点的横坐标 :是 A 区结点的纵坐标、

:平台的覆盖面积

q :二十个平台覆盖面积的重合总面积

–3–

数学建模解决交巡警服务平台的设置与调度问题

srandk :随意取二至五个平台的有效覆盖面积

mij

:任意两个标志点 i 与 j 间的距离 :标志点间的距离组成的距离矩阵 :标志点的邻接矩阵 :邻接矩阵的元素。 :相邻标志点间的距离矩阵。 :相邻标志点 i 与 j 间的距离

m

n
nij

D
Dij

W :标志点的权值矩阵 d

:标志点间的最短距离矩阵 :标志点 i 与 j 之间的最短距离。

d ij

–4–

数学建模解决交巡警服务平台的设置与调度问题

2

模型的建立与求解

2.1 问题一的求解:
方法一:本题通过两点之间距离最短的概念入手,又因为道路之间有转弯,所以 在所涵盖的范围内,可把路线分为两种情况考虑: 直线时:
( x ? xi ) 2 ? ( y ? yi ) 2 ? 30mm

i=1,2 ??? 20
2 ( x ? x ) ? ( y ? 2j y ) ? 3 0 j i=1,2 ??? 20 ;

折线 时 : j=1,2,3 ??? 92

( xi ? x j 2 ? ( yi ? y2j ) ? )

方法二:在某一静止状态,至少有一个警车能按时赶往某个一般部位的概率,等 于该巡逻方案中警车的总处警范围与该区域道内总长度的百分比。 证明:
p(i, j ) 为警车 i 按时赶到某一般部位 j 的概率模型

?1, t (i, j ) ? 3, j ? A, B, C P(i, j ) ? ? ?0

(1)

式中 t (i, j ) 为警车 i 赶到事发地点 j 的所需要的时间。式(1)便是评估警车的出 警效果是一个 0—1 模型,即当警车能在 3 分钟内感到某部位时,才能有效处理当前 事件。 所有警车中至少有一个赶到某个一般部位 j 的概率模型为

? p(i, j), i ?V
i

(2)

式(2)表明,该区域道路有 于警车的出警范围中。

? p(i, j)
i

的概率警车能在三分钟内到达,也就是位

–5–

数学建模解决交巡警服务平台的设置与调度问题

2.2 问题二的求解:
目前, 针对城市街区突发事件越来越频繁, 各交巡警平台面临的形势越来越严峻。 20 个交巡警服务平台分布散乱,13 个出入路口在各路段分布状况复杂而公安部门警力 有限。如何在确保各路段安全的情况下,使得所需要的警员人数最少?如何使得警员 到达现场的时间尽可能的短? 问题 2 我们可以转化为解警员的最少数量, 我们必须先根据题中所给的数据计算 出各标点任意两点之间的最短距离。然后再根据

dij

<30mm 得平台到突发事件地点的

有效标点。最后结合可能出现的一个巡警平台封锁一个路口的情况,利用线性优化得 到是警员数量最少的模型,求出至少需要的警员数量,同时还可以得到警员布置的初 步方案。 1)首先我们可以根据题中所给的各个标志点的坐标,用 matlab 计算出任意两点 之间的直线距离,得到 92*92 的距离矩阵:

? m11 ? ? m 21 m?? ? ? ? ? ?m ? n1

m12 m 22 ? ? mn 2

? ? m1n ? ? ? ? m2 n ? ? ? ? ? ? ? ? ? ? mnn ? ?

–6–

数学建模解决交巡警服务平台的设置与调度问题

2)根据题中的分布图,我们可以得到各标点的邻接矩阵:
? n11 ? ? n21 n?? ? ? ? ? ?n ? n1 n12 n22 ? ? nn 2 ? ? n1n ? ? ? ? n2 n ? ? ? ? ? ? ? ? ? ? nnn ? ?

,即如果两个点相邻,则邻接矩阵中相对应的元素的值

为 1,否则为 0;例如:1 和 2 这两个点相邻,那么

n =n
12

21

=1。

3)根据 Floyd 算法,我们是要求出各标点任意两两之间的距离,所以我们需要 得到相邻两个标志点的直线距离。我们可以利用距离矩阵的元素 到相邻标志点间的距离矩阵:
? D11 ? ? D21 D ? m. * n ? ? ? ? ? ? ?D ? n1 D12 D22 ? ? Dn 2 ? ? D1n ? ? ? ? D2 n ? ? ? ? ? ? ? ? ? ? Dnn ? ? ? ? W1n ? ? ? ? W2 n ? ? ? ? ? ? ? ? ? ? Wnn ? ?

mij



nij

的点乘积得

4)我们可以将 D 中不相邻点间距离 0 改为无穷大(Inf)从而得到标志点与标志
? W11 W12 ? ?W21 W22 W ?? ? ? ? ? ? ? ?W ? n1 Wn 2 点间的权值矩阵:

,即如果 1 和 5 之间不相邻,也即

不能直接到达, 那么 D 中的 D15 =0 和 D51 =0 都将变成W 15 和W 51 等于无穷大 (Inf) , 否则则等于 D 中相应元素的数据。 5 ) 运 用 Floyd 算 法 求 出 任 意 两 点 间 最 短 距 离 , 得 到 最 短 距 离 矩 阵 d :
? d11 ? ? d 21 d ?? ? ? ? ? ?d ? n1 d12 d 22 ? ? d n2 ? ? d1n ? ? ? ? d 2n ? ? ? ? ? ? ? ? ? ? d nn ? ?

–7–

数学建模解决交巡警服务平台的设置与调度问题

2.3 问题三得求解:
设原有的 20 个平台的覆盖面积分别为 z1 , z2 ??? z20 , 其中覆盖面积中重叠区域的总 面积为你 n ,又因为 A 的面积为 22 平方公里 所以 max ?

?z

1

? z2 ? ? ? ? ?2 0 z

? ?n/ 2 2 是一个定值

若我们从 92 个点中选择结点添加 2 至 5 个平台从而

z1 ? z2 ????? z20 ? n ? srandk ? / 22

k=2,3,4,5

–8–

数学建模解决交巡警服务平台的设置与调度问题

2.4 问题四的求解:
此题的设置方案只要是以服务平台的覆盖率最大化和在某一平台的管辖范围内 发 生 突 发 事 件 警 务 人 员 能 及 时 赶 到 现 场 的 最 短 时 间 为 主 。

对于问题二的模型,存在一个很严重的问题,即得到的警务人员执勤平台布置方 案只是可行方案,并不是最优方案,也不是唯一解。例如,对于某一点,既可以将执 勤平台安排在 A 点或 C 点都可行。而从最优的角度来看,应该讲警务人员执勤平台 安排在 B 点,这样警员才能在最短时间内到达现场。所以,我们必须建立优化模型 来弥补这个缺陷。我们将模型得到的结果,即“至少需要警务员平台 13 个”作为一 个约束条件,以所有警务人员赶赴险情现场所经过路程的总和最短为目标函数,以实 现警员赶赴险情现场所需时间的总和最少, 从而做到更合理地安排警务人员的执勤平 台位置,为此我们建立模型二如下: 目标函数: MIN 前面的系数为巡警执勤平台与相应的路口之间的距离

–9–

数学建模解决交巡警服务平台的设置与调度问题

0B1+0.54745B2+0.34828S17+0S18+0.24187S19+0.5346W21+0W22+0.68949Z24+ 0Z25+0.43658Z26+0.68837Z27+0.4272K135+0K136+0.2508N138+0N139+0.39115N14 0+0.74669U144+0.51865U145+0U146+0.47434U147+0G258+0.46325G259+0N265+0.3 1385R268+0R269+0.75655X273+0.41593X274+0X275+0.5016X276+0I386+0.43566I38 7+0.27P384+0P393+1.5968J5+1.1286J6+0.8066J7+0.57315J8+0J9+0.24597J10+1.0541J 11+0.80632J23+1.5272J24+1.06E120+1.5385E121+0.32016E129+0E130+0.7737E131+1. 5402E132+1.5049E142+0.75326E143+1.1651E144+1.3931E145+1.5314G121+1.4547G1 24+1.2201G129+1.5402G130+0.76655G131+0G132+0.52498G133+1.2566G134+1.0338 B241+0.80362B242+1.5553B243+0B253+0.70178B254+1.4326B255+1.4524I255+1.100 7I256+0I260+0.66611I261+0P267+1.32P279 约束条件: B1+B2=1 S17+S18+S19=1 W21+W22=1 Z24+Z25+Z26+Z27=1 K135+K136=1 N138+N139+N140=1 U144+U145+U146+U147=1 G258+G259=1 N265=1 R268+R269=1 X273+X274+X275+X276=1 I386+I387=1 P384+P393=1 J8+J9+J10>=1 !J8、J9 和 J10 中的一个标志点可能会安排两个警员,以下等同 E129+E130+E131+E143>=1 G131+G132+G133>=1 B253+B254>=1 I260+I261>=1 P267>=1 J5+J6+J7+J8+J9+J10+J11+J23+J24=2 E120+E121+E129+E130+E131+E132+E142+E143+E144+E145=2 G121+G124+G129+G130+G131+G132+G133+G134=2 B241+B242+B243+B253+B254+B255=2 I255+I256+I260+I261=2 P267+P279=2

–10–

数学建模解决交巡警服务平台的设置与调度问题

W21-E121=0 E121-G121=0 Z24-J24=0 J24-G124=0 E129-G129=0 E130-G130=0 E131-G131=0 E132-G132=0 E142-B242=0 E143-B243=0 E144-U144=0 E145-U145=0 B255-I255=0 B1+B2+S17+S18+S19+W21+W22+Z24+Z25+Z26+Z27+K135+K136+N138+N139 +N140+U144+U145+U146+U147+G258+G259+N265+R268+R269+X273+X274+X275 +X276+I386+I387+P384+P393+J5+J6+J7+J8+J9+J10+J11+J23+J24+E120+E121+E129+ E130+E131+E132+E142+E143+E144+E145+G121+G124+G129+G130+G131+G132+G 133+G134+B241+B242+B243+B253+B254+B255+I255+I256+I260+I261+P267+P279-2 W21-2Z24-E129-E130-E131-E132-E142-E143-E144-E145-B255=20 END INT 57 利用 lindo 运算,我们得到了最优解(见表 6):
突发事件 标号 B S W Z K1 N1 U1 G2 N2 R2 X2 B S W Y K1 N1 T1 G2 N2 R2 X2 J E1 G1 B2 I2 P2 J (200) F1(200) F1(200) B2(200) I2(200) P2(200) Y(400) T1(400) Y(400) D2(400) D2(400) P2(400) 对应巡察的点 结点标号 对应的执勤点

–11–

数学建模解决交巡警服务平台的设置与调度问题

I3 P3

I3 P3

表(6) 我们得出的最优配置点为:B D2 G2
数据 性 区域 A B C D E F 92 73 153 49 102 107 20 8 17 9 15 11 22 103 221 383 432 274 60 21 49 73 76 53

J X2

S I3

W P3

Y

F1

K1

N1

T1

B2

I2

N2


P2 R2

各城区的属性数据如下表:
交点 平台 面积 人口

首先,A 区路口共有 13 个,而全市仅有 20 个路口,因此 A 区应该多设置一些 警务员执勤平台;C 区的交点最多,发生突发状况的可能最大,因此 C 区也应该多设 置一些平台。 其次,每个城区的道路网存在着明显的疏密关系,而且明显看出在道路网的密集 之处,巡查平台的分布也是相当不均匀的,应该合理调配,使之分布均匀。 最后,各城区的人口分布存在一定差异,交通路线多以及人口数相对较多 的城区,平台也应与之相应成比例。

2.5 问题五的求解:

–12–

数学建模解决交巡警服务平台的设置与调度问题

此题的处理方案主要是缩小搜索罪犯所在范围的方法来找到这些犯罪地点发生 的“重心”。而在最后结案时罪犯恰好生活在用这种技术所预测的那个城镇里。从那 是开始,更多更复杂的技术被发展起来通过系列犯罪的地点用来确认罪犯的“地理轮 廓”。

由于警车的平均巡逻速度为 30km/h,接警后的平均行驶速度为 40km/h,由 于距离信息比较容易得到,于是我们将时间限制转化为距离限制,这样便于分析和求 解。当警车接警后,在三分钟内能从接警位置赶到事发现场的最大距离。 为了使警车的管辖范围尽量大,警车的巡逻范围越小越好,当时,即警车在初始 停靠点静止不动时,警车的管辖范围达到最大值 。道路分布不对称,为了使警车的 管辖范围尽量大,警车的巡逻范围越小越好。当时,即警车静止不动时,一辆警车的 管辖范围能达到最大值。 以上分析的仅作定性的分析, 以上的分析没有考虑到 90%的到达几率限制, 但在 设计算法需要充分考虑。 综上所述,当警车静止在初始停靠点时,在三分钟时间限制内,警车能从初始停 靠点赶到事发现场。 将道路离散化 由于事发现场是等概率地分布在道路上的,由区域地图可以发现,整个区域中的 道路长度不均,为了使计算结果更加精确,可将这些道路离散化。只要选取合适的离

–13–

数学建模解决交巡警服务平台的设置与调度问题

散方案,就能使警车在经过道路上的离散的点时就相当于经过了这条道路。这样,不 论是求解警车初始停靠点还求解警车赶到事发现场所经过的道路时, 所计算得的的结 果显然比仅考虑整条道路的叉路口要精确得多。用线性插值的方法,从道路的一个方 向进行线性插值,实现将每条道路离散化的目标。 采用这种插值方法道路离散后,将直线上的无穷多个点转化有限个点,便于分析 问题和实现相应的算法,所取得的整体离散效果还是比较理想的。 分区域求解警车数目的算法设计 考虑到警车配置和巡逻方案需要满足: 警车在接警后三分钟内赶到普通部位案发现场 的比例不低于 90%, 赶到重点部位必须控制在两分钟之内的要求。 总的警车数目最小, 即每个区域都尽可能多地覆盖道路节点。由于警车的初始位置是未知的,我们可设警 车初始停靠点在道路上的任一点, 即分布在图 4 所示的 582 个离散点中的某些点节点 上,总体思路是让每两辆车之间尽量分散地分布,一辆警车管辖一个分区,用这些分 区覆盖整个区域。 于是我们设计算法 1,步骤如下所示: Step1:将整个区域预分配为 6 个分区,每个分区分配一辆警车,警车的初始停靠位 置设在预分配区中心的道路节点上,若城区的中心不在道路节点上,则将警车放在离 中心最近的道路节点上; Step2:统计分区不能覆盖的节点,调整警车的初始停靠点,使分区覆盖尽可能多的 道路节点,调整分为区内调整和区间调整方案:(1)区内调整按照模拟退火思想构 造的函数,在区间调整调整车辆初始点的位置(后文中有详细说明),当分区内节点 数较多时,调整的概率小些,分区内节点数较少时,调整的概率大些,当区域中存在 未被覆盖的节点或节点群(大于等于三个节点集中在一个范围内)时,将警车初始位 置的调整方向朝这些未被覆盖的结点按一定的规则 (在算法说明中有详细叙述) 移动, 同时要保证 3 个重点部位能在 2 分钟之内 100%到达; Step3:用 Floyd 算法计算出警车初始停靠点到周边各道路节点的最短距离 ; Step4:以六个划分区域未覆盖的总的道路长度与整个区域的道路总长度的比值 来表 示警车不能 3 分钟内到达现场的概率; Step5:模拟足够多的次数,若依次将车辆数减 1,跳转到 Step1; Step6:计算结束后,比较当时所对应的值,当取得最小值时,记录此时的区域划分 方案,即为最少的警车数。

–14–

数学建模解决交巡警服务平台的设置与调度问题

3

模型的评价与改进

3.1 模型的评价
模型 1 的求解运用了 Dijstra 算法,虽然解决了 A 区交巡警服务平台管辖范 围的分配问题,另一方面使得 A 区中每一个节点只从属于一个服务平台。这样就使 得服务平台失去了灵活性, 即当在某一个交巡警服务平台所管辖的范围内同时发生两 个案件,则就有一个案件被延误。但是这样的分配方案避免了各服务平台之间因责任 推脱而造成无人区。 模型 2 解决了封锁 A 区 13 条要道节点的交巡警服务平台警力调度问题,运 用多目标规划,0-1 整数规划建立的模型比较清晰,同时熟练地运用 Lingo 快速地给 出封锁调度方案。此模型移植性比较好,我们也在模型 5 中很快的应用,计算出搜捕 围堵疑犯的警力调度方案。 模型 3 解决了确定需要增加交巡警服务平台的个数及位置问题, 此问题的解 决更贴近人性化设计,增添了交巡警服务平台的个数,使得每一个交巡警服务平台的 工作强度不会相差太大,而且还提高了交巡警服务平台的工作效率。但还存在个别案 件数不多的路口节点占用一个交巡警服务平台,浪费了警力资源,同时此模型的有一 点不足之处是所用算法为穷举法,当数据量变大时,运算时间过长。 模型 4 解决了评价全市现有交巡警服务平台设置方案的合理性问题, 此问题 的解决就是问题 1 的推广,进一步完善了题目所给的交巡警调度问题,增强了问题 1 所建模型的实用性。在时间及工作均衡条件的限制下,由于其他因素的影响还存在一 些节点在发生案件时不能够被及时处理。这样,就增加了交巡警车的出警时间。 模型 5 解决了搜捕围堵疑犯的警力调度问题, 同时很好地将模型 2 进行移植, 并根据所涉及的时间步长法, 运用 Lingo 程序快速地给出疑犯不同逃跑速度下的最优 快速围堵方案,可以计算该模型。

3.2 模型的优点:
1)对于给出的大量的数据,我们首先对数据进行处理,将其转化为有用的数据, 如:附件中的各点的坐标转化为点与点之间的距离。 2)模型建立的思路简单清晰,并且可以得到很好的效果。 3)模型的假设很符合实际生活,以致模型可以很好的运用于实际生活中。

–15–

数学建模解决交巡警服务平台的设置与调度问题

4)若对一些影响模型的因素加以改变,其结果的变化不大,从而模型的灵敏度 较高。

3.3 模型的不足:
1)没有考虑特殊情况在内,如:遇到不可抗力,多个路段同时发生险情等可能 性。 2)在第一问中,模型没有给出道路上的警员的具体范围。 3)在计算过程中求解时间过长等等,在今后的建模中一定会加以完善。 4)对于合理的利用和调配警力资源,政府和相关部门应该积极的做出相应的配 合,对于突发的事件能够做出及时妥善的处理。对于模型 5)可适当根据区域搜索法 进行围堵,首先可以看到 P 点在 A 区,可以根据疑犯逃跑速度计算是否能够在 A 区 各出口围堵,不行,则判断出口处,并根据出口处,按照时间步长法进行围堵。

参考文献:
[1] 薛毅,耿美英,运筹学与实验,北京:电子工业出版社,2008.9。 [2] 韩中庚,宋明武,邵光纪,数学建模竞赛,北京:科学出版社,2007。 [3] 戴明强,李卫军,杨鹏飞,数学模型及其应用,北京:科学出版社,2007。 [4] 叶其孝,郑绍辉,大学生数学建模竞赛辅导教材,湖南:湖南教育出版社,1997。 [5] 魏荣桥,何芊,运筹学,北京:清华大学出版社,2005。 [6] 陈杰,MATLAB 宝典,北京:电子工业出版社,2007。 [7] 周品、赵新芬 MATLAB 数学建模与分析 北京国防工业出版社 2006 年 [8] 王庚、王敏生 现代数学建模方法 科学出版社 2008 年 2 月第一版 [9] 寿纪麟 数学建模---方法与案例 西安交通大学出版社 1996 年 3 月第五次印刷 [10] 朱道元等 数学建模案例精选科学出版社 2006 年 12 月第四次印刷

–16–

数学建模解决交巡警服务平台的设置与调度问题

附件一

–17–

数学建模解决交巡警服务平台的设置与调度问题

附件二
突发事件 标号 B S W Z K1 N1 U1 G2 N2 R2 X2 I3 P3 数据 性 区域 A B C D E F 92 73 153 49 102 107 20 8 17 9 15 11 22 103 221 383 432 274 60 21 49 73 76 53 属 交点 平台 面积 人口 B S W Y K1 N1 T1 G2 N2 R2 X2 I3 P3 J E1 G1 B2 I2 P2 J (200) F1(200) F1(200) B2(200) I2(200) P2(200) Y(400) T1(400) Y(400) D2(400) D2(400) P2(400) 对应巡察的点 结点标号 对应的执勤点

–18–


赞助商链接
相关文章:
数学建模交巡警服务平台的设置与调度模型
数学建模交巡警服务平台的设置与调度模型 - 交巡警服务平台设置与调度方案 摘要 本文主要讨论了交巡警服务平台的设置与调度问题. 对于问题一,首先,运用 Floyd 算法...
...数学建模优秀论文——交巡警服务平台的设置与调度_...
2011数学建模优秀论文——交巡警服务平台的设置与调度 - 交巡警服务平台的设置与调度 摘要 本文对交巡警服务平台的设置与调度问题,应用 Dijstra 最短路算法,多目标...
2011数学建模B题 交巡警服务平台的设置与调度论文
2011数学建模B题 交巡警服务平台的设置与调度论文_数学_自然科学_专业资料。建模...解决了这些问题后,我们需要调用某种算法,从而 实现找到距每个各个交通节点最近的...
...生数学建模大赛论文 交巡警服务平台的设置与调度(获...
2011年全国大学生数学建模大赛论文 交巡警服务平台的设置与调度(获国家二等奖) - 2011 高教社杯全国大学生数学建模竞赛 交巡警服务平台的设置与调度 摘要:本文...
2011数学建模B题交巡警服务平台的设置与调度
2011数学建模B题交巡警服务平台的设置与调度_理学_高等教育_教育专区。2011数学...图论、贪婪算法、层次分析法、逐步逼近等方法,用以解决题干中的 各个子问题。 ...
2011年全国数学建模获奖论文 交巡警服务平台的设置与调度
2011年全国数学建模获奖论文 交巡警服务平台的设置与调度_数学_自然科学_专业资料...问题二: (1). 针对全市(主城六区 A,B,C,D,E,F)的具体情况,本文按照...
交巡警服务平台的设置与调度(数学建模论文)
交巡警服务平台的设置与调度(数学建模论文) - 交巡警服务平台的设置与调度 摘要 警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能,交巡警服 务平台的设置...
数学建模交警问题
2010 高教社杯全国大学生数学建模竞赛 承诺书 我们仔细阅读了中国大学生数学建模...交巡警服务平台的设置与调度问题 摘要 本文通过对交巡警服务平台的设置与调度进行...
交巡警服务平台的设置与调度-2011年全国大学生数学建模...
交巡警服务平台的设置与调度-2011年全国大学生数学建模赛题_营销/活动策划_计划/解决方案_实用文档。数学建模大赛 交巡警服务平台的设置与调度 摘要 本文是在一个...
交巡警服务平台的设置与调度数学建模论文_ 精品
交巡警服务平台的设置与调度数学建模论文_ 精品 - 交巡警服务平台的设置与调度 摘要 “有困难找警察” ,是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、...
更多相关标签: