文档介绍：最短路径规划研究摘要:交巡警肩负着刑事执法、治安管理、交通管理、服务群众四大职能。其警力的空间配置与工作效率直接影响着人民生活及社会安定。为解决某市交巡警服务平台(下称“平台”)管辖范围的分配,警力资源的快速调动等相关问题,建立了合理的规划模型并进行了分析。关键词:最小生成树;Floyd;规划模型中图分类号:TB文献标识码:A文章编号:1672-3198(2013)08-0189-021基本假设(1)不变更各区内交通线路及节点设置,新增平台和“围堵点”均不设在节点之外。(2)市内6城区各点不会在同一时间出现突发事件。(3)交巡警在赶往案发地的路途中保持60km/h匀速前进且没有发生道路拥堵。(4)平台警力集中使用,不能分散。(5)管辖范围的划分以及任务的分配可以最优化。(6)接到各类报案,交巡警决策部门的决策用时均为零。(7)尽管各区面积、人口数、人口密度分别与报案率完全不成比例,从题目要求中的任务的性质,警力部署看,可以肯定:各区人口数、面积与警力空间配置与优化无关,所以此二列数据不在本模型中使用。2参数符号说明i――A区各出入口标号;t――时间;j――节点标号;m――方案标号;ti――警力封锁第i个出入口所需要的时间;tjm――交巡警从平台出发到达j节点所需要的时间;xα――节点横坐标;yα――节点纵坐标;xb――与所求节点相邻节点的横坐标;yb――与所求节点相邻节点的纵坐标;Emm――距离矩阵。Ⅰ:规划模型minmmaxj{tjm|j=1,2,…,92,tjm≤3}交巡警平台管辖范围的大小取决于他到周围节点所需要的最长时间(尽量不超过3分钟)即maxtj,所以要求出各平台到j点需要的最长时间(由于某平台到某节点有若干种方案,所以将maxtj用maxtjm代替,m代表方案),为了能保证交巡警以最快速度到达案发平台,我们从各方案的maxtjm中筛选出maxtjm最小的一个方案,即合理分配辖区的最优方案。我们用excel软件对数据进行了大量处理,从而将时间问题转换为路径距离问题:交巡警3分钟内能走过的最长路径距离为3min*60km/h,即30mm,同时用Matlab绘制出了A区各点的关系图(如图1)。我们分别以A区中的每一个平台为起点,在C++,初步确定出每一个平台所能管辖的最大范围(如表1)。图1A区各点关系图表1中存在如下问题:(1)许多平台的管辖范围有重复。(2)个别节点没有被划分到任何一个平台的辖区(28、29、38、39、61、92号点)。(3)个别平台没有发挥作用(10、14号点)。为了解决这些问题,我们考虑以各平台的业务量为新标准优化辖区范围的分配(此处我们用各点发案率的高低衡量各点业务量的大小),尽量使各平台的业务量均衡。另外,对于那些没有被划分到任何一个辖区的点,我们实行“就近原则”使之有主可依。分配情况见表2。相邻节点间距离=(xa-xb)2+(ya-yb)2为确定交巡警的全力逮捕范围,即在案发后一段时间(大概是6分钟)后罪犯逃亡的路线。因涉及全市的交通要道,所以要先用最小生成树确定P点逃亡的区域。则在案发一段时间后,第一种情况是:罪犯仍在A区范围内,则动用一切交巡警服务平台的警力资源全面封锁路口,以确保可以及时的逮捕罪犯。第二中情况是不在A区内,通过C++语言