Open AccessNote—An Improved Conditional Monte Carlo Technique for the Stochastic Shortest Path Problem
Author(s) -
Veena Adlakha
Publication year - 1986
Publication title -
management science
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 4.954
H-Index - 255
eISSN - 1526-5501
pISSN - 0025-1909
DOI - 10.1287/mnsc.32.10.1360
Subject(s) - monte carlo method , shortest path problem , mathematics , monte carlo integration , mathematical optimization , importance sampling , quasi monte carlo method , hybrid monte carlo , computer science , algorithm , markov chain monte carlo , statistics , discrete mathematics , graph
This paper describes a simulation procedure for estimating the distribution function of the shortest path length in a network with random arc lengths. The method extends the concept of conditional Monte Carlo utilizing special properties of the Uniformly Directed Cutsets and the unique arcs. The objective here is to reduce the sampling effort and utilize known probability information to derive multivariate integrals of lower dimension. The experimental results show that the proposed method is substantially cost effective and performs better than traditional Monte Carlo and conditional methods.stochastic networks, shortest path, Monte Carlo methods, variance reduction