IEEE Transactions on Intelligent Transportation Systems · 2013 · 73 citations · 34 references
BusinessComputer ScienceTransportation PlanningStochastic ModelingTransportTransportationNetwork OptimizationRoute PlanningRouting AlgorithmsShortest Path AlgorithmsStochastic NetworksStochastic Shortest Path ProblemsPathfinding AlgorithmsRoad Network ModelingRoad Traffic NetworksShortest Path ModelingShortest Path On Road NetworksShortest Path OptimizationShortest Path ProblemsTime-dependent Shortest Paths
As travel times in road networks are dynamic and uncertain, it is difficult and time-consuming to search for the least expected time path in large-scale networks. This paper addresses the problem of finding the least expected time path in stochastic time-dependent (STD) road networks. A stochastic travel speed model is proposed to represent STD link travel times. It is proved that the link travel times in STD networks satisfy the stochastic first-in-first-out (S-FIFO) property. Based on this S-FIFO property, an efficient multicriteria A* algorithm is proposed to exactly determine the least expected time path in STD networks. Computational results using several large-scale road networks show that the proposed algorithm has a significant computational advantage over existing solution algorithms without the S-FIFO property.
34