Studies On Optimal Path Algorithms And Its Applications In Time-Varying And Stochastic Networks

The shortest path problem is a core model that lies at the heart of network optimization. It assume that the weight of the arcs in traditional network is static and a determinate number, which is not true in many fields such as intelligent transportation systems(ITS) and computer network and communication fields. The optimal path problems in variable-time and stochastic network break through the limit of traditional shortest path problems and become foundation theory in ITS .The new real problems make the optimal path computing to be more difficult.This dissertation aim at the research on the new problems and existing problems: (1) the shortest path problem in time-dependent network, and (2) the expected shortest path problem in time-dependent and stochastic network, and (3)real time calculation of shortest path for large scale network, and (4) application research on the route choice problems in ITS and the routing problems in computer network and communication based on theory and algorithms in this dissertation.hi the aspect of the time-dependent network, our work is divided into three parts: (l)the traditional theory of finding shortest path has theoretically proved to be of limitation for the first time. The sufficiency and necessary condition to optimize path in time-dependent network has been presented. Under no any constraint conditions, an algorithm for rinding least time path in time-dependent network is designed and implemented. The validity of algorithm has been established.(2) Using intelligent neuron model based on linear independent function presented hi this paper composes the generalized neural network ,and utilizing this neural network predicts traffic flow in transportation network. Further, prediction method of the traveling time of each arc in time-dependent network is proposed, which make least time path algorithm in time-dependent network can be applied for ITS because whole solution method of application for ITS is given (3)A distributed routing protocol for heterogeneous time-dependent networks (HTDN)is proposed for the first time. HTDN model contains both nodes allowing data packets to wait and nodes forbidding waiting. We theoretically research shortest-path algorithms for HTDN and propose an efficient distributed routing protocol to calculate all-pairs minimal-delay paths in HTDN and prove its correctness.In the aspect of the stochastic and time-dependent network, We consider the planning route problem of uncertain edge costs, with potential probabilistic dependencies and time dependencies among the costs, which make problem become very difficulty. We achieve main effort in this aspect as follows: (1) To convert the optimal path problems in time-dependent and stochastic network to system reliability problem, and to identify a weaker consistency reliabilitycondition that justifies a generalized dynamic programming approach based on reliable priority. We present a algorithm based reliability theory and prove that it produces optimal paths under time-dependent and stochastic cost; and (2) A new discriminant approach for stochastic dominance that reduce two discriminant parameter to one parameter is presented. An algorithm on K expected life path based on reliability theory and an algorithm on K expected travel time path based on stochastic dominance are presented for the first time; and (4) The distributed and parallel algorithm finding K expected shortest path in stochastic and time-dependent network is presented.Real time calculation for shortest path is one of bottleneck problem in large scale network, therefore, We present new the hierarchical network model and design the optimal and approximate algorithms for calculating shortest paths based on Hierarchical Networks in large scale network. But it is difficulty to expand the existing hierarchical network models and algorithms for finding optimal path problems in the stochastic and time-dependent network. Therefore, for the first time, this paper proposes the Network-Tree Model (NTM) and wholly new, high performance algo...