1、1最短路径规划研究摘要：交巡警肩负着刑事执法、治安管理、交通管理、服务群众四大职能。其警力的空间配置与工作效率直接影响着人民生活及社会安定。为解决某市交巡警服务平台（下称“平台” ）管辖范围的分配，警力资源的快速调动等相关问题，建立了合理的规划模型并进行了分析。 关键词：最小生成树；Floyd；规划模型 中图分类号：TB 文献标识码：A 文章编号：1672-3198（2013）08-0189-02 1 基本假设 （1）不变更各区内交通线路及节点设置，新增平台和“围堵点”均不设在节点之外。 （2）市内 6 城区各点不会在同一时间出现突发事件。（3）交巡警在赶往案发地的路途中保持 60km/h 匀
2、速前进且没有发生道路拥堵。 （4）平台警力集中使用，不能分散。 （5）管辖范围的划分以及任务的分配可以最优化。 （6）接到各类报案，交巡警决策部门的决策用时均为零。 （7）尽管各区面积、人口数、人口密度分别与报案率完全不成比例，从题目要求中的任务的性质，警力部署看，可以肯定：各区人口数、面积与警力空间配置与优化无关，所以此二列数据不在本模型中使用。 2 参数符号说明 iA 区各出入口标号；t时间；j节点标号；m方案标2号；ti警力封锁第 i 个出入口所需要的时间；tjm交巡警从平台出发到达 j 节点所需要的时间；x节点横坐标；y节点纵坐标；xb与所求节点相邻节点的横坐标；yb与所求节点相邻节点
3、的纵坐标；Emm距离矩阵。 3 模型的建立和求解 3.1 模型：规划模型 minmmaxjtjm|j=1，2，92，tjm3 交巡警平台管辖范围的大小取决于他到周围节点所需要的最长时间（尽量不超过 3 分钟）即 maxtj，所以要求出各平台到 j 点需要的最长时间（由于某平台到某节点有若干种方案，所以将 maxtj 用 maxtjm 代替，m 代表方案） ，为了能保证交巡警以最快速度到达案发平台，我们从各方案的 maxtjm 中筛选出 maxtjm 最小的一个方案，即合理分配辖区的最优方案。 我们用 excel 软件对数据进行了大量处理，从而将时间问题转换为路径距离问题：交巡警 3 分钟内能走
4、过的最长路径距离为 3min*60km/h，即 30mm，同时用 Matlab 绘制出了 A 区各点的关系图（如图 1） 。我们分别以 A 区中的每一个平台为起点，在 C+6.0 的环境中连续 20 次运用最小生成树法，初步确定出每一个平台所能管辖的最大范围（如表 1） 。 图 1A 区各点关系图表 1 中存在如下问题：（1）许多平台的管辖范围有重复。 （2）个别节点没有被划分到任何一个平台的辖区（28、29、38、39、61、92 号点） 。 （3）个别平台没有发挥作用（10、14号点） 。为了解决这些问题，我们考虑以各平台的业务量为新标准优化辖3区范围的分配（此处我们用各点发案率的高低衡量
5、各点业务量的大小） ，尽量使各平台的业务量均衡。另外，对于那些没有被划分到任何一个辖区的点，我们实行“就近原则”使之有主可依。分配情况见表 2。 相邻节点间距离=（xa-xb）2+（ya-yb）2 为确定交巡警的全力逮捕范围，即在案发后一段时间（大概是 6 分钟）后罪犯逃亡的路线。因涉及全市的交通要道，所以要先用最小生成树确定 P 点逃亡的区域。则在案发一段时间后，第一种情况是：罪犯仍在 A 区范围内，则动用一切交巡警服务平台的警力资源全面封锁路口，以确保可以及时的逮捕罪犯。第二中情况是不在 A 区内，通过 C+语言可以知道罪犯只能向 B 区逃亡。在 B 区内，可以用最小路径的方法求得罪犯逃亡
6、的最大范围，再利用就近原则给这个区间分配交巡警服务平台，然后快速地进行全面封锁，以达到逮捕罪犯的目的。图 2 是我们根据数据用 MATLAB 绘制出的包围圈（绿色线所包围的范围） 。其中空白区域的顶点即是 B 区域中的 237 号节点，也是罪犯逃亡路线中唯一位于 B 区域中的点。 图 2 包围圈我们再次运用 Floyd 算法，找出包围圈各顶点与临近交巡警服务平台间的最短路径，形成我们的最优围堵方案。特别需要指出的是，由于案发三分钟后才接到报警，所以此处所说的最短路径必须能在三分钟内到达。我们得到的最优围堵方案（如表 4） 。 表 4 新增平台后的最优方案 服务平台节点最优方案所需时间（分钟）5
7、83（新增）2922 到 29 必然小于 3584（新增）2821 到 28 必然小于 3101010 到 100161616 到4160585（新增）3923 到 39 必然小于 3232 到 31.23543 到 55 到542.275535 到 49 到 531.176596 到 591.6586（新增）6124 到 61 必然小于 37487 到 30 到 481.29173237（C 区点）173 到 235 到 2371.181 参考文献 1阳明盛，等.最优化原理、方法及求解软件M.北京：科学出版社，2006. 2施继红.数学建模与计算机应用的融合J.信息系统工程，2011， （05）：14-15. 3马莉.MATLAB 语言实用教程M.北京：清华大学出版社，2010. 4姜启源.数学实验与数学建模J.数学的实践与认识，2001， （05）：613-617. 5姜启源.数学模型（第三版）M.北京：高等教育出版社，2003.
