Article-detailsAdvances in Industrial Engineering and Management
 Article-details | AIEM

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 )



ISSN:2222-7059 (Print);EISSN: 2222-7067 (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
Author affiliation :
Corresponding author img Corresponding author at : Corresponding author img  

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.5-10, 2013

Full Text : PDF(size: 139.02 kB, pp. 5-10, Download times:2388)

DOI : 10.7508/AIEM-V2-N1-5-10

[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. 87-90.
[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. 551-556. Chania, Greece.
[6] Chau, K. W. 2007. ‘Application of a PSO-based neural network in analysis of outcomes of construction claims’. Automation in Construction 16(5), pp. 642-646.
[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. 895-909.
[8] Current, J. & Min, H. 1986. ‘Multi-objective 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. 269-271.
[11] Dreyfus, S. 1969 ‘An appraisal of some shortest path algorithms’. Operations Research 17, pp. 395-412.
[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. 1549-1564.
[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 time-dependent travel time’. Transportation Science 20(3), pp. 182-188.
[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. 899-907.
[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. 927-934.
[19] Kaufman, E., Lee, J. & Smith, R. L. 1993. Fastest paths in time-dependent networks for intelligent vehicle highway systems application. IVHS Journal 1(1), pp. 1-11.
[20] Lin, J. Y., Cheng, C. T. & Chau, K. W. 2006. ‘Using support vector machines for long-term discharge prediction’, Hydrological Sciences Journal 51(4), pp. 599-612.
[21] Loui, P. 1983. ‘Optimal paths in graphs with stochastic or multidimensional weights. Comm’. ACM 26, pp. 670-676.
[22] Martin, J. 1965. ‘Distribution of time through a directed acyclic network’, Operations Research (13), pp. 46–66.
[23] Martins, E. 1984. ‘On a multi-criteria 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 Time-Dependent, Stochastic Arc Costs’. IEEE International Conference on Systems, Man, and Cybernetics. Humans, Information and Technology 2, pp. 1716-1721.
[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. 129-177.
[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 relaxation-based pruning technique for a class of stochastic shortest path problems’. Transportation Science 30(3), pp. 220-236.
[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. 1670-1676.
[32] Ziliaskopoulos, A. K. & 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., 94-100.

Terms and Conditions   Privacy Policy  Copyright©2000- 2014 American Scientific Publishers. All Rights Reserved.