Probabilistic shortest path problems with budgetary constraints (Q1113810)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Probabilistic shortest path problems with budgetary constraints |
scientific article |
Statements
Probabilistic shortest path problems with budgetary constraints (English)
0 references
1989
0 references
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 function 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, communication, 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 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.
0 references
random arc length
0 references
approximate solutions
0 references
constrained shortest path problems
0 references
expected utility
0 references
simulation
0 references
project selection
0 references
transportation
0 references
communication
0 references
computer systems design
0 references