Research And Application Of K Shortest Path Problem

The problem of the k shortest route is an important branch of the class of the shortest route algorithms. It is the primary part of the Graph Theory and the Network Optimization as well. Besides the shortest route, under different conditions, it is necessary to consider the second shortest one, the third shortest one and so on. That is to say, several routes rather than the shortest one should be obtained in the network. As a result, it is meaningful to investigate the problem of the k shortest route, which is valuable and applicable in practice.This thesis has improved the traditional swarm intelligence method and solves the problem of the k shortest route. The main parts are as follows.At first, this thesis points out that an improper division of group will affect the speed of convergence in the flog-skip algorithm. So a novel division of group is proposed. Meanwhile, based on the Yen algorithm—which cares about the diverging route—a new learning strategy is put forward to solve the problem of the k shortest route. The simulation results show that the improved algorithm contributes to better effect concerning the precision of solutions, the efficiency and the stability.And then, based on the genetic algorithm, the coding of chromosome is redefined. An adaptive rule is used to determine the rate of chiasma and the rate of mutation. In such a mixture genetic algorithm, the new formulas of the rate of chiasma and the rate of mutation speed up the convergence. Moreover, to overcome early stop of the algorithm, the Metropolis criterion in the analog anneal algorithm is taken into account to choose the individuals in the next generation.At last, the Prim algorithm is applied to solve out the minimal generating trees of graphs. Since to solve the problem of the k shortest route is to obtain the minimal generating trees of graphs, an algorithm based on the minimal generating tree is proposed in this thesis. At the same time, a new method is presented to build the graph. And relative properties and inferences are shown. In addition, this thesis also analyzes the time-complexity. Finally, feasibility of the algorithm is exemplified.