Probabilistic shortest path problems with budgetary constraints

This paper presents an algorithm for finding approximate solutions to constrained shortest path problems whose arc lengths are random variables. An additional feature of the model is that the distribution functions associated with these random variables may be ‘improved’ by selectively allocating resources to the arcs. Performance is measured by a utility function defined over the range of possible outcomes. Consequently, rather than minimizing expected time or distance, the objective is to maximize expected utility. This is achieved with a heuristic that employs a dynamic programming algorithm to solve fixed instances of the probabilistic problem within a simulation framework. The approach is discussed with reference to the project selection problem, but has broad application in transportation, communications, and computer systems design. Results are presented for networks containing up to 25 nodes and 40 arcs, using exponential and normal distributions for the arc lengths. The fact that the computation times grow rapidly with network size, though, effectively limits the use of the methodology to problems with no more than 100 nodes and several 100 arcs.