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 :
Adapted Dynamic Program to Find Shortest Path in a Network having Normal Probability Distribution Arc Length
Author(s) : Mohammad Hessam Olya, Babak Shirazi, Hamed Fazlollahtabar
Abstract:
We adapt a dynamic program to find the shortest path in a network having 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 two normal probability distributions being employed in the dynamic program. Generally, stochastic shortest path problems are treated using expected values of the arc probabilities, but in the proposed method using distributed observed past data as arc lengths, an integrated value is obtained as the shortest path length. Key words:Shortest path; Dynamic program; Convolution; Normal distribution Cite it: Mohammad Hessam Olya, Babak Shirazi, Hamed Fazlollahtabar,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, 2013
Full Text : PDF(size: 139.02 kB, pp. 510, Download times:2702) DOI : 10.7508/AIEMV2N1510 References: [1] Bazaraa, M., Jarvis, J. & 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 16, pp. 8790. [3] Bertsimas, D. and Van Ryzin, G. 1991. ‘A stochastic and dynamic vehicle routing problem in the Euclidean plane’, Operations Research 39, pp. 601–615. [4] Bertsimas, D. and Van Ryzin, G. 1993. ‘Stochastic and dynamic vehicle routing in Euclidean plane with multiple capacitated vehicles’, Operations Research 41, pp. 60–76. [5] 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. [6] Chau, K. W. 2007. ‘Application of a PSObased neural network in analysis of outcomes of construction claims’. Automation in Construction 16(5), pp. 642646. [7] Cheng, C. T., Wang, W. C., Xu, D. M. & Chau, K. W. 2008. ‘Optimizing hydropower reservoir operation using hybrid genetic algorithm and chaos’. Water Resources Management 22(7), pp. 895909. [8] Current, J. & Min, H. 1986. ‘Multiobjective design of transportation networks: Taxonomy and annotation’, European Journal of Operational Research 26, pp. 187–201. [9] Deo, N. and Pang, C. 1984. ‘Shortest path algorithms: Taxonomy and annotation’, Networks 14, pp. 275–323. [10] Dijkstra, E. W. 1959. ‘A note on two problems in connection with graphs’. Numerical Mathematics 1, pp. 269271. [11] Dreyfus, S. 1969 ‘An appraisal of some shortest path algorithms’. Operations Research 17, pp. 395412. [12] Fan, Y. Y., Kalaba, R. E. & Moore, J. E. 2005. ‘Shortest Path in Stochastic Networks with Correlated Link Costs’, Computers and Mathematic with Applications 49, pp. 15491564. [13] Frank, H. 1969. ‘Shortest paths in probabilistic graphs’, Operations Research 17 pp. 583–599. [14] Fu, L. and Rilett, L. R. 1998. ‘Expected shortest paths in dynamic and stochastic traffic networks’, Transp. Res. 32(7), pp. 499–516. [15] Hall, R. 1986. ‘The fastest path through a network with random timedependent travel time’. Transportation Science 20(3), pp. 182188. [16] Huang, Z. K. & Chau, K. W. 2008. ‘A New Image Thresholding Method Based on Gaussian Mixture Model’. Applied Mathematics and Computation 205(2), pp. 899907. [17] Ji, X. 2005. ‘Models and algorithm for Stochastic Shortest Path problem’, Applied Mathematics and Computation 170(1), pp. 503–514. [18] Jia, W., Ling, B., Chau, K. W. & Heutte, L. 2008. ‘Palmprint Identification Using Restricted Fusion’. Applied Mathematics and Computation 205(2), pp. 927934. [19] Kaufman, E., Lee, J. & Smith, R. L. 1993. Fastest paths in timedependent networks for intelligent vehicle highway systems application. IVHS Journal 1(1), pp. 111. [20] Lin, J. Y., Cheng, C. T. & Chau, K. W. 2006. ‘Using support vector machines for longterm discharge prediction’, Hydrological Sciences Journal 51(4), pp. 599612. [21] Loui, P. 1983. ‘Optimal paths in graphs with stochastic or multidimensional weights. Comm’. ACM 26, pp. 670676. [22] Martin, J. 1965. ‘Distribution of time through a directed acyclic network’, Operations Research (13), pp. 46–66. [23] Martins, E. 1984. ‘On a multicriteria shortest path problem’, European Journal of Operational Research (16), pp. 236–245. [24] Miller, E. D., Mahmassani, H. S. & 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 2, pp. 17161721. [25] Mirchandani, B. P. 1976. ‘Shortest distance and reliability of probabilistic networks’, Computer and Operations Research 3, pp. 347–355. [26] Mirchandani, B. P. & Soroush, H. 1986. ‘Routes and flows in stochastic networks. Advanced Schools on Stochastic in Combinatorial Optimization, eds G. Angrealtta, F. Mason and P’. Serafini, CISM. Udine, Italy, pp. 129177. [27] Mirchandani, P. 1976. ‘Shortest distance and reliability of probabilistic networks’, Computer and Operations Research 3, pp. 347–355. [28] Murthy, I. & Sarkar, S. 1996. ‘A relaxationbased pruning technique for a class of stochastic shortest path problems’. Transportation Science 30(3), pp. 220236. [29] Psaraftis, H. & Tsitsiklis, J. 1993. ‘Dynamic shortest paths in acyclic networks with Markovian arc costs’, Operations Research 41, pp. 91–101. [30] Sigal, C.E., Pritsker, A.A.B. & Solberg, J.J. 1980. ‘The stochastic shortest route problem’, Oper. Res. 28(5), pp. 1122–1129. [31] Taormina, R., Chau, K. W. & Sethi, R. 2012. ‘Artificial Neural Network simulation of hourly groundwater levels in a coastal aquifer system of the Venice lagoon’. Engineering Applications of Artificial Intelligence 25(8), pp. 16701676. [32] Ziliaskopoulos, A. K. & Mahassani, H. S. 1993. ‘Timedependent, shortestpath algorithm for realtime intelligent vehicle system applications’. Transportation Research Record 1408, TRB, National Research Council, Washington, DC., 94100.
