Optimal paths planning in dynamic transportation networks with random link travel times

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(n²+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.

Keywords

min-max relative regret approach / robust optimal path problem / stochastic time-dependent transportation networks / stochastic consistent condition

References

[1] The fourth comprehensive transportation survey office.General report of the fourth comprehensive traffic survey in shanghai [R], 2010, Shanghai, Shanghai Construction and Traffic Committee

[2] LengJ-q, ZhangY-p, ZhangQ, ZhaoY-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

[3] HeH, GaoSong. Optimal paths in dynamic networks with dependent random link travel times [J]. Transportation Research Part B: Methodological, 2012, 46(5): 579-598

[4] ChengE, GrossmanJ W, LiptakL. Distance formula and shortest paths for the (n, k)-star graphs [J]. Information Sciences, 2010, 180(9): 1671-1680

[5] GaoYuan. Shortest path problem with uncertain arc lengths [J]. Computers & Mathematics with Applications, 2011, 62(6): 2591-2600

[6] ZhuX, WilhelmW 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

[7] AinA, SalehipourA. Speeding up the Floyd-Warshall algorithm for the cycled shortest path problem [J]. Applied Mathematics Letters, 2012, 25(1): 1-5

[8] ChitraC, SubbarajiP. 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

[9] Miller-HooksE D, MahmassaniH 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

[10] HallR W. The fastest path through a network with random time-dependent travel times [J]. Transportation Science, 1986, 20(3): 182-188

[11] Miller-HooksE D, MahmassaniH S. Least expected time paths in stochastic, time-varying transportation networks [J]. Transportation Science, 2000, 34(2): 198-215

[12] WellmanM P. Path planning under time-dependent uncertainty [C]. Proceedings of the 11th Conference on Uncertainty in Artificial Intelligence. Montreal, Quebec, Canada, 199518-20

[13] HasuikeT. Robust shortest path problem based on a confidence interval in fuzzy bi-criteria decision making [J]. Information Sciences, 2013, 221(1): 520-533

[14] KarasanO E, PinarM C, YamanHThe robust shortest path problem with interval data [R], 2001, Bilkent, Ankara, Turkey, Bilkent University, Department of Industrial Engineering

[15] BertsimasD, SimM. Robust discrete optimization and network flows [J]. Mathematical Programming, 2002, 98(1/2/3): 49-71

[16] SimMRobust optimization [D], 2004, Cambridge, Massachusetts, USA, Massachusetts Institute of Technology

[17] Jose’alemD, MorabitoR. Production planning in furniture settings via robust optimization [J]. Computers & Operations Research, 2012, 39(2): 139-150