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

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文要解决的就是判断某市的交巡警服务平台设置方案的合理性，以及如何处理突发事件问题。对于问题一：1.首先根据附件中的各点的坐标和图中所给的各标志点之间的相邻关系，利用MATLAB1绘制出A区的标号图，并求得任意两个相邻标志点的直线距离；再根据附件中的全市交通路口的路线做出了邻接矩阵，用Floyd算法求得任意两点间的最短距离，同时利用C语言编写DIJISTRA算法求出3分钟内警车可以到达的节点，以初步分配管辖范围。2.在此基础上，为了确定需要增加平台的具体个数和位置，采用主成分分析法，应用迪杰斯特拉（Dijkstra）算法进行搜索得到了该区交巡警服务平台警力合理的调度方案。对于问题二：1.结合所给路口发案率、城区面积和城区人口数，给出了设置交巡警服务平台的可量化的原则和任务，对现有方案进行评价然后进行优化。2.P点案发地点在A区，题目未给出逃犯的车速，且逃犯逃跑的方向具有不确定性，进行适当假设，采用圈套式方法，利用动态规划进行分析，找出人力，物力及时间达到一个平衡点，从而得出最佳的围捕方案。关键词：MATLAB、邻接矩阵、Floyd算法、DIJISTRA、迪杰斯特拉（Dijkstra）算法、动态规划。一问题的重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：（1）为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，提出出解决方案。如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，试给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题的分析 问题（1）中有三小问，一、要求要求在现有的警力平台分布条件下，确定出其管辖的区域，以便尽量在三分钟内尽可能到达；二、当有重大突发案件时，各交巡警需快速的到达指定路口封锁该路口，要求我们给出各警务平台出警时他们的行车路线；三、根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，要我们确定需要增加平台的具体个数和位置。根据给出的地图和其他数据，运用C语言使用DIJISTRA算法，确定出了最短路径，从而可以计算得出每个巡警台所能控制的范围。不仅仅要考虑运行路线的最短和优化性，还要考虑时间尽可能较少的优化。 问题（2）中有两小问，一、针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，我们需要分析研究该市现有交巡警服务平台设置方案的合理性。二、如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。三基本假设1.不考虑巡警在实际工作中所出现的故障而导致延误追捕。2.假设各站点的警力量是平均一致且为一固定值（巡警台人数高峰期和低潮期的平均值为单一均值）。3.在整个路途中，通过各种通讯工具，走的路程都是最短路程。4.不考虑巡警车在行驶过程中出现的塞车、抛锚等耽误时间的情况。5.不考虑警员所消耗的时间。7.在整个路途中，转弯处不需要花费时间8.由于题目没有给出逃犯的车速，假设逃犯的速度应该不大于警车的时速；四模型的建立与求解问题（1）：1）首先根据附表中的数据用MATLAB绘制出A区的标号图，如下（绘图代码见附录1）由题设中警车的速度为60km/h以及需要三分钟内到达节点的要求，可以求得交巡警服务平台的管辖范围F=60/60*3=3公里，再由所给比例尺=1:100000，可知在图上的管辖范围F=30。利用C语言编写DIJISTRA算法，以各个交巡警服务平台为中心，30为范围，可以得到距警务平台3公里以内的所有节点（程序源代码见附录2，节点见附录3），再根据警力资源最优化原则，将其进行筛选，从而得出最终的交巡警服务平台，如下表所示：交巡警平台位置平台管辖的节点1168697173747576782240434470723354556465666744575860626355495253566650515977303132474888334546993435101011112627121225131321222324141415153116163637171741421818808182839019197779202084858687888991将其图像化如下图： 2）为了得到该区交巡警服务平台警力合理的调度方案，首先我们计算A区92个节点彼此之间的实际距离：1根据题中所给的各个标志点的坐标，用MATLAB计算出任意两点之间的直线距离，得到92*92的距离矩阵m： 代码见附录42、根据题中交通路口的路线，我们可以得到各标志点的邻接矩阵：，即如果两个点相邻，则邻接矩阵中相对应的元素的值为1，否则为0；例如：1和2这两个点相邻，那么。（代码见附录5）3、根据Floyd算法，我们是要求出各标志点任意两两之间的实际交通距离，所以我们需要得到A区相邻两个标志点的沿公路的交通距离。我们可以利用距离矩阵的元素与的点乘积得到相邻标志点间的距离矩阵：4、我们可以将中不相邻点间距离0改为无穷大（Inf）从而得到标志点与标志点间的权值矩阵： ，即如果1和5之间不相邻，也即不能直接到达，那么D中的和都将变成和等于无穷大（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 来表示带权有向图，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。节点标号121416212223242829303848对应平台1014169151312117836Cost63.6400104.685.045.0026.9327.2980.1530.6124.4421.93MiniunTotal cost469.633）为了确定需要增加平台的具体个数和位置，这里我们采用主成分分析。 计算相关系数矩阵我们首先计算未设置为服务平台的72个节点如果设置为服务平台，那么相应的考虑了距离和发案率的工作量。从矩阵d后72列和后72行抽出得到7272的矩阵，该矩阵中的每一个元素乘以相应行数对应的发案率得到矩阵这样既考虑了平台相应的出警时间，又考虑了相应的发案率。由矩阵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）根据犯罪率和人口密度与巡警台的正比关系，可以得出，人口密度越大，犯罪率越高的地方，更应该增加巡警台的设置。首先形象地表示各区每个标点的犯罪率高低以及人口密度，从而更好地得出结论 2）在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑，按假设8逃犯速度为90km/h,则等效到图上后为45，同样利用附件2的DIJISTRA算法，以P（32）为中心，45为范围可以得到逃犯可能到达的节点，如下表：逃犯从P点3分钟内可以逃跑到的范围节点距P点距离813917320335341235214527463347334843可以将上表划分为两个区域，第一区域是往左边逃跑（如图一），也就只有三种可能出项的情况，通过计算可以得出，巡警台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结合实际，合理假设，提高了模型的适应度。模型的缺点：1.模型具有一定的缺点，无法完美的推广到所有的区域分配问题。 2.对于一些影响因素进行了忽略，会小程度上影响模型的准确度。模型的推广：1.模型可以用于市区公交路线的调度问题。 2.模型可以推广到全国物资的分配运输问题。六、参考文献1罗军辉，冯平，哈力旦A， MATLAB7.0在图像处理中的应用， 北京：机械工业出版 2005.6 2谢金星，刑文训， 网络优化， 北京：清华大学出版社， 2000.83数学模型编写组， 数学模型 ，广州：华南理工大学出版社， 2003.5附录1 x=413403383.5381339335317334.5333282247219225280290337415432418444251234225212227256250.5243246314315326327328336336331371371388.5411419411394342342325315342345348.5351348370371354363357351369335381391392395398401405410408415418422418.5405.5405409417420424438438.5434438440447448444.5441440.5445444;y=359343351377.5376383362353.5342325301316270292335328335371374394277271265290300301306328337367351355350342.5339334335330333330.5327.5344343346342348372374372382380.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.5333342282325247301219316225270280292290335337328415335432371418374444394251277234271225265212290227300256301250.5306243328246337314367315351326355327350328342.5336339336334331335371330371333388.5330.5411327.5419344411343394346342342342348325372315374342372345382348.5380.5351377348369370363371353354374363382.5357387351382369388335395381381391375392366395361398362401359405360410355408350415351418347422354418.5356405.5364.5405368409370417364420370424372438368438.5373434376438385440392447392448381444.5383441385440.5381.5445380444360;data2=17517824434536543946354955065973274789847935103411221126122514211571531161416381740174217811881188319792086212222132313241324252511262726102712282928152930307304831323134323333343383493545363536373616363937738393841394040241174192424343243724434546468465547484764754861495049535051515251595256535253545455546355356575758576057458596062616062462856364646564766566666766766744676868696875697069716917027043717271747273737473187417480757676777778771978797980801881828283829083848485852086878688878887928889889189208984899090919192;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 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,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 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; 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-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-arcs3334=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; 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-arcs5657=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.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-arcs8018=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(MGraph 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=D2v+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警务平台标号管辖节点号距离通过的路径11011824178798019192517576771975917576121757677161757677786178791217879801617879808329178798018832202320244344924433036515365661836566672236566676826365666768762736566764400631046364194636465244636465662746364656655054955495085505111550515215550515253115495356195505152565913550515966065916659752674756267476707824732338928732333493211732331673233342373233344712747482274748880891189328832331383233342083233343515893545218935454627893545464720847982593545468909354935451093545461693545461010010111101126911262716112627121201225171225132291322235132324241324212713222114140141515015312915311616016172191742432170174026174042917424317174243442817424324472251742437218180182025188384852081618818211188182835188384141883848521188384858628188384852086901918818290912318818290911918161979801819019794197980819798081221979801881822719798018818283211979801883202002084192086888984852620868889848586320868714208687881220868889162086888990192086888990912520868891附录4dist(x,y) 求任意两点距离function m=dist(a,b)% a为横坐标，b为纵坐标,且均默认为列向量；for i=1:size(a,1) for j=1:size(b,1) m(i,j)=(a(i)-a(j)2+(b(i)-b(j)2)0.5; endend其中a为A区交通网络中92个路口节点的横坐标，b为A区交通网络中92个路口节点的纵坐标。附录5load sjsxX.txtload sjsxY.txtsjX=sjsxXsjY=sjsxYN=92for i=1:Nfor