摘要
随着经济的不断发展,人民的生活水平不断提高,城市交通拥堵现象也与日俱增。车辆导航系统是智能交通系统中的重要研究内容,是当前国际交通领域中的研究热点之一。它融合了交通、车辆、电子通信、网络等领域的相关技术,可以根据不同的出行需求,向出行者提供实时的路径诱导,减少车辆在路网中的停留时间,提高路网效率,在一定程度上缓解城市交通拥堵现象。
路径规划在车辆导航系统中处于核心地位,传统的最短路径问题都是在假设权值确定的交通网络基础上进行研究,而这些假设与现实的交通环境是不完全符合的。随机环境下的最短路径问题则可以更好的模拟现实交通网络参数的随机性,在此基础上进行路径规划,使研究具有一定的现实意义。
本文从现实交通网络中的随机变量(路段行程时间)入手,对该变量的特定时间段历史数据进行统计分析,得到该随机变量的概率分布函数。根据车辆导航中与行程时间相关的出行需求,构建车辆导航路径规划的随机期望值模型、随机机会约束规划模型、随机相关机会规划模型,为出行者提供期望时间最短的路径、含时间约束的最短路径以及在预定时间内到达目的地概率最大的路径。由于模型中含有随机变量,文章设计了基于随机模拟遗传算法求解相应的模型,利用随机模拟来计算个体的适应度值,考虑到实际要解决的问题,在问题编码中采用了基于优先权编码的方式,使编码生成的路径更有效,提高了初始种群的性能。
最后,文章以广州市天河区某交通路网为例,通过系统仿真,验证了基于随机模拟的遗传算法可以有效的求解随机环境下车辆导航的路径规划问题。
With the development of economy, people's living standard has improved, and urban traffic congestion is also growing. As the important research content in intelligent transportation system, vehicle navigation system becomes one of the hotspots in the field of the current international traffic. It incorporates the related technology in the field of traffic, vehicles, electronic communication, network and so on. According to different travel demands, it can provide real-time route guidance for the drivers to reduce vehicle's retention time in the traffic network, improve the efficiency of road network, and, to some extent, relieve urban traffic congestion.
Path planning is in the key position in vehicle navigation system, and the traditional research on the shortest path problem always assume that the weights on the transportation network is certain, but these assumptions is not fully comply with the reality of the traffic environment. As the shortest path problem in the random environment can simulate the randomness of the real traffic network parameters better, the research has more practical significance than the traditional one.
Starting with the random variables (the travel time of a section) in the reality network traffic, this paper statistics and analysis the history data of the variables in specific time, then gets the probability distribution function of the random variable. According to the travel demand which is related with travel time in vehicle navigation, Stochastic expected value model, stochastic chance-constrained programming model and stochastic dependent-chance programming model are constructed for path planning. These models can provide the path of the shortest expected time, the shortest distance path with time constraint and the largest probability path witch arrived destination in the scheduled time for travelers. Because the model with random variables, this article designs genetic algorithms based on stochastic simulation for the corresponding model, using stochastic simulation to calculate the individual fitness value, considering actual of problem to solve, using genetic algorithms based on priority coding to make the generated code more effective, and improve the performance of the initial population.
Finally, a transportation network in Tianhe district of Guangzhou City is taken as an example, through system simulation, the experiment proves the genetic algorithm based on stochastic simulation can solve the vehicle navigation path planning problem in random environment.
引文
[1]中国汽车保有量突破一亿占全球十分之一[EB/OL].http://auto.people.com.cn/GB/16572085.html.
[2]道路发展低于经济增速我国每天300丧生车祸[EB/OL].http://www.chinahighway.com/news/2004/66958.php.
[3]张扬.不确定环境下城市交通中车辆路径选择研究[D].成都:西南交通大学,2006.
[4]环保部:机动车标志管理10月1日实施[EB/OL].http://money.163.com/09/0813/16/5GK32N8M00253CAA.html.
[5]中国15座城市因交通拥堵每天损失近10亿元[EB/OL].http://www.huaxia.com/zt/tbgz/10-078/2231176.html.
[6]赵丽红.基于神经模糊推理的交通拥挤实时评价方法研究[D].广州:广东工业大学,2009.
[7]金会庆,戴平,张树林.智能运输系统ITS研究现状及展望[J].人类工效学,2001,7(3):39-41.
[8]车辆导航系统[EB/OL].http://news.c-ps.net/2010/12/55733.html.
[9]E. W. Dijkstra. A note on two problems in connection with graphs[J]. Numerische Mathematik,1959,1:269-271.
[10]L. Ford and D. Fulkerson. Flows in Networks[M].Princeton, NJ:Princetor University Press,1962.
[11]李春葆.数据结构教程[M].北京:清华大学出版社,2007.
[12]P. E. Hart, N. J. Nilsson, B. Raphael. A formal basis for the heuristic determinatior of minimum cost paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968,4:100-107.
[13]N. J. Nilsson. Artificial intelligence:a new synthesis[M]. Beijing:China Machine Press,1999.
[14]E. V. Denardo. Dynamic programming:models and applications[M]. New York: Prentice Hall,1982.
[15]B. Cherkassky, A. Goldberg,T. Radzik. Shortest paths algorithms:Theory and experimental evaluation[J]. Mathematical Programming,1996,73:129-174.
[16]L. Cooke and E. Halsey. The shortest route through a network with time-dependent internodal transit times[J], Journal of Mathematical Analysis and Applications, 1966,14:492-498.
[17]J. Murchland. The effect of increasing or decreasing the length of a single arc on all shortest distances in a graph[R]. London:London Business School,1967.
[18]P. Loubal. A network evaluation procedure[J]. Highway Research Record,1967, 1:96-109.
[19]S. E. Dreyfus. An Appraisal of Some Shortest-Path Algorithms[J]. Operations Research,1969,17:395-412.
[20]Ahuja. Network Flows:Theory, Algorithms and Applications[R]. Englewood Cliffs, NJ:Prentice Hall,1993.
[21]A. Orda and R. Rom. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length[J]. Journal of the ACM,1990,37:607-625.
[22]A. K. Ziliaskopoulos and H. S. Mahmassani. Time dependent, shortest-path algorithm for real-time intelligent vehicle highway system applications[J].Transportation Research Record,1993,1:94-100.
[23]I. Chabini. Discrete dynamic shortest path problems in transportation applications: complexity and algorithms with optimal ms time[J]. Transportation Research Records,1998,1:170-175.
[24]Dreyfus S E. An appraisal of some shortest path algorithms[J]. Operations Research,1969,17(3):395-412.
[25]Kaufman D E, Smith R L. Fastest path in time-dependent networks for intelligent vehicle-highway systems application[J]. IVHS Journal,1993,11(1):1-11.
[26]Misra S, Oommen. Dynamic algorithms for the shortest path routing problem: Learning automata-based solutions[J]. IEEE Transaction on Systems, Man, and Cybernetics,2005,35(6):1179-1192.
[27]Alberto V. Time Dependent Vehicle Routing Problem with an Multi Ant Colony System[J]. IDSIA,2008,11(2):60-68.
[28]Jung Soojung. A genetic algorithm for vehicle routing problem with time dependent travel times[D]. Doctor Degree Dissertation,2000.
[29]Kiseok Sung. Shortest paths in a network with time-dependent flow speeds[J]. European Journal of Operational Research,2000,121:32-39.
[30]Nagurney A. Network economics:a variational inequality approach[M]. Dordrecht, The Netherlands:Kluwer Academic Publishers,1993.
[31]Suvrajeet Sen, Rekha Pillai. A mean-variance model for route guidance in advanced traveler information systems[J]. Transportation Science,2001,35:37-49.
[32]D. Elise, M. Hooks, S. Hani, et al. Least expected time paths in stochastic, time-varying transportation networks[J]. Transportation Science,2000,34: 198-215.
[33]林澜,闫春钢,蒋昌俊,周向东.动态网络最短问题的复杂性与近似算法[J].·计算机学报,2007,30(4):608—614.
[34]谭国真,高文.时间依赖的网络中最小时间路径算法[J].计算机学报,2002,25(2) : 165—172.
[35]魏航,李军,蒲云.时变条件下有害物品运输的路径问题研究[J]. 系统工程理论与实践,2006,26(10):107—112.
[36]李引珍.不确定环境下变通运输网络路径求解方法及应用研究[D].成都:西南交通大学,2005.
[37]B. P. Mirchandani. shortest distance and reliability of probabilistic Networks[J]. Computer and Operations Research,1976,3:347-676.
[38]C. E. Siga, A. B. Pritsker,J.J. Solberg. The stochastic shortest route problem[J]. Oper. Reas,1980,28(5):1122-1129. [39] R. Hassin, E. Zemel. On shortest paths in graphs with random weights[J]. Math Of Oper Reas,1985,10:557-564. [40] A. B. Wijeratne, M. A. Turnquist, P B. Mirchandani. Multi objective routing of hazardous materials in stochastic networks[J]. European Journal of Operational Research,1993,65:33-43. [41| G H. Polychronopoulos, Stochastic and dynamic shortest distance problems[D], Cambridge:MIT,1992.
[42]M. I. Henig. Risk criteria in a stochastic knapsack problem[J]. Oper. Reas,1990, 38(5):820-825.
[43]A. P. Eiger, P. B. Mirchandani and H. Soroush. Path preferences and optimal paths in probabilistic networks[J]. Transportation science,1985,19:75-84.
[44]谢延红.不确定网络中的最短路径问题[J].德州学院学报,2011,27(4):74—78.
[45]R. W. Hall. The fastest path through a network with random time-dependent travel times[J]. Transportation Science,1986,20:182-188.
[46]L. Fu and L. R. Rilett. Shortest Path Problems In Traffic Networks With Dynamic and Stochastic Link Travel Times[J]. Transportation Research Part B: Methodological,1998,32:499-515.
[47]H. N. Psaraftis and J. N. Tsitsiklis. Dynamic Shortest Paths in Acyclic Networks with Markovian Are Cost[J]. Operations Research,1993,41:91-101.
[48]A. Azaron and F.Kianfar. Dynamic shortest path in stochastic dynamic networks: Ship routing problem[J]. European Journal of Operational Research,2003,144: 138-156.
[49]E. D. Moller Hooks, H. S. Mahmassani. Least possible time paths in stochastic time-varying networks[J]. Comp.& Oper. Reas,1998,25(12):1107-1125.
[50]D. Dubois, H. Prade. Fuzzy set and systems:Theory and applications[M]. New York:Academic Press,1980.
[51]J. S. Yao, F. T.Lin. Fuzzy Shortest-Path Network Problems With Uncertain Edge Weights[J]. Journal of Information Science and Engineering,2003,19:329-351.
[52]K. C. Lin, M. S. Chern. The fuzzy shortest path problem and its most vital arcs[J]. Fuzzy Sets and Systems,1993,58:343-353.
[53]N. Funikawa. A parametric total order on fuzzy numbers and a fuzzy shortest routs problem[J]. Optimization,1994,30:367-377.
[54]S. Okada, TI Soper. A shortest path problem on a network with fuzzy arc lengths[J]. Fuzzy Sets and Systems,2000,109:129-140.
[55]车辆导航系统介绍[EB/OL].http://www.eefocus.com/article/08-05/43260s.html.
[56]王赛政.动态交通条件下车辆导航系统的最优路径规划方法研究[D].长沙:长沙理工大学,2010.
[57]赵磊.动态交通条件下车辆导航的路径寻优分析[D].西安:长安大学,2010.
[58]常青,杨东凯等.车辆导航定位方法及应用[M].北京:机械工业出版社,2005.
[59]王永庆.人工智能原理与方法[M].两安:两安交通大学出版社,2001.
[60]安惜平.城市交通路径诱导算法研究[D].石家庄:河北科技大学,2008.
[61]谢秉磊.随机车辆路径问题研究[D].成都,西南交通大学,2003.
[62]周大勇.动态交通条件下车辆导航的路径寻优分析[D].武汉:武汉理工大学,2007.
[63]俞峰.复杂动态随机网络最短路径问题研究[D].浙江:浙江大学,2009.
[64]王芬.Dijkstra最短路径优化算法在汽车导航中的研究及实现[D].上海:上海师范大学,2006.
[65]肖宁.微粒群算法在随机规划问题求解中的应用研究[D].太原:太原科技大学,2008.
[66]熊志华,邵春福.随机需求条件下道路网行程质量评估-行程时间可靠性[J].交通运输工程与信息学报,2006,4(2):40—44.
[67]余艳春.基于统计的路网行程时间可靠性研究[D].北京:北京交通大学,2006.
[68]陈琨.基于移动源数据的城市路网行程时间可靠性评价模型与算法[D].北京:北京交通大学,2008.
[69]Turner S. Guidelines for Developing ITS Data Archiving Systems[R]. Texas:The Texas Department of Transportation in cooperation with The U. S. Department of Transportation Federal Highway Administration,2001.
[70]耿彦斌.城市道路交通流数据质量控制的模型及对策研究[D].北京:北京交通大学,2006.
[71]胡俊.高速公路收费系统数据处理与分析[D].北京:东南大学,2007.
[72]刘宝碇,赵瑞清,王纲.不确定规划及应用[M].北京:清华大学出版社,2003.
[73]张侃.基于优先权编码的最短路径求解[J].商丘师范学院学报,2007,23(9):89-92.
[74]张书源,郭聪.基于遗传算法的最短路径问题及其MATLAB实现[J].交通世界(运输车辆),2009,6(12):104-105.