We propose a dynamic program to find the shortest path in a network having exponential, gamma and normal probability distributions as arc lengths. Two operators of sum and comparison need to be adapted for the proposed dynamic program. Convolution approach is used to sum probability distributions being employed in the dynamic program.
:Stochastic shortest path; dynamic program; convolution; probabilistic network
Mohammad Hessam Olya, Hamed Fazlollahtabar, Finding Shortest Path in a Combined Exponential -Gamma-Normal Probability Distribution Arc Length, Advances in Industrial Engineering and Management, Vol.3, No.4, 2014, pp.35-44, doi: 10.7508/AIEM-V3-N4-35-44
(size: 533.83 kB, pp.35-44
, Download times:
 Bazaraa, M., Jarvis, J., and Sherali, H., 1990. Linear Programming and Network Flows, second ed., Wiley, New York.
 Bellman, E., 1958. On a routing problem. Quarterly of Applied Mathematics, vol. 16, pp. 87-90.
 Dijkstra, E.W., 1959. A note on two problems in connection with graphs. Numerical Mathematics, vol. 1, pp. 269-271.
 Dreyfus, S., 1969. An appraisal of some shortest path algorithms. Operations Research, vol. 17, pp. 395-412.
 Cook, K.L. and Halsey, E., 1966. The Shortest Route Through a Network With Time-Dependent Internodal Transit Times. Journal of Mathematical Analysis and Application, vol. 14, pp. 493-498.
 Halpern, J.L., 1977. Shortest Route with Time-Dependent Length of Edges and Limited Delay Possibilities in Nodes. Zeitschrift fur Operations Research, vol. 21, pp. 117-124.
 Orda, A. and Rom, R., 1990. Shortest-path and minimum-delay algorithms in networks with time-dependent edge-length. Journal of the ACM, vol. 37, pp. 607-625.
 Kaufman, E., Lee, J., and Smith, R.L., 1993. Fastest paths in time-dependent networks for intelligent vehicle highway systems application. IVHS Journal, vol. 1, no. 1, pp. 1-11.
 Ziliaskopoulos, A.K. and Mahassani, H.S., 1993. Time-dependent, shortest-path algorithm for real-time intelligent vehicle system applications. Transportation Research Record 1408, TRB, National Research Council, Washington, DC, pp. 94-100.
 Chabini, I., 1997. A new algorithm for shortest paths in discrete dynamic networks. Proceeding of the 8th International Federation of Automatic Control (IFAC) Symposium on Transportation Systems, eds M. Papageorgiu and A. Pouliezos 2, pp. 551-556. Chania, Greece.
 Malandraki, C., 1989. The Time-Dependent Vehicle Routing Problem. Doctoral Dissertation, Northwestern University.
 Ziliaskopoulos, A. and Mahmassani, H.S., 1996. Note on least time path computation considering delays and prohibitions for intersection movements. Transportation Research, Part B (Methodological). vol. 30B, no. 5, pp. 359-367.
 Mirchandani, B.P. and Soroush, H., 1986. Routes and flows in stochastic networks. Advanced Schools on Stochastic in Combinatorial Optimization, eds G. Angrealtta, F. Mason and P. Serafini, pp. 129-177, CISM. Udine, Italy.
 Haquari, M, and Dejax, P., 1997. Time Dependent Shortest Path Problem: Solution and Application to Routing Problems. Recherche Operationnelle, vol. 31, no. 2, pp. 117-31.
 Frank, H., 1986. Shortest paths in probabilistic graphs, Operations Research, vol. 17, pp. 583-599.
 Loui, P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Comm. ACM, vol. 26, pp. 670-676.
 Murthy, I. and Sarkar, S., 1996. A relaxation-based pruning technique for a class of stochastic shortest path problems. Transportation Science, vol. 30, no. 3, pp. 220-236.
 Wijerante, A., Turnquist, M., and Mirchandani, P., 1993. Multiobjective routing of hazardous materials in stochastic networks, European Journal of Operational Research, vol. 65, pp. 33-44.
 Martins, E., 1984. On a multi-criteria shortest path problem. European Journal of Operational Research, vol. 16, pp. 236-245.
 Hall, R., 1986. The fastest path through a network with random time-dependent travel time. Transportation Science, vol. 20, no. 3, pp. 182-188.
 Fu, L. and Rilett, L. R., 1998. Expected shortest paths in dynamic and stochastic traffic networks, Transp. Res, vol. 32, no. 7, pp. 499-516.
 Fan, Y.Y., Kalaba, R.E., and Moore, J.E. 2005. Shortest Path in Stochastic Networks with Correlated Link Costs. Computers and Mathematic with Applications, vol. 49, pp. 1549-1564.
 Bertsekas, D. and Tsitsiklis, J., 1991. An analysis of stochastic shortest path problems. Mathematics of Operations Research, vol. 16, pp. 580–595.
 Koutsopoulos, H.N., and Xu, H., 1994. An information discounting routing strategy for ATIS. Transportation Research Part C (Emerging Technologies), vol. 1, no. 3, pp. 249-264.
 Miller, E.D., Mahmassani, H.S., and Ziliaskopoulos, A., 1994. Path search techniques for Transportation Networks with Time-Dependent, Stochastic Arc Costs. IEEE International Conference on Systems, Man, and Cybernetics. Humans, Information and Technology, vol. 2, pp. 1716-1721.
 Cai, X., Kioks, T., and Wong, C.K., 1997. Time-Varying Shortest Path Problems with Constraints. Networks, vol. 29, no. 3(3), pp. 141-149.
 Friesz, T.L., Bernstein, D., Smith, T.E., Tobin, R.L., and Wie, R., 1993. A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem. Operations Research, vol. 41, no. 1, pp. 179-191.
 Azaron, A. and Kianfar, F., 2003. Dynamic shortest path in stochastic dynamic networks: Ship routing problem, European Journal of Operational Research, vol. 144, pp. 138-156.
 Thompson, A.M. and Cluett, W.R., 2005. Stochastic iterative dynamic programming: a Monte Carlo approach to dual control, Automatica, vol. 41, pp. 767-778.
 Olya, M.H., Shirazi, B., Fazlollahtabar, H, 2013. Adapted Dynamic Program to Find Shortest Path in a Network having Normal Probability Distribution Arc Length. Advances in Industrial Engineering and Management, vol. 2, no. 1, pp. 5-10.
 Olya, M. H., 2014. Finding shortest path in a combined exponential – gamma probability distribution arc length. International Journal of Operational Research, vol. 21, no. 1, pp. 25-37.
 Olya, M.H., 2014. Applying Dijkstra’s algorithm for general shortest path problem with normal probability distribution arc length. International Journal of Operational Research, vol. 21, no. 2, pp. 143-154.