2011年数学建模B题国家一等奖

1交巡警服务平台的设置与调度摘要：在我国经济社会快速发展进程中,警察的工作任务日益繁重。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。问题一：（1）题目要求在城区A的20个巡警服务台位置确定的情况下，按照尽量3min到达案发地的原则为各服务平台分配管辖范围。对于此问题本文建立最大集合覆盖模型，并利用数学软件MATLAB进行分配求解，最后得到A区现有每个巡警服务台的管辖范围如表1。（2）我们对于13条交通要道实现快速全封锁的问题，以所用时间最小为目标，引入0-1变量，建立该问题的0-1规划模型，并借助数学软件LINGO进行求解，求解结果表明需要8.05分钟可以实现快速封锁。（3）由问题（1）的分配结果可知，在现有巡警服务台的设置下：①还有6个路口在案发时巡警不能在3min之内到达，即某些地方出警时间过长；②我们根据巡警服务台的工作量的方差定义工作量不均衡度，结果显示：此时服务台的工作量不均衡度为8.4314。为了解决上述出警时间过长与工作量不均衡的问题。我们建立集合覆盖的0-1规划模型，求解结果表明：在增加4个平台的情况下，可以解决出警时间过长的问题。在此基础上我们优化分配方案：在增加4个巡警服务台的情况下，使平台的工作量的不均衡度降为3.0742。增加的4个巡警服务台的路口标号见表8。问题二：（1）本文定义了两个评价原则，原则一：巡警能在3min之内到达案发路口；原则二：巡警服务台的工作量均衡度尽量小。根据以上两个原则对该市现有巡警服务台的设置方案的合理性进行评价，评价结果显示：①全市有138个路口，在案发时巡警不能在3min之内到达；②此时的不均衡度已达40.3。基于上述两点，现有的巡警服务台设置不合理。针对现有巡警服务台设置不合理的情况下，本文提出三种方案对设置进行优化调整。方案一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；方案二：保持现有巡警服务台的个数，但对其位置进行调整；方案三：不考虑现有巡警服务台的设置情况，重新确定全城的最佳巡警服务台数目与位置。（2）本问题实质是单目标规划问题，我们建立0-1规划模型，以巡警围堵时间最短为目标，以成功围堵为条件。对于巡警的成功围堵，可以转化为二部图的完全匹配，利用匈牙利算法，求得最佳围堵方案，原始方案和三种优化方案的求解结果见表18、表19、表20和表21。关键字：最大集合覆盖0-1规划模型MATLAB软件LINGO软件二部图2一、问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：问题一：(1)根据附件中的图与数据，为城区A中各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。问题二：（1）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。（2）如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析与建模思路问题一：（1）问题要求在城区A的20个巡警服务台位置确定的情况下，按照3min到达案发地的原则为各服务平台分配管辖范围。本文引入经典离散定位理论中的最大集合覆盖模型进行求解。记{1,292}I为城区A的所有路口节点集合，{1,220}J为城区A巡警服务台的节点集合，,ijciIjJ为巡警服务台j到达路口i的最短距离。引入0-1变量,ijsiIjJ，当路口i分配给巡警服务台j管辖是为1，当路口i不分配给巡警服务台j管辖是为0。即：1,0ijijsij路口分配给服务台管辖，路口不分配给服务台管辖由题目的要求可知，当3ijckm时，路口i可能分配给巡警服务台j，也可3能分配给其他可在3min到达i路口的巡警服务台，而不分配给平台j，故有1ijs；当3ijckm时，巡警服务台j不可能在规定的时间内到达路口i，故此时路口i不能分配给巡警服务台j管辖，故此时0ijs。根据上述的分配原则及每个路口只由一个巡警服务台进行管辖、每个巡警服务台至少要管辖一个路口，可建立最大集合覆盖模型，并借助数学软件MATLAB进行求解。（2）问题要求调度全区20个交巡警服务平台的警力资源，对进出A区的13条交通要道进行快速全封锁，且每个平台的警力最多封锁一个路口。本文将问题转化为：从20个服务平台中选出13个对13条交通要道进行封锁，且这13个平台所用的时间要最小的规划问题。本文引入0-1变量表示一个巡警服务台是否封锁一条交通要道，从而建立这个问题的0-1规划模型，并借助数学软件LINGO进行求解。（3）根据问题一（1）的分配方案可知：当标号为39、61、28、29、38、92的路口有案件发生时，标号为2、7、15、16、20的巡警服务台的出警时间将超过3min，即出警时间过长。此时每个巡警服务台的工作量分别为：表1按问题一（1）的分配方案20个巡警服务台的工作量平台标号12345678910工作量10.38.35.66.69.72.5958.21.6平台标号11121314151617181920工作量4.648.52.52.13.85.36.13.410.7此时巡警服务台的工作量不均衡度为8.4314。由1），2）可知现有巡警服务台的工作量极其不均衡且有些地方出警时间过长。针上述问题，题目要求再增加2—5个巡警服务台来解决上述问题。本文首先建立集合覆盖的0-1规划模型，然后利用MATLAB对模型进行求解，可得到初步的分配方案，最后再引入工作量不均衡度，通过计算求解可确定增加巡警服务台的数目与位置。问题二：（1）本文定义了两个评价原则：原则一：巡警能在3min之内到达案发路口原则二：巡警服务台的工作量均衡度尽量小。根据以上两个原则对该城区现有巡警服务台的设置方案的合理性进行评价。若现有巡警服务台的设置不合理，本文则提出三种方案对全城的巡警服务台设置进行优化：方案一：保持现有巡警服务台的个数和位置，再在其他路口增设巡警服务台；方案二：保持现有巡警服务台的个数，但对其位置进行调整；方案三：不考虑现有巡警服务台的设置情况，重新确定全城的最佳巡警服务台数目与位置。（2）当该市某路口发生重大刑事案件时，犯罪嫌疑人已逃跑，由于在案发3min后巡警才能接到报警，为了快速搜捕嫌疑犯，将调度全市交巡警服务平台警力围堵嫌疑犯。因为警车相对于嫌疑犯车延迟三分钟行驶，而且巡警不知道嫌疑犯逃跑方向，所以此问题可转化为以下模型：对于任意时间t，嫌疑犯驾车逃4跑的最大范围为：在3t时间内嫌疑犯所有可能行驶路线所包含路口节点的并集，记为Q，将Q的边界点集记为Q。所谓最快围堵方案，即寻找一个最短时间t，适当的调配巡警警力，使其在t时间内能够到达边界点Q，这样嫌疑犯就被控制在区域Q中，此时嫌疑犯将无法逃脱。三、基本假设与符号说明3.1基本假设1.假设每个巡警服务台的职能和警力配备基本相同；2.假设每个路口只由一个巡警服务台进行管辖；3.假设每个巡警服务台至少管辖一个路口；4.假设巡警都按最短路径到达各案发路口；5.假设犯罪案件都在路口上发生；6.假设在重大案件发生时，每个平台都有能够封锁一个路口的能力；7.工作量：每个巡警服务台所管辖范围内的所有路口案发率之和；8.出警时间：巡警到达案发路口所需时间；9.假设逃犯的逃跑速度等于警车的行驶速度；10.假设巡警在接到报案后并不知道逃犯的逃跑方向；3.2符号说明1.ijc：为巡警服务台j到达路口i的最短距离，其中：1,292i，1,220j；2.iju：为路口i与路口j之间的最短距离，其中：1,292i，1,292j2.1,0ijijsij路口分配给服务台管辖，路口不分配给服务台管辖，其中：1,292i，1,220j；3.0313ijijijukmkukm，其中1,220i，1,292j3.10ijijxij，服务台对要道进行封锁，服务台不对要道进行封锁，其中1,220i，1,292j；4..jc：j巡警服务台的工作量，其中1,224j；5.C：平均工作量6.iIn：i路口的发案次数，其中1,292i；7.：工作量不均衡度；8.ABC类路口：只由一个服务台进行管辖；类路口：可被多个服务台进行管辖；类路口；不能被任何服务台进行管辖；9．isolatedI：C类路口的集合；10.3tQ：嫌疑犯在3mint内行驶的最大区域；511.3tQ：嫌疑犯在3mint内行使的最大区域边界点集；四、模型的建立与求解4.1问题一（1）：管辖区域的确定---最大集合覆盖模型4.1.1模型建立：最大覆盖函数：根据问题一（1）的分析确定最大覆盖函数为：1192120maxijiiIjJjfs。满足条件：1）因为每个路口只由一个巡警服务台管辖，所以1()ijjJsiI；2）根据实际情况每个巡警服务台管辖的路口数至少等于1，所以1()ijiIsjJ。综上所述，得到最大集合覆盖模型为：1192120max1(3)0(3)s.t.1()(1)1()01ijiiIjJjijijijijijjJijiIijfssckmsckmsiIsjJs满足：或4.1.2模型求解：1.最短路径矩阵9292U的建立本文选用Warshall算法确定城区A任意两个路口之间的最短路径矩阵9292U。Warshall算法为：任意两点(,)ij之间的最短路径（记为ijD）等于从i出发到达j点的以任一点为中转点所有可能方案中，距离最短的一个。即：min(,,),1ijijikkjDDDDkn，n为节点总数。计算方法为：(1)0iiu，(1)ijijuwij，(1)()()()min{,},,,1,,kkkkijijikkjuuuuijkn在上式中，临时标号()kiju是不通过,1,,kkn节点（,ij除外）时从节点i到节点j的最短路径。通过上述算法，利用数学软件MATLAB计算出各节点的最短路径，组成一个最短路径矩阵9292U。矩阵中，元素1iju为从路口1i到路口j的最短距离，其中61192i，192j。2.集合覆盖矩阵9220K的建立以巡警服务台能否在3min内到达案发路口为分配标准，将上述最短路矩阵转化为集合覆盖问题，即0-1覆盖问题。转化方法为：03(2)13ijijijukmkukm此时将得到集合覆盖矩阵9220K。此时从矩阵中可以得到巡警服务台在只考虑能在规定时间内到达的初始分配情况。3.最终分配方案的确定从上述得到的集合覆盖矩阵中，我们可以清楚的看到如下问题：1）在仅满足分配标准时有些路口可同时被多个巡警服务台管辖；2）在仅满足分配标准时标号为28、29、38、39、61、92的路口无巡警服务台进行管辖；那么此时并不满足模型的要求，