交巡警服务平台的设置与调度方案

2011高教社杯全国大学生数学建模竞赛承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的,如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）：B我们的参赛报名号为（如果赛区设置报名号的话）：所属学校（请填写完整的全名）：参赛队员(打印并签名)：1.2.3.指导教师或指导教师组负责人(打印并签名)：指导组日期：2011年9月12日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：1交巡警服务平台的设置与调度方案摘要本文是对交巡警服务平台设置与调度问题的分析研究，分别完成了对城区A的辖区划分、快速封锁、添加平台方案的确定，然后对全市六个城区的交巡警服务平台设置的合理性进行了评价，最后完成了对犯罪嫌疑人围堵方案的确定。问题一主要解决三个问题，分别是(1)辖区划分；(2)快速封锁；(3)添加平台。(1)辖区划分时，先以就近原则为各个服务平台划分管辖范围；对于划分结果中出现的工作量不均衡的情况，我们定义了工作量均衡度，以工作量均衡度为优化目标，对辖区的划分进行了调整，使各平台的工作量更为平衡。对于(2)快速封锁问题，要从20个交巡警平台中选出13个去封锁进出路口，整个封锁过程所用时间由路程最长的路径所确定。我们对所有方案中的最长路径进行筛选，得到快速封锁的最优方案。对于(3)添加平台问题，我们以平台覆盖率最大及工作量均衡度最高建立双目标优化模型，得到结论添加4个平台，其位置分别在29、38、61、92四个节点。问题二中，对于合理性的评价，我们首先建立了评价标准，考查案发率分布与平台分布的一致性，对现有平台设置作出了较为合理的评价，并提出了改进意见及解决方案。对于P点犯罪嫌疑人的围堵，我们采用逐圏搜索方案，就是由中心点向外扩散，先寻找与它相连的点，测算是否能在犯罪嫌疑人到达之前封锁它们，如果能，则方案完成；否则，从未能封锁的第一圈中的点继续向外扩散，测算是否能封锁与该点相连的下一圈的点，如果能则结束，否则，依此类推进行搜索，最终完成对犯罪嫌疑人的围堵。关键词：平台覆盖率；工作量均衡度；双目标优化；逐圈搜索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)添加平台。其中，(1)(3)问题联系紧密，我们将其放在一起讨论。问题(1)要求当管辖范围内发生突发事件时，交巡警尽量能在3分钟内到达事发地，即要求其管辖范围内的路口节点到该服务平台的路程小于等于3km。同时，问题(3)要求在考虑出警时间的同时，还要考虑工作量的均衡性，因此通过确定新增服务平台的个数，并对服务平台的管辖范围进行适当的调整，从而使得管辖范围的划分更为合理。对于(2)快速封锁问题，要求从20个交巡警平台中选出13个去封锁这13个路口。交巡警从各自平台出发到达13个交通要点，分别构成了13条路线。在各种因素都相同的条件下，整个封锁过程所用时间的长短取决于这13条路线中路程最长的那一条路线所用的时间。所以，遍历搜索所有方案，比较各方案的最长路程，其中，最长路程最短的那一种方案可最快完成封锁，即为最优方案。问题二中，为了对全市六个城区交巡警服务平台设置的合理性进行评价，首先明确平台设置的原则和目的，建立合理的评价标准，用案发率与平台分布之间的关系来衡量平台设置的合理性。对于P点犯罪嫌疑人围堵方案的确定，由于我们对犯罪嫌疑人的逃跑路线是完全不确定的，只能确定罪犯在三分钟时间内有可能达到的范围。我们通过对犯罪嫌疑人可能到达的地段的推算，确定最小围堵的范围，使得所有交巡警人员到位时，罪犯还没有到达或逃出这个围堵范围。此方案即为最佳围堵方案。3三、模型假设1、整个模型以节点作为划分交巡警服务平台的管辖范围的基本单位；2、警车的速度一定，交巡警到达事发现场的时间只与路程的远近有关，不考虑警车行驶过程中其它人为或自然因素对时间的影响；3、假设每辆警车只会在图中所示道路上行驶，且只会在路口节点处转弯；4、假设事发现场都在路口节点，不会出现在道路上；5、假设犯罪嫌疑人在驾车逃跑的时候，选择的路线是随机的；6、假设犯罪嫌疑人的驾车逃跑速度不超过60km/h；7、假设全市交巡警在对犯罪嫌疑人进行围堵时，对罪犯的行驶路线完全不确定。四、符号说明符号描述(Xi,Yi)第i路口坐标，单位kmPi第i路口的发案率Dij第i个路口到第j个路口的最短路径，单位kmRi第i个路口到Ai第i个交巡警服务平台的位置标号Ui第i个交巡警服务平台的管辖节点集Eti第i个出入口标号Wi第i个交巡警服务平台的工作量指标W交巡警服务平台的平均工作量E交巡警服务平台工作量的均衡程度Cpi第i个交巡警平台所覆盖的路口数量（以3分钟行程为界）C交巡警服务平台覆盖率R交巡警服务平台覆盖半径，单位kmN路口总数na增加的交巡警服务平台数，52NaNA交巡警平台总数Sij0-1变量，表征A区中第i号路口被第j号交巡警服务平台管辖与否Qij0-1变量，表征A区中第i号路口被j号交巡警服务平台覆盖与否4五、模型建立与求解5.1数据预处理根据图论知识，对附件2中的“全市交通路口节点数据”与“全市交通路口的路线”数据进行处理，将A区中92个路口节点之间的距离关系转换成对应的无向图的邻接矩阵表示形式（该邻接矩阵即为上述路口节点分布图的数字存储形式），然后利用Floyd最短路径算法，计算出两两路口节点之间的最短路径。具体实施过程如下：Step1:图的邻接矩阵表示。首先根据附件2中A区路口节点坐标和线路图计算出A区路口连通情况，并形成描述这92个路口节点位置分布关系的二维邻接表(,)Bij，其中没有直接连通的两个路口节点之间的距离，以一个相对较大值表示（表示无穷大），以便于后面更新。Step2:迭代计算，计算最短路径。对任意两节点(,)ij，若存在k，使(,)(,)(,)BikBkjBij，则更新(,)(,)(,)BijBikBkjStep3:停止迭代，得到最短路径矩阵。直到所有点的距离不再更新停止计算。则得到最短路距离矩阵ijD，(,1,2,.50)ij。上述求解过程可通过编程实现（具体程序见附录一），各路口节点之间的最短路径(,)ijDij=1,2,...,50见附录二。5.2第一问设置交巡警服务平台的首要目的是更好地维护社会稳定，保护人民群众的生命财产安全，及时迅速地做出反应，打击违法犯罪活动。因此要求该服务平台反应迅速、灵活机动。为保证出警速度，我们以三分钟内到达案发地点为标准，为交巡警平台划分辖区。但是，我们一味强调出警速率，而不考虑警务资源的合理分配，会导致工作量的严重失衡。所以在考虑出警迅速的同时，也要保证工作量的均衡。我们建立了出警速度和工作量均衡性的双优化模型，得到较好的结果。问题一的求解过程由三部分组成，分别是（1）辖区划分；（2）快速封锁；（3）添加平台。5.2.1辖区划分为交巡警服务平台划分管辖区域时，要求能在3分钟内有交巡警到达事发地。由于警车的速度为60km/h，因此，服务平台能够管辖的范围最大为3km。但是按这种原则进行划分时，会出现管辖范围交叉的现象，交叉范围内的节点如何划分将影响平台工作量的均衡性，因此我们将划分过程分为两步：Step1：对城区A中的每个路口节点，分别计算出它到该区内20个交巡警服务平台的路程大小，并暂时将其划分到路程最小的那个服务平台的管辖范围；Step2：分析Step1划分后的结果，以平台工作量的均衡性为标准，重新划分交叉节点的辖区归属。在此，我们首先给出工作量指标的定义，工作量=交巡警服务平台到路口的距离×该路口的发案率。由定义，第i个交巡警服务平台的工作量为：iUjjijiPDW。则交巡警服务平台的平均工作量为：5NAPDNAWWiUjjijiii工作量均衡程度可用各服务平台与平均值的偏离程度，即各服务平台工作量的方差之和来表示：2)(iiWWE。其中，E表示交巡警服务平台工作量的均衡程度。首先，我们对城区A中的节点进行标号，如下图所示：2002503003504004502602803003203403603804001234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192图5-1城区A中各个节点的标号我们用Step1对城区A的所有路口节点进行辖区划分，得到划分结果如下：表5-1Step1对所有节点的划分结果交巡警平台号所管辖节点116768697173747576782239404344707233545565664457606263645549505152535658596677303247486188334699313435451010111126271212251313212223241414151528291616363738171741421818808182831919777920208485868788899091926表5-2服务平台到其管辖范围内的各路口节点的距离交巡警平台号路口节点到服务平台的距离101619120750011401029626930128464020368219148009498601606302271126615241840401868173935010311937505008491230166011712084230315226070583114012811290419080828930902055