algorithm - Finding a connection between two cities -

i have hypothetical problem. let's assume have bunch of cities connected in way each other. question purely hypothetical doesn't matter how connect them (we can think of them kind of graph). between cities bus connections, these connections aren't reliable. add or remove random time time expect them leave city, , time arrive other one. how find way bring person 1 city fast possible / relatively fast bigger probability? kind of algorithms should read solve this?

this difficult problem can approached in game-theoretic manner.

the best paper comes mind multi-modal journey planning in presence of uncertainty botea et. al

the gist of paper this:

• each mode of transportation (walk, bus, or taxi) has range of times takes destination, associated probabilities.
• you need @ place x time y, assume worst case each mode of transportation
• assuming worst, take route highest probability of getting there on time.

so if taxi takes between 60-90 minutes destination, bus takes 70 always, , need destination in next 80 minutes, you'd take bus.

however, if need destination in next 65 minutes, take taxi, because it's mode possibly there on time.

i'm thinking adapt approach yours. each city connected k other cities via bus routes have own associated durations , probabilities of durations. think of each bus route different mode of transportation.

---

another approach use a* on graph, heuristic seeks minimize uncertainty , duration.

a relevant paper second approach (not quite same, related) firm: feedback controller-based information-state roadmap - framework motion planning under uncertainty.

while paper covers lot dynamical systems, part extracting path through roadmap (graph) minimize uncertainty useful. perhaps adapt incorporate aspect of speed.