INSPIRING FUTURES

Time-dependent Hyperstar algorithm for robust vehicle navigation in time-dependent stochastic road networks.

Bell, Michael G H, Trozzi, Valentina, Hosseinloo, Solmaz Haji, Gentile, Guido and Fonzone, Achille (2010) Time-dependent Hyperstar algorithm for robust vehicle navigation in time-dependent stochastic road networks. In: 4th International Symposium on Transportation Network Reliability, 2010 July, Minneapolis, USA. (Unpublished)

[img]
Preview
PDF
Available under License Creative Commons Attribution Non-commercial.

Download (744kB) | Preview

    Abstract/Description

    The vehicle navigation problem studied in Bell (2009) is revisited and a time-dependent reverse Hyperstar algorithm is presented. This minimises the expected time of arrival at the destination, and all intermediate nodes, where expectation is based on a pessimistic (or risk-averse) view of unknown link delays. This may also be regarded as a hyperpath version of the Chabini and Lan (2002) algorithm, which itself is a time-dependent A* algorithm. Links are assigned undelayed travel times and maximum delays, both of which are potentially functions of the time of arrival at the respective link. The driver seeks probabilities for link use that minimise his/her maximum exposure to delay on the approach to each node, leading to the determination of the pessimistic expected time of arrival. Since the context considered is vehicle navigation where the driver is not making repeated trips, the probability of link use may be interpreted as a measure of link attractiveness, so a link with a zero probability of use is unattractive while a link with a probability of use equal to one will have no attractive alternatives. A solution algorithm is presented and proven to solve the problem provided the node potentials are feasible and a FIFO condition applies for undelayed link travel times. The paper concludes with a numerical example.

    Item Type: Conference or Workshop Item (Paper)
    Uncontrolled Keywords: Robust route guidance; vehicle navigation; encertain networks;
    University Divisions/Research Centres: Faculty of Engineering, Computing and Creative Industries
    Dewey Decimal Subjects: 300 Social sciences > 380 Commerce, communications & transportation > 388 Transportation; ground transportation
    Library of Congress Subjects: H Social Sciences > HE Transportation and Communications
    Item ID: 4243
    Depositing User: Computing Research
    Date Deposited: 14 Mar 2011 16:40
    Last Modified: 14 Mar 2011 16:40
    URI: http://researchrepository.napier.ac.uk/id/eprint/4243

    Actions (login required)

    View Item

    Document Downloads

    More statistics for this item...

    Edinburgh Napier University is a registered Scottish charity. Registration number SC018373