2017（Volume 6） Vol. 6, No. 2 (2017) Vol. 6, No. 1 (2017) 2016（Volume 5） Vol. 5, No. 2 (2016) Vol. 5, No. 1 (2016) 2015（Volume 4） Vol. 4, No. 2 (2015) Vol. 4, No. 1 (2015) 2014（Volume 3） Vol.3, No.4 ( 2014 ) Vol.3, No.3 ( 2014 ) Vol.3, No.2 ( 2014 ) Vol.3, No.1 ( 2014 ) 2013 ( Volume 2 ) Vol.2, No.2 ( 2013 ) Vol.2, No.1 ( 2013 ) 2012 ( Volume 1 ) Vol. 1, No.1 ( 2012 ) 

ADVANCES IN INDUSTRIAL ENGINEERING AND MANAGEMENT ISSN:22227059 (Print);EISSN: 22227067 (Online) Copyright © 2000 American Scientific Publishers. All Rights Reserved.
Title :
Finding Shortest Path in a Combined Exponential GammaNormal Probability Distribution Arc Length
Author(s) : Mohammad Hessam Olya, Hamed Fazlollahtabar
Author affiliation : Mohammad Hessam Olya, Wayne State University, Industrial and Systems Engineering Department, Detroit, MI 48201, United States
Hamed Fazlollahtabar, Faculty of Industrial Engineering, Iran University of Science and Technology, Tehran, Iran
Abstract:
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. Key words:Stochastic shortest path; dynamic program; convolution; probabilistic network Cite it: Mohammad Hessam Olya, Hamed Fazlollahtabar, Finding Shortest Path in a Combined Exponential GammaNormal Probability Distribution Arc Length, Advances in Industrial Engineering and Management, Vol.3, No.4, 2014, pp.3544, doi: 10.7508/AIEMV3N43544
Full Text : PDF(size: 533.83 kB, pp.3544, Download times:300) DOI : 10.7508/AIEMV3N43544 References: [1] Bazaraa, M., Jarvis, J., and Sherali, H., 1990. Linear Programming and Network Flows, second ed., Wiley, New York.
[2] Bellman, E., 1958. On a routing problem. Quarterly of Applied Mathematics, vol. 16, pp. 8790. [3] Dijkstra, E.W., 1959. A note on two problems in connection with graphs. Numerical Mathematics, vol. 1, pp. 269271. [4] Dreyfus, S., 1969. An appraisal of some shortest path algorithms. Operations Research, vol. 17, pp. 395412. [5] Cook, K.L. and Halsey, E., 1966. The Shortest Route Through a Network With TimeDependent Internodal Transit Times. Journal of Mathematical Analysis and Application, vol. 14, pp. 493498. [6] Halpern, J.L., 1977. Shortest Route with TimeDependent Length of Edges and Limited Delay Possibilities in Nodes. Zeitschrift fur Operations Research, vol. 21, pp. 117124. [7] Orda, A. and Rom, R., 1990. Shortestpath and minimumdelay algorithms in networks with timedependent edgelength. Journal of the ACM, vol. 37, pp. 607625. [8] Kaufman, E., Lee, J., and Smith, R.L., 1993. Fastest paths in timedependent networks for intelligent vehicle highway systems application. IVHS Journal, vol. 1, no. 1, pp. 111. [9] Ziliaskopoulos, A.K. and Mahassani, H.S., 1993. Timedependent, shortestpath algorithm for realtime intelligent vehicle system applications. Transportation Research Record 1408, TRB, National Research Council, Washington, DC, pp. 94100. [10] 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. 551556. Chania, Greece. [11] Malandraki, C., 1989. The TimeDependent Vehicle Routing Problem. Doctoral Dissertation, Northwestern University. [12] 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. 359367. [13] 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. 129177, CISM. Udine, Italy. [14] Haquari, M, and Dejax, P., 1997. Time Dependent Shortest Path Problem: Solution and Application to Routing Problems. Recherche Operationnelle, vol. 31, no. 2, pp. 11731. [15] Frank, H., 1986. Shortest paths in probabilistic graphs, Operations Research, vol. 17, pp. 583599. [16] Loui, P., 1983. Optimal paths in graphs with stochastic or multidimensional weights. Comm. ACM, vol. 26, pp. 670676. [17] Murthy, I. and Sarkar, S., 1996. A relaxationbased pruning technique for a class of stochastic shortest path problems. Transportation Science, vol. 30, no. 3, pp. 220236. [18] Wijerante, A., Turnquist, M., and Mirchandani, P., 1993. Multiobjective routing of hazardous materials in stochastic networks, European Journal of Operational Research, vol. 65, pp. 3344. [19] Martins, E., 1984. On a multicriteria shortest path problem. European Journal of Operational Research, vol. 16, pp. 236245. [20] Hall, R., 1986. The fastest path through a network with random timedependent travel time. Transportation Science, vol. 20, no. 3, pp. 182188. [21] Fu, L. and Rilett, L. R., 1998. Expected shortest paths in dynamic and stochastic traffic networks, Transp. Res, vol. 32, no. 7, pp. 499516. [22] 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. 15491564. [23] Bertsekas, D. and Tsitsiklis, J., 1991. An analysis of stochastic shortest path problems. Mathematics of Operations Research, vol. 16, pp. 580–595. [24] 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. 249264. [25] Miller, E.D., Mahmassani, H.S., and Ziliaskopoulos, A., 1994. Path search techniques for Transportation Networks with TimeDependent, Stochastic Arc Costs. IEEE International Conference on Systems, Man, and Cybernetics. Humans, Information and Technology, vol. 2, pp. 17161721. [26] Cai, X., Kioks, T., and Wong, C.K., 1997. TimeVarying Shortest Path Problems with Constraints. Networks, vol. 29, no. 3(3), pp. 141149. [27] 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. 179191. [28] Azaron, A. and Kianfar, F., 2003. Dynamic shortest path in stochastic dynamic networks: Ship routing problem, European Journal of Operational Research, vol. 144, pp. 138156. [29] Thompson, A.M. and Cluett, W.R., 2005. Stochastic iterative dynamic programming: a Monte Carlo approach to dual control, Automatica, vol. 41, pp. 767778. [30] 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. 510. [31] 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. 2537. [32] 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. 143154.
