全国数学建模竞赛一等奖论文.doc

交巡警服务平台的设置与调度摘要由于警务资源有限，需要根据城市的实际情况与需求建立数学模型来合理地确定交巡警服务平台数目与位置、分配各平台的管辖范围、调度警务资源。设置平台的基本原则是尽量使平台出警次数均衡，缩短出警时间。用出警次数标准差衡量其均衡性，平台与节点的最短路衡量出警时间。对问题一，首先以出警时间最短和出警次数尽量均衡为约束条件，利用无向图上任意两点最短路径模型得到平台管辖范围，并运用上下界网络流模型优化解,得到A区平台管辖范围分配方案。发现有6个路口不能在3分钟内被任意平台到达，最长出警时间为5.7分钟。其次，利用二分图的完美匹配模型得出20个平台封锁13个路口的最佳调度方案，要完全封锁13个路口最快需要8.0分钟。最后，以平台出警次数均衡和出警时间长短为指标对方案优劣进行评价。建立基于不同权重的平台调整评价模型，以对出警次数均衡的权重u和对最远出警距离的权重v为参数，得到最优的增加平台方案。此模型可根据实际需求任意设定权重参数和平台增数，由此得到增加的平台位置，权重参数可反映不同的实际情况和需求。如确定增加4个平台，令u=0.6，v=0.4，则增加的平台位置位于21、27、46、64号节点处。对问题二，首先利用各区平台出警次数的标准差和各区节点的超距比例分析评价六区现有方案的合理性，利用模糊加权分析模型以城区的面积、人口、总发案次数为因素来确定平台增加或改变数目。得出B、C区各需改变2个平台的位置，新方案与现状比较，表明新方案比现状更合理。D、E、F区分别需新增4、2、2个平台。利用问题一的基于不同权重的平台调整评价模型确定改变或新增平台的位置。其次，先利用二分图的完美匹配模型给出80个平台对17个出入口的最优围堵方案，最长出警时间12.7分钟。在保证能够成功围堵的前提下，若考虑节省警力资源，分析全市六区交通网络与平台设置的特点，我们给出了分阶段围堵方案，方案由三阶段构成。最多需调动三组警力，前后总共需要29.2分钟可将全市路口完全封锁。此方案在保证成功围堵嫌疑人的前提下，若在前面阶段堵到罪犯，则可以减少警力资源调度，节省资源。【关键字】：不同权重的平台调整评价 模糊加权分析 最短路 二分图匹配目 录一、问题重述3二、问题分析3三、模型假设3四、定义与符号说明3五、问题一 平台管辖范围的确定45.1 建模分析45.2基于上下界网络流模型的平台管辖范围的确定45.3 结果及其分析与评价5六、问题一 交巡警调度方案的确定66.1 建模分析66.2 基于二分图完美匹配模型的调度方案的确定66.3 结果及其分析与评价6七、问题一 平台设置调整方案的确定77.1 建模分析77.2 指标体系77.3基于不同权重的平台调整评价模型的平台设置方案77.4 结果及其分析与评价8八、问题二 平台设置方案评价及调整108.1 建模分析108.2 评价现有方案的合理性108.3 基于模糊加权分析模型，确定平台增加或改变数量118.4利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置128.5 利用问题一基于不同权重的平台调整评价模型确定优化方案138.6 结果及其分析与评价13九、问题二 全市围堵方案的确定139.1 建模分析139.2 基于二分图的完美匹配模型的围堵方案139.3 可节省警力资源的分阶段围堵方案14十、参考文献16一、问题重述现需在某市的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同，但警务资源有限。故需根据城市的实际情况与需求建立数学模型来合理设置交巡警服务平台、分配各平台的管辖范围、调度警务资源。(1)已知A区交通网和现有20个交巡警服务平台的位置。建立数学模型，为各平台分配管辖范围，使其管辖范围内出事时，尽量在3分钟内（车速为60km/h）赶到。(2)若有重大突发事件，需调度全区20个交巡警服务平台的警力，建立模型计算如何用最短时间对进出该区的13条交通要道实现全封锁。一个平台最多封锁一个路口。(3)根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，建立模型确定需要增加平台的具体个数和位置。(4)已知城区的面积、人口、发案率，按照设置交巡警服务平台的原则和任务，评价全市A，B，C，D，E，F六区现有交巡警服务平台设置方案，并给出优化解决方案。(5)P（32号节点）处发生重大案件，案发3分钟后接到报警，罪犯已逃跑。需用最短时间搜捕罪犯。在现有平台设置方案下建立模型，给出调度全市平台的最佳围堵方案。二、问题分析要求各平台（车速为60km/h）尽量在3分钟内赶到事发地，即平台与其辖区内各节点的最短路尽量在3km内。每个交巡警服务平台的工作能力有限，各节点发案率高低不同。分配平台管辖范围和确定围堵方案时，应考虑让各平台工作量尽量均衡。平台工作量即出警次数，可用其标准差来衡量均衡性。出警时间长短则用节点与平台的距离来判断。确定评价指标，对现有方案合理性进行评价，通过计算比较确定需要增加平台的具体个数和位置。三、模型假设(1)假设一个路口节点可以被多个交巡警服务平台管辖管辖。(2)假设A、B、C、D、E、F区域内的交巡警服务平台只管辖各自区域内的节点。(3)假设在发生重大刑事案件时A、B、C、D、E、F区域内的交巡警服务平台都可封锁进出全市的各个路口。(4)假设犯罪嫌疑人逃跑的时速为60km/h。四、定义与符号说明(1)节点A与节点B的距离是指从A出发到达B通过的最短路径的距离，距离节点最近的平台即指到达该节点路径最短的平台。(2)交巡警通过最短路，从平台出发到达目标路口所用的时间为出警时间。(3)平台的出警次数可衡量平台工作量大小。(4)符号说明：路口节点：交通网络中任意两点间最短路距离：最远距离：该节点平均每天的发生报警案件数量：人均发案率：节点等效的平均每天发生报警案件数量：区域平台出警次数标准差：1个平台最多只能管辖个路口节点：平台工作量影响力的权重：一个节点最多可被ki个平台管辖：出警时间影响力的权重：交巡警服务平台的出警次数（工作量）五、问题一 平台管辖范围的确定5.1 建模分析将所有路口看作节点vi（i=1,2，92），已知平台Aj（j=1,2，20）也位于节点上。因为平台与节点之间可能有多种到达方式，所以该网络是一个加权无向图。交巡警要在3分钟内以时速为60km/h到达事发地，则平台距事发地的最短路应不大于3000米。此外，在分配平台管辖范围时，也应考虑到平台出警次数的均衡性。5.2基于上下界网络流模型的平台管辖范围的确定5.2.1 基于无向图上任意两点最短路模型的初始方案为了讨论方便，先引入图论中的相关定义：定义1 无向图中，任意两点路径为保持两点连通性的点集，两点间路径不是唯一的。定义2 路径的权值为路径上点权之和，最短路径为加权最小的路径。定义3 设G(V1,V2,E)是一个二分图，M是E的一个子集，如果M不含环且任意两边都不相邻，则称M为G的一个匹配。在最短路理论中有以下定理：定理1 最短路径的子路径是最短路径，最短路具有最优结构，可使用动态规划解决。定理2 设Di,j,k为从i到j的只以(1,2,k)集合中的节点为中间节点的最短路的长度。1) 若最短路径经过点k，则Di,j,k = Di,k,k 1 + Dk,j,k 1；2) 若最短路径不经过点k，则Di,j,k = Di,j,k 1。因此，Di,j,k = min(Di,k,k 1 + Dk,j,k 1,Di,j,k 1)。Floyd-Warshall算法就是基于以上定理的一类动态规划算法1。输入无向图的初始邻接矩阵，使用它可以得到图上任意两点的最短路长度。首先，我们为平台管辖制定下述规则：1)在交巡警辖区范围内，；2)节点发案时首先呼叫最近平台，若最近平台忙，则呼叫第二近的平台，以此类推；3)若节点与任意平台的距离均满足，强制该点被距离最近的平台管辖；4)当Ci2，ki=3，优先被最近的平台管辖；5)当1Ci2，ki=2，优先被最近的平台管辖；6)当Ci1，ki=1, 只被最近平台管辖。利用原始数据，可得初始化邻接矩阵，使用Floyd-Warshall算法，得到任意两点间最短路，结合规则1) 6)可得平台管辖范围分配方案。5.2.2 基于上下界网络流模型的优化方案上下界网络流4是图论中的一种理论与方法，研究网络上的一类最优化问题。所谓网络或容量网络指的是一个连通的赋权有向图G(V,E,C)，其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量集。此外顶点集中包括一个源点和一个汇点。网络上的流就是由源点流向汇点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去源点和汇点以外，在所有中途点要求保持流入量和流出量平衡。我们假设一个平台最多管辖Q个节点，并利用上下界网络流中的容量限制来模拟平台和路口的约束，从而得到一个较为平衡的解。算法1 构建二分图； 定义左集合代表A区所有路口节点，； 定义右集合代表A区所有交巡警服务平台，； 设置源点S，向各点连接成边，边容量 ； 设置汇点T，从各点向T连接成边， ，； 从各点向各自满足的点连边，=1 ； 用二分法枚举Q值，判断是否满足在使用上下界网络流算法后，各必要弧满流（所有路口节点均被管辖）； 重复以上二分步骤逼近满足条件的最小Q值。5.3 结果及其分析与评价利用题设数据，使用Floyd-Warshall算法，对5.2.1得到的方案，利用5.2.2的算法，可得优化的管辖范围分配方案。在两点间最短路基础上，得平台管辖范围的初始分配方案1；再使用上下界网络流算法得到各交巡警服务平台管辖范围优化分配方案2，见表1.1 。表1.1 A区交巡警服务平台管辖范围分配方案从方案1可见，共有六个问题节点28,29,38,39,61,92与任何平台的最短路均大于3000米。A区交巡警服务平台管辖范围分配方案1虽然给出了各平台管辖范围，保证所有节点都能被平台支配，但平台管辖范围分布不均。有些平台如A2、A5辖区内节点数量密集，一个平台却要负责十几个路口；而有些平台如A6、A12只负责一两个节点，造成警务资源浪费。可见此方案虽可行，但仍有不合理之处，故需要优化。平台管辖范围优化分配方案2中，给出了每个平台管辖范围。可以明显看出与方案1相比，方案2中各平台辖区大小的分布更均匀，其中65%的平台辖区内路口数目均为67个，另外方案1中只负责一两个路口的A6、A12等平台辖区内路口数目也有所适量增加，大大减少了平台管辖范围分配不均衡的现象。共有86个路口在3分钟中内能被交巡警到达，但28，29，38，39，61，92号这6个路口不能在3分钟内被任意平台到达。最长出警时间为5.7分钟。见表1.2 。表1.2 离最近平台距离超过3千米的节点情况六、问题一 交巡警调度方案的确定6.1 建模分析本题的目标函数为从现有20个交巡警服务平台中优选出封锁13个进出该区路口的方案。可将两种不同对象处理成二分图的结构，平台和路口的可达关系处理成图中的边集，一对一的封锁关系即是二分图的一个匹配，整个问题是一个典型的二分图完美匹配问题。我们使用二分逼近技术配合二分图完美匹配的相关模型求解上述问题。6.2 基于二分图完美匹配模型的调度方案的确定求一个二分图的完美匹配的普遍算法是Hungary最大匹配算法5，我们可以通过枚举最远距离L后验证，从而将一个求解性问题转化为判定性问题，简化了问题的求解过程。算法2 建二分图； 定义左集合代表出入A区的所有路口， ； 定义右集合代表A区所有交巡警服务平台，； 二分法枚举出节点与平台匹配的最远距离L，然后将和中最短路距离DijL的点对连边，使用Hungary最大匹配算法判断是否能够得到左集合的完美匹配； 重复以上二分步骤逼近满足条件的最小L值。6.3 结果及其分析与评价利用二分图的完美匹配模型，得出A区20个平台封锁13个路口的最佳调度方案，即每个平台应该负责封锁的路口，路程距离和出警时间。见表2.1 ：表2.1 A区20个平台封锁13个路口的调度方案从表2.1可见，在13条封锁路径中，出警时间最长为8.0分钟，最短为2.4分钟。要完全封锁13个路口最快需要8.0分钟。七、问题一 平台设置调整方案的确定7.1 建模分析在A区增加2至5个平台，建立模型求解平台增数和位置。首先制定评价指标对现有平台设置方案进行评价，分析比较新方案与现有方案的优劣。 通过分析题目，平台设置方案可以从交巡警服务平台工作量的均衡性和出警时间长短两个方面进行评价。交巡警服务平台工作量的均衡性体现为区域内各平台间出警次数差异的大小，可用其标准差来衡量。已知交巡警时速为60km/h，则出警时间可用平台与路口节点的最短路距离来衡量。平台与节点间的最短路应尽量在3000米以内。建立基于不同权重的平台调整评价模型，求解对应平台增数的所增平台位置，得出结论。7.2 指标体系7.2.1最远距离Dmax：某区域共有n个节点，则辖区内从各个平台出发到达各个节点共有n条最短路。定义这n条最短路中距离最长的为该区最远距离Dmax，对应最长出警时间。7.2.2平台工作量的标准差：第i号节点可被ki个平台管辖，定义该节点的等效发案率。hj：定义平台工作量hj指其平均每天需要处理的报警案件的总次数。若第j个平台辖区内共有n个节点，则其工作量。：定义平台工作量的标准差 。其中，为工作量的平均值。7.3基于不同权重的平台调整评价模型的平台设置方案7.3.1初始方案的确定下面给出增加不同平台数时的可行方案，算法规则：（1）节点与平台间的距离Dij应尽量在3000m以内；（2）当节点发案率C2，至少被最近的2个平台管辖；（3）当节点发案率C3000的节点数目占总节点数目的比例为超距比例p。p值越大，说明该区内出警时间大于3分钟的节点越多，即该区的出警时间越需要优化。8.2.2 评价现有方案分别计算出A、B、C、D、E、F六个区域的工作量标准差和超距比例p。表4.1 各区域工作量标准差和超距比例分析表4.1，A区的两项评价指标均远优于其他五区。于是，假设A区现状完美，不需要优化，把它设为其他五区的努力方向。定义3的区域（B、C、D、E、F区）需要优化工作量的均衡性，p0.1的区域（C、D、E、F区）需要优化缩短出警时间。8.3 基于模糊加权分析模型，确定平台增加或改变数量8.3.1 建立模型为确定需要改变或增加平台的数量，建立模糊加权分析模型。已知城区的面积，城区的人口和城区总发案率等数据。1)定因素集，；2)确定被分析集，；3)确定权重集，需客观地反映实际情况，权重可根据经验人为定义。4)确定分析矩阵，。5)加权比例W，计算，W代表被分析对象指标的理论比例。8.3.2 模型求解带入所给数据，对现有交巡警服务平台方案进行分析，确定平台增加数。1)确定因素集；2)确定被分析集；3)确定权重集：分别为城区面积、城区人口、城区总发案率在评价平台设置合理性时所占的权重，分析这三个因素对交巡警服务平台数量的影响。由于发案率对平台数目影响程度最大，城区人口影响次之，城区面积影响最小。综合考虑给出；4)确定分析矩阵由于城区的面积、城区的人口、城区总发案率三个因素的量纲不一致，无法比较，故对城区的面积、城区的人口、城区总发案率三个因素进行归一化处理。利用表4.2得出的数据确定分析矩阵表4.2 模糊加权分析模型影响因素相关数据5)加权比例W计算，可得A、B、C、D、E、F六区的理论值与实际值对比如下：表4.3 模糊加权分析模型得出的平台数目尽管A区的实际平台数目均大于理论值。由于A区作为该市市中心，属于城市最繁华地段，地理位置特殊，对安全保障有较高要求，一旦发生突发事件会造成更严重地影响。故应尽量使其安全性能最高。且平台已经建设好，撤除平台不仅需花费大量人力、物力。此外，在城市规划中，市中心的资源配置同城市其他区域相比相对最好。故A区的平台设置方案将不再改变，其他区域的平台设置方案将参考A区进行改进。由表4.3可知现有方案中各城区的平台数目并不是理论上的最佳数目。其中B区的平台数目大于理论值，D、E、F的平台数目小于理论值。可见，现有平台设置方案并不合理，没有实现资源的最优化配置。当理论平台增数，尽管B区实际平台数目大于理论数目，但仅比理论值多了一个平台，且平台已建设完工，如若拆除，将白白耗费大量人力、财力。另外，只多一个平台并不会造成很大的资源浪费，反而可以提高B区安全系数。而C区实际平台数目与理论值相等。因此，B、C区不需要改变现有平台数目。但由于8.2中说明，B、C区的两项评价指标并不理想，所以这两区需通过改变平台位置来实现两项指标的优化。当理论平台增数，实际平台数目小于理论数目，即该区域的平台数目少于理论值，需要增加交巡警服务平台。故D、E、F三个区域分别需要增加4、2、2个平台。但如何增加和改变各城区平台数量及位置仍需引入权重u、v进一步判断。8.4利用基于不同权重的平台调整评价模型，确定增加或改变的平台位置(1)符号定义与说明若一个区域共有n个路口节点、M万人，定义人均发案率由于已假设A区现状完美，故只需对比B、C、D、E、F六区的人均发案率即可。(2)u，v权重值的确定规则由前面对现有交巡警服务平台设置方案合理性的分析，可知C、D、E、F四个区域既要均衡平台工作量还要缩短最长出警时间，而B区只需考虑如何优化均衡平台工作量，根据权重参数定义，可知，.则C、D、E、F四个区域的.定义，.人均发案率越高，工作量影响力权重越大。设，可得区域i的工作量影响力权重，如表4.4所示：表4.4 人均发案率(3)权重值的修订对B、C区，调整方案为改变平台而不是增加平台。如果增加平台，在，时所得结论是只考虑优化工作量的均衡，而最远距离不变。但在改变平台的情况下，如果，即改变平台的原则是寻找标准差最小的方案，这可能使最远距离变大。为了平衡两项原则的侧重度，设定权重值的修订规则：1.当方案为改变平台时，修订后的u值为原值的0.5倍；2.当方案为增加平台时，修订后的u值等于原值。计算最优调整方案时，用修订后的u值。8.5 利用问题一基于不同权重的平台调整评价模型确定优化方案已确定平台增数和改变数和各区域权重参数，利用基于不同权重的平台调整评价模型，分别对B、C、D、E、F区给出调整方案如下：表4.5 B、C、D、E、F区平台调整方案及此方案与五区现状的两项指标对比8.6 结果及其分析与评价如表4.5所示，可以看到调整方案：B、C区均需改变2个平台的位置，D区需新增4个平台，E、F区均需新增2个平台。根据所给城区面积、人口数量、人均发案率及交通网络，可以推断A区为市中心，B区为低级住宅区、C区为工业区，D区为高级住宅区，E区为中高级住宅区，F区为低级住宅区。因此，在制定各区调整方案时，对u、v赋值时应考虑到不同区域的功能。分析调整方案的优化值，可以发现六个区域的工作量均衡性都有较大提高，且D、E区的出警时间显著缩短。对于D、E区而言，人均发案率较低，交巡警工作量不大，因此应优先考虑缩短出警时间提高执法效率。与现有方案相比，调整方案更优。九、问题二 全市围堵方案的确定9.1 建模分析该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。假设犯罪嫌疑人的逃跑速度为60km/h。9.2 基于二分图的完美匹配模型的围堵方案要保证以最快速度抓住罪犯（暂不考虑节省警力资源），需设定从全市80个交巡警服务平台中优选出封锁17个进出城市路口的方案。如果P点到全市17个路口中最近路口的时间大于17个平台完全封锁住全市的时间加3分钟，则方案可行。运用无向图上任意两点最短路径模型计算出案发地点P到17个路口的距离：表5.1 P点到达各路口最短距离排序运用二分图完美匹配模型计算出从80个平台中优选出封锁17个路口的方案：表5.2 80个平台对17个路口的最佳匹配方案由表5.1和5.2可知，P点到达17个路口中距离最近的一个需要21.7分钟，17个平台被完全封锁最快需要12.7分钟。如果17个最佳匹配平台在接到报警第一时刻以最快方案封锁全市，那么他们至少比罪犯到达最近出口快21.7-（12.7+3）=6(分钟)。以表5.2给出的方案封锁全市，可最快抓捕到罪犯。9.3 可节省警力资源的分阶段围堵方案上述方案虽能保证抓住罪犯，但是耗费的警力资源太多。分析全市地图，综合P点与A区13个路口距离的特点，可提出一种节省警力的围堵方案。图5.1 出入市区及A区的路口示意图在已封锁A区所有区出入口的前提下，运用无向图上任意两点最短路径模型计算出案发地点P到该市17个市出入路口的距离如表5.3。编程发现，当接到报警电话时立刻对A区进行封锁，可保证12,13,21,22,23,24,28号这7个路口在罪犯到达它们之前被封锁（即若罪犯试图从这7个路口逃离，一定会被抓住）。而如果罪犯试图从16,29,30,38,48,62号这6个路口逃离，则不一定会被抓住。所以，围堵的第一阶段是从80个平台中找出与A区13个路口的最佳匹配进行最快封锁。表5.3 P点到达各路口最短距离排序（除去A区一定能封锁的7个点）分析上述可能逃出的6个路口的布局并编程计算可得，它们距离C、F区内的572、203、541、317、177、264、483、202、578号这9个全市路口较近，如果罪犯从这6个路口逃出，那么他逃向C、F区的可能性较大。所以，围堵的第二阶段是从除去封锁A区的13个平台以外的67个平台中找出与C、F区的9个路口的最佳匹配进行封锁。但是必须考虑罪犯没有逃向C、F区的可能性。所以，围堵的第三阶段是从再除去封锁C、F区的9个平台以外的58个平台中找出与剩下8个B、D、E区内的全市路口（即418、362、325、328、332、151、153、387号路口）的最佳匹配进行封锁。具体方案和计算如下：表5.4 全市封锁围堵方案由表5.4可知，此围堵方案分成三个阶段：（1）接到电话立刻调动第一组警力，按表中封锁方案对A区所有路口进行