随机路网的最短路径问题研究.pdf

24 9 Vol24 o9 2007 9 Journal of Highway andTransportation Research and Development Sep 2007 :(2007) 范巍巍, 程 琳 ( , 210096) : 主要研究随机路网中的最短路径问题, 首先给出随机路网的定义, 建立了随机路网的模型, 假定路段的费用是 足正态分布的随机变量, 并给出从历史数据中得到此变量的均值和方差的统计学方法; 然后得出路径出行费用的均 值及方差的递推公式, 将费用的方差当作一 个限制条件, 从而在 Dijkstra 算法的基础上, 提出了带单一限制条件的最 短路径算法, 同时给出了算法的具体流程; 最后用一 个简单例子演示了算法的具体步骤, 并在南京路网中验证了此算 法的实用性 : 交通工程; 最短路径问题; 限制条件; 随机路网; 期望; 方差 : U491 : A The St udy on Shortest Path Problems in Stochastic Traffic Network FA Weiwei; CHE G Lin ( School of Transportation, Southeast University, Jiangsu anjing 210096 China) Abstract: The shortest path problem inthe stochastic traffic network is studiedFirst, the definition of stochastic traffic network is given andthe stochastic network model is builtAssuming the link cost is the normally distributed random variable, a statistic method is proposed to get this random variablefrom historical dataThen theformulasto acquire the mean and variance of path cost is proposedAn algorithm of shortest path based on Dijkstra with single restriction ( variance of link cost) is proposedFinally, an example is given to show the algorithm Key words: traffic engineering; shortest path problem; restriction; stochastic traffic network; mean; variance , ( Shortest Path , Problem, SPP) , , , , , , , , , , [ 1] , Dijkstra , O ( n2 )