2011年全国大学生数学建模竞赛获奖优秀论文__作者：刘苗苗,蒋朝

很好的大学建模范文,值得大家借鉴。

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

摘要

警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。交巡警服务平台的设置与调度直接关系到上述职能的实现，因此做好交巡警服务平台的设置与调度优化极为重要。本文重点解决的是对某地区交警服务平台的设置与调度优化问题.

首先以A区为研究对象，运用Floyd算法，并对相应的算法建立流程图,计算出各个节点之间的最短距离及其路径，根据最短距离优先以及在三分钟内尽量到达报警地的原则，对各平台分配管辖范围.

为了实现对A区13条交通要道的快速封锁，调度原则为在最短的时间实现全部封锁，根据由上界找上确界的原则得到封锁全区的最短时间为8.02分钟以

对出警时间过长的问题，增加了四个节点分别为：28（或29）、38（或39）、61、9，根据工作量不平衡的情况，采用贪婪算法，在工作量最大的服务平台周围增加，新增个数由工作量的大小决定，为此得到新增的节点数为5，增加的位置分别分布在：A5、A7、A15、A20以及A1A2A3处，综合以上两个方面得到需增加的服务站为：28 48 39 91 66.

对问题二，针对全市六区现有交警服务平台的设置进行合理性评价，既找到了合理之处，同时也发现了存在的明显不足，即C、F区交警平台管辖的平均发案率明显高于其他区，需要对这两区增加新的交巡警服务平台，使全市每个区的服务平台处理的发案率相差不多，得到新增平台数，然后结合地图决定其位置。当P处发生重大刑事案件，在全市范围内进行围堵时，在满足围堵成功的前提下，尽量缩小围堵范围，减少调度平台的个数，从而得到最优的围堵方案，为此分析计算A区是否能够成功围堵时发现，从A区逃跑后仅可能进入Ｃ区和Ｆ区，再对Ｃ、Ｆ区进行围堵，围堵时采用与问题一中围堵Ａ区时相同的算法。舍掉了B、D、E区，减少了围堵范围，比较合理。同时，由于对Ａ区进行了全封锁，又对Ｃ和Ｆ区进行了出口处得封锁，形成三个封锁圈，从而很大程度上降低了进一步搜索的困难程度；当一个嫌疑犯确定了所在区时，可以将另外两区解除封锁，减少对居民生活的不便，因而比较合理.

关键字: Floyd算法 贪婪算法 最短路径 可行域

很好的大学建模范文,值得大家借鉴。

一 问题重述

“有困难找警察”，是家喻户晓的一句流行语。警察肩负着刑事执法、治安管理、交通管理、服务群众四大职能。为了更有效地贯彻实施这些职能， 。每个交巡警服务平台的职能和警力配备基本相同。由于警务资源是有限的，如何根据城市的实际情况与需求合理地设置交巡警服务平台、分配各平台的管辖范围、调度警务资源是警务部门面临的一个实际课题。

试就某市设置交巡警服务平台的相关情况，建立数学模型分析研究下面的问题：

（1）附件1中的附图1给出了该市中心城区A的交通网络和现有的20个交巡警服务平台的设置情况示意图，相关的数据信息见附件2。请为各交巡警服务平台分配管辖范围，使其在所管辖的范围内出现突发事件时，尽量能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。

对于重大突发事件，需要调度全区20个交巡警服务平台的警力资源，对进出该区的13条交通要道实现快速全封锁。实际中一个平台的警力最多封锁一个路口，给出该区交巡警服务平台警力合理的调度方案。

根据现有交巡警服务平台的工作量不均衡和有些地方出警时间过长的实际情况，拟在该区内再增加2至5个平台，确定需要增加平台的具体个数和位置。

（2）针对全市（主城六区A，B，C，D，E，F）的具体情况，按照设置交巡警服务平台的原则和任务，分析研究该市现有交巡警服务平台设置方案（参见附件）的合理性。如果有明显不合理，请给出解决方案。

如果该市地点P（第32个节点）处发生了重大刑事案件，在案发3分钟后接到报警，犯罪嫌疑人已驾车逃跑。为了快速搜捕嫌疑犯，给出调度全市交巡警服务平台警力资源的最佳围堵方案。

二 模型的假设和符号说明

2.1 模型假设

（1）题目中所给的数据真实可靠；

（2）案件发生在节点处，对每个调度站的管辖的范围确定到节点处，忽略发生在节点间路上的事故；

（3）交巡警在工作时不会出现堵车等意外情况； （4）所有巡警执行任务都是按照最短路径行走； （5）犯罪嫌疑人的车速不超过60km/h 2.2.符号说明

dMij：M区i号节点与j号服务平台之间的最短路径距离； wij：A区各节点所组成的无向图的邻接矩阵； Wij：所有节点组成的无向图的邻接矩阵； fMj：M区第j号服务平台的工作量；

； pMi：M区第i号平台的发案率（M代表A B C D E F）

很好的大学建模范文,值得大家借鉴。

其余符号文中说明

三 问题分析

此题是与图论有关的分配、调度问题，在进行具体的问题解决时，首先运用MATLAB软件根据题目中的各个节点的坐标将节点编号与具体图形相接合，将图形中各点进行编号，并求出有连线的点的距离。

第一问要求A区各点在出现突发事件时，在3分钟内有交巡警到达事发地，即要求A区在划分节点归属时，结点距离最近的平台为隶属平台，即可满足。

对于服务站的指派问题，要求A区发生重大突发事件时，对进出A区的13条交通要道实现快速全封锁的调度方案，以各种方案中最大调度距离的最小值为目标函数，根据各个节点的最短距离表格（已求出），就可以确定最优调度方案。

对服务站的再分配问题，是由于出于对某些工作交巡警服务平台的工作量不均和出警时间过长问题，则先单独考虑出警时间过长问题，给出一种增加平台的个数和位置，然后根据工作量不均问题，找出不均点，在其周围新增交警服务平台，即综合权衡来决定新增平台的最后位置。

第二问分析全市服务平台设置合理性时，只针对发案率尽量平均的指标，按照A区的分析方法进行分析，再根据平台设置点自身的发案率大小评判合理性，还可以考虑区域面积、人口密度等因素对平台设置方案的影响来评判。

当P点发生重大刑事案件时，求最佳围堵方案时，在确保围堵一定成功的前提下，尽量减少交巡警力；尽量避免多区围堵，首先计算A区情况及可能逃跑到外区的路径，再考虑外区的围堵方案，采用排除法，逐步化简，从而得到最佳的围堵方案。

四 模型的建立与求解

4.1问题1模型的建立与求解 4.1.1最短路径模型 1、当管辖范围无交集时

a.巡警在城市出警，若要使得其在所管辖的范围内出现突发事件时，能在3分钟内有交巡警（警车的时速为60km/h）到达事发地。为了尽量迅速，同时每个平台能够有更大的覆盖范围。首先把该问题转化为带权无向图最短路径问题。 A区各个平台，节点，要道可以看做是图G中的节点，G (V,{E})，其中G中边的权为D(e)，利用Floyd算法可以计算出任意两个节点之间的最短距离。 Floyd算法步骤

由于是带权无向图最短路径问题，用wij表示无向图的带权邻接矩阵。矩阵中非零元素的数值表示直接相连两点间的距离，用+∞表示没有直接相连的节点，求图中任意两点间的最短路径。令循环控制数p=1，对于一个n个点的带权邻接矩阵。

（1）如果在两节点i，j之间加入节点p，若wip wpj wij，则将节点p放入路径（i,j）中，则路径变为(i,p,j)。若wip wpj wij则路径不变。p=p+1

很好的大学建模范文,值得大家借鉴。

（2）判断p>n是，则退出，否则回到1

遍历图中所有节点，即可以得到任意两点间的最短路径矩阵D。A区具 …… 此处隐藏：2722字，全部文档内容请下载后查看。喜欢就下载吧 ……