Method for finding minimal cost paths under uncertainty
View Patent ↗A computer implemented method finds a path having a minimal expected cost through a network of nodes connected by arcs, in which the path is from a source node to a destination node, and in which a traversal time for traversing each arc is a random variable. An expected cost of traversing each possible path from the source node to the destination node is determined as an average value of a nonlinear cost function applied to each possible total travel time for traversing the path. The expected cost is weighted according to a probability of each possible total travel time. For each node in the network and for each possible time to start, a particular path from the source node to the node having a minimal expected cost and an optimal time to start on that path is determined.
1. 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.
2. The method of claim 1 , in which the expected cost function is a convolution of the nonlinear cost function with probability distribution functions of the random variables.
3. The method of claim 1 , further comprising:
maintaining, for each node and the optimal path to the node, the expected cost according to sets of values obtained from a subset of terms of the expected cost function.
4. The method of claim 3 , further comprising:
discretizing the values of terms of the expected cost function.
5. The method of claim 1 in which travel time represents an arbitrary resource, and the expected cost function represents a penalty for expending the arbitrary resource.
6. The method of claim 2 , in which the nonlinear cost function is a quadratic function augmented with an exponential term.
7. The method of claim 1 , in which the network is a transportation network.
8. The method of claim 1 , in which the network is a communications network.
9. The method of claim 1 , in which each possible total travel time is expressed as a probability distribution function.