2011数学建模优秀论文——交巡警服务平台的设置与调度

1、交巡警服务平台的设置与调度摘要本文对交巡警服务平台的设置与调度问题,应用Dijstra最短路算法，多目标规划，0-1整数规划，时间步长法，针对不同情况的具体问题，分别建立了相应的数学模型，给出了合理的交巡警服务平台的设置与调度方案。对A区交巡警服务平台管辖范围的分配问题，首先根据节点坐标计算出节点邻接对称矩阵，然后利用Dijstra算法求解出各节点到每个平台的最短距离，并根据到平台最短距原则分配各节点给相应的平台管辖，最后得到了各平台管辖的范围（见表1），同时给出了各平台管辖范围内3分钟路程外的节点（见表1）。对封锁A区13条要道节点的交巡警服务平台警力调度问题，考虑到各平台出警时间的同步，出

2、警的平台数量最少以及一个平台警力最多封锁一个路口的约束，运用多目标规划，0-1整数规划建立了一个封锁13条要道节点最长时间最小化模型，并运用Lingo求解出平台3,4,5,6,7,9,10,11,12,13,14,15,16分别封锁要道节点16,38,62,48,29,30,12,24,22,21,23,28,14，得到了A区13条要道全部封锁完成的最短时间为8分钟。对确定需要增加交巡警服务平台的个数及位置问题，考虑到各平台工作量的均衡及出警时间，运用各平台工作量（所管辖范围内的发案数和）的标准差来衡量其工作量的均衡，建立了一个对每个节点的出警时间不超过3分钟，且各服务平台工作量的标准差最小（

3、各平台工作量越均衡）的数学模型，并得到可在本区增加4个平台，分别增加在节点28,39,48,87.对评价全市现有交巡警服务平台设置方案的合理性问题，首先根据主城区以及最短距原则将全市各区节点分配给本区现有的平台，然后根据各平台工作量的均衡、出警时间、本区人口密度及发案率对现有平台设置进行了评价，并对明显不合理处进行了调整，给出了新的平台设置方案，同时对新方案各平台工作量，所辖3分钟路程节点数进行了比较，验证了新的平台设置方案明显优于现有平台的设置方案（见表3）。对于搜捕围堵疑犯的警力调度问题，以3分钟为时间步长，首先计算出疑犯在逃跑3分钟后的每个时间步长内的可达点及花费时间，然后运用多目标规划

4、，0-1整数规划建立一个封锁疑犯所有可达点的最长时间最小化调度模型，并满足交巡警到达疑犯各可达点的时间小于疑犯到达该点时间，进而讨论了疑犯以40km/h，60km/h，90km/h，120km/h四种不同逃跑速度下的最优搜捕围堵方案（见表4-7）。最后，对文中所建模型进行了深刻探讨，并对文中所建模型进行了评价，同时给出了最优搜捕围堵方案模型允许疑犯逃跑的最大速度为148km/h，进一步讨论了最优搜捕围堵方案模型的改进。关键词：Dijstra算法，多目标规划，0-1整数规划，时间步长法1 问题的重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能

5、。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题1：附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。问

6、题2：对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。问题3：根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题4：针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。问题5：如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，

7、犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。2 模型假设1、假设警车出行线路是双行的，警车在服务于事发节点时不考虑交通拥堵，转弯等的影响；2、假设巡警通讯、处理案件所花费的时间不必考虑；3、假设两节点的路线是直线，且事发地点只能在节点处；4、假设交巡警车在到达事发地点时是匀速行驶（60km/h）；5、假设每辆警车在服务于事发节点时都是选择最短路线；6、假设疑犯在逃跑过程中不会停止；7、假设在全市搜捕疑犯时，各平台警力可跨区进行围堵。3 符号说明 ：A区中交巡警车服务点 （）；：A区中路口节点（包含交巡警车服务点，）； ：路口节点被服务平台的警力

8、封锁的时间；：犯罪嫌疑人驾车从P点到第个路口节点的距离；: 犯罪嫌疑人驾车从P逃跑的速度。4 模型的分析、建立与求解4.1 A区交巡警服务平台管辖范围的分配模型为了使A区中任意一个节点在发生事故后都有交巡警车在最短时间内到达并服务于该点，根据假设1-5，并为了使得事发地点有明确的交巡警平台服务，即一个节点只被一个平台所管辖，我们给出了下面的算法模型：模型1(A区各交巡警服务平台分配管辖范围模型)Step1:构造邻接对称矩阵，为中的元素。其中，,分别为点与点的坐标。Step2:依据邻接对称矩阵，利用Dijstra 算法求出节点到交巡警服务平台的最短距离。Step3:按最短距原则分配节点到平台中。

9、根据上述算法模型，运用MATLAB程序(见附录program1)求解得出A区交巡警服务台管辖路口节点表（见表1）。表1 A区交巡警服务台覆盖路口节点表灰色斜体节点表示所属平台不能在3分钟内可达服务台路口节点服务台路口节点11， 67，68，69， 71， 73，74，75，76， 781111， 26，2722，39，40，43，44， 70， 721212，2533，54，55， 65，661313，21，22，23，2444，57，60，62，63，64141455，49，50，51，52，53，56，58，591515，28，29661616， 36，37，3877， 30， 32， 4

10、7，48，611717，41，4288， 33，461818， 80，81，82，8399， 31， 34，35，451919， 77， 7910102020，84，85，86，87，88，89，90，91，92同时考虑到所管辖节点到平台的时间尽量在3分钟路程内，我们可进一步计算平台到所管辖节点的时间，发现有六个节点（28,29,38,39,61,92，见表1）在所属管辖平台并不能在3分钟内到达，又由于每个节点是按照最短距进行分配，所以这六个节点只能按照表1分配给相应的平台，而A区其余所有节点都可以在所属平台范围内3分钟到达，故按照节点距平台的最短距原则进行分配，就可使得各平台在所管辖的范围内

11、出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。4.2 封锁A区13条要道节点的交巡警服务平台警力的调度模型对于重大突发事件，需要快速封锁全区13条要道节点，根据假设1-5，并考虑到每一个平台的警力最多封锁一个路口节点，同时考虑到现实中警力资源有限，出警时间相同的条件，故问题可转化为各平台出警时间的同步，出警的平台数量最少以及一个平台警力最多封锁一个路口的约束条件下，如何从20个平台中选择13个平台封锁13条要道节点，并使得完成封锁每条要道的时间的最大值要最小，即需要建立一个最长时间最小化模型，因此可运用多目标规划及0-1整数规划理论建立模型。设为路口节点被交巡

12、警服务平台的封锁情况，即并假设为所有服务平台的警力都到达指定封锁路口的最大时间，即在发生重大突发事件后，由于每个平台的警力同时出警，所以目标为到达要道节点所花费时间最长的平台所用的时间最短，即下面讨论约束函数。（1）警力平台的约束。由于一个平台的警力最多封锁一个要道节点的路口，所以，（2）出入城区路口的约束。由于现实中警力资源有限，要求出警的平台数量最少，故每一个要道节点只能被一个平台封锁，所以，为了能够利用Lingo进行方便求解，需要将上述多目标问题进行转化，得到运用Matlab和Lingo程序（见附录program2，LINGO2）可求解出如下平台警力的调度方案。表2 封锁A区13条要道节

13、点的交巡警服务平台警力的调度方案平台3路口16平台4路口38平台5路口62平台6路口48平台7路口29平台9路口30平台10路口12平台11路口24平台12路口22平台13路口21平台14路口23平台15路口28平台16路口144.3 确定需要增加交巡警服务平台的个数及位置模型由前面的分析可得，A区20个平台并不能保证在3分钟内赶到其所管辖的每一个路口节点，同时考虑到现实中警力资源有限的约束，即问题转化为增加平台数最少，并使得增加平台后所有平台都能在3分钟内赶到其所管辖的每一个路口节点。又要求各平台工作量均衡，为此运用各平台工作量（所管辖范围内的发案数和）的标准差来衡量其工作量的均衡，并建立一

14、个对每个节点的出警时间不超过3分钟，且各服务平台工作量的标准差最小（各平台工作量越均衡）的数学模型。设为平台的所管辖的节点的发案数，为拟增加的平台个数，为第个节点的发案数，为平台到所管辖的节点的时间，则A区所有节点的发案数和为，增加平台数后各平台接案平均值为，增加平台数后平台发案率的总和为，为使工作量尽可能均衡，只需要让标准差最小，即为了能够求出增加平台数后的所有方案，下面我们给出穷举算法：算法1：Step1：令，判断是否小于等于5，是，则对所增加的节点位置进行穷举；否则退出；Step2：对于每一增加节点按最短距原则重新分配各节点的管辖范围，并判断所属平台到每个所管辖的节点的时间是否小于3，可

15、以则进行Step3，否则增加节点到下一位置，并转向Step2；Step3：记录该位置的标准差；Step4：计算所有标准差的最小值，并输出结果，同时增加1，转向Step1. 运用Matlab程序(见附录program3)得出最优方案为：增加4个平台，分别增加在节点28,39,48,87.4.4 全市交巡警调度模型在问题1的基础上把A区扩展到全市，题中已给出全市交巡警服务平台的位置，问题在于如何判断题中交巡警服务平台位置是否合理。为此，我们依据设置交巡警服务平台的原则和任务给出评判原则。评判原则：（1）在时间要求的前提下（3分钟内）使交巡警服务平台尽可能到达更多的节点。（2）是否将现有的交巡警服务

16、平台有效的利用。（3）是否考虑人口因素。基于上面的三个评判原则以及给定的交巡警服务平台位置用MATLAB绘图，使每个节点分配给最近的交巡警服务平台管辖，找出该市交巡警服务平台在3分钟内不能达到的节点，这些节点的分布情况如图1所示。图1 该市所有节点的管辖情况图中方框处为交巡警服务平台的位置，实心圆点为交巡警服务平台在3分钟内能到达的位置，空心圆点处为交巡警服务平台在3分钟内不能到达的位置。图2 在三分钟内服务台不能到达的节点由图1显示，有些集中的路口节点没有设置交巡警服务平台，然而有些区域路口节点却比较密集，需要移动或增设平台。于是，可用圆圈的方法找出每个区域内最需要增设交巡警服务平台的节点，

17、具体方法如下。Step1：在每个区中，依次以该区的每个节点为圆心，以巡警车3分钟的路为半径画抽象的圆，即找出巡警车从该节点出发行驶3分钟所能达到的所有节点。Step2：将所画的抽象的圆内所有节点的发案率相加，作为以该节点为圆心的重要等级指标。Step3：找出该区域重要等级指标中最大的节点，即为该区域最需要增设交巡警服务平台的节点。由以上步骤，得到如图3所示每个区最适宜添加服务平台的位置，即为图中五角星处。图3 各区添加服务平台最佳位置图由表格数据可看出，该市各区的人口密集程度不同，因此用各区总人口数除以该区的面积，即为各区的人口密集程度。在人口比较密集且发案率总和较高的市区，应增设交巡警服务平

18、台，在人口密集程度一般的市区，应适当移动某个工作量较低的交巡警服务平台。根据上面的调整方案，做出的调整方案为：分别在B区和区的五角星处添加一个平台，添加前和添加后两区方差比较如表3。表3 添加前和添加后两区方差添加交巡警服务平台前添加交巡警服务平台后3.67873.12855.49994.2202经比较可看出，此改进方案合理。4.5 搜捕围堵疑犯的警力调度P点发生重大刑事案件，犯罪嫌疑人乘车逃跑，3分钟后交巡警接到报警并立即调动全市交巡警服务平台对犯罪嫌疑人进行围堵逮捕。与4.2相似，并根据假设2,6,7，该问题可转化为以最快速度封锁下一刻疑犯逃跑可达节点。假设疑犯逃跑速度为，针对不同速度，我

19、们建立了以时间步长法来搜索并围堵疑犯下一刻可达节点。首先以3分钟为时间步长，计算出疑犯在逃跑3分钟后的每个时间步长内的可达点及花费时间，然后与4.2相似，建立一个封锁疑犯所有可达点的最长时间最小化调度模型，并满足交巡警到达疑犯各可达点的时间小于疑犯到达该点时间，即其中为疑犯在每个时间步长内的可达点，表示疑犯在每个时间步长内的可达点与P点的距离，表示交巡警到达疑犯各可达点的时间小于疑犯到达该点时间。疑犯能否被围堵与交巡警服务平台的调度方案及疑犯逃跑速度密切相关。考虑到交通阻塞等原因可取疑犯逃跑速度小于警车速度，考虑到疑犯为了尽快逃离城区，逃跑速度可取大于警车速度。下面我们分别取疑犯逃跑速度为40

20、km/h，60km/h，90km/h，120km/h四种情况下，运用Matlab和Lingo程序（见附录）的搜捕围堵时间分别为6分钟，18分钟，24分钟，18分钟，相应的围堵方案（见表4-7）。表 4 当犯罪嫌疑人开车速度为40km/h时巡警平台围堵路口节点的情况平台位置编号平台所经过的路口节点935453（5.3415535839.714434498）1010（09.282262734）1638（3.4058772739.742088068）174039（4.4557029649.2920880686.29917881411.9437385）197776756867

21、44（4.12721489211.45889）24435554（4.3825400859.323067506）3656463457（5.91153934410.39306741）45758（2.6181541699.268067408）17576646346260（6.27446111511.61397895）73048235173232231171（6.48659933211.44016214）174219172227228229230（5.90336694111.71010642）64748235173232231（6.98169788410.35849675）173236237238（3

22、.9608826579.629777863）182273241242（7.60637216811.16092954）172227228229230243(2.96450562311.26010642)170227228171231244(5.66218722310.21817312)171230243242246(2.9490869099.819288751)482488560(4.7698700889.604778753)注：1（从表4表7表示根据犯罪嫌疑人开车不同速度逃跑时巡警的不同围堵方案，数据的每一行表示一个巡警平台去封堵一个路口节点的路线，其中深色标记的表示巡警平台初始位置和到达终点

23、路口节点）注:2(每行括号里面的数据，第一个表示交巡警到达最终节点的时间，第二个表示犯罪嫌疑人开车到达最终节点的时间)表5 当犯罪嫌疑人开车速度为60km/h时巡警平台围堵路口节点的情况平台位置编号平台所经过的路口节点326347320349368369248249167(13.1415814220.51877425)179296297306180(5.00496775619.86532001)3656463462190189192193194175196183(15.6052026220.34371448)1977766463462190189168186188176184(15.27742

24、7919.37341492)2446766656463462190189192193194(15.049297218.14612668)175196198199208209210178204(14.1084603220.13096446)177201200207206205210(3.22534241718.13650297)323361322367368369248(14.5968991320.71142938)169254253252250(15.5760274119.03512391)322367368369248249167255(14.0676520518.01532001)1822

25、72271256257(14.497243119.26612998)320349368369248259260261262267(7.74128873219.67617781)321368369248259260261262267268(10.4768194618.77543685)173232231171228227170273182272271270269(7.16336783319.70951393)166181308307180306297298289290285286(14.3194452520.83756535)180306297298289288287(13.552968220.

26、56537607)178284285290289298297(8.69243353919.79827585)172226225170273274179296297298(13.5005546720.41532001)181308307180306297298299(10.7378256820.94696326)167255256257270180305304303300(574888034)174224223225170273274179296297298299304(14.7534743320.27098332)170273274179296297306(13.57

27、79524620.53029509)171228227170273182272271270269307(15.3799447518.60314622)324365366369(0.29154759520.56253091)372456373(12.0257267920.85407851)95115165377376375429432374(7.31874954820.67409621)98165377376423378(68094998)327341340474473385449450451452453462460383(14.2772902820.47861522)

28、374432(10.6734795218.05182407)142122372457374432433(14.023397919.10314622)1323372457374435(9.37103705419.99757341)377376375429432374436(15.1488619219.97861522)376375429431373456455454453(15.4367547719.47861522)1225241323372456(3.53970326720.27861522)37845845737223383460(14.5270015520.71517671)112213

29、23383460461(11.764749419.58712529)93382402403404407438446455454453462(3.10558346418.04683311)380396441386444445446455454453462463(7.56555580920.17476037)384467466468464(6.52772665520.46056623)1026112524470469468466(12.7264539920.09095311)386444447448385449467466468(11.240646418.17278267)383470469(6.

30、78550405618.52072563)385449467384472471(15.5221511820.47460235)478539484(12.3575185320.8409312)479577573485(6.26337354718.4409312)482489490481531530501477500502504507(15.2969860318.40440792)481531530501477500502504507508(14.8275695718.12914292)484539526512511510(7.05758095419.83940606)48056756647853

31、9526512(8.76549325618.79966007)477500502504505513(6.26337354718.4409312)485571569567566565542543536528527525514(15.2969860318.40440792)16560549548532533529521522523524525(14.8275695718.12914292)475555544543536528527525526(7.05758095419.83940606)483511512526539(8.76549325618.79966007)4765535545564755

32、65566567569568574(14.8073263919.92367155)表 6 当犯罪嫌疑人开车速度为90km/h时巡警平台围堵路口节点的情况平台位置编号平台所经过的路口节点38293104105118126127133140141146147(11.0316032726.51919247)96142145146147150(2.27171718926.73262994)99148149152151(4.26020270727.34726624)97143142145146147150152(3.72961155726.87008915)9513699148149152153(6.9

33、4894247127.60644655)328334333331329(11.1073480527.46335793)386442440395392331329330(10.5814033627.05927426)380394393391390(8.57317209828.26613091)表 7 当犯罪嫌疑人开车速度为120km/h时巡警平台围堵路口节点的情况平台位置编号平台所经过的路口节点96134133132100388(9.27579063822.74957671)100388389(7.98679622623.69297482)380394393391390(7.9867962262

34、3.69297482)对于此围堵模型允许疑犯逃跑的最大速度，假设逃跑速度为，则他到达市区第个出口的时间为，其中为P点到市区第个出口的距离，由于疑犯提前3分钟逃跑，故可以计算出警车到达市区第个出口的时间为，和模型4.2相似，我们可以计算出从全区80个平台选出17个平台快速到达市区每一个出口，且只需到达第个时间（），由此可以计算出17个节点的最小的逃跑速度为148km/h。6 模型评价与改进6.1 模型评价模型1的求解运用了Dijstra算法，虽然解决了A区交巡警服务平台管辖范围的分配问题，另一方面使得A区中每一个节点只从属于一个服务平台。这样就使得服务平台失去了灵活性，即当在某一个交巡警服务平台

35、所管辖的范围内同时发生两个案件，则就有一个案件被延误。但是这样的分配方案避免了各服务平台之间因责任推脱而造成无人区。模型2解决了封锁A区13条要道节点的交巡警服务平台警力调度问题，运用多目标规划，0-1整数规划建立的模型比较清晰，同时熟练地运用Lingo快速地给出封锁调度方案。此模型移植性比较好，我们也在模型5中很快的应用，计算出搜捕围堵疑犯的警力调度方案。模型3解决了确定需要增加交巡警服务平台的个数及位置问题，此问题的解决更贴近人性化设计，增添了交巡警服务平台的个数，使得每一个交巡警服务平台的工作强度不会相差太大，而且还提高了交巡警服务平台的工作效率。但还存在个别案件数不多的路口节点占用一个

36、交巡警服务平台，浪费了警力资源，同时此模型的有一点不足之处是所用算法为穷举法，当数据量变大时，运算时间过长。模型4解决了评价全市现有交巡警服务平台设置方案的合理性问题，此问题的解决就是问题1的推广，进一步完善了题目所给的交巡警调度问题，增强了问题1所建模型的实用性。在时间及工作均衡条件的限制下，由于其他因素的影响还存在一些节点在发生案件时不能够被及时处理。这样,就增加了交巡警车的出警时间。模型5解决了搜捕围堵疑犯的警力调度问题，同时很好地将模型2进行移植，并根据所涉及的时间步长法，运用Lingo程序快速地给出疑犯不同逃跑速度下的最优快速围堵方案，可以计算该模型。6.2 模型改进对于模型5，可适

37、当根据区域搜索法进行围堵，首先可以看到P点在A区，可以根据疑犯逃跑速度计算是否能够在A区各出口围堵，不行，则判断出口处，并根据出口处，按照时间步长法进行围堵。参考文献1 薛毅,耿美英，运筹学与实验，北京:电子工业出版社,2008.9。2 韩中庚,宋明武,邵光纪，数学建模竞赛，北京:科学出版社,2007。3 戴明强,李卫军,杨鹏飞，数学模型及其应用，北京:科学出版社,2007。4 叶其孝,郑绍辉，大学生数学建模竞赛辅导教材，湖南:湖南教育出版社,1997。5 魏荣桥,何芊，运筹学，北京:清华大学出版社,2005。6 陈杰，MATLAB宝典，北京:电子工业出版社,2007。附录%program1%

38、function program1clear allclcA=zeros(582);A=A.(-1);B=load('data3.txt');C1=load('data1.txt');C2=load('data2.txt');C=C1,C2;for i=1:size(B,1); A(B(i,1),B(i,2)=(C(B(i,1),1)-C(B(i,2),1)2+(C(B(i,1),2)-C(B(i,2),2)2)(1/2); A(B(i,2),B(i,1)=(C(B(i,1),1)-C(B(i,2),1)2+(C(B(i,1),2)-C(B(i,

39、2),2)2)(1/2);endD=A(1:92,1:92);SS1=;path=;for i=1:92 % dijstra算法 x=i; y=size(D,1); m=size(D,1); T=zeros(m,1); T=T.-1; lmd=T; P=T; S=zeros(m,1); S(x)=1; P(x)=0; lmd(x)=0; k=x; while 1 a=find(S=0); b=find(S=1); if size(b,1)=m break end for j=1:size(a,1) p=a(j,1); if A(k,p)=inf if T(p)>P(k)+D(k,p) T

40、(p)=P(k)+D(k,p); lmd(p)=k; end end end mi=min(T(a); if mi=inf break else d=find(T=mi); d=d(1); P(d)=mi; T(d)=inf; k=d; S(d)=1; end end SS1=SS1,P; %所有路口到所有服务台的最短路矩阵 path=path,lmd;endsave SS1E=zeros(92,20);for i=1:92 a,b=min(SS1(i,1:20); E(i,b)=1; %一对一0-1矩阵endfor i=1:20 Z1(i,1:length(find(E(:,i)=find(E(:,i);endZ1%一对一管辖矩阵(按最短距原则)F=zeros(92,20);vec=;for i=1:92 for j=1:20 if SS1(i,j)<=30 F(i,j)=1; end end if isempty(find(F(i,:) vec=vec,i; a,b=min(SS1(i,1:20); F(i,b)=1; end endvec%按3分钟原则后无法分配的temps=sum