Abstract
The shortest path problem is an archetypal combinatorial optimization problem arising in a variety of application settings. For real-time applications, parallel computational approaches such as neural computation are more desirable. This paper presents a new recurrent neural network with a simple structure for solving the shortest path problem (SPP). Compared with the existing neural networks for SPP, the proposed neural network has a lower model complexity; i.e., the number of neurons in the neural network is the same as the number of nodes in the problem. A simple lower bound on the gain parameter is derived to guarantee the finite-time global convergence of the proposed neural network. The performance and operating characteristics of the proposed neural network are demonstrated by means of simulation results.
The work described in the paper was supported by the Research Grants Council of the Hong Kong Special Administrative Region, China, under Grants CUHK417608E and CUHK417209E.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bodin, L., Golden, B., Assad, A., Ball, M.: Routing and scheduling of vehicles and crews: The state of the art. Comput. Oper. Res. 10(2), 63–211 (1983)
Ephremides, A., Verdu, S.: Control and optimization methods in communication network problems. IEEE Transactions on Automatic Control 34(9), 930–942 (1989)
Jun, S., Shin, K.: Shortest path planning in distributed workspace using dominance relation. IEEE Trans. Robot. Automat. 7, 342–350 (1991)
Antonio, J.K., Huang, G.M., Tsai, W.K.: A fast distributed shortest path algorithm for a class of hierarchically clustered data networks. IEEE Trans. on Computers 41, 710–724 (1992)
Tank, D., Hopfield, J.: Simple neural optimization networks: An a/d converter, signal decision circuit, and a linear programming circuit. IEEE Transactions on Circuits and Systems 33(5), 533–541 (1986)
Wang, J.: A recurrent neural network for solving the shortest path problem. IEEE Transactions on Circuits and Systems-I 43(6), 482–486 (1996)
Wang, J.: Primal and dual assignment networks. IEEE Transactions on Neural Networks 8(3), 784–790 (1997)
Wang, J.: Primal and dual neural networks for shortest-path routing. IEEE Transactions on Systems, Man, and Cybernetics-A 28(6), 864–869 (1998)
Xia, Y., Wang, J.: A discrete-time recurrent neural network for shortest-path routing. IEEE Transactions on Automatic Control 45(11), 2129–2134 (2000)
Liu, Q., Wang, J.: A one-layer recurrent neural network with a discontinuous activation function for linear programming. Neural Computation 20(5), 1366–1383 (2008)
Bazaraa, M., Sherali, H., Shetty, C.: Nonlinear Programming: Theory and Algorithms, 3rd edn. John Wiley & Sons, Hoboken (2006)
Liu, Q., Wang, J.: A one-layer recurrent neural network for convex programming. In: Proc. IEEE International Joint Conference on Neural Networks, pp. 83–90 (2008)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Liu, Q., Wang, J. (2010). A One-Layer Dual Neural Network with a Unipolar Hard-Limiting Activation Function for Shortest-Path Routing. In: Diamantaras, K., Duch, W., Iliadis, L.S. (eds) Artificial Neural Networks – ICANN 2010. ICANN 2010. Lecture Notes in Computer Science, vol 6353. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15822-3_61
Download citation
DOI: https://doi.org/10.1007/978-3-642-15822-3_61
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15821-6
Online ISBN: 978-3-642-15822-3
eBook Packages: Computer ScienceComputer Science (R0)