The Research And Implementation Of The Shortest Path Optimization Algorithm

Shortest Path Problem is one of the basic problems in networks. It has been widely applied in the areas of Intelligent Transportation System (ITS), Geographic Information Science, Path Planning, Computer Network Communication, etc. Based on systematically summarizing the relevant works on shortest path problem, this dissertation studies on dynamically updating shortest path problem, traveling salesman problem and multiple traveling salesman problem, and gains several achievements on these domains. The major workings of this dissertation are as below:1. In dynamic networks, it is a stochastic process that the the topology changes dynamicaly in shortest path tree. However, if we reconstruct or update the shortest path tree by static algorithm when the topology is changed, the system load is so heavy that it is unacceptable. Ball-and-String Model is an widely applied algorithm which can dynamically update shortest path tree (SPT), but exists redundant computation. This dissertation presents a new dynamic SPT algorithm that optimizes the processing of edges in Ball-and-String Model. New algorithm raises the efficiency of dynamically updating SPT. Additionally, new algorithm implements adding nodes or deleting node in SPT. Experimental results show that new algorithm is more efficient than Ball-and-String Model.2. This dissertion studies on Traveling Salesman Problem and proposes a new method, called as Cycle-optimization, for solving TSP. Cycle-optimization algorithm combines2-OPT with branch-and-bound algorithm to optimize a given cycle. Using2-OPT is in order to optimize the given cycle, and using branch-and-bound algorithm is in order to reconstruct the given cycle. The new algorithm utilizes two factors to restrict the scale of branch-and-bound algorithm and the convergence conditions. Based on the balance between efficiency and the degree of optimization, the values of two factors are determined by Cycle-optimization. Illuminated by experiment, the optimal degree of cycle-optimization is better than that of2-OPT.3. This dissertion presents a model, SModel, to simplify an initial network. SModel deletes redundant edges of a given network, then, the initial network is transformed into a connected network where the reatio of (the number of edges)/(the number of nodes) is less than1.2. Based on SModel, this dissertion proposes three methods for solving the variations of multiple traveling salesmen problem (MTSP), which include single depot closed paths (SDC_MTSP), single depot open paths (SDO_MTSP), and multiple depots closed paths (MDC_MTSP) problems. Based on an SModel, new algorithms are with the same processures which are simplifying the initial network, adjusting the paths of SModel, and achieving a solution set. The experiment shows that the SModel can be used to solve variations of MTSP. Compared with previous workings, the proposed algorithms are with good stability, fast convergence, and can achieve the same optimum degree while cost less than that of previous workings.