The K Dynamic Stochastic Shortest Paths Problem and Its Application to Transportation Mode.pdf

The K Dynamic Stochastic Shortest Paths Problem and Its Application to Transportation Mode Selection Raymond K. Cheung Haiqing Song Department of Industrial Engineering and Engineering Management The Hong Kong University of Science and Technology Clearwater Bay, Kowloon, Hong Kong fax.: +852 – 2358 – 0062 e.mail: rcheung@ust.hk Extended Abstract Finding K paths with smallest possible length between a pair of nodes in a network is known as the K shortest paths problem. Because of its many applications, this problem has received considerable attention in the literature. Our research is motivated by the advances in Global Positioning System and communication technology, with which we can change route dynamically when new information is received during the routing process. In this paper, we consider the problem of finding the expected length of the K shortest paths for an acyclic network where arc lengths are independent, finite, discrete random variables which are realized progressively when the network is traversed. We provide the problem formulation, develop an efficient algorithm, and apply it to solve a special dynamic constrained shortest path problem with an application in transportation mode selection. There are several possible definitions of shortest paths for stochastic networks such as finding the expected length of the shortest paths among all possible realizations of a stochastic network [1], the path with minimum expecte length [2], the distribution function of the shortest path length [3], and the expected length of the shortest path that is formed dynamically as the network is traversed [4, 5]. For the last version, when a node is visited, the