《全国大学生数模竞赛B题参赛论文交巡警服务平台的设置与调度》由会员分享，可在线阅读，更多相关《全国大学生数模竞赛B题参赛论文交巡警服务平台的设置与调度（18页珍藏版）》请在金锄头文库上搜索。
1、2011高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： 我们的参赛报名号为（如果赛区设置报名
2、号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：2011高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：交巡警服务平台的设置与调度摘要本文主要是研究城市交巡警服务平台的设置、管辖范围的分配、警务资源的调度等问题。在对各个问题的研究过程中分别采用了Dijkstra 最短
3、路径算法、指派模型，0-1规划，多目标规划模型，层次分析法等模型和算法。本题共有5个问题，问题一中包括3个小问，其研究对象都是A区的交巡警服务平台。问题二有2个小问，其研究的对象则扩大到全市的交巡警服务平台。第（1）问是为交巡警服务平台分配管辖范围。该市A区共有92个路口节点，其中20个设置有交巡警服务平台。管辖范围的分配原则是能使警车以60km/h的速度在3分钟内达到，若存在节点同时满足多个平台都能在3分钟内到达，那么就以就近原则分配。最后用Dijkstra 最短路径算法来筛选从服务台出发能在3分钟达到的路口节点，并通过MATLAB编程得到分配方案。但是结果显示有6个路口节点是警车无法在3分
4、钟内到达的。如下表3分钟内无法到达的路口节点282938396192第（2）问是要设计一个调度方案，使得在发生重大事件时，能够最快封锁13条出入该区的交通要道。约束条件是一个平台的警力只能封锁一个路口，我们将其归结为“一事多人”的指派问题。建立指派模型后用LINGO编程，考虑到算法的复杂性，可以先从实际情况出发，排除远距离指派警力封锁的可能性。于是可以由LINGO运算得到结果为用时最短的最优调度方案。该方案所需花费的时间是8.01分钟。第（3）问是选址问题，要在A区内选取2-5个点建立交巡警服务平台。根据问题（1）可知有6个节点是警车无法在3分钟内到达的，所以在选择新增服务平台的地址时要考虑让
5、这些点满足3分钟内到达的目标，另外还要综合考虑新增平台能否有效分担原有服务平台的工作量。所以可以建立多目标规划模型，最后解得需要新增4给服务平台，分别设在节点29、40、48、89上。第（4）问是评价该市现有交巡警服务平台设置方案的合理性，所以采用层次分析法来分析研究。通过计算后得到权重，即A-F区现有交巡警服务平台设置方案权重分别占0.2188，0.1204，0.2142，0.1530，0.1497和0.1439 。权重大的平台设置较合理。由于各区所占权重相差不大，所以无明显不合理的情况存在。 第（5）问是设计围堵方案，去围堵逃逸的犯罪嫌疑人。假设犯罪嫌疑人犯案后必定逃离A区，那么就有两种可
6、能，一是犯罪嫌疑人还没逃离A区就已经被围堵抓获。另一种情况是逃犯逃离了A区在其他区被分度抓获。最后使用穷举法，找出所有可能的情况。关键词：Dijkstra算法 指派模型 多目标规划模型 层次分析法 穷举法 0-1规划模型2一 问题重述警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。试就某市设置交巡警服务平台的相关情况，建
7、立数学模型分析研究下面的问题：1.1 问题一：（1）根据附件1中的图表，附件2的相关数。为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，请给出该区交巡警服务平台警力合理的调度方案。（3）根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，请确定需要增加平台的具体个数和位置。1.2 问题二：（1）针对全市（主城六区A，B
8、，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。（2）如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，请给出调度全市交巡警服务平台警力资源的最佳围堵方案。二 问题分析2.1问题一： 第（1）问的目标是为20个交巡警服务平台分配管辖范围，其约束条件是使在管辖范围内出现突发事件时，交警以60km/h的时速尽量能在3分钟内到达事发地。由附件2提供的数据可知，该市A区共有92个路口节点，其中20个设置有交巡警服务平台。以服
9、务台为出发点选择能在3分钟内到达的，则选为该服务台的管辖范围。于是引入Dijkstra 最短路径算法来筛选从服务台出发能在3分钟达到的路口节点。第（2）问的目标是将20个交巡警服务平台的警力资源分配到13个进出该区的路口，其约束条件是一个平台的警力最多封锁一个路口。这个可以理解为“一事多人”的指派问题的推广。再使用穷举法穷举出所有可能的调度方案，然后根据短板效应的原理，选择一个方案所花地调度时间最短的为最优调度方案。第（3）问的目标是选择该区的一些路口建立平台，根据第（1）问得结论可以知道有6个节点是警车在三分中内是无法到达的，所以要考虑在这些点附件新增服务点，使得能有警车在3分钟内能到达该节
10、点，这里可以引用问题（1）建立的模型来找出符合的节点，然后根据所选节点能否分担周边服务台的工作量 。22 问题二：第（1）问是要求对该市现有的交巡警服务平台设置情况进行评价，对存在明显不合理的，给出解决方案。本文结合城区面积、人口，案发率的数据，综合考虑各区服务平台密度，各区人均享有平台数，各区平均案发率和各区单位个数平台管辖的总距离这四项指标，建立综合评价模型。以全市交巡警平台合理分布为目标层，上述四项指标为准则层，分别以A， B，C，D，E，F这六个区各自的平台分布方案为方案层，用层次分析法进行分析，得出各个方案的权重。权重较大的城区就是在设置交巡警平台时相对合理的城区。第（2）问考虑到犯
11、罪嫌疑人在A区犯案之后肯定要逃离该区，所以要在最短时间内封锁所有出入A区的路口，然后对犯罪嫌疑人进行搜捕。然而，由于在接到报警前，犯罪嫌疑人已经驾车逃离3分钟，根据第一问中求出的答案，在封锁13个出入A区的路口时需要8.01分钟，因此在接到报警后，按照预定的封锁计划可能会出现犯罪嫌疑人已经逃离A区的情况。所以要对原先封锁13个出入A区路口的方案进行改进。利用GPS跟踪犯罪嫌疑人的行踪，根据犯罪嫌疑人的行踪，充分估计到犯罪嫌疑人逃离路线的所有可能，在时间允许的情况下，封锁关键路口，即有好几种逃离路线都可能经过的共同路口；在时间来不急，犯罪嫌疑人已经逃离A区的情况下，调动其它区的警力对犯罪嫌疑人可
12、能逃离的路线进行围堵。一旦围堵成功，那么在这个范围内抓捕犯罪嫌疑人就是轻而易举的事，所以本文着重考虑如何围堵，而不考虑围堵后抓捕的过程。三 模型假设（1） 所有事件均发生在区域图所示的道路上，不会发生在空白区域内。（2） 接到报警后交巡警立刻赶往事发现场，不考虑实际中存在的延时。（3） 警车均以60km/h的速度赶往事发现场，不受路况影响。（4） 每次出警后均能处理好事件。（5） 犯罪嫌疑人在A去犯案后要逃离A区（6） 假设犯罪嫌疑人驾车逃跑的速度为60km/h（7） 假设犯罪嫌疑人最初选择的逃跑路线是所有从案发点到离开A城区路口的最短路线之中的一条（8） 假设犯罪嫌疑人在不知道道路前方已经有
13、警察的情况下会继续按原定路线逃离A区，当遇到前方有警察时，立刻返回至该路段的起始结点处，在随机选择其他路线逃离四 符号说明警车的速度交巡警到达事发现场所用时间，交巡警时间内能达到的最大路径A区交巡警平台编号表示全市各路口节点，所有路口节点集合从服务平台到路口节点的路径路径上的权值已经找到从出发的最短路径的终点的集合第个交巡警服务平台管辖的路口节点集合表示从到每个终点的最短路径长度五 模型的建立与求解5.1问题一5.1.1 Dijkstra算法分配管辖范围Dijkstra 算法是由著名的数学家EWDijkstra 于1959 年首先提出来的。它是按路径长度递增的次序产生最短路径的一种算法,该算法
14、采用了在优化问题中常用的贪心技巧。贪心算法在每一步都选择局部最优解以期望产生一个全局最优解。采Dijkstra 算法不仅求出从起点到终点的最短路径,而且最后所得到的实际上是从起点到各顶点的最短路径2。引用图论相关知识，将附件中所提供的交通要道线路网络抽象成一个有向赋权图,其定点为道路节点，如果中的顶点到有可达到的路线那么两点之间就用有向边相连，记作，方向从指向，相应有一个数表示该有向边的权。赋权图中的权值可根据不同的目标进行定义，本模型将从到的路径长度定义为权。不妨定义为所有路口节点集合，为有向边 的最短路径长度，第一次取值时为从起点到选择的第一个节点的路径长度，即 ，接着选择第个节点时，要重新赋值，使其为最小值定义为
