2011高教社杯全国大学生数学建模竞
2011高教社杯全国大学生数学建模竞赛
摘要
在（1）第一问中，我们根据附表1所给各路口坐标算出A图中每条路线的长度，然后通过floyd算法出了两点之间的最短路程，得出矩阵D，通过使用matlab圈出各服务平台到周围路口小于3min（即3km）的点，再根据就近原则，将各路口划分到这个圈中离此路口最近的交巡警平台。对于任意到交巡警平台路程大于3min（即3km）序号为28，29，38，39，61，92的五个路口，则采用就近原则人工划入距离其最近的交巡警平台辖区，这样就在保证出警时间基本都小于3min的条件下，划分出各警务平台合理的管辖范围。 对于（1）第二问中，我们采用指派模型，用lingo软件对20个巡警服务平台对17个城市出入口进行封锁的方法进行了优化，得到初步的调度方案。在这个方案的基础上，如果在某条巡警服务平台调度路线中经过其他的的调度点，则与所经过的调度点互换目标路口，由
此得到最佳调度方案，即最快8分钟可以实现快速封锁路口。
对于（1）第三问，我们按照工作量均衡和出警时间尽可能短的原则考虑增加交巡警平台。首先，利用excel算出了各辖区内交巡警服务平台的工作量总和以及出警时间的平均值，求出了所有辖区的工作总量与出警时间的平均值，取出工作总量明显高于平均值且平均出警时间超过3min的四个辖区来增设新的交巡警平台。我们通过（1）第一问中的最短路程矩阵得到各辖区内种增设平台的所有可能的方法，通过比较每种方法的工作量总和及出警时间综合考虑得到一个最优的设置。最后通过spss软件求得优化前后两组数据的标准差，比较后发现优化后的数据标准差明显下降，达到了优化的目的。
在（2）第一问中，首先参照（1）中A区的处理方法分别求出了城区B，C，D，E，F中路口到最近交巡警服务平台的路程，出警时间以及工作量。通过spss软件计算出标准差，并与优化后的A城区进行比较，出了交巡警平台明显分配不合理（标准差远高于A区优化后方案的标准差）的三个区，在其距离较远工作量较大的路口增设服务平台。
成都信息工程学院学报对于（2）中第二问搜捕嫌疑犯问题，我们采用时间圈法，以事发地点为圆心，以一分钟所行使的路程为单位半径，画出等间隔的数个同心圆，这样就可以确定每个时间段嫌疑犯的
逃逸范围（因为任意两点间的路程大于等于两点间的距离，所以在某时间内嫌疑犯必定在对应的时间圈内），根据每个路口在这些时间圈上的位置，要求警察到这些路口的时间小于罪犯到达的时间（即可以围堵住罪犯），出所有这些路口，构成闭圈，最小的闭圈便是围堵罪犯的最佳方案。
关键词：floyd算法，指派模型，spss分析数据，时间圈法
一、问题的提出
1.1背景
“有困难警察”，这是一句家喻户晓的流行语。警察是保证人民生命安全及财产安全的守护神，他们肩负着刑事执法、治安管理、交通管理、服务众四大职能。为了更有效地贯彻实施这些职能，所以需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务
部门面临的一个实际课题。
1.2问题
（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。
对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。
根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。
（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果
有明显不合理，请给出解决方案。
如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。
二、模型的假设
1.警察接到报案后能立即出警
2.案发地点都在路口附近
3.嫌疑犯逃逸速度与警察速度相同
4.各城区内交巡警平台在不发生特殊情况时只管辖自己城区的路口
5.警察接到报警后犯罪嫌疑人不能再通过有警察的路口
三、符号说明
：m点的横坐标
：n点的横坐标
：m点的纵坐标
：n点的纵坐标
L：任意两点间距离
xij：交巡警平台i封锁路口j
Z：交巡警平台封锁交通要道经过的总路程
Cij：经巡警平台i封锁路口j所走的距离
四、问题分析
4.1问题一
碳税和碳关税的区别附件1给出了某市中心城区A的交巡警服务平台的相关情况，首先要求分配平台管辖范围使交巡警在有突发事件时尽可能3分钟内赶到事发地；而后要求给出重大事件时20个平台快速封锁13条交通要道的合理方案，最后要求对交巡警服务平台进行改进。
对问题一的解答可先采用floyd算法算出任意两点间最短路径并根据就近原则进行分配管辖范围；而后可利用指派模型对巡警封锁路口问题进行初步优化；最后可根据出警时间和工作量总和出服务平台不均衡的地方，优化后可利用标准差进行比较。
4.2问题二
根据附件中全市交巡警平台的相关数据，首先要求分析六个区的交巡警平台设置方案的合理性，并给出解决方案；最后要求给出一个调度服务平台警力资源的最佳围堵方案。
对与问题二，首先可计算出除A区外其余五区的标准差并于优化过的A区想关数据的标准差进行比较，分析各区服务平台设置方案的合理性；而对于最佳围堵方案，我们则可先做出带有时间圈的图然后采用时间圈法进行优化。
懦夫博弈五、模型的建立和求解
5.1问题一模型的建立和求解
5.1.1
任意两点m,n之间的距离可利用程序由坐标求得
得出一个关于各点距离的矩阵，，将相邻两点的距离保留，不相邻点之间的距离变为inf用floyd算法（程序1）求出任一两点间的路程矩阵，下图为的一部分：
出每个路口到交巡警平台的路程，并通过matlab程序（程序2）根据就近原则筛选出小于3min(3km)的点，划归各交巡警平台。
对于大于3min（3km）的点28，29，38，39，61，92在R2中出其对应的最短路程，并对其进行分配,分区图如下图1：
图1（不同颜线条表示不同区域）
说明：
杀气三时作阵云（1）图中实线表示市区道路；红线表示连接两个区之间的道路；
（2）实圆点“·”表示交叉路口的节点，没有实圆点的交叉线为道路立交；
（3）星号“*”表示出入城区的路口节点；
（4）圆圈“○”表示现有交巡警服务平台的设置点；
（5）圆圈加星号“○* ”表示在出入城区的路口处设置了交巡警服务平台；
5.1.2
记交巡警平台i=1，2,3……20
出入城区的路口节点j=1,2,3……13
第一：一个交巡警平台的警力最多封锁一个路口
雏鹰网
则有
第二：每个路口节点最少需要一个交巡警平台的警力封锁
则有
当交巡警平台i封锁路口节点j时表示交巡警平台所走的路程，否则=0
则，目标函数为交巡警总路程
综上所述，该问题为0-1规划
模型为：
通过lingo编程（程序3）求解出一个可使总时间即总路程最小的最优解。
通过lingo求出最快封锁道路的初步优化模型：
X( 2, 11) 1.000000 39.82200
X( 4, 13) 1.000000 3.500000
X( 5, 12) 1.000000 24.75800
X( 7, 10) 1.000000 5.831000
X( 8, 9) 1.000000 104.9300
X( 9, 4) 万方数据资源1.000000 115.3900
X( 10, 7) 1.000000 82.43700
X( 11, 5) 1.000000 32.69600
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议