Model of Time-dependent Network Paths and Two-level Optimal Intelligent Algorithm
Ruichun He · Journal of the China Railway Society · 2008
The shortest path problem is the core model that lies at the heart of network optimization.It assumes that the weight of the arcs in traditional networks is static and a determinate number,which is not true in many fields such as intelligent transportation systems and computer network and communication fields.The TDSP(Time-Dependent Shortest Path) problem is one of the problems derived from SP(Shortest Path).Comparing with the traditional SP,TDSP is of more practical meaning in the fields of communication networks and traffic and transportation networks.In some limited conditions,such as the FIFO network and no-FIFO network,there can be some instances of polynomial time algorithms for TDSP.However,it has been proved that there is not any polynomial time algorithm when the cost of the network arc is general functions.More universally,in the cases of not limiting characters of arc cost functions,the optimal model of TDSP is formulated,and the two-level optimal intelligent algorithm based on node priority encoding is presented in this paper.Finally,a numerical instance is given.