Research On Resource-constrained Time-varying Shortest Path Problem

Resource-constrained time-varying shortest path problem is an important problem in the field of network optimization.The existing algorithms have the disadvantages of large errors and low efficiency when solving this kind of problems.In order to overcome these shortcomings,this paper proposed three neural network models to solve three different resource-constrained time-varying shortest path problems.The main innovations are as follows:First,we proposed the hop-constrained time-varying neural network(HTNN)model and algorithm,which can obtain the optimal solution of the hop-constrained time-varying shortest path problem.HTNN is a neural network driven by auto-waves,which is characterized by parallel computing and does not require training.The hopconstrained time-varying neuron on HTNN has a seven-layer structure.The problem to be solved is a resource-constrained time-varying shortest path problem on a singleweight time-varying network.The experimental simulation results on the international standard dataset show the superiority of HTNN.Second,for obtain the optimal solution of the cost-constrained time-varying shortest path problem,the cost-constrained time-varying neural network(CTNN)models and algorithms were proposed.CTNN is a time-wave neural network that is calculated in parallel and does not require training.The cost-constrained time-varying neuron on CTNN has a six-layer structure.The problem to be solved is a resourceconstrained time-varying shortest path problem on a dual-weight time-varying network.The experimental simulation results on the international standard dataset show the superiority of CTNN.Third,the delay-constrained time-varying neural network(DTNN)model and algorithm were proposed for obtain the optimal solution of the delay-constrained timevarying shortest path problem.Delay-constrained time-varying shortest path problem is another resource-constrained time-varying shortest path problem on dual-weight time-varying networks,which includes three variant problems: zero waiting delayconstrained time-varying shortest path problem,arbitrary waiting delay-constrained time-varying shortest path problem and restrained waiting delay-constrained timevarying shortest path problem.The proposed DTNN is based on a delay-constrained time-varying neuron with a seven-layer structure.Unlike traditional algorithms that can only solve one variant problem,DTNN can solve three variant problems with delayconstrained time-varying shortest path at the same time without any modification.The experimental results on the international standard dataset show that DTNN has distinct advantages over existing algorithms.