Time‐dependent Hyperstar algorithm for robust vehicle navigation

Time‐dependent Hyperstar algorithm for robust vehicle navigation

0.00 Avg rating0 Votes
Article ID: iaor20123361
Volume: 46
Issue: 5
Start Page Number: 790
End Page Number: 800
Publication Date: Jun 2012
Journal: Transportation Research Part A
Authors: , , , ,
Keywords: vehicle routing & scheduling, simulation: applications, queues: applications
Abstract:

The vehicle navigation problem studied in 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 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. Probabilities for link use are sought that minimise the driver’s maximum exposure to delay on the approach to each node, leading to the determination of a pessimistic expected time of arrival at the destination and all intermediate nodes. Since the context considered is vehicle navigation, the probability of link use measures 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 to undelayed link travel times. The paper concludes with a numerical example.

Reviews

Required fields are marked *. Your email address will not be published.