Probabilistic shortest path problems with budgetary constraints
type: Item
instance of: scholarly article
title: Probabilistic shortest path problems with budgetary constraints
zbMATH Open document ID: 0661.90090
DOI: 10.1016/0305-0548(89)90016-6
author: Jonathan F. Bard
author: Jeanne L. Miller
published in: Computers \& Operations Research
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90C35
Mathematics Subject Classification ID: 90C39
Mathematics Subject Classification ID: 90B15
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 65K05
zbMATH DE Number: 4081324
zbMATH Keywords: random arc length
zbMATH Keywords: approximate solutions
zbMATH Keywords: constrained shortest path problems
zbMATH Keywords: expected utility
zbMATH Keywords: simulation
zbMATH Keywords: project selection
zbMATH Keywords: transportation
zbMATH Keywords: communication
zbMATH Keywords: computer systems design
MaRDI profile type: Publication
full work available at URL: 0305-0548(89)90016-6
OpenAlex ID: W2046265805
cites work: Technical Note—Shortest-Path Algorithms: A Comparison
cites work: Optimal paths in graphs with stochastic or multidimensional weights
cites work: Distribution of the Time Through a Directed, Acyclic Network
cites work: The Stochastic Shortest Route Problem
cites work: Estimating Network Characteristics in Stochastic Activity Networks
cites work: Bounding Distributions for a Stochastic Acyclic Network
cites work: Approximating the Criticality Indices of the Activities in PERT Networks
cites work: Q3950274
cites work: Q3734141
description: scientific article; zbMATH DE number 4081324