Dynamic Shortest Path Algorithm in Stochastic Traffic Networks Using PSO Based on Fluid Neural Network

Yanfang Deng, Hengqing Tong

.

DOI: 10.4236/jilsa.2011.31002                

Abstract

The shortest path planning issure is critical for dynamic traffic assignment and route guidance in intelligent transportation systems. In this paper, a Particle Swarm Optimization (PSO) algorithm with priority-based encoding scheme based on fluid neural network (FNN) to search for the shortest path in stochastic traffic networks is introduced. The proposed algorithm overcomes the weight coefficient symmetry restrictions of the traditional FNN and disadvantage of easily getting into a local optimum for PSO. Simulation experiments have been carried out on different traffic network topologies consisting of 15-65 nodes and the results showed that the proposed approach can find the optimal path and closer sub-optimal paths with good success ratio. At the same time, the algorithms greatly improve the convergence efficiency of fluid neuron network.

Keywords

Particle Swarm Optimization, Fluid Neuron Network, Shortest Path, Traffic Networks

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	L. Fu, D. Sun and L. R. Rilett, “Heuristic Shortest Path Algorithms for Transportation Applications: State of the Art,” Computers & Operations Research, Vol. 33, No. 11, 2006, pp. 3324-3343. doi:10.1016/j.cor.2005.03.027
[2]	D. Wang, B. Zhang, N. Jiang, Y. W. Jing and S. Y. Zhang, “Traffic Dynamics Based on the Shortest Path Routing Strategy,” Proceedings of the 21st Annual International Conference on Chinese Control and Decision Conference, Guilin, 17-19 June 2009, pp. 1106-1109.
[3]	R. Bellman, “On a Routing Problem,” Quarterly of Applied Mathematics, Vol. 16, 1958, pp. 87-90.
[4]	E. Dijkstra, “A Note on Two Problems in Connexion with Graphs,” Numerische Mathematik, Vol. 1, No. 1, 1959, pp. 269-271. doi:10.1007/BF01386390
[5]	A. Goldberg and T. Radzik, “A Heuristic Improvement of the Bellman-Ford Algorithm,” Applied Mathematics Letters, Vol. 6, No. 3, 1993, pp. 3-6. doi:10.1016/0893- 9659(93)90022-F
[6]	M. Ali and F. Kamoun, “Neural Networks for Shortest Path Computation and Routing Incomputer Networks,” IEEE Transactions on Neural Networks, Vol. 4, No. 6, 1993, pp. 941-954. doi:10.1109/72.286889
[7]	R. Wang, S. Guo and K. Okazaki, “A Hill-Jump Algorithm of Hopfield Neural Network for Shortest Path Problem in Communication Network,” Soft Computing-A Fusion of Foundations, Methodologies and Applications, Vol. 13, No. 6, 2009, pp. 551-558.
[8]	C. Ahn and R. Ramakrishna, “A Genetic Algorithm for Shortest Path Routing Problem and the Sizing of Populations,” IEEE Transactions on Evolutionary Com- putation, Vol. 6, No. 6, 2002, pp. 566-579. doi:10.1109/ TEVC.2002.804323
[9]	J. Kuri, N. Puech, M. Gagnaire and E. Dotaro, “Routing Foreseeable Lightpath Demands Using a Tabu Search Meta-Heuristic,” Proceedings of Global Telecommunica- tions Conference, New York, 17-21 November 2002, pp. 2803-2807.
[10]	N. R. Raidl and B. A. Julstrom, “A Weighted Coding in a Genetic Algorithm for the Degree-Constrained Minimum Spanning Tree Problem,” Proceedings of the 2000 ACM Symposium on Applied Computing, Como, 2000. doi:10. 1145/335603.335888
[11]	E. Elbeltagi, T. Hegazy and D. Grierson, “Comparison among Five Evolutionary-Based Optimization Algorithms,” Advanced Engineering Informatics, Vol. 19, No. 1, 2005, pp. 43-53. doi:10.1016/j.aei.2005.01.004
[12]	C. Mouser and S. Dunn, “Comparing Genetic Algorithms and Particle Swarm Optimisation for an Inverse Problem Exercise,” ANZIAM Journal, Vol. 46, 2004, pp. 174-181.
[13]	A. Salman, I. Ahmad and S. Al-Madani, “Particle Swarm Optimization for Task Assignment Problem,” Micro- processors and Microsystems, Vol. 26, No. 10, 2002, pp. 363-371. doi:10.1016/S0141-9331(02)00053-4
[14]	X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu and Q. X. Wang, “Particle Swarm Optimization-Based Algorithms for Tsp and Generalized Tsp,” Information Processing Letters, Vol. 103, No. 5, 2007, pp. 169-176. doi:10.1016/j.ipl. 2007.03.010
[15]	M. F. Tasgetiren, Y.-C. Liang, M. Sevkli and G. Gencyilmaz, “A Particle Swarm Optimization Algorithm for Makespan and Total Flowtime Minimization in the Permutation Flowshop Sequencing Problem,” European Journal of Operational Research, Vol. 177, No. 3, 2007, pp. 1930-1947. doi:10.1016/j.ejor.2005.12.024
[16]	G. Lei, “A Neuron Model with Fluid Properties for Solving Labyrinthian Puzzle,” Biological Cybernetics, Vol. 64, No. 1, 1990, pp. 61-67. doi:10.1007/BF0020 3631
[17]	H. Wen and Z. Yang, “Study on the shortest Path Algorithm Based on Fluid Neural Network of in-Vehicle Traffic Flow Guidance System,” Proceedings of the IEEE International Vehicle Electronics Conference, Changchun, 6-9 September 1999, pp. 110-113
[18]	J. Kennedy and R. Eberhart, “Particle Swarm Optimi- zation,” IEEE International Conference on Neural Net- works, Vol. 4, 1995, pp. 1942-1948.
[19]	M. Clerc,“The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimi- zation,” Proceedings of the IEEE Congress on Evolu- tionary Computation, Washington, 1999, pp. 1951-1957.