Optimal paths planning in dynamic transportation networks with random link travel times
来源期刊：中南大学学报(英文版)2014年第4期
论文作者：SUN Shi-chao(孙世超) DUAN Zheng-yu(段征宇) YANG Dong-yuan(杨东援)
文章页码：1616 - 1623
Key words：min-max relative regret approach; robust optimal path problem; stochastic time-dependent transportation networks; stochastic consistent condition
Abstract: 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.
SUN Shi-chao(孙世超), DUAN Zheng-yu(段征宇), YANG Dong-yuan(杨东援)
(Key Laboratory of Road and Traffic Engineering of the Ministry of Education
(Tongji University), Shanghai 201804, China)
Abstract: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.
Key words:min-max relative regret approach; robust optimal path problem; stochastic time-dependent transportation networks; stochastic consistent condition
