10 2011高教社杯：数学建模交巡警服务平台的设置与调度

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

2、报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2011 年 9 月 12 日赛区评阅编号（由赛区组委会评阅前进行编号）：632011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务

3、资源是警务部门面临的一个实际课题。本文给出的就是某市的交巡警服务平台设置方案合理性的判断方法，以及如何处理突发事件问题的解决办法。对于问题一，首先根据附件中的各点的坐标和图中所给的各标志点之间的相邻关系，利用matlab绘制出a区的标号图，并求得任意两个相邻标志点的直线距离；再由附件中给出的全市交通路口的路线做出了邻接矩阵，用floyd算法求得任意两点间的最短距离，同时利用c语言编写dijkstra算法求出3分钟内警车可以到达的节点，从而初步分配管辖范围；在此基础上，为了确定需要增加平台的具体个数和位置，采用主成分分析法，得到了该区交巡警服务平台警力调度的合理方案。对于问题二，结合所给的路口发

4、案率、城区面积和城区人口数，给出了设置交巡警服务平台的可量化的原则和任务，对现有方案进行评价然后进行优化。p点案发地点在a区，题目未给出逃犯的车速，且逃犯逃跑的方向具有不确定性，进行适当假设，采用圈套式方法，利用动态规划进行分析，找出人力，物力及时间达到的一个平衡点，从而得出最佳的围捕方案。关键词：警力分配，matlab，floyd算法， dijkstra算法，动态规划。一问题的重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根

5、据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台

6、，确定需要增加平台的具体个数和位置。（2）针对全市（主城六区a，b，c，d，e，f）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，提出出解决方案。如果该市地点p（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，试给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题的分析问题（1）中有三小问，一、要求要求在现有的警力平台分布条件下，确定出其管辖的区域，以便尽量在三分钟内尽可能到达；二、当有重大突发案件时，各交巡警需快速的到达指定路口封锁该路口，要求我们给出各

7、警务平台出警时他们的行车路线；三、根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，要我们确定需要增加平台的具体个数和位置。根据给出的地图和其他数据，运用c语言使用dijistra算法，确定出了最短路径，从而可以计算得出每个巡警台所能控制的范围。不仅仅要考虑运行路线的最短和优化性，还要考虑时间尽可能较少的优化2。 问题（2）中有两小问，一、针对全市（主城六区a，b，c，d，e，f）的具体情况，按照设置交巡警服务平台的原则和任务，我们需要分析研究该市现有交巡警服务平台设置方案的合理性。二、如果该市地点p（第32个节点）处发生了重大刑事案件，在案发

8、3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案3。三基本假设1.不考虑巡警在实际工作中所出现的故障而导致延误追捕。2.假设一定时期内该区的交通路线不会改变。3.在整个路途中，通过各种交通工具，走的路程都是最短路程。4.不考虑巡警车在行驶过程中出现的塞车、抛锚等耽误时间的情况。5.不考虑警员所消耗的时间。6.假设所有的案件均发生在节点处。7.在整个路途中，转弯处不需要花费时间。8.由于题目没有给出逃犯的车速，假设逃犯的速度为90km/h。四符号说明f： 巡警服务平台实际管辖范围f，：巡警服务平台在模型图上的等效距离m： 距离矩阵n:

9、 邻接矩阵d： 最短距离矩阵r： 相关系数矩阵五模型的建立与求解问题（1）：1）首先根据附表中的数据用matlab1绘制出a区的标号图，如下（绘图代码见附录1）fig. 1由题设中警车的速度为60km/h以及需要三分钟内到达节点的要求，可以求得交巡警服务平台的管辖范围f=60/60*3=3公里，再由所给比例尺=1:100000，可知在图上的管辖范围f=30。利用c语言编写dijkstra算法，以各个交巡警服务平台为中心，30为范围，可以得到距警务平台3公里以内的所有节点（程序源代码见附录2，节点见附录3），再根据警力资源最优化原则，将其进行筛选，从而得出最终的交巡警服务平台，如下表所示：tab

10、le 1交巡警平台位置平台管辖的节点1168697173747576782240434470723354556465666744575860626355495253566650515977303132474888334546993435101011112627121225131321222324141415153116163637171741421818808182839019197779202084858687888991将其图像化如下图：fig. 22）为了得到该区交巡警服务平台警力合理的调度方案，首先我们计算a区92个节点彼此之间的实际距离：1根据题中所给的各个标志点的坐标，用matla

11、b计算出任意两点之间的直线距离，得到92*92的距离矩阵m： 代码见附录42、根据题中交通路口的路线，我们可以得到各标志点的邻接矩阵：，即如果两个点相邻，则邻接矩阵中相对应的元素的值为1，否则为0；例如：1和2这两个点相邻，那么。（代码见附录5）3、根据floyd算法，我们是要求出各标志点任意两两之间的实际交通距离，所以我们需要得到a区相邻两个标志点的沿公路的交通距离。我们可以利用距离矩阵的元素与的点乘积得到相邻标志点间的距离矩阵：4、我们可以将中不相邻点间距离0改为无穷大（inf）从而得到标志点与标志点间的权值矩阵： ，即如果1和5之间不相邻，也即不能直接到达，那么d中的和都将变成和等于无穷

12、大（inf），否则则等于d中相应元素的数据。5、运用floyd算法求出任意两点间最短距离，得到最短距离矩阵： （floyd算法见附录6）（矩阵d见附录7）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁，也即要封锁13条交通要道在a区内的交通路口节点，标号为12、14、16、21、22、23、24、28、29、30、38、48。该问题转化为整数线性规划问题：min 约束：i、j、k、l、m、n、p、q、r、s、t、u，属于整数且互不相同；这里应用迪杰斯特拉（dijkstra）算法进行搜索，算法描述如下：（1）假设用带权的邻接矩阵arcs 来

13、表示带权有向图，s为1-20整数的集合，它的初始状态为20个元素的集合，初值为0。i、j、k、l、m、n、p、q、r、s、t、u这12个未知数各自按先后顺序实现从1-20的循环，每一次选择了一个1-20之间的整数，则将其从s的集合中删除。（2）d表示总共的cost，每一次对未知数选择了一个整数v后，则加上以该未知数为列数，v为行数的d矩阵中相应的元素值。（3）如果后面算的的d值比前面所算得的d值小，那么选取小的那个d值（4）在操作（1）、（2）中共循环2020!/8!次。结论：i=12,j=14,k=16,l=14,m=15,n=13,p=12,q=11,r=10,s=7,t=3,u=6。ta

14、ble 2节点标号121416212223242829303848对应平台1014169151312117836cost63.6400104.685.045.0026.9327.2980.1530.6124.4421.93miniuntotal cost469.633）为了确定需要增加平台的具体个数和位置，这里我们采用主成分分析。 计算相关系数矩阵我们首先计算未设置为服务平台的72个节点如果设置为服务平台，那么相应的考虑了距离和发案率的工作量。从矩阵d后72列和后72行抽出得到7272的矩阵，该矩阵中的每一个元素乘以相应行数对应的发案率得到矩阵这样既考虑了平台相应的出警时间，又考虑了相应的发案

15、率。由矩阵x可以计算出相关系数矩阵 在上式中，rij（i，j=1，2，p）为原变量的与之间的相关系数，矩阵x的第i列和第j列，其计算公式为 ，为矩阵x第i列和第j列元素的平均值，n=72 计算特征值与特征向量首先解特征方程，通常用雅可比法（jacobi）求出特征值，并使其按大小顺序排列，即0。 计算主成分贡献率及累计贡献率主成分的贡献率为累计贡献率为(i=1,2,)选取累计贡献率达8595%的特征值建议增加的平台个数为3个，分别是22、23、24。matlab源代码见附录8问题（2）1） 根据犯罪率和人口密度与巡警台的正比关系，可以得出，人口密度越大，犯罪率越高的地方，更应该增加巡警台的设置。

16、充分考虑各区每个标点的犯罪率高低以及人口密度，从而更好地得出结论，全市六个城区的面积abcdef22103221383432274全市六个城区的人口（万人）abcdef602149737652结合全市六大城区的犯罪率表（附录9），可以得知其犯罪率的方差为：a=6.38，b=1.6， c=5.4， d=4.9， e=3.7, f=3.4平均值 5.1 3.2 7 6.5 5.8 5.9通过比较全市六大城区的平均值和方差可以看出，a，c,d,e,f五区的波动性较大，因此巡警服务平台的布局不合理,由此以及巡警服务平台的任务和责任可以看出，当前设置的巡警台存在不合理性，更改的结果是：a区情况第一问已经

17、给出，b区警力配置基本合理，不需再多做调度。c区需要增加一个，增加在273路口处。d区中应该新增8个巡警台，e区中需要增加4个巡警台f区中新增4个巡警台较为合理。 2）在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑，按假设8逃犯速度为90km/h,则等效到图上后为45，同样利用附件2的dijistra算法，以p（32）为中心，45为范围可以得到逃犯可能到达的节点，如下表：逃犯从p点3分钟内可以逃跑到的范围节点距p点距离813917320335341235214527463347334843可以将上表划分为两个区域，第一区域是往左边逃跑（如图一），也就只有三种可能出项的情况，通过计算可以得出，巡警

18、台15封锁28号路口，10平台封锁26路口，14平台封锁14路口即可。另一区域是往右边逃跑（如图二），通过计算得出，2,3,4号巡警台往最近的路口处进行封堵就可以达到围捕成功。 但p（32）点至c区节点30的距离小于4.5公里，罪犯有可能逃跑至c区，所以此时我们应该考虑c区巡警台的围捕问题。经计算可以得出，出动173,174 号平台的警力封锁216,299号节点即可。六、模型的评价与推广模型的优点：1.模型建立思路清晰，运用floyd算法、dijistra、迪杰斯特拉（dijkstra）算法等，提高了模型的精确度。2.将附件中所给的数据用matlab转化为图形，更加直观清晰。3结合实际，合理假

19、设，提高了模型的适应度。4. 对于见巡警平台划分管辖范围的问题该模型给出了比较合理的划分方法，当有事故发生时可以保证交警第一时间到达事故现场，提高了交警处理事故的效率。在当今社会环境下，效率就是生命，经济迅猛发展，城市的规模日渐扩大，城市的交通也越来越紧张，如何合理的安排交巡警平台的位置及划分管辖范围对一个城市的效率起到了极大的。模型的缺点：1.模型具有一定的缺点，无法完美的推广到所有的区域分配问题。 2.对于一些影响因素进行了忽略，会小程度上影响模型的准确度。模型的推广：1.模型可以用于市区公交路线的调度问题。 2.模型可以推广到全国物资的分配运输问题。 3.此模型还可以应用到消防救援最优捷

20、径问题、重大安全事故急救等问题，同时也可拓展模型在其他领域的应用。七、参考文献1罗军辉，冯平，哈力旦a， matlab7.0在图像处理中的应用， 北京：机械工业出版 2005.6 2谢金星，刑文训， 网络优化， 北京：清华大学出版社， 2000.83数学模型编写组， 数学模型 ，广州：华南理工大学出版社， 2003.5附录1 x=413403383.5381339335317334.5333282247219225280290337415432418444251234225212227256250.5243246314315326327328336336331371371388.5411419

21、411394342342325315342345348.5351348370371354363357351369335381391392395398401405410408415418422418.5405.5405409417420424438438.5434438440447448444.5441440.5445444;y=359343351377.5376383362353.5342325301316270292335328335371374394277271265290300301306328337367351355350342.5339334335330333330.5327.534

22、4343346342348372374372382380.5377369363353374382.5387382388395381375366361362359360355350351347354356364.5368370364370372368373376385392392381383385381.5380360;for i=1:92plot(x,y,.);hold onc=num2str(i);c= ,c;text(x(i),y(i),c)end data1=413359403343383.5351381377.5339376335383317362334.5353.5333342282

23、325247301219316225270280292290335337328415335432371418374444394251277234271225265212290227300256301250.5306243328246337314367315351326355327350328342.5336339336334331335371330371333388.5330.5411327.5419344411343394346342342342348325372315374342372345382348.5380.5351377348369370363371353354374363382.

24、5357387351382369388335395381381391375392366395361398362401359405360410355408350415351418347422354418.5356405.5364.5405368409370417364420370424372438368438.5373434376438385440392447392448381444.5383441385440.5381.5445380444360;data2=17517824434536543946354955065973274789847935103411221126122514211571

25、531161416381740174217811881188319792086212222132313241324252511262726102712282928152930307304831323134323333343383493545363536373616363937738393841394040241174192424343243724434546468465547484764754861495049535051515251595256535253545455546355356575758576057458596062616062462856364646564766566666766

26、766744676868696875697069716917027043717271747273737473187417480757676777778771978797980801881828283829083848485852086878688878887928889889189208984899090919192;c=413 403 383.5 381 339 335 317 334.5 333 282 247 219 225 280 290 337 415 432 418 444 ;d=359 343 351 377.5 376 383 362 353.5 342 325 301 316

27、 270 292 335 328 335 371 374 394;e=219 280 337 251 234 225 212 243 246 314 371 315 381;f=316 292 328 277 271 265 290 328 337 367 330 374 381;for i=1:140 x1=data1(data2(i,1),1);y1=data1(data2(i,1),2); x2=data1(data2(i,2),1);y2=data1(data2(i,2),2); a=x1,x2;b=y1,y2; plot(x1,y1,b.,x2,y2,b.,c,d,ro,a,b,e,

28、f,r*);hold on end附录2#include#include#define mvnum 100#define maxint 32767typedef char vertextype;typedef int adjmatrix;typedef enum false,true boolean;typedef struct vertextype vexsmvnum; adjmatrix arcsmvnummvnum;mgraph;int d1mvnum,p1mvnum;int dmvnummvnum,pmvnummvnum;void createmgraph(mgraph *g,int

29、n,int e)int i,j,k,w;for(i=1;ivexsi=(char)i; for(i=1;i=n;i+) for(j=1;jarcsij=maxint; g-arcs175=9.3; g-arcs178=6.4; g-arcs244=9.4; g-arcs345=42.4; g-arcs365=15.2; g-arcs439=45.6; g-arcs463=10.3; g-arcs549=5.0; g-arcs550=8.4; g-arcs659=16.0; g-arcs732=11.4; g-arcs747=12.8; g-arcs89=11.5; g-arcs847=20.7

30、; g-arcs832=8.6; g-arcs935=4.2; g-arcs1034=49.2; g-arcs1122=32.6; g-arcs1126=9.0; g-arcs1225=17.8; g-arcs1227=33.1; g-arcs1421=32.6; g-arcs157=38.1; g-arcs1531=29.6; g-arcs1614=67.4; g-arcs1638=34.0; g-arcs1740=26.2; g-arcs1742=9.8; g-arcs1781=40.2; g-arcs1881=6.7; g-arcs1883=5.3; g-arcs1979=4.4; g-

31、arcs2086=3.6; g-arcs2122=18.0; g-arcs2213=9.0; g-arcs2313=5.0; g-arcs2413=23.8; g-arcs2425=18.0; g-arcs2511=20.0; g-arcs2627=7.4; g-arcs2610=35.3; g-arcs2712=33.0; g-arcs2829=9.4; g-arcs2815=37.5; g-arcs2930=74.3; g-arcs307=5.8; g-arcs3048=7.0; g-arcs3132=11.7; g-arcs3134=15.5; g-arcs3233=5.0; g-arc

32、s3334=7.5; g-arcs338=8.2; g-arcs349=5.0; g-arcs3545=6.7; g-arcs3635=5.0; g-arcs3637=5.0; g-arcs3616=6.0; g-arcs3639=35.0; g-arcs377=30.4; g-arcs3839=3.0; g-arcs3841=40.0; g-arcs3940=17.6; g-arcs402=19.1; g-arcs4117=8.5; g-arcs4192=46.3; g-arcs4243=8.0; g-arcs432=2.0; g-arcs4372=8.1; g-arcs443=11.6;

33、g-arcs4546=6.0; g-arcs468=9.3; g-arcs4655=29.4; g-arcs4748=10.1; g-arcs476=14.8; g-arcs475=14.5; g-arcs4861=29.0; g-arcs4950=10.4; g-arcs4953=6.7; g-arcs5051=3.8; g-arcs5152=4.3; g-arcs5159=2.9; g-arcs5256=4.2; g-arcs5352=8.5; g-arcs5354=22.8; g-arcs5455=10.0; g-arcs5463=24.1; g-arcs553=12.6; g-arcs

34、5657=12.3; g-arcs5758=7.5; g-arcs5760=8.1; g-arcs574=18.6; g-arcs5859=7.8; g-arcs6062=13.8; g-arcs6160=34.7; g-arcs624=3.5; g-arcs6285=60.0; g-arcs6364=9.0; g-arcs6465=5.8; g-arcs6776=13.1; g-arcs6566=3.1; g-arcs6667=4.2; g-arcs6676=9.2; g-arcs6644=14.7; g-arcs6768=4.1; g-arcs6869=7.0; g-arcs6875=4.

35、5; g-arcs6970=5.3; g-arcs6971=6.4; g-arcs691=5.0; g-arcs702=8.6; g-arcs7043=7.6; g-arcs7172=5.0; g-arcs7174=6.1; g-arcs7273=8.0; g-arcs7374=4.0; g-arcs7318=19.7; g-arcs741=0.2; g-arcs7480=16.9; g-arcs7576=3.5; g-arcs7677=4.4; g-arcs7778=10.0; g-arcs7719=9.8; g-arcs7879=6.7; g-arcs7980=4.4; g-arcs801

36、8=8.0; g-arcs8182=5.0; g-arcs8283=5.4; g-arcs8290=8.7; g-arcs8384=9.8; g-arcs8485=7.2; g-arcs8520=4.4; g-arcs8687=11.0; g-arcs8688=9.3; g-arcs8788=4.0; g-arcs8790=21.3; g-arcs8889=4.0; g-arcs8891=3.0; g-arcs8920=9.4; g-arcs8984=3.0; g-arcs8990=3.5; g-arcs9091=4.7; g-arcs9192=20.0; void dijkstra(mgra

37、ph g,int v1,int n,int scope)int d2mvnum,min;int p2mvnum;int v,i,w;boolean smvnum;for(v=1;v=n;v+)sv=false;d2v=g.arcsv1v;if(d2vmaxint)p2v=v1;elsep2v=0;/ford2v1=0;sv1=true;for(i=2;in;i+)min=maxint; for(w=1;w=n;w+) if(!sw&d2wmin) v=w; min=d2w; /if sv=true; for(w=1;w=n;w+) if(!sw&(d2v+g.arcsvwd2w) d2w=d2

38、v+g.arcsvw; p2w=v; /if /forprintf(long, pathn);for(i=1;i=n;i+)if(d2iscope)printf(%5d,d2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v; printf(n);void main() mgraph g; int n,e,v,w,k,scope; n=92; e=143; createmgraph(&g,n,e); printf( 请输入起始点和控制点n); scanf(%d%d,&v,&scope); dijkstra(g,v,n,scope);附录3

39、警务平台标号管辖节点号距离通过的路径110118241787980191925175767719759175761217576771617576777861787912178798016178798083291787980188322023202443449244330365153656618365666722365666768263656667687627365667644006310463641946364652446364656627463646566550549554950855051115505152155505152531154953561955051525659135505159

40、6606591665975267475626747670782473233892873233349321173233167323334237323334471274748227474888089118932883233138323334208323334351589354521893545462789354546472084798259354546890935493545109354546169354546101001011110112691126271611262712120122517122513229132223513232424132421271322211414014151501531291531161601617219174243217017402617404291742431717424344281742432447225174243721818018202518838485208161881821