Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function

DOI10.1016/S0377-2217(97)00264-6zbMath0922.90141MaRDI QIDQ1280137

Sumit Sarkar, Ishwar Murthy

Publication date: 10 March 1999

Published in: European Journal of Operational Research (Search for Journal in Brave)

zbMATH Keywords

pruningstochastic shortest path problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Stochastic programming (90C15)

Related Items (7)

Arrival time dependent routing policies in public transport ⋮ A fully polynomial time approximation scheme for the probability maximizing shortest path problem ⋮ Mean‐standard deviation model for minimum cost flow problem ⋮ Comparison of the Exact and Approximate Algorithms in the Random Shortest Path Problem ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Dynamic journeying under uncertainty ⋮ Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

Cites Work

• Unnamed Item
• Unnamed Item
• Optimal paths in probabilistic networks: A case with temporary preferences
• A reoptimization algorithm for the shortest path problem with time windows
• Stochastic spanning tree problem
• Optimal paths in graphs with stochastic or multidimensional weights
• A computational analysis of alternative algorithms and labeling techniques for finding shortest path trees
• Algorithms for finding paths with multiple constraints
• Generalized Dynamic Programming for Stochastic Combinatorial Optimization
• Technical Note—A Note on the Stochastic Shortest Route Problem
• Note—An Improved Conditional Monte Carlo Technique for the Stochastic Shortest Path Problem
• Approximation of Pareto Optima in Multiple-Objective, Shortest-Path Problems
• The Stochastic Shortest Route Problem
• Solving min-max shortest-path problems on a network
• Shortest path problems with node failures
• A Relaxation-Based Pruning Technique for a Class of Stochastic Shortest Path Problems
• Arc Reduction and Path Preference in Stochastic Acyclic Networks
• Dynamic Shortest Paths in Acyclic Networks with Markovian Arc Costs
• Shortest Paths in Probabilistic Graphs

This page was built for publication: Exact algorithms for the stochastic shortest path problem with a decreasing deadline utility function