Statistical Shortest Path Problem

Question 1

What is statistical shortest path?

Answer 1

It uses mean and variance to capture model uncertainties

Question 2

What kind of statistical uncertainties does the this method cover? Examples

Answer 2

I.E process variation, temperature variation, voltage variation, trip planning

Question 3

What is the difference between previous path problems and statistical ones?

Answer 3

Previous methods do not account for model uncertainties and are deterministic. I.E link cost = li whereas in statistical method link cost = (mu, sigma^2)

Question 4

What are assumptions made when modelling transportation road modelling? (2)

Answer 4

• That each link delay is Gaussian distributed
• Delays of each link are independent of other links

Question 5

How would we denote travel time for a path (pi) ?

Answer 5

t(pi) = N(mu(pi), sigma^2(pi))

mu = sum from first link to last link INath of mu-e
sigma^2 = sum from first link to last link IN path of sigma^2-e

N: normally distributed with following mean and s.d
e: link
mu-e : link mean
sigma^2-e : link variance

Question 6

How to calculate expected cost of travelling when using path pi if cost is C(t) = t

Answer 6

Expected cost of pi = EC(pi) = integral from -infinity to +infinity of t*f(t) dt = mu(pi)

• f(t) : delay pdf.

Question 7

What happens to the expected cost of travelling when using path PI if the cost of the path increases sharpy?

Answer 7

It becomes very large:

Expected cost of pi = EC(pi) = integral from -infinity to +infinity of e^(kt)f(t) dt = e(kmu(pi) + (k*sigma^2pi)/2)

• f(t) : delay pdf.

Question 8

How could