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

1/16交巡警服务平台的设置与调度摘要由于警务资源有限，需要根据城市的实际情况与需求建立数学模型来合理地确定交巡警服务平台数目与位置、分配各平台的管辖范围、调度警务资源。设置平台的基本原则是尽量使平台出警次数均衡，缩短出警时间。用出警次数标准差衡量其均衡性，平台与节点的最短路衡量出警时间。对问题一，首先以出警时间最短和出警次数尽量均衡为约束条件，利用无向图上任意两点最短路径模型得到平台管辖范围，并运用上下界网络流模型优化解,得到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分钟可将全市路口完全封锁。此方案在保证成功围堵嫌疑人的前提下，若在前面阶段堵到罪犯，则可以减少警力资源调度，节省资源。【关键字】：不同权重的平台调整评价模糊加权分析最短路二分图匹配2/16目录一、问题重述...........................................................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十、参考文献..........................................................163/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)符号说明iv：路口节点ijD：交通网络中任意两点间最短路距离maxD：最远距离iC：该节点平均每天的发生报警案件数量均C：人均发案率iC：节点等效的平均每天发生报警案件数量v：区域平台出警次数标准差Q：1个平台最多只能管辖Q个路口节点u：平台工作量影响力的权重ik：一个节点最多可被ki个平台管辖v：出警时间影响力的权重jh：交巡警服务平台的出警次数（工作量）4/16五、问题一平台管辖范围的确定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)在交巡警辖区范围内，3000Dij；2)节点发案时首先呼叫最近平台，若最近平台忙，则呼叫第二近的平台，以此类推；3)若节点与任意平台的距离均满足ijD3000，强制该点被距离最近的平台管辖；4)当Ci≥2，ki=3，优先被最近的平台管辖；5)当1≤Ci2，ki=2，优先被最近的平台管辖；6)当Ci1，ki=1,只被最近平台管辖。利用原始数据，可得初始化邻接矩阵，使用Floyd-Warshall算法，得到任意两点间最短路，结合规则1)~6)可得平台管辖范围分配方案。5.2.2基于上下界网络流模型的优化方案上下界网络流[4]是图论中的一种理论与方法，研究网络上的一类最优化问题。所谓网络或容量网络指的是一个连通的赋权有向图G(V,E,C)，其中V是该图的顶点集，E是有向边(即弧)集，C是弧上的容量集。此外顶点集中包括一个源点和一个汇点。网络上的流就是由源点流向汇点的可行流，这是定义在网络上的非负函数，它一方面受到容量的限制，另一方面除去源点和汇点以外，在所有