Risk-aware path selection with time-varying, uncertain travel costs: a time series approach

Jilin Hu, Bin Yang*, Chenjuan Guo, Christian Søndergaard Jensen

*Corresponding author for this work

Research output: Contribution to journalJournal articleResearchpeer-review

43 Citations (Scopus)


We address the problem of choosing the best paths among a set of candidate paths between the same origin–destination pair. This functionality is used extensively when constructing origin–destination matrices in logistics and flex transportation. Because the cost of a path, e.g., travel time, varies over time and is uncertain, there is generally no single best path. We partition time into intervals and represent the cost of a path during an interval as a random variable, resulting in an uncertain time series for each path. When facing uncertainties, users generally have different risk preferences, e.g., risk-loving or risk-averse, and thus prefer different paths. We develop techniques that, for each time interval, are able to find paths with non-dominated lowest costs while taking the users’ risk preferences into account. We represent risk by means of utility function categories and show how the use of first-order and two kinds of second-order stochastic dominance relationships among random variables makes it possible to find all paths with non-dominated lowest costs. We report on empirical studies with large uncertain time series collections derived from a 2-year GPS data set. The study offers insight into the performance of the proposed techniques, and it indicates that the best techniques combine to offer an efficient and robust solution.

Original languageEnglish
JournalVLDB Journal
Issue number2
Pages (from-to)179–200
Number of pages22
Publication statusPublished - 1 Apr 2018


  • Risk preferences
  • Stochastic dominance
  • Uncertain time series
  • Utility functions


Dive into the research topics of 'Risk-aware path selection with time-varying, uncertain travel costs: a time series approach'. Together they form a unique fingerprint.

Cite this