期刊文献+

Optimal paths planning in dynamic transportation networks with random link travel times 被引量:3

Optimal paths planning in dynamic transportation networks with random link travel times
下载PDF
导出
摘要 A theoretical study was conducted on finding optimal paths in transportation networks where link travel times were stochastic and time-dependent(STD). The methodology of relative robust optimization was applied as measures for comparing time-varying, random path travel times for a priori optimization. In accordance with the situation in real world, a stochastic consistent condition was provided for the STD networks and under this condition, a mathematical proof was given that the STD robust optimal path problem can be simplified into a minimum problem in specific time-dependent networks. A label setting algorithm was designed and tested to find travelers' robust optimal path in a sampled STD network with computation complexity of O(n2+n·m). The validity of the robust approach and the designed algorithm were confirmed in the computational tests. Compared with conventional probability approach, the proposed approach is simple and efficient, and also has a good application prospect in navigation system. A theoretical study was conducted on finding optimal paths in transportation networks where link travel times were stochastic and time-dependent(STD). The methodology of relative robust optimization was applied as measures for comparing time-varying, random path travel times for a priori optimization. In accordance with the situation in real world, a stochastic consistent condition was provided for the STD networks and under this condition, a mathematical proof was given that the STD robust optimal path problem can be simplified into a minimum problem in specific time-dependent networks. A label setting algorithm was designed and tested to find travelers' robust optimal path in a sampled STD network with computation complexity of O(n2+n·m). The validity of the robust approach and the designed algorithm were confirmed in the computational tests. Compared with conventional probability approach, the proposed approach is simple and efficient, and also has a good application prospect in navigation system.
出处 《Journal of Central South University》 SCIE EI CAS 2014年第4期1616-1623,共8页 中南大学学报(英文版)
基金 Project(71001079)supported by the National Natural Science Foundation of China
关键词 min-max relative regret approach robust optimal path problem stochastic time-dependent transportation networks stochastic consistent condition 动态交通网络 最优路径规划 路段行程时间 旅行时间 随机性 时间依赖性 稳健优化 STD
  • 相关文献

参考文献17

  • 1The fourth comprehensive transportation survey office. General report of the fourth comprehensive traffic survey in shanghai JR]. Shanghai: Shanghai Construction and Traffic Committee, 2010. (in Chinese).
  • 2LENG Jun-qiang, ZHANG Ya-ping, ZHANG Qian, ZHAO Ying-ping. Integrated reliability of travel time and capacity of urban road network under ice and snowfall conditions [J]. Journal of Central South University: Science and Technology (English Edition), 2010, 17: 419-424.
  • 3HE Huang, GAO Song. Optimal paths in dynamic networks with dependent random link travel times [J]. Transportation Research Part B: Methodological, 2012, 46(5): 579-598.
  • 4CHENG E, GROSSMAN J W, LIPTAK L. Distance formula and shortest paths for the (n, k)-star graphs [J]. Information Sciences, 2010, 180(9): 1671-1680.
  • 5GAO Yuan. Shortest path problem with uncertain arc lengths [J]. Computers & Mathematics with Applications, 2011, 62(6): 2591-2600.
  • 6ZHU X, WILHELM W E. A three-stage approach for the resource-constrained shortest path as a sub-problem in column generation [J]. Computers & Operations Research, 2012, 39(2): 164-178.
  • 7AIN A, SALEHIPOUR A. Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem [J]. Applied Mathematics Letters, 2012, 25(1): 1-5.
  • 8CHITRA C, SUBBARAJI E A non-dominated sorting genetic algorithm solution for shortest path routing problem in computer networks [J]. Expert Systems with Applications, 2012, 39(1): 1518-1525.
  • 9MILLER-HOOKS E D, MAHMASSANI H S. Path comparisons for a priori and time-adaptive decisions in stochastic, time-varying networks [J]. European Journal of Operational Research, 2003, 146(1): 67-82.
  • 10HALL R W. The fastest path through a network with random time-dependent travel times [J]. Transportation Science, 1986, 20(3): 182-188.

同被引文献15

引证文献3

二级引证文献6

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

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