A Minimum Resource Neural Network Framework for Solving Multiconstraint Shortest Path Problems
- 10 January 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks and Learning Systems
- Vol. 25 (8), 1566-1582
- https://doi.org/10.1109/tnnls.2013.2293775
Abstract
Characterized by using minimum hard (structural) and soft (computational) resources, a novel parameter-free minimal resource neural network (MRNN) framework is proposed for solving a wide range of single-source shortest path (SP) problems for various graph types. The problems are the k-shortest time path problems with any combination of three constraints: time, hop, and label constraints, and the graphs can be directed, undirected, or bidirected with symmetric and/or asymmetric traversal time, which can be real and time dependent. Isomorphic to the graph where the SP is to be sought, the network is activated by generating autowave at source neuron and the autowave travels automatically along the paths with the speed of a hop in an iteration. Properties of the network are studied, algorithms are presented, and computation complexity is analyzed. The framework guarantees globally optimal solutions of a series of problems during the iteration process of the network, which provides insight into why even the SP is still too long to be satisfied. The network facilitates very large scale integrated circuit implementation and adapt to very large scale problems due to its massively parallel processing and minimum resource utilization. When implemented in a sequentially processing computer, experiments on synthetic graphs, road maps of cities of the USA, and vehicle routing with time windows indicate that the MRNN is especially efficient for large scale sparse graphs and even dense graphs with some constraints, e.g., the CPU time taken and the iteration number used for the road maps of cities of the USA is even less than ~2% and 0.5% that of the Dijkstra's algorithm.Keywords
Funding Information
- Chinese National Science Foundation (61070137, 91130006, 61201312)
- Research Fund for the Doctoral Program of Higher Education of China
This publication has 46 references indexed in Scilit:
- An improving dynamic programming algorithm to solve the shortest path problem with time windowsElectronic Notes in Discrete Mathematics, 2010
- Real-Time Robot Path Planning Based on a Modified Pulse-Coupled Neural Network ModelIEEE Transactions on Neural Networks, 2009
- A modified pulse coupled neural network for shortest-path problemNeurocomputing, 2009
- Finding the first K shortest paths in a time-window networkComputers & Operations Research, 2004
- Finding All Hops Shortest PathsIEEE Communications Letters, 2004
- Output-threshold coupled neural network for solving the shortest path problemsScience China Information Sciences, 2004
- Time-Dependent, Label-Constrained Shortest Path Problems with ApplicationsTransportation Science, 2003
- Finding the shortest path in the shortest time using PCNN'sIEEE Transactions on Neural Networks, 1999
- Finding the Hidden Path: Time Bounds for All-Pairs Shortest PathsSIAM Journal on Computing, 1993
- Observation of periodic waves in a pulse-coupled neural networkOptics Letters, 1993