交巡警服务平台的设置与调度的问题2011年B题

2010高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则。我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的，如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：S13036所属学校（请填写完整的全名）：河南科技学院参赛队员（打印并签名）：12.3.指导教师或指导教师组负责人（打印并签名）：数学建模指导小组日期：2011年9月12日赛区评阅编号（由赛区组委会评阅前进行编号）：2010高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1交巡警服务平台的设置与调度模型摘要“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。本文研究的是交巡警服务平台的设置与调度问题，目的是为了使交巡警服务平台的调度方案达到最佳问题一首先我们通过建立网格模型求解关于某市中心城区A的交警服务台的分配管辖范围问题，采用了floyd的算法得到任意两点之间的距离，再根据两点之间的邻接矩阵运用Matlab软件求出A区任意两路口之间的距离，然后通过网络各点间最短距离的矩阵算法求出网络图中任意连通的两点之间的最短路径；最后通过网格算法得出分配交巡警服务平台的管辖范围(如表1)；对于服务平台警力的合理调度问题，建立分配问题的混合整数线性规划模型，采用矩阵作业算法得出有效地警力的调度方案：10→12,16→14，9→16,14→21,13→22,12→23,11→24,7→28,5→29,8→30,2→38，6→48,4→62（从服务台到各个出口）。可以达到快速全封锁。紧接着本文根据平台选择原则并对相关数据进行分析处理得到应加的平台数为4，且在分别在29,40,48,90节点处；问题二在分析研究该市现有交巡警服务平台设置方案的合理性的问题中本文采用了模糊层次综合法，通过建立模糊层次综合模型，继而对因素权重进行求解以及归一化的处理分别对ABCDEF六区进行评价，最后得出ADE是相对比较合理的，BCF区域中存在明显不合之处，通过权重分析在分别在BCF区中在各增加一个服务平台能够得到合理改善。在最后的围堵问题中本文采用逐步跟随以及全局考虑的思想对犯罪嫌疑人实现了快速围堵的目的。在文章的最后，本文就本篇论文模型的优缺点进行了评价并对其推广进行了说明。关键词：网格模型floyd的算法Matlab软件模糊层次综合法2一、问题重述“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：一、(1)根据该市中心城区A相关的数据信息为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。(2)对于重大突发事件，怎样调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。(3)根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。二、(4)针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如果有明显不合理，请给出解决方案。(5)如果该市地点P(第32个节点)处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二、问题分析在问题(一)中当各交巡警服务平台所管辖的范围内出现突发事件，我们只需要考虑最短路径即可，但是数据量过大，我们分别运用floyd算法和Matlab软件选择最短路径，得出平台所管辖范围。第二小问需要从20个平台中找出13个平台分派到13个交通要道去，这是一个木桶理论问题，即求众多组合中最大时间最小化问题，我们可以通过建立解混合整数线性规划模型决这个问题。第三小问由于各平台的工作范围分布不均匀，且各节点的发案率差异，导致各平台工作量的不平衡，且部分地区出警时间过长，不利于维护地方的治安稳定，因此需要增加部分平台，从而改善治安环境。问题(二)第一小问需要对全市所有区的交巡警平台布置做出分析评价，这里数据非常大，我们采取可以采取模糊层次综合模型来解决这个问题。第二小问要设计追捕逃犯的路线，这就要根据逃犯的速度分情况考虑，可以采用动态优化三、模型假设（1）假设材料中所给的数据真实可靠；（2）假设图中任意两路口之间的道路为直线；3（3）假设警车以60km/h的速度匀速行驶，并且在执行任务的过程中不会出现故障；（4）假设不考虑交通堵塞、红绿灯问题；（5）假设在整个路途中，转弯处不需要花费时间；（6）假设出警时道路恒畅通(无交通事故、交通堵塞等发生)，警车行驶正常。四、符号说明ix：各路口点的横坐标iy：各路口点的纵坐标b:任意两路口间的距离B:任意两坐标之间的直线距离C：邻接矩阵五、模型的建立与求解5.1问题一5.1.1第一小问Step1：首先由题中所给出的数据，我们可以根据解析几何中两点之间的距离公式：22(,)()()ijijbijxxyy，（i,j1,2,3,…92）,用Matlab软件计算求出任意两坐标点之间的直线距离，并得到关于ijb的矩阵B。11119292nnnnbbBbbStep2:根据题中所给的分布图我们可以人工的得到各路口的邻接情况，来得到其邻接矩阵C，方便以后的求解。其中直接相连的两路口之间用1表示，反之用0来表示。11119292nnnnccCccStep3:由于我们需要求出任意两路口之间的实际距离，需用Matlab软件先算出各相邻路口之间的距离，该过程可以有B点乘C来计算得到：411119292nnnnffFBCffStep4:因为D中未相邻两路口的值为0，在后面求解最小距离是会使其一直为0，所以把不相邻的路口中得ijd数值该为无穷（inf）得到一个新的矩阵11119292nnnneeEeeStep5:通过matlab，运用Floyd算法求出任意两点间最短距离，得出最短距离矩阵D(具体程序祥见附件)；11119292nnnnddDdd5表1交巡警平台管辖区域交巡警服务平台管辖区11至75,75至68,1至69,69至68,68至67,69至70,69至71,71至72,72至73,1至74,74至73,74至7122至44，2至40,2至43,43至72，2至70,43至4233至55并向46延伸633米，55至54,3向45延伸3千米，3至44,44至67,3至65,65至64,64至63,76至6444至57,4至62,62至60,60至61,4至63,63至54,62至3955至47,5至49,49至53,53至52,52至51，52向57延伸与4管区相接66至47,47至48,6至50,50至59,59至59,50至51，77至32,32至33,7向15延伸3千米，7向29延伸3千米，7向34延伸与9管辖相接，7至47,7至30,30至48,48至6188至33,33至32,8至9,8至46并向55延伸并与3管区相接，8至4799至35,35至36,35至45,45至46,45向3延伸与3管区相接，9至34,34向10延伸与10管区相接，34向7延伸与7管区相接1010向26延伸与11管区相接，10向34与9管区相接1111至26并向10延伸，11至27并向12延伸468米，25向24延伸与13管区相接1212至25，12向27延伸与11管区相接1313至23,13至22并向11延伸2.1千米，22至21并向14延伸297米，13至24并向25延伸615米1414向21延伸与13管区相接，14向16延伸与16管区相接1515至28，15至29并向30延伸1千米，15至31，15向7延伸与7管区相接1616向14延伸3千米，16至38,38至39,16至36,36至37,37至431717至40,17至42,17至41并向38延伸2.15千米，41至92,17至811818至80,18至73,80至72,18至83,83至84,83至32,32至90,90至91,18至81,81至321919至79,79至78,78至77,19至77,77至76,76至74,69至66,76至752020至85并向62延伸与4管区相接，85至84,84至89,20至89,89至85,89至90,85至91,91至92,85至87,20至86,86至87,86至85,87至92,91至926图1交巡警平台管辖区域5.1.2第二小问1.0.ijijx第服务台到第个出口第i服务台不到第j个出口i=1,2…20;j=1,2,3…13则走过最大路程为：,maxijijijzcx限定条件为：1311,1,2,...20()ijjxi既每个服务台只能到一个路口2011,1,2...13()ijixj既每个路口要有服务台到达运用矩阵作业法直接从距离表格得出矩阵11111320nmmnrrRrr，联立目标函数求解得出最佳警力调度方案。7表2交巡警服务平台到出口的最短距离1214162122232428293038486212.05911.65340.97921.97992.16022.30022.06051.36361.26881.19750.63861.19810.534821.89271.4130.73881.73951.91982.05981.89411.19721.10241.03120.39821.03170.520831.68151.27670.60251.60321.78351.92351.68290.98610.89120.820.60940.82050.439442.03541.50090.82671.82742.00772.14772.03680.90510.81030.8240.48610.73960.03551.5961.3070.63281.63351.75981.88591.59740.41320.31830.3320.95210.24760.518261.59911.31010.63591.63661.76291.8891.60050.41630.32140.33510.95520.25070.533971.32231.09170.41751.41821.48611.61221.32370.29460.19970.05