A wave time-varying neural network for solving the time-varying shortest path problem

In this paper, we propose a wave time-varying neural network (WTNN) to solve the time-varying shortest path problem (TSPP). The complexity of the TSPP is NP-hard, so it is difficult to solve this problem using traditional algorithms, such as the Dijkstra algorithm. In contrast, the proposed WTNN can arrive at the global optimal solution of three TSPP variant problems with different waiting polices (viz. arbitrary waiting, restricted waiting, and zero waiting at nodes). The WTNN is a novel neural network framework based on time-varying neurons, the structure of which depends on the network topology of the problem to be solved. All neurons on the WTNN are computed in parallel, and each neuron consists of seven parts: input, wave receiver, status updater, status memorizer, wave generator, wave sender, and output. Waves are vehicles for transmitting information between neurons. The underlying idea of the WTNN is based on the following mechanism: all neurons are updated in steps; after updating, each neuron calculates the temporary shortest path and transmits that temporary path to its successor through the wave; and the destination neuron then calculates the final shortest path among all the received waves and outputs optimal solution. The performance evaluation results are based on three public data sets and demonstrate that the proposed WTNN outperforms other existing algorithms.