Studies On Optimal Path Algorithms And Its Applications In TimeVarying And Stochastic Networks  Posted on:20030325  Degree:Doctor  Type:Dissertation  Country:China  Candidate:G Z Tan  Full Text:PDF  GTID:1118360095455222  Subject:Computer application technology  Abstract/Summary:  PDF Full Text Request  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 variabletime 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 timedependent network, and (2) the expected shortest path problem in timedependent 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 timedependent 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 timedependent network has been presented. Under no any constraint conditions, an algorithm for rinding least time path in timedependent 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 timedependent network is proposed, which make least time path algorithm in timedependent network can be applied for ITS because whole solution method of application for ITS is given (3)A distributed routing protocol for heterogeneous timedependent 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 shortestpath algorithms for HTDN and propose an efficient distributed routing protocol to calculate allpairs minimaldelay paths in HTDN and prove its correctness.In the aspect of the stochastic and timedependent 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 timedependent 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 timedependent 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 timedependent 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 timedependent network. Therefore, for the first time, this paper proposes the NetworkTree Model (NTM) and wholly new, high performance algo...
 Keywords/Search Tags:  timedependent network, stochastic network, large scale network, shortest path algorithm, parallel algorithm, routing protocol  PDF Full Text Request  Related items 
 
