110出警线路优化系统的设计与实现
|
摘要
随着社会的不断发展进步,110报警服务平台已经成为人民生活不可或缺的重要安全保障。这一方面说明我国公安系统建设取得了巨大的进步;另一方面也意味着公安系统承载的责任也愈加重大。如何进一步提高110出警平台的工作效率,缩短出警车辆的时间消耗成为今后110警务平台建设的重要内容。基于上述考虑,本文以山东省潍坊市的城市道路网络为基础设计并实现了最优路径优化模块,为110出警信息系统的构建提供基础,以达到提高110出警系统出警效率的目的。
为了提高110公安系统的出警效率,本文对城市环境下的110出警路径优化算法进行了研究。论文首先对路网数学模型进行了研究,根据地图学和图论的有关原理,将地图数据划分为节点和路段两种类型,分析总结了各种存储结构的原理和特点,最终采用邻接矩阵存储地图矢量数据。然后,论文从更加实际的角度出发,探讨道路阻值的设定,采用AHP层次分析法对道路阻值权重进行初步的比较设定,使影响道路畅通性的各种因素可以纳入优化模型。论文的关键部分是路径优化算法的研究,首先介绍各种路径寻优算法的分类和特点,重点讨论了Dijkstra算法和A*启发式算法的原理和实现步骤,分析了两种算法各自的特点,并将Dijkstra算法和A*启发式算法作为本案例的路径优化算法进行实现。最后以潍坊市的道路网络作为数据背景进行编程实现,选取MAPINFO软件作为地图平台,采用MapBasic二次开发语言进行算法编程,最终实现了潍坊城区的110出警线路的优化选择。
With the development and progress of our society, 110 service platform has become an indispensable security to people's life safety. On the one hand, it means the public security system of out country has made a tremendous progress. On the other hand it means the responsibility of the public security system bearing becomes more and more important. So how to improve the work efficiency of 110 Police Platform and shorten the time consuming of police vehicles becomes the important part of building 110 platform in future. Based on the above considerations, this thesis designs and achieves the optimal path optimization module and set the stage for building the information system for 110 to go to patrol, on basis of urban road network of Weifang in Shandong province. It will increase the efficiency of the 110 police system.
In order to improve the work efficiency of 110 Police Platform, this thesis researches the arithmetic path optimization of 110 to go to patrol in the city proper. At first, the thesis researches into the road network model, divides map data into two types which are node and section according to the principle of cartography and graph theory, and summarizes the principles and characteristics of storage structures, which leads to store map vector data by adjacency matrix. Second, from a more practical point of view, it researches into how to set road resistance and sets the weights of road resistance initially by use of AHP, which brings various aspects influencing road smoothness into optimization model. Then the most important part of this thesis is the research of path optimization. It introduces classifications and characteristics of every kind of path searching firstly, and focus on the discussion of principles and implementation steps of Dijkstra and A* heuristic algorithm, then analyzes own characteristics of two algorithms. At the end we achieve those two algorithms as path optimization. Finally we make use of MapBasic secondary development language to program the algorithms set data in road network of Weifang on MapInfo and achieve the optimization of the line for 110 to go to patrol in the city proper of Weifang.
为了提高110公安系统的出警效率,本文对城市环境下的110出警路径优化算法进行了研究。论文首先对路网数学模型进行了研究,根据地图学和图论的有关原理,将地图数据划分为节点和路段两种类型,分析总结了各种存储结构的原理和特点,最终采用邻接矩阵存储地图矢量数据。然后,论文从更加实际的角度出发,探讨道路阻值的设定,采用AHP层次分析法对道路阻值权重进行初步的比较设定,使影响道路畅通性的各种因素可以纳入优化模型。论文的关键部分是路径优化算法的研究,首先介绍各种路径寻优算法的分类和特点,重点讨论了Dijkstra算法和A*启发式算法的原理和实现步骤,分析了两种算法各自的特点,并将Dijkstra算法和A*启发式算法作为本案例的路径优化算法进行实现。最后以潍坊市的道路网络作为数据背景进行编程实现,选取MAPINFO软件作为地图平台,采用MapBasic二次开发语言进行算法编程,最终实现了潍坊城区的110出警线路的优化选择。
With the development and progress of our society, 110 service platform has become an indispensable security to people's life safety. On the one hand, it means the public security system of out country has made a tremendous progress. On the other hand it means the responsibility of the public security system bearing becomes more and more important. So how to improve the work efficiency of 110 Police Platform and shorten the time consuming of police vehicles becomes the important part of building 110 platform in future. Based on the above considerations, this thesis designs and achieves the optimal path optimization module and set the stage for building the information system for 110 to go to patrol, on basis of urban road network of Weifang in Shandong province. It will increase the efficiency of the 110 police system.
In order to improve the work efficiency of 110 Police Platform, this thesis researches the arithmetic path optimization of 110 to go to patrol in the city proper. At first, the thesis researches into the road network model, divides map data into two types which are node and section according to the principle of cartography and graph theory, and summarizes the principles and characteristics of storage structures, which leads to store map vector data by adjacency matrix. Second, from a more practical point of view, it researches into how to set road resistance and sets the weights of road resistance initially by use of AHP, which brings various aspects influencing road smoothness into optimization model. Then the most important part of this thesis is the research of path optimization. It introduces classifications and characteristics of every kind of path searching firstly, and focus on the discussion of principles and implementation steps of Dijkstra and A* heuristic algorithm, then analyzes own characteristics of two algorithms. At the end we achieve those two algorithms as path optimization. Finally we make use of MapBasic secondary development language to program the algorithms set data in road network of Weifang on MapInfo and achieve the optimization of the line for 110 to go to patrol in the city proper of Weifang.
引文
[1]陆锋,卢东梅,崔伟宏.交通网络限制搜索区域时间最短路径算法.中国图像图形学报,1999,4(10):850-853.
[2]尚华艳.物流配送中车辆路径问题研究[M].武汉理工大学硕士论文.
[3]严寒冰,刘迎春。基于GIS的城市道路网最短路径算法研讨。中国计算机学报,2000,2:210-215
[4]姚娜编著.GIS、MapInfo与MapBasic学习教程.北京:北京大学出版社,2000.
[5]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统—CIMS,2002.6(8):451~454.
[6]纪寿文,王荣本,徐友春,李斌.智能车辆导航路径识别的模糊神经网络方法研究[J].中国图象图形学报,2003.2(2):225~230.
[7]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法[J].系统工程学报,2004(4)
[8] A.P.Eiger,P.Mirchandani and H.Soroush,“Path preferences and optimal pathsin probabilistic networks,”Transp.Sci,vol.19,no.1,1985.pp.75-84.
[9] A.P.Eiger,P.Mirchandani and H.Soroush,“Path preferences and optimal paths in probabilistic networks,”Transp.Sci,vol.19,no.1,1985.pp.75-84.
[10] R.Hall,“The fastest path through a network with random time-dependent travel times,”Transp.Sci,vol.20,no.3,1986,pp.183-188.
[11] J.Pearl,Heuristics:Intelligent Search Strategy for Computer Problem Solving. Reading,MA:Addison- Wesley,1984.
[12] M.P.Wellman,M.Ford and K.Larson,“Path planning under time-dependent uncertainty,”in Proc.11th Conf.Uncertainty in Artificial Intelligence, Montreal, Canada,Aug.1995,pp 532-539.
[13] E.D.Miller-Hooks and H.S.Mahmassani,“Least possible time paths in stochastic,time-varying transportation networks,”Comput.Oper.Res.Vol.25, no.12 , 1998.pp.1107-1125.
[14] E.D.Miller-Hooks and H.S.Mahmassani,“Least possible time paths instochastic, time-varying transportation networks,”Comput.Oper.Res.Vol.25,no.12,
[15] Herbert D T. Urban geography: a first approach [J]. Chicester: John Wiley & Sons, 1981: 1~25
[16] Caro G D,Dorigo M.Mobile agents for adaptive routing[EB/OL].
[17] David Levinson.The value of advanced traveler information systems for route choice.http://www.elsevier.com/locate/trf/Transportion Research Part C 11(2003):75-87
[18]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].物流技术2003(12):72~73.
[19]陈湘州,黎志明,刘祖润.一种改进的整数编码遗传算法在车辆路径优化问题中的应用[J].南方冶金学院学报.2004.2(1):36~41.
[20]顾志康,李旭宏,徐家兵.一种改进遗传算法在物流配送车辆调度中的应用研究[J].公路交通科技,2004.11:118~120.
[21]章兢,周泉.基于免疫克隆算法的物流配送车辆路径优化研究[J].湖南大学学报报(自然科学版),2004.10(5):54~58.
[22]李宁,邹彤,孙德宝.车辆路径问题的粒子群算法研究[J].系统工程学报,2004,6:130-135.
[23]党国英,王建仁,崔俊凯.模糊理论在VRPTW问题上的蚁群算法研究[J].统计与决策,2005,24:35-37.
[24]宋延,石建军,许国华。适用于路径规划系统的动态路网描述。模型交通与计算机,2004年第5期,第22卷:28-31.
[25]余震江.基于最短路径Dijkstra算法的铁路客运中转径路优化研究[D].重庆大学硕士论文.
[26]景玲.城市动态路径诱导系统框架及最优路径选择算法研究[D].重庆大学硕士学位论文.
[27]于东凯,刘玉树。基于平面图的最短路径算法的研究。北京理工大学学报Vol 21,No1,Feb 2001:31-34.
[28]冯霞,刘丽萍。基于人工智能的城市交通系统关键技术研究。武汉大学学报,Vol 34,No 6,Dec 2001:79-82
[29]张虎,施一民.基于MapX的公安110报警系统的设计与实现[J].测绘通报,2004(9):23~39
[30]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理科学工程学报,2005(1):124~130.
[31]金星.灭火救援系统中最优路径规划方法研究[D].吉林大学硕士论文,2008.
[32]张颖.基于最优规划的事故应急救援系统的研究及其实现[D].重庆大学硕士学位论文.2005.
[33]宋晓宇,于澜洋,孙焕良.动态交通网络中最优路径查找算法[J].计算机应用研究,2009.6,26(6):2066~2069.
[34]刘江.基于层次分析法的企业运输方式的选择[D].对外经贸大学硕士论文,2006.
[35]朱建军.层次分析法的若干问题研究及应用[D].东北大学博士论文,2005.
[36]王华,夏立民.交通最优路径选择算法的对比与仿真[J].计算机应用与软件,2009.2, 26(2) :63~68.
[37]杨素琼,林碧琴,何伟.基于A*算法的地图路径搜索的实现[J].铁道计算机应用,2000(4):8~11.
[38]李元臣,刘维群.基于Dijkstra算法的网络最短路径分析[J].微计算机应用,2004,25(3):295~298.
[39]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].物流技术,2003(12):72~73.
[40]王峰等. Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用[J].计算机应用研究,2006(9):203~208.
[41]张静,李茂清.由邻接矩阵求解可达矩阵的一种改进简便算法[J].开发研究与设计技术,2006,:177~178.
[42]邹亮,徐建闽,朱玲湘.A*算法改进及其在动态最短路径问题中的应用[J].深圳大学学报理工版,2007.1,24(1):32~36.
[43]蔡自兴,徐光佑.人工智能及其应用[M].北京:清华大学出版社.2007.7:25~33.
[44]苏永云,晏克非,黄翔,朱培康。车辆导航系统的动态最优路径搜索算法研究。系统工程,第18卷,第4期:32-37
[45]邹志云,宋程,虢向阳.基于灰色理论的应急物流最优路径选择[J].物流技术, 2008,27(1):46~48.
[2]尚华艳.物流配送中车辆路径问题研究[M].武汉理工大学硕士论文.
[3]严寒冰,刘迎春。基于GIS的城市道路网最短路径算法研讨。中国计算机学报,2000,2:210-215
[4]姚娜编著.GIS、MapInfo与MapBasic学习教程.北京:北京大学出版社,2000.
[5]张丽萍,柴跃廷,曹瑞.有时间窗车辆路径问题的改进遗传算法[J].计算机集成制造系统—CIMS,2002.6(8):451~454.
[6]纪寿文,王荣本,徐友春,李斌.智能车辆导航路径识别的模糊神经网络方法研究[J].中国图象图形学报,2003.2(2):225~230.
[7]崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法[J].系统工程学报,2004(4)
[8] A.P.Eiger,P.Mirchandani and H.Soroush,“Path preferences and optimal pathsin probabilistic networks,”Transp.Sci,vol.19,no.1,1985.pp.75-84.
[9] A.P.Eiger,P.Mirchandani and H.Soroush,“Path preferences and optimal paths in probabilistic networks,”Transp.Sci,vol.19,no.1,1985.pp.75-84.
[10] R.Hall,“The fastest path through a network with random time-dependent travel times,”Transp.Sci,vol.20,no.3,1986,pp.183-188.
[11] J.Pearl,Heuristics:Intelligent Search Strategy for Computer Problem Solving. Reading,MA:Addison- Wesley,1984.
[12] M.P.Wellman,M.Ford and K.Larson,“Path planning under time-dependent uncertainty,”in Proc.11th Conf.Uncertainty in Artificial Intelligence, Montreal, Canada,Aug.1995,pp 532-539.
[13] E.D.Miller-Hooks and H.S.Mahmassani,“Least possible time paths in stochastic,time-varying transportation networks,”Comput.Oper.Res.Vol.25, no.12 , 1998.pp.1107-1125.
[14] E.D.Miller-Hooks and H.S.Mahmassani,“Least possible time paths instochastic, time-varying transportation networks,”Comput.Oper.Res.Vol.25,no.12,
[15] Herbert D T. Urban geography: a first approach [J]. Chicester: John Wiley & Sons, 1981: 1~25
[16] Caro G D,Dorigo M.Mobile agents for adaptive routing[EB/OL].
[17] David Levinson.The value of advanced traveler information systems for route choice.http://www.elsevier.com/locate/trf/Transportion Research Part C 11(2003):75-87
[18]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].物流技术2003(12):72~73.
[19]陈湘州,黎志明,刘祖润.一种改进的整数编码遗传算法在车辆路径优化问题中的应用[J].南方冶金学院学报.2004.2(1):36~41.
[20]顾志康,李旭宏,徐家兵.一种改进遗传算法在物流配送车辆调度中的应用研究[J].公路交通科技,2004.11:118~120.
[21]章兢,周泉.基于免疫克隆算法的物流配送车辆路径优化研究[J].湖南大学学报报(自然科学版),2004.10(5):54~58.
[22]李宁,邹彤,孙德宝.车辆路径问题的粒子群算法研究[J].系统工程学报,2004,6:130-135.
[23]党国英,王建仁,崔俊凯.模糊理论在VRPTW问题上的蚁群算法研究[J].统计与决策,2005,24:35-37.
[24]宋延,石建军,许国华。适用于路径规划系统的动态路网描述。模型交通与计算机,2004年第5期,第22卷:28-31.
[25]余震江.基于最短路径Dijkstra算法的铁路客运中转径路优化研究[D].重庆大学硕士论文.
[26]景玲.城市动态路径诱导系统框架及最优路径选择算法研究[D].重庆大学硕士学位论文.
[27]于东凯,刘玉树。基于平面图的最短路径算法的研究。北京理工大学学报Vol 21,No1,Feb 2001:31-34.
[28]冯霞,刘丽萍。基于人工智能的城市交通系统关键技术研究。武汉大学学报,Vol 34,No 6,Dec 2001:79-82
[29]张虎,施一民.基于MapX的公安110报警系统的设计与实现[J].测绘通报,2004(9):23~39
[30]刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述[J].管理科学工程学报,2005(1):124~130.
[31]金星.灭火救援系统中最优路径规划方法研究[D].吉林大学硕士论文,2008.
[32]张颖.基于最优规划的事故应急救援系统的研究及其实现[D].重庆大学硕士学位论文.2005.
[33]宋晓宇,于澜洋,孙焕良.动态交通网络中最优路径查找算法[J].计算机应用研究,2009.6,26(6):2066~2069.
[34]刘江.基于层次分析法的企业运输方式的选择[D].对外经贸大学硕士论文,2006.
[35]朱建军.层次分析法的若干问题研究及应用[D].东北大学博士论文,2005.
[36]王华,夏立民.交通最优路径选择算法的对比与仿真[J].计算机应用与软件,2009.2, 26(2) :63~68.
[37]杨素琼,林碧琴,何伟.基于A*算法的地图路径搜索的实现[J].铁道计算机应用,2000(4):8~11.
[38]李元臣,刘维群.基于Dijkstra算法的网络最短路径分析[J].微计算机应用,2004,25(3):295~298.
[39]王正彬,杜文.考虑线路安排的物流配送方案模型及其算法研究[J].物流技术,2003(12):72~73.
[40]王峰等. Dijkstra及基于Dijkstra的前N条最短路径算法在智能交通系统中的应用[J].计算机应用研究,2006(9):203~208.
[41]张静,李茂清.由邻接矩阵求解可达矩阵的一种改进简便算法[J].开发研究与设计技术,2006,:177~178.
[42]邹亮,徐建闽,朱玲湘.A*算法改进及其在动态最短路径问题中的应用[J].深圳大学学报理工版,2007.1,24(1):32~36.
[43]蔡自兴,徐光佑.人工智能及其应用[M].北京:清华大学出版社.2007.7:25~33.
[44]苏永云,晏克非,黄翔,朱培康。车辆导航系统的动态最优路径搜索算法研究。系统工程,第18卷,第4期:32-37
[45]邹志云,宋程,虢向阳.基于灰色理论的应急物流最优路径选择[J].物流技术, 2008,27(1):46~48.