Potentially optimal paths and route choice in networks with arc delays.

Abstract

The shortest path problem has been widely studied in graph theory and its solutions have been largely used in the transport field, both in assignment and vehicle navigation applications. Solutions have been proposed under different assumptions concerning the time-dependency and the randomness of arc costs. In particular it has been shown that in networks affected by not completely predictable events travellers can minimize their expected travel times by adopting adaptive strategies, i.e. sets of paths, instead of single routes. The present paper focuses on the problem of route guidance in a network in which the travel time on each link can assume only two values, corresponding to the free flow situation and to the delayed one. Path set selection and route choice are decoupled. The problem of finding the set of the potentially optimal paths is solved implicitly by identifying the set of the potentially optimal links. Sufficient and necessary conditions for a link to be optimal do not coincide and therefore an algorithm is presented which can identify only a subset of all potentially optimal links. An approach considering risk aversion is proposed for route choice.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 2 citations exist upstream.