摘要
本文以吉林省科技厅项目《基于浮动车的动态路径导航方法的研究》为背景,主要对车辆导航系统中的关键技术交通流预测方法和动态路径规划方法进行了研究。
基于车辆导航系统路径规划方法的要求,设计了相应的路网模型和合理的电子地图存储数据结构,讨论了分层地图的存储以及地图的动态加载。通过大量仿真实验数据,比较分析了几种常用路径规划算法在搜索时间和规划路径长度方面的性能。在交通流预测方面,从时序模型的分析入手,提出了使用自回归模型和卡尔曼滤波相结合的道路行程时间预测方法,仿真实验的结果表明了该方法提高了道路行程时间预测的准确程度,进而增强了车辆导航系统的稳定性。提出了融入预测信息的动态路径规划方法,该方法综合考虑了道路固有属性、实时交通状况和预测交通状况等因素进行路径规划,仿真实验结果表明,它能为用户提供更准确的路径行驶方案,从而有效的调节整体交通流量的分布。
Traffic jam and its induced problems such as traffic environment pollution,traffic security and traffic energy consumption and so on have attracted more and more attention. If we can combine the satellite, the general control center on the ground, the detecting equipment on the road, the in-vehicle computer and the control system on the road together into a stereo omnibearing traffic system by network communication techniques, then the driver can obtain an optiamal driving path in real time as long as inputing starting and ending point in vehicle navigation computer., intelligent transportation system (ITS)and intelligent vehicle highway system (IVHS)emerge as the time requires.
The vehicle navigation system (VNS) is one of important researches on ITS. The so-called vehicle navigation system. The so-called vehicle navigation system based on the road network digital map constructed by Geographic Information reckoning, applying GPS ,navigation calculation ,map-matching techniques for vehicle localizaton . Thus, as long as the traveler tells in-vehicle computer that where he is and where he wants to go, the VNS will in real time present the static or dynamic optimal route information in real time according to the information supplied by traffic information center. In addition, the driver can make the travel convenient and it is valuable in the view of economy and society.
The VNS is a very complicated system, refering to various theories and techniques widely. Researchers have performed deeply study on many parts of VNS, including digital map, position system, path planning and communication. At present, there are many kinds of mature navigation equipments, but as a complex system, there still are many issues required study. For example, the VNS, which can communicate in both directions, can not only can offer the traveler with various services, but also it can collect the traffic information used as reference of dynamic assignment of the traffic flow. So far, this kind of advanced traffic information system has been applied in the USA, Japan and Europe, but still there are some techniques and theories required to be improved.
Vehicle navigation system is an important ITS subsystem, what is the main function about vehicle to achieve the positioning of map matching, route arithmetic and road guidance functions. Route arithmetic is one of the key technologies. The optimal route arithmetic and real-time directly determine whether the system is good or bad. Route arithmetic and its related technologies are including: The data storage of digital map, arithmetic of static path planning, dynamic Traffic flow forecasting and processing, dynamic route arithmetic, forecast information fusion vehicle navigation system path planning.
In this paper we mainly study on digital map storage,the static route programming algorithm in the CDRGS, about journey time dynamic traffic information prediction, forecast information fusion center-vehicle navigation route planning algorithm. The main content will be introduced as follows:
1. The storage of digital map. First of all, construct the mathematical model to describe the road net and the road network property in this paper; Comparison of commonly used map storage; To multi layers map, stored the data in the different layer, and construct the relevancy with different layer. To big map, partition the map into grid or administration area, loaded dynamically.
2. Arithmetic of static path planning. Firstly, The Arithmetic of static planning in common use are described, the complexity and applicability are compared and discussed; Introduce a simulation platform, and based on the existing experimental platform, in order to better meet the actual application, layered search as improved strategy is adopted. Compare the result and the cost of search in the experiment, and get the reason. Finally, the conclusion can be gotten: if the map is a single layer map, the arithmetic should be A star and D, and form experiments in the search time and frequency shift we can adopted A star arithmetic is better then the early D arithmetic; If the map a multilayer map, when the distance between start node and the destination node is near, the arithmetic should be A star arithmetic, when the distance between start node and the destination node is far , the arithmetic should be adopted layered arithmetic.
3. Dynamic Traffic flow forecasting. First introduced the concept of dynamic traffic flow prediction, classification and principles; the modeling methods are studied that is based on general time sequence model and Bayesian combination time sequence model starting with general time sequence .second ,we study applicability of Kalman filter theory in the traffic flow forecast field,and then deduce mathematical model applying Kalman filter theory. Including parameter, flow arithmetic, and adopt the VC + + and MapX to carry on the simulation. The simulation results drawn through the application of Kalman filter model can achieve a higher precision, more suitable for vehicle navigation system stability.
4. The path planning of vehicle navigation system fusing forecast information. Analysis of dynamic path planning on the path planning model, the objective function model, and the solution to simulation system, and then bring in a dynamic path planning in the forecast increase in information theory, that is the so-called integration of dynamic path planning information. And we further divide the weights of the dissipation prediction function. And take the path forecasting factor affected by man into account. Come to optimize navigation planning. Through experiments in the car and we come to the conclusion: the optimized dynamic navigation path planning fusing forecast information can reduce traffic jam,reduce the average journey cost ,and then the navigation with forecast information is realized.
In summary, we have done some research on the road network model in this paper. And give the static data and dynamic data to describe, consider the analysis and design of the road network limited to traffic, write the update definition of the data path which could store dynamic traffic. We introduce the method of storage digital map, and discuss the dynamic information load method of hierarchical map;Aimed at the classical A start arithmetic, classical Dijkstra arithmetic, we study and accomplish the arithmetic on our system by programming; Because of the character of the digital map which is offered by digital map company, this paper presents a layered search arithmetic. Layered search arithmetic assort of the map into detailed map, summary map. Through transforming in layers, it is resolved that the search time is too long and path search is too complex. The layered search algorithm is realized on our system by programming ,and the effedt is very evidence; the modeling methods are studied that is based on general time sequence model and Bayesian combination time sequence model starting with general time sequence .second ,we study applicability of Kalman filter theory in the traffic flow forecast field,and then deduce mathematical model applying Kalman filter theory. Finally we use the Kalman filter method to research and design it. The simulation results can be drawn through the application of this model can achieve a higher precision, more suitable for vehicle navigation system stability;we study the dynamic path planning model,solve the mathematical model and determine traffic information update cycle. And then propose the dynamic programming simulation model,give a definition of total forecast diffusion function. Taking the future number of vehicles goal factor which man-made affect into account,we redefine the total forecast diffusion function. Obtain the ideal result through the race car experiment,then realize the more predictability guidance about the vehicles.
引文
[1]张其善,吴今培,杨东凯.智能车辆定位导航及应用[M].北京:科学出版社.2002.
[2] Zhigang Zhu,Guangyou Xu,Bo Yang,et al. Visa tramcar Real-time Vision System for Automatic Traffic Monitoring[J]. Image and Vision Computing,2000(18):781-794.
[3] Xumei Chen,Lei Yu,Jifu Guo,Yongshen Quan,Yanbin Geng,Yong Gao. Development of Beijing regional intelligent transportation system architecture[J]. Proceedings of 6th IEEE. Intelligent Transportation Systems. Shanghai,China,2003:560-565.
[4] Courtney R.L.A broad view of ITS standards in the US[J]. Proceeding of Intelligent Transportation System. 1997:529-536.
[5]交通部公路科学研究所.中国智能运输系统体系框架研究总报告[R].2001.7.
[6] Heng Wei , Qingyan Yang. Improve applicability of ITS-generated data via prioritizing positioning of surveillance devices over a road network[J]. Proceeding of Intelligent Transportation Systems. 2003:590-597.
[7] Meier R.,Harrington A.Cahill V. A framework for integrating existing and novel Intelligent transportation systems[J]. Proceeding of Intelligent Transportation Systems. 2005:154-159.
[8] Hamza-Lup G. L,Hua K. A.,Ming Lee,Rui Peng. Enhancing intelligent transportation Systems to improve and support homeland security[J]. Proceedings of the 7th International IEEE Conference on Intelligent Transportation Systems. 2004:250-255.
[9] Massimo Bertozzi,Alberto Broggi,Alessandra Fascioli.Vision-based Intelligent Vehicles: State of the Art and Perspective[J]. Robotics and Autonomous System, 1998, 17(5):56-63.
[10] T. Ito.Universal traffic management system in Japan[J].Proceedings of the 1th WorldCongress on Applications of Transport Telematic and Intelligent Vehicle-High way Systems,1995:34-39.
[11]富立,范耀祖.车辆定位导航系统[M].北京:中国铁道出版社,2004:1-5.
[12] N. Deo,C. Pang. Shortest-path algorithms: taxonomy and annotation[J]. Networks, 1984,V14:275-32.
[13] Dijkstra. E. A note on two problems with graphs[J]. Mathematic.1959,V1:267-271.
[14] R. K. Ahuja, K. Mehlhorn, J.B.Orlin, et al. Faster Algorithms for the shortest path problem[J]. J.ACM.1990,V37:213-223.
[15] Dial,R.B.Algorithm 360:Shortest Path Forest with Topological Ordering[J]. Communications of the ACM.1969,V12:632-633.
[16] Cherkassky,B. V.,Goldberg,A. V.,Radzik,T. Shortest Paths Algorithms:Theory and Experimental Evaluation[J]. Computer Science Department,Stanford University Technical Report.1993:V93-1480.
[17] R. E. Bellman. On a routing problem[J]. Quart. Apple. Math. 1958,V16:87-90.
[18] L. R. Ford. Network Flow Theory[J]. The Rand Corporation:1956. p923.
[19] E. F. Moore. The Shortest Path through a Maze[J]. Proc. Int. On the Theory of Switching. 1957:285-292.
[20] U. P ape. Implementation and efficiency of Moore algorithms for the shortest route problem[J]. Math Prog. 1974.V7:212-222.
[21] Stefano Pallottino. Shortest-path methods : complexity, interrelations and new propositions[J]. Networks. 1984. V14:257-267.
[22] Fred Glover, Randy Glover, Darwin Kling man. Computational study of an improved shortest path algorithm[J]. Networks. 1984, V14:25-36.
[23] Hart. P.,N. Nilsson,B. Raphael. A formal basis for the heuristic determination of minimum cost paths[J]. IEEE Transportation System Science and Cybernetics. 1968, V4:100-107.
[24] Hart. P.,N. Nilsson,B. Raphael. Correction to“A formal basis for the heuristic determination of minimum cost paths”[J]. SIGART Newsletters. 1972, V37: 38-39.
[25] Riko Jacob,Madhav V. Marathe,Kai Nagel. A Computational Study of Routing Algorithms for Realistic Transportation Networks[J]. Los Alamos National Laboratory tech.Rep. 1998:LA-UR-98-2249.
[26] Fuliping , L.R.Rilett. Expected shortest paths in dynamic and stochastic trafficnetworks[J]. Transportation Research B, 1998, V32:499-516.
[27] Fuliping. An adaptive routing algorithm for in-vehicle route guidance systems with real-time information[J]. Transportation Research B, 2001, V35:749-765.
[28] Suvrajeet Sen,Rekha Pillai,Shirish Joshi,et al. A mean-variance model for route guidance in advanced traveler information systems[J]. Transportation Science. 2001, V35:37-49.
[29] Elise D.,M. Hooks,Hani S.,et al. Least expected time paths in stochastic,time-varying transportation networks[J]. Transportation Science. 2000 , V34 :198-215.
[30] Stuart E. Dreyfus. An appraisal of some shortest-path algorithms[J]. Operations Research,1969,V17:395-412.
[31] I. Chabini. Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal run time[J]. Transportation Research Record, 1998, V1645:170-175.
[32] D. E. Kaufman,R. L. Smith. Fastest paths in time-dependent network for intelligent-vehicle-highway systems application[J]. IVHS J., 1993, V1: 1-11.
[33] J. Shaprio,J.Waxman,D. Nir. Level graphs and approximate shortest path algorithms[J]. Networks. 1992, V22:691-717.
[34] J.Shaprio , J.Waxman. Rank constrained level graphs[J]. Congress Numevartium.1991, V84:9-20.
[35]韩超.基于时间序列分析的短时交通流量实时自适应预测[D].北京工业大学硕士学位文, 2004.5.
[36]贺国光,李宇,马寿峰.基于数学模型的短时交通流预测方法探讨[J].系统工程理论与实践,2000.12:51-56.
[37]王正武,黄中祥.短时交通流预测模型的分析与评价[M].系统工程, 2003.11.
[38]杨兆升.关于智能运输系统的关键理论——综合道路行程时间预测的研究[J].交通运输工程学报,2001.3:65-67.
[39]宫晓燕,汤淑明.基于非参数回归的短时交通流量预测与事件检测综合算法[J].中国公路学报,2003.1:82-86.
[40]朱中,杨兆升.实时交通流量人工神经网络预测模型[N].中国公路学报,1998.10.
[41] Robert Sedgewick. Algorithms in C++ , Part 5 : Graph Algorithms , Third Edition[M].Person Education,Inc.2002.
[42]许永.车载导航系统中最优路径规划方法研究[D].吉林:吉林大学通信工程学院,2007.
[43] M .L .G . Thoone,“CARIN,A Car Information and Navigation System,”[J]Philips Technical Review,Vol.43,No.11/12,Dec.1987:317-329.
[44] H .J .G .M .Benning,“Digital Maps Compact Disc,”[J]SAE Paper No.860125,Society of Automotive Engineers,1986.
[45] K. Ishilawa, M . Ogawa , T . Tsujibayashi and Y.Shoji ,“Digital Map on CD(Called CD Information),”[J]SAE Paper No.880221,Society of Automotive Engineers,1988.
[46] DAVID J. KRUGLINSKI. Visual C + +技术内幕(第四版) [M].北京:清华大学出版社, 1999.
[47]刘光,刘小东编著.地理信息系统二次开发实例教程--VC.NET和Map Objects实现(第1版)[M].清华大学出版社,2004.
[48]吕凤翥编著.C++语言基础教程[M].人民邮电出版社,2005.
[49]宋斌,陈玉亭等. VisualC++6.0教程[M].北京:希望电子出版社,1999.
[50]张剑平,任福继,叶荣华等.地理信息系统与Mapinfo应用[M].北京:科学出版社,1999.
[51]王晓武,陈宗敏,杜兴国等.MapBasic程序设计[M].北京:电子工业出版社,2000.
[52]姚娜编著.GIS、MapInfo与MapBasic学习教程[M].北京:北京大学出版社,2000.
[53]蓝运超,黄正东,谢熔.城市信息系统[M].武汉:武汉测绘科技大学出版社,2000.
[54]安鸿志编著.时间序列分析[M].华东师范大学出版社, 1992.3.
[55]贺国光,李宇,马寿峰.基于数学模型的短时交通流预测方法探讨[J].系统工程理论与实践, 2000.12:51-56.
[56]韩超.基于时间序列分析的短时交通流量实时自适应预测[D].北京工业大学硕士学位论文, 2004.5.
[57]郑为中,史其信.基于贝叶斯组合模型的短期交通量预测研究[J].中国公路学报,2005,1.
[58]朱中,杨兆升.基于卡尔曼滤波理论的实时行程时间预测模型[J].1999.9:75-77.
[59]张宇,姜双林.动态道路行程时间函数与BPR函数的比较研究[J].黑龙江交通科技, 2002.7.
[60]苏野.基于浮动车的动态交通信息提取与分析[D].吉林:吉林大学通信工程学院,2008.5.