|
==Shortest path in stochastic time-dependent networks==
In real-life situations, thea transportation network is usually stochastic and time-dependent. InThe fact,travel aduration traveler traversingon a linkroad dailysegment may experiences different travel timesdepends on thatmany linkfactors duesuch not only toas the fluctuationsamount in travelof demandtraffic (origin-destination matrix), but also due to such incidents asroad work zones, bad weather conditions, accidents and vehicle breakdowns. As a result, a stochastic time-dependent (STD) network is aA more realistic representationmodel of ansuch actuala road network comparedis witha thestochastic deterministictime-dependent one(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.
Despite considerable progress during the course of the past decade, it remains a controversial question how an optimal path should be defined and identified in stochastic road networks. In other words, there is no unique definition of an optimal path under uncertainty. One possible and common answer to this question is to find a path with the minimum expected travel time. The main advantage of using this approach is that efficient shortest path algorithms introduced for the deterministic networks can be readily employed to identify the path with the minimum expected travel time in a stochastic network. However, the resulting optimal path identified by this approach may not be reliable, because this approach fails to address travel time variability. To tackle this issue some researchers use distribution of travel time instead of expected value of it so they find the probability distribution of total travelling time 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 concept of travel time reliability is used interchangeably with travel time variability in the transportation research literature, so that, in general, one can say that the higher the variability in travel time, the lower the reliability would be, and vice versa. ▼
▲Despite considerable progress during the course of the past decade, it remains a controversial question how an optimal path should be defined and identified in stochastic road networks. In other words, there is no unique definition of an optimal path under uncertainty. One possible and common answer to this question is to find a path with the minimum expected travel time. The main advantage of using this approach is that efficient shortest path algorithms introduced for the deterministic networks can be readily employed to identify the path with the minimum expected travel time in a stochastic network. However, the resulting optimal path identified by this approach may not be reliable, because this approach fails to address travel time variability. To tackle this issue , some researchers use distributiontravel ofduration travel timedistribution instead of its expected value . of it soSo, they find the probability distribution of total travellingtravel timeduration 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 concept ofterms ''travel time reliability '' isand used interchangeably withand ''travel time variability '' are used as opposites in the transportation research literature , so that, in general, one can say that: the higher the variability in travel time, the lower the reliability would be, and viceof versapredictions.
In order to account for travel time reliability more accurately, two common alternative definitions for an optimal path under uncertainty have been suggested. Some have introduced the concept of the most reliable path, aiming to maximize the probability of arriving on time or earlier than a given travel time budget. Others, alternatively, have put forward the concept of an α-reliable path based on which they intended to minimize the travel time budget required to ensure a pre-specified on-time arrival probability. ▼
▲In order toTo account for travelvariability, timeresearchers reliabilityhave more accurately,suggested two common alternative definitions for an optimal path under uncertainty have been suggested. Some have introduced the concept of theThe ''most reliable path ,'' aimingis toone that maximizemaximizes the probability of arriving on time or earlier thangiven a given travel time budget. Others, alternatively, have put forward the concept of anAn ''α-reliable path '' basedis onone which they intended tothat minimizeminimizes the travel time budget required to ensure a pre-specifiedarrive on - time arrivalwith a given probability.
==See also==
|
