基于遗传算法的路径诱导系统的研究与设计
|
摘要
智能交通系统能使交通基础设施发挥出最大的效能,提高服务质量,使社会能够高效地使用交通设施和资源,从而获得巨大的社会经济效益。路径诱导是用于提高道路的通行能力和车辆的运输效率,减少交通拥挤和交通事故的有效方法,它是智能交通领域的核心内容之一,近年来已经成为国际学术界研究的热点与难点课题之一。本论文对路径诱导方法进行了深入的研究,提出了基于遗传算法的智能交通路径诱导方法。以仿制的某城市的有向路径的交通路网为研究对象,进行了理论分析和仿真试验研究,证明了该方法是有效的。
路径诱导问题是一个典型的NP难题。针对路径诱导问题进行深入的分析,研究路径诱导需要遵循的原则以及所涉及的各种因素、问题,分析了路径诱导模型和相关实现技术。针对最优行车选择路线模型中,使用一般算法搜索效率低下的问题,采用在处理高度复杂的非线性优化问题上具有极大优越性的遗传算法,并根据路径诱导本身的特点,对遗传算法设计进行了优化。设计了改进的初始种群产生方法,使得迭代过程中能够有效的避免环路或者断路的产生;采用二种适应度函数能够在遗传算法初期排除不合理路径。设计了关键的优化遗传算子,完成了路径诱导系统。
基于该算法的路径系统已在Windows XP操作系统平台上开发实现,具体使用的开发工具是Visual Studio.Net和ESRI公司的MapObjects。同时,为了进一步满足实用要求,还对路径诱导系统进行了完善,增加了鹰眼,距离测算等功能,并且全部过程均利用与用户人机交互完成。实践证明该系统具有较好的适应性和实用性。
Intelligent Transport System (ITS) can make the traffic facilities to work at the most efficient way, raise the service quality. So it really helps the whole society gain huge economic benefit. The Route Guidance System (RGS) is an effective way to raise the quality of transport service, enhance the driving efficiency of the vehicle, decrease the pressure of the crowed traffic and reduce the traffic accidences. It is an important part of the ITS and nowadays it has become one of the difficulties and hotspots in the field of international science. Moreover, a new route guidance method, based on the genetic algorithm is put forward in this paper. To probe into the technology of the RGS, experiments combining with the analysis of the results have been carried on, which consider the traffic net work of a city. At last it has been proved that the method is effective.
Vehicle Route Guidance is a typical NP problem. We analyze the Route Guidance Problem, research about the principles that it must obey and all the factors which influence it. We also analyze the Route Guidance models and the technologies to realize the system. To improve the weakness that search efficiency is at a low level by using other algorithms, we suggest use the Genetic Algorithm (GA) which has great advantages in solving complex nonlinearity optimization problem. According to the features of Route Guidance itself, we improved the way to create initial population in order to prevent the appearances of the ring circuits and the open circuits. We also designed two kinds of fitness functions to eliminate unreasonable circuits. And we have designed the key GA operators and finished the Route Guidance System.
Route Guidance System based on GA has been developed. The development tools are Visual Studio.Net and ESRI’s MapObjects. To feed the needs of practical using, we improved the system by realizing some other functions like eagle eye, distance measurement and so on. The practice proved this system has the good compatibility and the usability.
路径诱导问题是一个典型的NP难题。针对路径诱导问题进行深入的分析,研究路径诱导需要遵循的原则以及所涉及的各种因素、问题,分析了路径诱导模型和相关实现技术。针对最优行车选择路线模型中,使用一般算法搜索效率低下的问题,采用在处理高度复杂的非线性优化问题上具有极大优越性的遗传算法,并根据路径诱导本身的特点,对遗传算法设计进行了优化。设计了改进的初始种群产生方法,使得迭代过程中能够有效的避免环路或者断路的产生;采用二种适应度函数能够在遗传算法初期排除不合理路径。设计了关键的优化遗传算子,完成了路径诱导系统。
基于该算法的路径系统已在Windows XP操作系统平台上开发实现,具体使用的开发工具是Visual Studio.Net和ESRI公司的MapObjects。同时,为了进一步满足实用要求,还对路径诱导系统进行了完善,增加了鹰眼,距离测算等功能,并且全部过程均利用与用户人机交互完成。实践证明该系统具有较好的适应性和实用性。
Intelligent Transport System (ITS) can make the traffic facilities to work at the most efficient way, raise the service quality. So it really helps the whole society gain huge economic benefit. The Route Guidance System (RGS) is an effective way to raise the quality of transport service, enhance the driving efficiency of the vehicle, decrease the pressure of the crowed traffic and reduce the traffic accidences. It is an important part of the ITS and nowadays it has become one of the difficulties and hotspots in the field of international science. Moreover, a new route guidance method, based on the genetic algorithm is put forward in this paper. To probe into the technology of the RGS, experiments combining with the analysis of the results have been carried on, which consider the traffic net work of a city. At last it has been proved that the method is effective.
Vehicle Route Guidance is a typical NP problem. We analyze the Route Guidance Problem, research about the principles that it must obey and all the factors which influence it. We also analyze the Route Guidance models and the technologies to realize the system. To improve the weakness that search efficiency is at a low level by using other algorithms, we suggest use the Genetic Algorithm (GA) which has great advantages in solving complex nonlinearity optimization problem. According to the features of Route Guidance itself, we improved the way to create initial population in order to prevent the appearances of the ring circuits and the open circuits. We also designed two kinds of fitness functions to eliminate unreasonable circuits. And we have designed the key GA operators and finished the Route Guidance System.
Route Guidance System based on GA has been developed. The development tools are Visual Studio.Net and ESRI’s MapObjects. To feed the needs of practical using, we improved the system by realizing some other functions like eagle eye, distance measurement and so on. The practice proved this system has the good compatibility and the usability.
引文
[1]陈任标,苏奎,杨浩.ITS是交通运输可持续发展的关键.公路,1992(2):25-26.
[2]杨兆升,初连禹.动态路径诱导系统的研究进展.公路交通科技,2000.
[3]杨兆升.城市交通流诱导系统理论与模型.北京:人民交通出版社,2000.
[4] Mitusyuki Okamoto,Tetuso Yamamoto,Kentaro Sakamoto,Masakuni Tuge,Evolution of the VICS,Proceeding of the World Congress on ITS,Korea,1998.
[5] Nobuo Nishi,Etsuji Kurda,Akio Uekawa.Evaluation of Effectiveness of CDRGS, Proceeding of the World Congress on ITS,Berlin,1997.
[6]陈洪亮,张保忠.交通路径诱导系统及其发展跟踪,中国公路学报,1996(2):84-89.
[7] Homepage of ADVANCE project.http://ais.its-program.anl.gov/.
[8] Dial R,Glover F,Kamey D,A computational analysis of altemative algorithms and labeling techniques for finding shortest path trees [J].Networks, 1979, 9(9): 214-248.
[9] CHABINI I . Discrete dynamic shortest path problems in transportation applications:Complexity and algorithms with optimal run time[J].Transportation Research Records,l998.1645:170-175.
[10] FU I P,L RII ETT R.Expected shortest paths in dynamic and stochastic traffic networks [J].Transp0rtati0n Research B,1998.32(7):499-516.
[11] DEON,PANG Y.Shortest path algorithms:taxonomy and annotation [J].Networks, 1981.14:175-323.
[12] HALI R.The fastest path through a network with random time-dependent travel time[J].Transportation Science.1986,20(3):182-188.
[13] JIAMTN,TONGCO.A dynamic route guidance system based on historical and current traffic pattern[A].Proceedings of 1992 IEEE Intelligent Vehicles Symposium.Detroit:Sage Publications.1992:365-369.
[14] SUNGSK,JONGHI .A study on design of dynamic route guidance system using forecasted travel time based on GPS data and modified shortest path algorithm algorithm[A].Proceedings of 1 999 IEEE/IEEJ/JSAI International Conferenceon Intelligent Transportation Systems[C].Tokyo:IEEE.1999:44-48.
[15] GAETANI F,MINCIDARDI R.Dynamic models and optimal control methods for route guidance in urban raffic networks[A]. Proceedings of IEEE 5th international conference on intelligent transportation systems[C]. Singapore: IEEE.2002: 154- 459.
[16] KOBAYASHIMA,SHIMIZU H.YOEZAWA Y.Dynamic route search algorithms of a traffic network[A].Proceedings of the 36 SICE Annual Conference International Session Papers[c].Tokushima:IEEE,1997:1211-1216.
[17]苏永云,晏克非,杨晓光等.VNS中动态行程时间与多端动态最短路算法[J].中国公路学报,2001,14[1]:97-103
[18] FULP.An adaptive routing algorithm for in vehicle route guidance systems with real time information[J].Transportation Research B,2001,35(8):749-765.
[19] SENS,PILLAIR,JOSHI S,et a1.A mean variance model for route guidance in advanced traveler information systems[J].Transportation Science,2001, 35(1): 37 -49.
[20] ZILIASKOPOIULOS A. A Massively parallel time dependent least-time-path algorithm for intelligent transportation systems applications[J] Computer-Aided Civil and Infrastructure Engineering, 2001,16:337-346.
[21] WEN Huimin,YANG Zhaosheng.Study on the shortest path algorithm based on fluid neural network of in vehicle traffic flow guidance system.Proceedings of the IEEE International Conference on Vehicle Electronics[c].Changchung:IEEE,1 999, 1: 110 -11 3.
[22] HE Guoguang,MA Shoufeng AI based dynamic route guidance strategy and its simulation[A].Proceedings of IEEE Intelligent Transportation Systems Conference [C] Oakland:IEEE,2001:28-32.
[23] Jeff A. Bimles A Gentle Tutorial of the EM Algorithm and its Application to Paramter Estimation for Gaussian Mixture and Hidder Markov Models Computer Science Apirl 1998.
[24] Tom M Mitchell.机器学习[M].北京:机械工业出版社,2003.263-276
[25] Alan Dix(蔡利栋方思行周继鹏张庆丰译).人机交互[M],电子工业出版社,2006
[26]贾长沙.城市路网路线诱导系统的交通流优化策略安防科技,2003(2):79-82
[27]景玲,黄席樾,潘娅.基于遗传算法的动态路径诱导,重庆大学学报,2002, 25(4):68-71.
[28]冯春,李柏林.解TSP的有序遗传算法[J].西南交通大学学报, 1997,32(5):528 -532.
[29]杨昊,钟雁,钱大琳.城市交通流路段行程时间预测模型[J].北
[30]方交通大学学报,2001,25(2):65-69.
[31]吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导系统中的应用,计算机应用与研究,2006,5:177-179.
[32] A. Hertz. Findung a feasible course schedule using tabu search. Discrete Applied Mathematices, 35(3):p255-270,1992.
[33] Shi L, Olafsson S, Chen Q. A new hybrid optimization algorithm. Computers and Industrial Engineering, 1999, 36: 409-426.
[34] Hansen P,Mladenovic N.Variable neighborhood search:principles and applications. European Journal of Operational Research, 2001, 130: 449-467.
[35] Charon I, Hudry O. The noising method: a new method for combinatorial optimization. Operations Research Letters, 1993, 14: 133-137.
[36]邹亮徐建闽基于遗传算法的动态网络中的最短路径问题算法,计算机应用,2005,(4):76-80.
[37]陈曦,蔡辉,柳林基于遗传算法的路径安排,长沙交通学院学报2005,21(4): 76-80
[38]向怀绅,刘小明车辆导航系统的研究开发现状与趋势,汽车工程,2001, 23(5):296-299, 318
[39]闻新,张伟,任传祥.卫星导航系统在智能交通系统中的应用现状分析,中国航天,2003, (2): 7-10
[40]张志青,张鹏.智能交通系统研究综述东北林业大学学报,1999, 27(2): 57-59
[41]孙晋文,鄂卓茂.智能运输系统的现状与发展中国农业大学学报,2000, 5(4):113-116
[42]丁艳.我国智能交通系统应用现状.智能建筑与城市信息,2003, (11): 7-12
[43]向怀绅,刘小明二车辆导航系统的研究开发现状与趋势.汽车工程,2001, 23(5):296-299, 318
[44]苏永云,晏克非,黄翔,朱培康车辆导航系统的动态最优路径搜索方法研究.系统工程,2000, 18(4): 32-37
[45]王元庆,周伟,吕连恩.道路阻抗函数理论与应用研究.公路交通科技,2004,21(9):82-85
[46]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究.系统工程,2001,19(2): 48-53
[47]张晓绩,方浩,戴冠中.遗传算法的编码机制研究.信息与控制,1997, 26(2):134-139
[48]曹鲁寅,罗斌.用遗传算法求解最短路径问题.合肥工业大学学报,1996, 19(3):112-116
[49]廖美英,郭荷清,张勇军.一种整数编码的改进遗传算法.计算机工程与应用,2003, (1): 103-105, 120
[50]李庆中,顾伟康,叶秀清.基于遗传算法的移动机器人动态避障路径规划方法[J].模式识别与人工智能.2002,15(2):160-165.
[51]冯文镛,杨灿军,陈鹰.ACR原型系统的全局路径规划遗传算法的研究[J].控制理论与应用,2002,19(4):282～286
[52]孙树栋,曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报,1998,16(2):79-83
[53] Gen M,Cheng R . Genetic algorithm and Engineering design[M] . New York:Wiley,1977.134～140
[54]仲欣,吕恬生.基于遗传算法的汽车式移动机器人路径规划方法[J].上海交通大学学报,1999.
[55]玄光男(日),程润伟.遗传算法与工程设计[M].北京:科学出版社,2O00.
[56]吕永刚,谢存禧.移动机器人的导航与路径规划的研究[J].机电工程技术,2004,33(1):19-21.
[57] Bauer,R.Genetic Algorithms and Investment Strategies[J].John Wiley&Sons, New York,1994:102-105.
[58] Allbrecht
[2]杨兆升,初连禹.动态路径诱导系统的研究进展.公路交通科技,2000.
[3]杨兆升.城市交通流诱导系统理论与模型.北京:人民交通出版社,2000.
[4] Mitusyuki Okamoto,Tetuso Yamamoto,Kentaro Sakamoto,Masakuni Tuge,Evolution of the VICS,Proceeding of the World Congress on ITS,Korea,1998.
[5] Nobuo Nishi,Etsuji Kurda,Akio Uekawa.Evaluation of Effectiveness of CDRGS, Proceeding of the World Congress on ITS,Berlin,1997.
[6]陈洪亮,张保忠.交通路径诱导系统及其发展跟踪,中国公路学报,1996(2):84-89.
[7] Homepage of ADVANCE project.http://ais.its-program.anl.gov/.
[8] Dial R,Glover F,Kamey D,A computational analysis of altemative algorithms and labeling techniques for finding shortest path trees [J].Networks, 1979, 9(9): 214-248.
[9] CHABINI I . Discrete dynamic shortest path problems in transportation applications:Complexity and algorithms with optimal run time[J].Transportation Research Records,l998.1645:170-175.
[10] FU I P,L RII ETT R.Expected shortest paths in dynamic and stochastic traffic networks [J].Transp0rtati0n Research B,1998.32(7):499-516.
[11] DEON,PANG Y.Shortest path algorithms:taxonomy and annotation [J].Networks, 1981.14:175-323.
[12] HALI R.The fastest path through a network with random time-dependent travel time[J].Transportation Science.1986,20(3):182-188.
[13] JIAMTN,TONGCO.A dynamic route guidance system based on historical and current traffic pattern[A].Proceedings of 1992 IEEE Intelligent Vehicles Symposium.Detroit:Sage Publications.1992:365-369.
[14] SUNGSK,JONGHI .A study on design of dynamic route guidance system using forecasted travel time based on GPS data and modified shortest path algorithm algorithm[A].Proceedings of 1 999 IEEE/IEEJ/JSAI International Conferenceon Intelligent Transportation Systems[C].Tokyo:IEEE.1999:44-48.
[15] GAETANI F,MINCIDARDI R.Dynamic models and optimal control methods for route guidance in urban raffic networks[A]. Proceedings of IEEE 5th international conference on intelligent transportation systems[C]. Singapore: IEEE.2002: 154- 459.
[16] KOBAYASHIMA,SHIMIZU H.YOEZAWA Y.Dynamic route search algorithms of a traffic network[A].Proceedings of the 36 SICE Annual Conference International Session Papers[c].Tokushima:IEEE,1997:1211-1216.
[17]苏永云,晏克非,杨晓光等.VNS中动态行程时间与多端动态最短路算法[J].中国公路学报,2001,14[1]:97-103
[18] FULP.An adaptive routing algorithm for in vehicle route guidance systems with real time information[J].Transportation Research B,2001,35(8):749-765.
[19] SENS,PILLAIR,JOSHI S,et a1.A mean variance model for route guidance in advanced traveler information systems[J].Transportation Science,2001, 35(1): 37 -49.
[20] ZILIASKOPOIULOS A. A Massively parallel time dependent least-time-path algorithm for intelligent transportation systems applications[J] Computer-Aided Civil and Infrastructure Engineering, 2001,16:337-346.
[21] WEN Huimin,YANG Zhaosheng.Study on the shortest path algorithm based on fluid neural network of in vehicle traffic flow guidance system.Proceedings of the IEEE International Conference on Vehicle Electronics[c].Changchung:IEEE,1 999, 1: 110 -11 3.
[22] HE Guoguang,MA Shoufeng AI based dynamic route guidance strategy and its simulation[A].Proceedings of IEEE Intelligent Transportation Systems Conference [C] Oakland:IEEE,2001:28-32.
[23] Jeff A. Bimles A Gentle Tutorial of the EM Algorithm and its Application to Paramter Estimation for Gaussian Mixture and Hidder Markov Models Computer Science Apirl 1998.
[24] Tom M Mitchell.机器学习[M].北京:机械工业出版社,2003.263-276
[25] Alan Dix(蔡利栋方思行周继鹏张庆丰译).人机交互[M],电子工业出版社,2006
[26]贾长沙.城市路网路线诱导系统的交通流优化策略安防科技,2003(2):79-82
[27]景玲,黄席樾,潘娅.基于遗传算法的动态路径诱导,重庆大学学报,2002, 25(4):68-71.
[28]冯春,李柏林.解TSP的有序遗传算法[J].西南交通大学学报, 1997,32(5):528 -532.
[29]杨昊,钟雁,钱大琳.城市交通流路段行程时间预测模型[J].北
[30]方交通大学学报,2001,25(2):65-69.
[31]吴成东,杨丽英,许可.神经网络和遗传算法在动态路径诱导系统中的应用,计算机应用与研究,2006,5:177-179.
[32] A. Hertz. Findung a feasible course schedule using tabu search. Discrete Applied Mathematices, 35(3):p255-270,1992.
[33] Shi L, Olafsson S, Chen Q. A new hybrid optimization algorithm. Computers and Industrial Engineering, 1999, 36: 409-426.
[34] Hansen P,Mladenovic N.Variable neighborhood search:principles and applications. European Journal of Operational Research, 2001, 130: 449-467.
[35] Charon I, Hudry O. The noising method: a new method for combinatorial optimization. Operations Research Letters, 1993, 14: 133-137.
[36]邹亮徐建闽基于遗传算法的动态网络中的最短路径问题算法,计算机应用,2005,(4):76-80.
[37]陈曦,蔡辉,柳林基于遗传算法的路径安排,长沙交通学院学报2005,21(4): 76-80
[38]向怀绅,刘小明车辆导航系统的研究开发现状与趋势,汽车工程,2001, 23(5):296-299, 318
[39]闻新,张伟,任传祥.卫星导航系统在智能交通系统中的应用现状分析,中国航天,2003, (2): 7-10
[40]张志青,张鹏.智能交通系统研究综述东北林业大学学报,1999, 27(2): 57-59
[41]孙晋文,鄂卓茂.智能运输系统的现状与发展中国农业大学学报,2000, 5(4):113-116
[42]丁艳.我国智能交通系统应用现状.智能建筑与城市信息,2003, (11): 7-12
[43]向怀绅,刘小明二车辆导航系统的研究开发现状与趋势.汽车工程,2001, 23(5):296-299, 318
[44]苏永云,晏克非,黄翔,朱培康车辆导航系统的动态最优路径搜索方法研究.系统工程,2000, 18(4): 32-37
[45]王元庆,周伟,吕连恩.道路阻抗函数理论与应用研究.公路交通科技,2004,21(9):82-85
[46]张可,刘小明,王笑京.车辆自动导航的路线优化系统研究.系统工程,2001,19(2): 48-53
[47]张晓绩,方浩,戴冠中.遗传算法的编码机制研究.信息与控制,1997, 26(2):134-139
[48]曹鲁寅,罗斌.用遗传算法求解最短路径问题.合肥工业大学学报,1996, 19(3):112-116
[49]廖美英,郭荷清,张勇军.一种整数编码的改进遗传算法.计算机工程与应用,2003, (1): 103-105, 120
[50]李庆中,顾伟康,叶秀清.基于遗传算法的移动机器人动态避障路径规划方法[J].模式识别与人工智能.2002,15(2):160-165.
[51]冯文镛,杨灿军,陈鹰.ACR原型系统的全局路径规划遗传算法的研究[J].控制理论与应用,2002,19(4):282～286
[52]孙树栋,曲彦宾.遗传算法在机器人路径规划中的应用研究[J].西北工业大学学报,1998,16(2):79-83
[53] Gen M,Cheng R . Genetic algorithm and Engineering design[M] . New York:Wiley,1977.134～140
[54]仲欣,吕恬生.基于遗传算法的汽车式移动机器人路径规划方法[J].上海交通大学学报,1999.
[55]玄光男(日),程润伟.遗传算法与工程设计[M].北京:科学出版社,2O00.
[56]吕永刚,谢存禧.移动机器人的导航与路径规划的研究[J].机电工程技术,2004,33(1):19-21.
[57] Bauer,R.Genetic Algorithms and Investment Strategies[J].John Wiley&Sons, New York,1994:102-105.
[58] Allbrecht