发布时间 : 星期一 文章2011国赛B题论文 - 图文更新完毕开始阅读
题目 交巡警服务平台的设置与调度
摘要
针对本文要解决的问题，通过图论对问题进行转化，采用Floyd算法，再通过数据的分析、筛选和计算，从而得到各节点到交巡警服务平台的最短距离。
问题一，我们分为三部分进行求解，依次为1）管辖范围的求解；2）交巡警服务平台的合理调度方案；3）对增加的交巡警服务平台的具体数量及位置的求解。
对于1）的求解，根据对各节点到交巡警服务平台的最短距离可以将第一部分分为两类考虑依次为距离小于3000m的和距离大于3000m的。对于第一类来说，采用优化模型，以最短距离为目标函数，再引用0-1变量规划用Lingo软件进行求解，得到表2.对于第二类，考虑1)6个节点到相邻的交巡警服务平台的距离；2）6个节点处的案发率；3）交巡警服务平台所承担的案发率。得到表4.最终得到20个交巡警服务平台的管辖范围，详见正文中的表5.
对于2）的求解，采用的是多目标规划模型。以最短距离，最短时间和最短时间方差为目标函数，同样再引入0-1变量规划，运用Lingo软件进行求解，得到合理调度方案，详见正文中的表6.
对于3）的求解，采用的是多目标规划模型。在考虑对交巡警服务平台的工作量的情况下，以最小案发率方差为目标函数，同样再引入0-1变量规划，运用Lingo软件得出应该增加的交巡警服务平台为5个，其具体位置为28,39,48,61,92.
问题二，将其分为两个部分进行求解依次为1）对现有的交巡警服务平台设置方案的合理性判断，若不合理的话，给出解决方案；2）给出最佳的围堵方案。
对于1）的求解，要考虑各区的人口和面积的基础上再对各交巡警服务平台的现有工作量进行讨论，最后得出其合理性。若不合理的将对其进行优化。最终得到的解决方案见正文中的表7.
对于2）的求解，根据题目中所提供的条件，要求快速围堵嫌疑人，给出最佳的围堵方案。对嫌疑人的围堵是在A区的P点开始的。因此，以P为中心，向外发散选取最靠近P点的点即为一级节点，一级节点连线成圈称为一级圈。在此对服务平台到一级节点的时间进行考虑，若时间小于嫌疑犯到达一级节点的时间，则被逮捕。若大于的，再依据此方法进行展开，直至围堵到嫌疑犯为止。最终确定的围堵方案为：2->40 3->55 4->60 5->5 6->6 7->7 8->8 10->10 15->15 16->16 17->41 167->248 171->245 171->246 475->561
关键词： 0-1变量规划 平均案发率 Floyd算法 图论 一级节点 一级圈 多目标规划 Lingo软件
1.问题重述
为了更有效地贯彻实施这些职能，需要在市区的一些交通要道和重要部位设置交巡警服务平台。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。
试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题： （1）根据附件中所给出的资料，为各交巡警服务平台分配管辖范围，让他们在所管辖的范围内出现突发事件时，尽量在3分钟之内有交巡警到达事发地（警车的时速为60km/h)。
（2）对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。但在实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。
（3）根据现有的交巡警服务平台的实际情况，想在该区在增加2-5个平台，确定增加的具体个数和位置。
（4）针对全市的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案的合理性。如有明显的不合理，给出解决方案。
（5）若在该市的P店发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已经驾车逃离。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。
2.问题分析
2.1问题一的分析
对于问题一的分析，首先是在考虑最短距离的前提下来确定各交巡警服务平台的管辖范围的。我们首先是将A区上的92个点进行标定。其次，运用Floyd算法求得各节点到交巡警服务平台的最短距离，最后求得管辖范围。对于合理的调度方案，在确保距离最短，时间最小，时间方差最小的前提下对13个重要道路进行封锁，然后在每
个重要道路路口保证都会有警力。在此基础上我们运用Lingo软件最终得出合理的调度方案。
在考虑每个交巡警服务平台的工作量均衡的情况下，以最小案发率方差为目标函数，同样再引入0-1变量规划，运用Lingo软件求解。
2.2问题二的分析
对于问题二的分析，我们将其分为两部分进行求解，依次为1）对现有的交巡警服务平台设置方案的合理性判断，若不合理的话，给出解决方案；2）给出最佳的围堵方案。对于1）的求解时，要考虑各区的人口和面积的基础上再对各交巡警服务平台的现有工作量进行讨论，判断其合理性。再考虑工作量均衡的前提下对服务平台的设置与调度进行调节；对于2）的求解，将围堵区域由小到大的进行围堵。以P为中心，向外发散进行围堵，得出最佳围堵方案。
3.模型假设
1.假设城区内的所有道路都是畅通无阻的； 2.假设相邻两个节点之间的道路为直线；
3.假设在同一时间内同时发生突发事件的地点相差很远； 4.假设在交巡警的出警过程中不发生意外情况； 5.假设每段道路上突发事件都归结发生在节点；
7.警车在形式过程中都是以最快时速匀速行驶的，在市区内嫌疑犯驾驶的车速最快不会超过警车的时速，所以假设嫌疑犯的时速同警车相同； 8.一个平台的警力可以围堵多个道路节点。
4.符号说明
0-1变量，判断q节点是否归属j服务平台管辖 xjq 1表示q节点归属j服务平台管辖； 0表示q节点不归属j服务平台管辖 0-1变量，判断j交巡警服务平台是否封锁i重要道路 xij 1表示j交巡警服务平台封锁i重要道路； 0表示j交巡警服务平台不封锁i重要道路 gjpdij 0-1变量，判断节点是否为服务平台。 节点到服务平台的最短距离 交巡警服务平台到13个出入城区节点的最短距离 交巡警服务平台到92个节点的最短距离 交巡警服务平台封锁13个出入城区节点所需要的时间 各节点的工作量 20个交巡警服务平台
dij d jptij Wpg jj5.模型建立及求解
5.1问题一
对于问题一，将其分为三个小问题进行考虑，依次为： 1.交巡警服务平台管辖范围的求解；
2.A区交巡警服务平台警力的合理调度方案的求解； 3.增加的交巡警服务平台的具体数量及位置的求解。 5.1.1管辖范围的求解
首先对该市A城区的92个节点进行标注，详见图1。
图1