Patent ID: 7756021

Claim:
A computer implemented method for finding a path having a minimal expected cost, in which the path is through a network of nodes, in which the path is from a source node to a destination node, and in which the path includes one or more subpaths, comprising the steps of: representing the network in a memory as a stochastic graph of nodes connected by arcs, in which a travel time for traversing each arc is a random variable expressing a probability of the travel time; representing, in the stochastic graph in the memory, a cost of a traversing each subpath in the path from the source node to the destination node as a nonlinear cost function of a total travel time on the path; determining, for particular subpath, an expected cost function as a weighted average of the nonlinear cost function over all possible traversal times according to the probabilities on the subpath, in which the expected cost function determines an expected cost for the subpath; and determining for each node in the network and for each possible time to start, an optimal path from the source node to the node having a minimal expected cost and an optimal time to start on the optimal path, wherein the steps are performed in a computer system.