Note—An Improved Conditional Monte Carlo Technique for the Stochastic Shortest Path Problem

Management Science · 1986 · Volume 32 · Issue 10

Abstract

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.

Keywords

stochastic networks, shortest path, Monte Carlo methods, variance reduction

Enable JavaScript for citation tools and additional paper interactions.