1004144573数学建模论文交巡警服务平台的设置与调度

1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： b 我们的参赛报名号为（如果赛区设置

2、报名号的话）： 29011 所属学校（请填写完整的全名）： 学院 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 09 月 11 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）： 交巡警服务平台的设置与调度摘要本文针对某市设置交巡警服务平台的相关情况，根据题目要求，并在合理的假设之下：针对问题（1

3、）：我们首先，将附件1中的附图1给出的该市中心城区a的交通网络和现有的20个巡警服务平台的设置情况采用把交通路线节点用完全图表示，首先将道路交叉口作为节点，构建92个节点的树，然后从任意节点出发，构建与之相通节点的最小支撑树（即距离最短），对于某个平台他做节点的最小支撑树的节点间距离不超过3km，就是该平台所管辖的区域。构建最小支撑树的算法是： 从某个结点开始；计算最小距离 ；重复过程 ，i从1循环到92。然后，在上一问题的基础上，当有重大突发事件发生时，调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，我们在每条道路所属区域内找出距离要封锁路口最近交巡警服务平

4、台，在此交巡警服务平台派出警力进行围堵封锁，最后，我们根据a区现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，采取基于工作划分最优的原则，通过数型分析，将地图上的节点数字化，利用vc+、vb程序、数组、矩阵，数据导入与连接，对a区节点部分数据进行筛选，我们发现a区编号20交巡警服务平台所管辖地方，发生事故率较高且附近交巡警服务平台的工作量较多，因此我们在该区域内再增加了3个平台，期望能缓解附近交巡警服务台的工作量，能相对减轻繁重的交巡警服务平台减轻工作压力，同时为更还的交通治安打下了良好的基石。针对问题（2）：我们可以根据附表二中所给每个城区发案率，用原始数据统计出全市六个主

5、城每个城区总的发案率、总面积、总人口及交巡警服务平台总数，我们利用概率统计模型，统计出单位发案率、单位人口数量及单位面积交巡警服务平台个数，再根据每个城区现有警力资源情况，对其交巡警服务平台的设置进行合理性分析，按照设置交巡警服务平台的原则和任务分配，采用均值方法分析可知，d、e、f三个区域警力明显不足，需要对其增设交巡警服务平台，使该市交巡警服务平台设置位置尽量合理化。 针对a市地点p点处发生了重大刑事案件，在案发3分钟后接到报警后，为能快速搜捕嫌疑犯，我们采用圆内区域划分模型，对该区的主要路段进行封锁，使其在封锁范围内巡查搜索嫌疑犯，以保证在最短的时间内逮捕嫌疑犯。关键词：最小支撑树 图形

6、的数据化 路径最优 均值方法 原始数据一、 问题重述背景提出：当前，我国经济社会正处于一个发展上升的时期公安机关和广大民警在推进和谐社会建设的进程中付出了大量心血，在经济社会发展的进程中各种社会矛盾错综复杂 ，刑事犯罪发案率仍居高不下，既对构建社会主义和谐社会的战略目标提出了挑战，也对公安工作提出了新的要求。如何科学配置警力资源 ，解决警力资源有限性与维稳工作艰巨性之间的矛盾，是当前警务改革工作中需要研究的重要内容，也是我们需要解决的问题。待解决的问题：（1）我们需要根据附件1中的附图1给出的该市中心城区a的交通网络和现有的20个交巡警服务平台的设置情况示意图，及附件2相关的数据信息。为各交巡

7、警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。并且对于重大突发事件，由于实际中一个平台的警力最多封锁一个路口，我们需要将全区20个交巡警服务平台的警力资源进行合理调配，使对进出该区的13条交通要道实现快速全封锁。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，并给出需要增加平台的具体个数和位置。（2）针对全市a、b、c、d、e六个主城区的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性，如果有明显不合理，请给出

8、解决方案。如果该市地点p（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，需要给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析由题目所给条件，我们分析得知，（1）问首先是对a区现有的20个交巡警服务平台的设置情况，各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地，此问题可以归结为路径最优问题来解决，运用两点间距离公式，采用vc+、vb软件编程可以计算出各节点间距离。其次对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条

9、交通要道实现快速全封锁，根据实际中一个平台的警力最多封锁一个路口，我们采用优化工作量来给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，根据工作量最优化原则，经过模型一的分析，我们分别在 编号为7、18、20 所管辖的范围内增加了交巡警服务平台，以达到合理分配警力资源，保证我城区的良好治安，为人民提供一个良好的市区环境。针对(2)问题，根据主城六区a，b，c，d，e，f的具体情况，按照设置交巡警服务平台的原则和任务，由区域划分和调度调节，通过vb编程，首先实现划分距离范围，根据不同节点的属性，为节点分配不同的任务，从而进行调度，基于

10、路径节点的多路性，应在节点密集的地方多设警力，出城区的路口节点必须给与相对较多的警力，剩余的在a，b，c，d，e，f六个主城区进行优化分配，参照以上的解决办法，应对人口密集，发案率频繁的地方多设置一些交巡警平台，从而更有效的维护各城区的治安。针对a该市地点p（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，采用圆内区域划分模型，采用路径最优方法，对该区的主要路段进行封锁，并且在封锁范围内巡查搜索嫌疑犯。三、模型假设1、两节点间的路化为节点力2、警车不受红绿灯、路况等影响，保持时速60km/h3、巡警服务平台第一时间接案4、现实生活中警车平均

11、时速大于其他车辆平均时速5、在填加平台时，假设两个相邻区域是独立的，互相不影响6、路上一些扰动因素忽略不计四、 符号说明 求最小值 每个交巡警服务平台管辖的区域 巡警服务平台编号 各个节点编号 点e到点f的距离 新增设的巡警服务平台 五、模型建立（）、针对问题（1）我们建立三个模型进行研究，模型如下：模型一：警力分配最优化模型我们总体思路是：按照现有的20 个交巡警服务平台，首先将a区划分为20个区域，使每个区域内有一个交巡警服务平台，之后按照题目要求及每个交巡警服务平台实际情况为其划分管辖范围，具体做法如下：由题目要求将为a区的20个交巡警管理平台分配管辖范围，使其在所管辖的出现突发事件时，

12、尽量能在3min内赶到，由于警车时速为60km/h，又由附件2中的全市交通路口节点数据这个表知，地图距离与实际距离比例为1：00000，经计算可知，事故发生地距离交巡警台的距离应该小于等于30mm，由附表可知，a区共有92各路口节点，其中有20 个为交巡警服务平台，我们根据附加2所给坐标，根据题中附件一我们可以知道图形中各个节点连接关系，运用matlab软件对92个节点进行编号，编程见附件1，编程所得图形如下：（ 图形1）我们分两步考虑这个问题，具体分析如下：题目要求根据将城区a这一区域分配给其现有的20 个交巡警服务平台进行管辖，并使其在发生突发事件时，尽量能在3min内有警车赶到，（1）、

13、首先我们只考虑每个交巡警服务平台到路口节点距离小于30mm这一情形， 全区除去交巡警服务平台外，剩余72个路口节点，我们将这72节点按路径最短原则分给20巡警服务平台，我们对a区所有节点（包含交警平台）进行编号192，并建立坐标矩阵，及其建立路权矩阵，其中我们采取如下算法：可以用vb编程得到各个巡警服务平台所管辖的交叉节点编号，这样每个巡警服务平台都有自己的管辖范围。但是这样分配我们发现，一些交叉路口节点同属几个巡警服务平台，这时我们根据最优化原则，考虑到每个巡警服务平台到交叉路口节点的距离最短及其工作量小两方面原因，即将同时在两个巡警服务平台管两个辖下的交叉路口节点均匀的分配到相应的巡警服务

14、平台，达到警力最优化分配。（2）、然而，只考虑到交叉路口节点这一段距离并不精确，总会有些交叉结点及路段不属于任何巡警服务平台所管辖，我们需要将其拿出单独研究，我们分别将其设为p1，p2，p3，pn ，考虑到交巡警服务平台工作量均衡及到平台路径最优及问两方面问题， 我们对其进行分类模型二：路径选取模型由题中附件二我们可以知道出入a区的13个路口标号和20个交巡警服务平台编号，坐标也可以在题中附件二中查到，这样我们就可以在模型一的图形1中找到它们相应的位置关系，以及13路口分别处在哪个交巡警服务平台管辖范围内，用vb编程可求解各个相连同节点之间的距离，根据节点到交巡警服务平台之间距离尽量小于等于3

15、0这一条件，对每个距离再进性排序，找出其中的，此时节点就归交巡警服务平台所管，有这时又有个问题出现，如果同时p个交巡警服务平台满足这一条件，这时我们取p个中距离再进行排序，取距离最短者，如果路口所处管辖范围内没有满足条件的，我们可以从相邻选取满足条件的，选法同上，如果节点到交巡警服务平台的距离，没有满足这一条件，我们选择距离最短交巡警服务平台。模型三：警力合理分配模型由模型一我们可以看出交巡警服务平台的工作量不均衡，而有些地方出警时间过长，结合实际情况我们将在这几个节点处附近，增设了交巡警服务平台，而交巡警服务平台无法在3min内到达一些路口节点，我们根据实际情况对其设置了交巡警服务平台。（）

16、、针对问题（2）我们建立三个模型进行研究，模型如下：模型四 ：交巡警服务平台分布优化模型由附表2给出的六个主城区的一些数据，并对它们总发案率(次数)、城区的人口城区的人口、城区的面积、巡警平台个数，进行了汇总列表如下：路口所属区域总发案率(次数)城区的人口城区的面积巡警平台个数a247.4602220b66.4211038c187.24922117d67.8733839e1177643215f109.25327411我们从将表中数据分析对比，得出交巡警服务平台设置方案的合理性关系，具体求解同 模型一。模型五：圆内区域划分模型如果该市地点（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报

17、警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，我们采取划分圆区域模型，进行対警力的分配。采取本模型的原因有三点：(1)由于犯罪嫌疑人以驾车逃跑三分钟，如果按照警车时速，那么，犯罪嫌疑人已经距离案发地点3公里了。(2)基于之前处理过的巡警服务平台的划分，划分区域应在3公里以内。(3)考虑接到报案马上出警的情况，如果在巡警服务台的范围之内，到达警区控制范围内的时间应为3分钟，加上报警之前的3分钟，总共应为6分钟的路程，即6千米。所以我们采取圆内区域模型，将犯罪嫌疑人控制在半径为6千米的圆内，这是犯罪嫌疑人能走的最大程度，我们将6千米以外的具有多路聚集的主干要道封锁，并在区域内寻找犯罪嫌疑人。 根据

18、我们所提供的c+编写程序，能够计算出直接连通或间接连通的节点间距离，六、模型求解模型一求解:a区共有92个路口节点，但是并不是每个路口节点间都有路连通，我们可以从据附件一所给的图形中观察出哪些路口节点间是连通的，建立坐标矩阵，及其建立路权矩阵我们记：,相连同的道路情况列表如下：根据表中所给数据我们用vb软件编程（见附表2）我们可得出各个路口节点距离巡警服务平台距离,并将其分到相应的20个巡警服务平台，具体分法见下表：a区平台编号a区节点编号168，69，71，73，74，75，76，78240，43，44，70，72344，54 ，55，64，65，66，67，457，58，60，62，635

19、49，51，52，53650，56，59，61730，32，47，48833，46934，35，451026112712251322，23，2414211528，29，311636，37，381739，41，42，921880，81，82，83，90，911977，792084，85，86，87，88，89由表中可知，交巡警服务平台18和交巡警服务平台20，所管辖范围较大，作案率较高，而且交巡警服务平台20，为出城区路口，更因该加大警力，因此应该在和两个区域内增设交巡警服务平台模型二求解：我们设各个节点为交巡警服务平台为 , 到之间的距离为,比较的大小关系：当时，只有一个满足条件,则交叉路口d

20、f由交巡警服务平台ae的负责围堵，当时，只有p个满足条件,则需要进一步比较他们的大小关系，求得, 此时df由交巡警服务平台的负责围堵时，需向相邻区域借用警力，算法同上。用vb编程求的结果为：13不动、10-22、14-21、16-14、11-24、12不动、15-28、7-29、9-16、8-30、5-48、2-38、4-62模型三求解：设在节点出位置一个新的平台，假设平台工作量相对繁重，且所管辖区域为内共有个节点，节点位置是事故高发区且交通放便，故我们把平台设在节点位置，我们要从这个节点中选出节点出位置，我们用vb编程后，在各个区域内我们得到与巡警服务平台连通的接点归类后，编号如下：a区平台

21、编号a区节点编号133，37，69，74，75，78243，44，70344，46，54462，50，57，63547，49647，50715，30，32，34，4789，33，46，4798，34，351026，341122，25，261225，261323，24147，28，311528，31164，36，811740，421873，80，81，831977，792085，86，88，89对表其进行分析，我们得到、这两个交巡警服务平台所管辖的范围工作量相对繁重分配，考虑到合理分配工作量及运输经费等实际因素，我们最终确定在、这两个交巡警服务平台所管辖的范围内各个添加一个交巡警服务平台。模型四

22、求解：设面积为，人口，平台数，案件次数进行表示，,算法法如下： ; ; ; ； ; ; 区号（平台数/案件数） (平台数/人口数)平台数/面积a0.08080.33330.9091b0.12050.38100.0777c0.09090.34690.0769d0.13270.12330.0235e0.12820.19740.0347f0.10070.20750.0401（平均值）0.10060.24100.0557采用均值方法分析图表可得，列中a、b、c、d、e、f各行数列分别与平均值相比较可知，b、d、e、的值均大于，f的值接近，也就是说b、d、e、f三个区域工作量相对较大，之后、列中各个数据

23、相比较知，、列中d、e、f的值均小于，由于d、e、f三个区域工作量相对较大，单位人口和单位面积警力资源相对较少，由此可知该市现有交巡警服务平台设置方案不完全合理，基于以上分析我们需要在三个区域增加新的巡警服务平台。模型五求解：根据已知，接到报警的时候，犯罪嫌疑人已经离开案发处3分钟，假设犯罪嫌疑人所驾驶的车辆行驶速度不超过警车的时速60km/h,说明目前犯罪嫌疑人已经在案发现场3km左右，根据所给市区图形分析可知，接到报警以后必须首先封锁逃离市区的各个出城路口，若犯罪嫌疑人逃往东南西北四个方向，若逃向a区以东,a区警力资源充沛，无网络型线路漏洞，若从c区逃离，可调度c1到节点263，c13到2

24、86号路口。若从d区逃离，可调度d1到356，d3到323,d5到324号路口。若从p点以南逃离，即从f区逃离，可派遣f4到540号路口，f6到569号路口堵截。 七、模型结果分析本文建立了五个模型，涉及大量的数据处理问题，这样使用软件求解比较困容易简化问题，（1）中模型一的建立尤为重要，它为以下的建模打基础，本文我们运用了vb软件编程对其数据做了处理，模型较简单，也很清晰，编程不太难但编出来也不太容易，本文采用vb软件编程大大简化了计算量，之后的一些计算也变得较为容易，所以有效地利用计算机软件编程，对本题极为重要。八、模型优缺点模型一运用vb软件来实现区域划分，放便快捷，应用广泛；模型二没有

25、考虑到相邻管辖区域ma的实际情况，区域ma可能也在忙，没有多余的警力出动这一因素，但此模型能够调动某个区域全部的所有警力资源，在遇到特殊事故时，此模型非常好用；模型三是一个比较理想化的模型，没有考虑相邻区域之间的相互影响，但是在解决某一特定区域警力如何调度问题是，此模型很实用，九、改进方向本文理论上的模型都有其特定的限制条件，特定的问题情景，而实际生活中所遇到的问题，一般具有随机性、不确定性，存在很多我们未知的因素，总之，基于多种原因，本文一些数学模型实际生活由其难以被普遍适用，如果能多考虑一些影响因素进来，此模型应用范围，可能会更广泛一些。十、参考文献1赵静，但琦，数学建模与数学实验，北京：

26、高等教育出版社，2008；2肖华勇，实用数学建模与软件应用，西安：西北工业大学出版社，2008；3韩中庚，数学建模竞赛获奖论文精选与点评，北京：科学出版社，2007；4 钟求喜，基于遗传算法的任务分配与调度，第37卷第10期：119，2000年10月十一、附录附录1clearx=413 403 383.5 381 339 335 317 334.5 333 282 247 219 225 280 290 337 415 432 418 444 251 234 225 212 227 256 250.5 243 246 314 315 326 327 328 336 336 331 371 37

27、1 388.5 411 419 411 394 342 342 325 315 342 345 348.5 351 348 370 371 354 363 357 351 369 335 381 391 392 395 398 401 405 410 408 415 418 422 418.5 405.5 405 409 417 420 424 438 438.5 434 438 440 447 448 444.5 441 440.5 445 444 ;y=359 343 351 377.5 376 383 362 353.5 342 325 301 316 270 292 335 328 335 371 3