Editing Shortest path problem (section)

==Shortest path in stochastic time-dependent networks==
In real-life, a transportation network is usually stochastic and time-dependent. The travel duration on a road segment depends on many factors such as the amount of traffic (origin-destination matrix), road work, weather, accidents and vehicle breakdowns. A more realistic model of such a road network is a stochastic time-dependent (STD) network.<ref>Loui, R.P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Communications of the ACM, 26(9), pp.670-676.</ref><ref>{{cite journal |last1=Rajabi-Bahaabadi |first1=Mojtaba |first2=Afshin |last2=Shariat-Mohaymany |first3=Mohsen |last3=Babaei |first4=Chang Wook |last4=Ahn |title=Multi-objective path finding in stochastic time-dependent road networks using non-dominated sorting genetic algorithm |journal=Expert Systems with Applications |date=2015 |volume=42 |issue=12|pages=5056–5064 |doi=10.1016/j.eswa.2015.02.046 }}</ref>

There is no accepted definition of optimal path under uncertainty (that is, in stochastic road networks). It is a controversial subject, despite considerable progress during the past decade. One common definition is a path with the minimum expected travel time. The main advantage of this approach is that it can make use of efficient shortest path algorithms for deterministic networks. However, the resulting optimal path may not be reliable, because this approach fails to address travel time variability.

To tackle this issue, some researchers use travel duration distribution instead of its expected value. So, they find the probability distribution of total travel duration using different optimization methods such as [[dynamic programming]] and [[Dijkstra's algorithm]] .<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Finding shortest path in a combined exponential – gamma probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=1|pages=25–37 |doi=10.1504/IJOR.2014.064020 }}</ref> These methods use [[stochastic optimization]], specifically stochastic dynamic programming to find the shortest path in networks with probabilistic arc length.<ref>{{cite journal |last1=Olya |first1=Mohammad Hessam |title=Applying Dijkstra's algorithm for general shortest path problem with normal probability distribution arc length |journal=International Journal of Operational Research |date=2014 |volume=21 |issue=2|pages=143–154 |doi=10.1504/IJOR.2014.064541 }}</ref> The terms ''travel time reliability'' and ''travel time variability'' are used as opposites in the transportation research literature: the higher the variability, the lower the reliability of predictions.

To account for variability, researchers have suggested two alternative definitions for an optimal path under uncertainty. The ''most reliable path'' is one that maximizes the probability of arriving on time given a travel time budget. An ''α-reliable path'' is one that minimizes the travel time budget required to arrive on time with a given probability.