2011全国大学生数模竞赛B题参赛论文-交巡警服务平台的设置与调度.doc

2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要本文主要是研究城市交巡警服务平台的设置、管辖范围的分配、警务资源的调度等问题。在对各个问题的研究过程中分别采用了Dijkstra 最短路径算法、指派模型，0-1规划，多目标规划模型，层次分析法等模型和算法。本题共有5个问题，问题一中包括3个小问，其研究对象都是A区的交巡警服务平台。问题二有2个小问，其研究的对象则扩大到全市的交巡警服务平台。第（1）问是为交巡警服务平台分配管辖范围。该市A区共有92个路口节点，其中20个设置有交巡警服务平台。管辖范围的分配原则是能使警车以60km/h的速度在3分钟内达到，若存在节点同时满足多个平台都能在3分钟内到达，那么就以就近原则分配。最后用Dijkstra 最短路径算法来筛选从服务台出发能在3分钟达到的路口节点，并通过MATLAB编程得到分配方案。但是结果显示有6个路口节点是警车无法在3分钟内到达的。如下表3分钟内无法到达的路口节点282938396192第（2）问是要设计一个调度方案，使得在发生重大事件时，能够最快封锁13条出入该区的交通要道。约束条件是一个平台的警力只能封锁一个路口，我们将其归结为“一事多人”的指派问题。建立指派模型后用LINGO编程，考虑到算法的复杂性，可以先从实际情况出发，排除远距离指派警力封锁的可能性。于是可以由LINGO运算得到结果为用时最短的最优调度方案。该方案所需花费的时间是8.01分钟。第（3）问是选址问题，要在A区内选取2-5个点建立交巡警服务平台。根据问题（1）可知有6个节点是警车无法在3分钟内到达的，所以在选择新增服务平台的地址时要考虑让这些点满足3分钟内到达的目标，另外还要综合考虑新增平台能否有效分担原有服务平台的工作量。所以可以建立多目标规划模型，最后解得需要新增4给服务平台，分别设在节点29、40、48、89上。第（4）问是评价该市现有交巡警服务平台设置方案的合理性，所以采用层次分析法来分析研究。通过计算后得到权重，即A-F区现有交巡警服务平台设置方案权重分别占0.2188，0.1204，0.2142，0.1530，0.1497和0.1439 。权重大的平台设置较合理。由于各区所占权重相差不大，所以无明显不合理的情况存在。 第（5）问是设计围堵方案，去围堵逃逸的犯罪嫌疑人。假设犯罪嫌疑人犯案后必定逃离A区，那么就有两种可能，一是犯罪嫌疑人还没逃离A区就已经被围堵抓获。另一种情况是逃犯逃离了A区在其他区被分度抓获。最后使用穷举法，找出所有可能的情况。关键词：Dijkstra算法 指派模型 多目标规划模型 层次分析法 穷举法 0-1规划模型17一 问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：1.1 问题一：（1）根据附件1中的图表，附件2的相关数。为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。1.2 问题二：（1）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。（2）如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二 问题分析2.1问题一： 第（1）问的目标是为20个交巡警服务平台分配管辖范围，其约束条件是使在管辖范围内出现突发事件时，交警以60km/h的时速尽量能在3分钟内到达事发地。由附件2提供的数据可知，该市A区共有92个路口节点，其中20个设置有交巡警服务平台。以服务台为出发点选择能在3分钟内到达的，则选为该服务台的管辖范围。于是引入Dijkstra 最短路径算法来筛选从服务台出发能在3分钟达到的路口节点。第（2）问的目标是将20个交巡警服务平台的警力资源分配到13个进出该区的路口，其约束条件是一个平台的警力最多封锁一个路口。这个可以理解为“一事多人”的指派问题的推广。再使用穷举法穷举出所有可能的调度方案，然后根据短板效应的原理，选择一个方案所花地调度时间最短的为最优调度方案。第（3）问的目标是选择该区的一些路口建立平台，根据第（1）问得结论可以知道有6个节点是警车在三分中内是无法到达的，所以要考虑在这些点附件新增服务点，使得能有警车在3分钟内能到达该节点，这里可以引用问题（1）建立的模型来找出符合的节点，然后根据所选节点能否分担周边服务台的工作量 。22 问题二：第（1）问是要求对该市现有的交巡警服务平台设置情况进行评价，对存在明显不合理的，给出解决方案。本文结合城区面积、人口，案发率的数据，综合考虑各区服务平台密度，各区人均享有平台数，各区平均案发率和各区单位个数平台管辖的总距离这四项指标，建立综合评价模型。以全市交巡警平台合理分布为目标层，上述四项指标为准则层，分别以A， B，C，D，E，F这六个区各自的平台分布方案为方案层，用层次分析法进行分析，得出各个方案的权重。权重较大的城区就是在设置交巡警平台时相对合理的城区。第（2）问考虑到犯罪嫌疑人在A区犯案之后肯定要逃离该区，所以要在最短时间内封锁所有出入A区的路口，然后对犯罪嫌疑人进行搜捕。然而，由于在接到报警前，犯罪嫌疑人已经驾车逃离3分钟，根据第一问中求出的答案，在封锁13个出入A区的路口时需要8.01分钟，因此在接到报警后，按照预定的封锁计划可能会出现犯罪嫌疑人已经逃离A区的情况。所以要对原先封锁13个出入A区路口的方案进行改进。利用GPS跟踪犯罪嫌疑人的行踪，根据犯罪嫌疑人的行踪，充分估计到犯罪嫌疑人逃离路线的所有可能，在时间允许的情况下，封锁关键路口，即有好几种逃离路线都可能经过的共同路口；在时间来不急，犯罪嫌疑人已经逃离A区的情况下，调动其它区的警力对犯罪嫌疑人可能逃离的路线进行围堵。一旦围堵成功，那么在这个范围内抓捕犯罪嫌疑人就是轻而易举的事，所以本文着重考虑如何围堵，而不考虑围堵后抓捕的过程。三 模型假设（1） 所有事件均发生在区域图所示的道路上，不会发生在空白区域内。（2） 接到报警后交巡警立刻赶往事发现场，不考虑实际中存在的延时。（3） 警车均以60km/h的速度赶往事发现场，不受路况影响。（4） 每次出警后均能处理好事件。（5） 犯罪嫌疑人在A去犯案后要逃离A区（6） 假设犯罪嫌疑人驾车逃跑的速度为60km/h（7） 假设犯罪嫌疑人最初选择的逃跑路线是所有从案发点到离开A城区路口的最短路线之中的一条（8） 假设犯罪嫌疑人在不知道道路前方已经有警察的情况下会继续按原定路线逃离A区，当遇到前方有警察时，立刻返回至该路段的起始结点处，在随机选择其他路线逃离四 符号说明警车的速度交巡警到达事发现场所用时间，交巡警时间内能达到的最大路径A区交巡警平台编号表示全市各路口节点，所有路口节点集合从服务平台到路口节点的路径路径上的权值已经找到从出发的最短路径的终点的集合第个交巡警服务平台管辖的路口节点集合表示从到每个终点的最短路径长度五 模型的建立与求解5.1问题一5.1.1 Dijkstra算法分配管辖范围Dijkstra 算法是由著名的数学家EWDijkstra 于1959 年首先提出来的。它是按路径长度递增的次序产生最短路径的一种算法,该算法采用了在优化问题中常用的贪心技巧。贪心算法在每一步都选择局部最优解以期望产生一个全局最优解。采Dijkstra 算法不仅求出从起点到终点的最短路径,而且最后所得到的实际上是从起点到各顶点的最短路径2。引用图论相关知识，将附件中所提供的交通要道线路网络抽象成一个有向赋权图,其定点为道路节点，如果中的顶点到有可达到的路线那么两点之间就用有向边相连，记作，方向从指向，相应有一个数表示该有向边的权。赋权图中的权值可根据不同的目标进行定义，本模型将从到的路径长度定义为权。不妨定义为所有路口节点集合，为有向边 的最短路径长度，第一次取值时为从起点到选择的第一个节点的路径长度，即 ，接着选择第个节点时，要重新赋值，使其为最小值定义为已经找到从出发的最短路径的终点的集合，若果符合要求则加入集合的求解过程是不断搜索下一个最短路径比已有的最短路径短的节点，一旦搜索到更短的路径方案，就用该路径的值代替原来的路径，继续搜解，直到剩下所有结点可达的最短路径都比现在的大，则记录该方案，输出该最短路径的值。： 综上所述，建立模型可得第个平台的管辖范围为：上式中要判断路口结点集合中的结点是否都属于第个平台结点的管辖范围，通过比较集合中各点到平台结点的最短路径是否小于管辖范围，如果小于则属于其管辖范围。其中题目给出条件，在交巡警服务平台所管辖范围内发生突发事件，尽量能在3分钟内赶到，而且给出了交巡警的警车速度为60km/h。可得：于是可以以各路口到所有交巡警平台的最短路径长度最短为目标，最短路径小于3km为约束条件，建立优化模型:其中表示路口结点，可以使用0-1规划模型来求解，定义变量为0时表示不在平台管辖范围之内，为1则表示在平台管辖范围之内。下图为A区交通网络与平台设置示意图模型建立后运用MATLAB5编程计算（代码见附录一）得各平台的管辖范围如表2表2 交巡警服务平台管辖范围交巡警服务平台管辖的路口节点交巡警服务平台管辖的路口节点1,67,68,69,71,73,74,75,76,7811,25,26,272,40,43,44,70,72123,54,55,65,6613,21,22,23,244,57,60,62,63,64145,49,50,51,52,53,56,58,5915616,36,377,30,32,47,4817,41,428,33,4618,80,81,82,839,31,34,35,4519,77,791020,84,85,86,87,88,89,90,91通过编程计算后发现有6个路口节点，警车是不能在3分钟内到达的，我们归为异常节点，见表2表2 3分钟内无法到达的路口节点282938396192所以以现有的交巡警平台数量不足以管辖全区所有的结点，这些异常点只有在发生突发状况时才会派警力前往处理。5.1.2 指派模型求解最佳调度方案传统的指派问题中，一般要求被分配的人数和要做的工作件数相等，每个人要做且只做一件事3。本题相当于20个人要去做13件事，且每件事只许一个人去做，所以这里将指派问题推广到“一事多人”的问题。建立优化模型如下表示第个封锁点由第处平台派警力封锁，表示对应该封锁点由平台派警力去封锁的调度方案所对应的路程。该问题可以用0-1规划模型求解。为0时表示不调度平台派警力去封锁封锁点，为1时表示调度平台派警力去封锁封锁点。其中的函数是关于和的路程函数。考虑到算法的复杂性，难以用LINGO编程实现，所以联系实际情况，距离过远的平台不会远距离调度，以此来初步划定13个封锁点各自对应的几个附近的平台，一旦需要封锁，就调度封锁点附近的平台进行封锁。表4是划分后的情况：表4 封锁点附近平台封锁点附近的平台封锁点附近的平台1212，11，13，10624，2412，13，11487，5，62313，11307，6，52213，11，14297，151413，11，16，142815，71614，16，92113，14，113816，17，9，2用LINGO11.04编程得到最佳封锁方案如表5：表5 交巡警服务平台警力调度方案编号封锁点调度的服务台路径路径长度/km时间/min11210102627123.983.982141616140.350.35316993536166.746.744211414213.063.065221111221.531.536231313238.018.01724121225244.754.758281515282.482.489297730293.273.2710308833327303.263.261138224039387.587.5812485547480.500.5136244623.593.59可得该封锁方案所需时间为8.01分钟5.1.6 多目标规划模型求解新增服务点由第（1）问可知，A区中有六个节点是警车无法在三分中内到达的，见表6表6 3分钟内无法到达的路口节点282938396192在设置新的服务平台时优先考虑这六个节点，要使得能有警车在3分钟内到达该节点，即如果直接把服务台设置这些节点上固然能满足要求，然而由附件提供的交通网络图可以发现，在这六个节点近邻存在一些更优节点，这些节点不但能解决3分钟内不能到达的问题，还能更好缓解周边服务平台的工作压力。综合发案率、三分钟内可到达的点数，按照其所占权重，可得所以，建立模型得为节点处的发案率，为三分钟内可到达的节点数，为节点处的综合指数。表示确定要建立服务平台的节点的集合由5.1.1建立的Dijkstra模型，再通过MATLAB编程可得这些节点的数据，见表7表7 新增服务台待选点数据分析区域路口节点发案率（件数）三分钟内可到达的点数综合指数1281.311.126291.411.2262381.220.699391.420.819401.775.1273481.499.080610.610.2804880.9143.378891.4143.613900.9143.378910.9143.378920.853.344确定要建立服务平台的节点的集合5.2问题二 5,2.1 层次分析法评价服务台设置方案的合理性建立层次结构由附件提供的数据，整理后得到各准则层的相关数据，见表8表8城区各区单位面积享有平台数（台/平方公里）各区人均享有平台数（台/人）各区平均案发率（次数）各区单位个数平台管辖的总距离A0.9090.3671.3534086.29B0.0780.3810.9103323.93C0.0770.3471.21618139.41D0.0230.1231.3043006.94E0.0350.1971.1599034.99F0.0400.2081.0111483.69建立判断矩阵：其中表示相对于的重要程度，且有 确定特征向量：及最大特征根计算一致性指标一致性比率：得到结果见表9表9-1 判断矩阵表层权重=4=0=00.111/31/71/50.0625313/73/50.187577/317/50.437555/35/710.3125表9-2 判断矩阵表=6=0=00.119/59/599/29/20.37505/91155/25/20.20845/91155/25/20.20841/91/51/511/21/20.04172/92/52/52110.08332/92/52/52110.0833表9-2 判断矩阵表=6=0=00.1114/34220.2500114/34220.25003/43/4133/23/20.18751/41/41/311/21/20.06251/21/22/32110.12501/21/22/32110.1250表9-3 判断矩阵表=6=0=00.117/27/517/47/30.25002/712/52/71/22/30.07145/75/215/75/45/30.178617/27/517/47/30.25004/724/54/714/30.14283/73/23/53/73/410.1071表9-4 判断矩阵表=6=0=033-34-9-35-36-16-1422132-33-34-9-35-36-16-14-2132232-33-34-10-26-11-2242332-33-34-10-26-11-22-13-2352432-33-34-10-26-11-25-2461232-33-34-10-26-27-12路线1和路线2都要经过，而在犯罪嫌疑人还未到达时已经接到报警，由于处有交巡警平台，所以可以直接进行封锁。在接到报警后，派处的警力去，派处的警力去，处的警力原地封锁。表示成如下方式 ， ， 最终将犯罪嫌疑人围堵在16、35、39、7结点形成的包围圈内。路线3-6都要经过，而犯罪嫌疑人还未到达时已经接到报警，由于处有交巡警平台，所以可以直接进行封锁。而且在这种情况下，犯罪嫌疑人还在开往的路上，只需派的警力去，即可将犯罪嫌疑人围堵在10-34这条路上表11-1 从A区逃向F区路线出A区的路口逃跑线路73832-33-34-9-35-36-39-3881632-33-34-9-35-36-16路线7要经过，可是犯罪嫌疑人经过时，处警察还未接到报警，无法及时进行围堵，当接到报警时，犯罪嫌疑人已经在往的路上。立刻派处的警力去，同时派处的警力去，处的警力去，处的警力在原地封锁。最终将犯罪嫌疑人围堵在36、38、40、4形成的包围圈中。 路线8的围堵方法与路线1、2的围堵方案一致。表11-2 从A区逃向D区路线出A区的路口逃跑线路92932-7-30-29102832-31-15-28路线9要经过交巡警平台7，可是犯罪嫌疑人经过时，处警察还未接到报警，无法及时进行围堵，当接到报警时，犯罪嫌疑人已经在往的路上。立刻派处的警力去，同时派处的警力去。最终将犯罪嫌疑人围堵在29-30这条路上。 路线10要经过，而犯罪嫌疑人还未到达时已经接到报警，由于处有交巡警平台，所以可以直接进行封锁。接到报警后，立刻派处的警力去。最终将犯罪嫌疑人围堵在15-31这条路上。表11-3 从A区逃向C区路线出A区的路口逃跑线路116232-7-47-6-59-58-57-60-62124832-7-30-48133032-7-30142932-7-30-29路线11要经过，而犯罪嫌疑人还未到达时已经接到报警，由于处有交巡警平台，所以可以直接进行封锁。接到报警后，立刻派处的警力去。最终将犯罪嫌疑人围堵在47-6这条路上。 路线12，当犯罪嫌疑人到达时一共才行驶了2.43km，即犯罪嫌疑人可以逃离A区。再根据A区到C区点距离为1.698km，所以在接到报案时，犯罪嫌疑人正在48-235这条路上。接到报警后，立刻派C区的警力去，同时派的警力去。最后将犯罪嫌疑人围堵在48-235这条路上，即正要从A区进入到C区的路上。 路线13，当犯罪嫌疑人到达时一共才行驶了1.72km，即犯罪嫌疑人可以逃离A区。再根据A区到C区距离为1.868km，所以在接到报案时，犯罪嫌疑人正在30-237这条路上。接到报警后，立刻派的警力去，的警力去，的警力，的警力去，结点的警力原地封锁。最终将犯罪嫌疑人围堵在由238、245、232、168、7所形成的包围圈内。 路线14与路线9的围堵方案一致。六 模型评价及推广6.1模型优点：（1） 第（1）问中采用Dijkstra算法在计算最短路径时效果较好，针对性强。（2） 第（2）在使用穷举法搜解之前，先从实际情况出发，对13个封锁点附近的交巡警平台进行划分，将那些明显不符合实际情况的结点排除在考虑范围之外。有利于减少穷举法的时间复杂度，便于搜得最优解。（3） 问采用多目标规划，根据需要考虑的目标重要程度不同，对目标进行主次区分，采取多步规划的策略，得出的解在保证满足主要目标的前提下，尽量满足次要目标。思路清晰，过程清楚。（4） 第（4）问中在评价现有交巡警平台设置情况是否合理时，将城区面积、人口，各结点的案发率，平台管辖的范围等都纳入评价模型之中，思考全面。（5） 第（5）问设计最佳围堵方案时，充分考虑到犯罪嫌疑人的智商和心理，先初步拟定所有可能逃跑的路线，再对犯罪嫌疑人路遇警察封锁，会折返该路段起始点，并重新选择逃跑路线这一实际情况进行研究。在这种情况下设计出的围堵方案具有很强实践性和可操作性。6.2模型缺点：（1） 第（2）问中根据实际问题，可能性很多，本文进行了主观判断，首先确定13个封锁点附近的点，然后利用穷举法进行求解。该过程由于主观地对20个交巡警平台进行位置的划分，虽然简化了算法，可是有可能会使得最优解丢失。（2） 第（4）问中层次分析的过程中，在确定对比矩阵时，存在较大的主观性。对全市不合理的交巡警平台设置，没有分析哪些是存在明显不合理的情况，而且缺少具体的改进方案。（3） 问中在研究交巡警平台如何调派警力对犯罪嫌疑人进行围堵时，很大程度上取决于犯罪嫌疑人已经逃离的距离，以及在接到报警之后，犯罪嫌疑人的驾车速度。所以假设犯罪嫌疑人的驾车速度是60km/h可能会对围堵方案造成很大的影响。七文献参考1 乐阳 龚健雅，Dijkstra 最短路径算法的一种高效实现，武汉测绘科技大学学报，第24卷第3期：209至212页，1999年9月。2 严蔚敏,吴伟民. 数据结构M ，清华大学出版社, 158- 159，1997. 3 姜启源，数学模型，北京：高等教育出版社，2004年4 谢金星、薛毅，优化建模与LINDO/LINGO软件，北京：清华大学出版社，2005年7月第一版5 Duane Hanselman、Bruce Littlefield 著，朱仁峰译，Matlab 7，北京：清华大学出版社，2006 年5月第一版6 尚东方,张黎明,张业宏,基于最佳路径的警力资源调度改进算法, 上海电机学院学报，第14 卷第1期： 63至66页 2011年附录一#include#include #includeusing namespace std;const int maxnum = 260;/* change 100 - 200*/const double maxint = 200