期刊文献+

不完全信息下交通网络的关键路径问题 被引量:16

Most Shortest Vital-path Problem with Incomplete Information on Traffic Network
下载PDF
导出
摘要 在交通运输中,车辆总是选择最短路径行驶。然而因各种突发事件(交通事故、自然灾害等)造成道路中断的现象普遍存在,车辆在行驶的过程中并不具有道路中断的完全信息,只有行进到中断处时才获得道路中断的信息,此时原来的最短路径就很可能失去其最优性,从而增加交通运输的成本。为了解决这一问题,本文提出了不完全信息下交通网络的关键路径问题,给出了相应的求解算法,并分析了其时间复杂性,然后结合实际交通网络给出算例,最后指出这对提高交通运输的效率更具有实际意义。 Usually, the vehicles take the shortest path as their optimum way when dealing with transportation. However, due to the various outbursts of the traffic jams and natural disasters leading to blockages on the roads, the vehicles don't have the complete information about the blockages until they arrive at the blocked sites. On this occasion, the original optimum path will not be the optimum one any longer, leading to the increase in the transportation cost. In order to solve this problem caused by the happening of the unknown traffic jams, this paper puts forward th.e vital-path problem under incomplete information ,and gives the Algorithm to .solve it. Meanwhile,this paper analyzes the time complexity of the Algorithm. The problem this paper concerning is of great significance to deal with the practical transportation problems.
出处 《系统工程》 CSCD 北大核心 2006年第12期16-20,共5页 Systems Engineering
基金 国家杰出青年科学基金资助项目(70525004)
关键词 关键边 不完全信息 关键路径 算法 Most Vital Edge Incomplete Information Vital Path Algorithm
  • 相关文献

参考文献6

  • 1Corley H W,Sha D Y.Most vital link s and nodes in weighted networks[J].Operation Research Letters,1982,(1):157~161.
  • 2李引珍,郭耀煌.交通运输网络最短路径关键边问题研究[J].中国管理科学,2004,12(4):69-73. 被引量:28
  • 3Malik K,MittalA K,Gupta S K.The k most vital arcs in the shortest path problem[J].Operation Research Letters,1989,(8):223~227.
  • 4Nardelli E,Proietti G,Widmyer P.A faster computation of the most vital edge of a shortest path between two nodes[J].Info rmat ion Processing Letters,2001,79(2):81~85.
  • 5Nardelli E,Proietti G,Widmyer P.Finding the detour critical edge of a shortest path between nodes[J].Information Processing Letters,1998,67(1):51~54.
  • 6闫化海,徐寅峰.不完全信息下交通网络最短路径关键边问题[J].系统工程,2006,24(2):37-40. 被引量:17

二级参考文献13

  • 1李引珍,郭耀煌.交通运输网络最短路径关键边问题研究[J].中国管理科学,2004,12(4):69-73. 被引量:28
  • 2B.V.Cherkassky,Andrew V.Goldbergy,Tomasz Radzik.Shortest paths algorithms:Theory and experimental evaluation[J].Mathematical programming,1996,73:129-174.
  • 3H.W.Corley,D.Y.Sha.Most vital links and nodes in weighted networks[J].Oper Res Letters,1982,(1):157-160.
  • 4M.O.Ball,B.L.Golden,R.v.Vohra.Finding the most vital arcs inanetwork[J].Oper.Res.Lett.1988,(8):73-76.
  • 5E.Nardlli,G.Proietti,P.Widmayer.Finding the detour-critical edge of a shortest path between nodes[J].Infor Proc Letters,1998,67(1):51-54.
  • 6E.Nardelli,G.Proietti,P.Widmyer.A faster computation of the most vital edge of a shortest path between two nodes.Inform.Process.Lett.2001,79(2):81-85.
  • 7E.Nardelli,G.Projetti,P.Widmayer.Finding the most vital node of a shortest path[J].Theoretical computer science 2003,296:167-177.
  • 8Corley H W,Sha D Y.Most vital links and nodes in weighted networks[J].Operation Research Letters,1982,(1):157~161.
  • 9Malik K,Mittal A K,Gupta S K.The k most vital arcs in the shortest path problem[J].Operation Research Letters,1989,(8):223~227.
  • 10Nardelli E,Proietti G,Widmyer P.A faster computation of the most vital edge of a shortest path between two nodes[J].Information Processing Letters,2001,79(2):81~85.

共引文献37

同被引文献114

引证文献16

二级引证文献65

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部