Research On Shortest Path Problems Based On Genetic Algorithms

Shortest Path (SP) problems are traditional combinatorial optimization problems. And SP problems are common in real-word applications, such as car navigation problems and network routing problems. There are many kinds of SP problems, such as Static SP (SSP) problems, Dynamic SP (DSP) problems, Single-Objective SP (SOSP) problems and Multi-Objective SP (MOSP) problems. In this paper, the DSP problems, MOSP problems and Dynamic MOSP (DMOSP) problems are investigated. The classical optimization method and the evolutionary optimization method are combined, and the hybrid method is proposed. For more details, the main work in this paper is described as follows.(1) For SP problems in static topologies, there are many deterministic algorithms. However, in dynamic topologies, these deterministic algorithms are not efficient due to the necessity of restart. In this paper, an improved Genetic Algorithm (GA) with four local path replacement operators for Dynamic Shortest Path (DSP) problems is proposed. The local path replacement operators are inspired by Dijkstra’s Algorithm and carried out when the topology changes to generate local shortest path trees, which are used to promote the performance of the individuals in the population. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes. The experimental results show that the proposed algorithm could obtain the solutions which adapt to new environments rapidly and produce high-quality solutions after environmental changes.(2) In real-word applications, some problems are multi-objective. In MOSP problems, each edge owns multiple different costs corresponding to different objectives. In this paper, an algorithm combining the k-th Shortest Path algorithm and the NSGA-Ⅱ, named as KSPNSGA, is proposed to solve the multi-objective shortest path problems. For the KSPNSGA, in each generation, a random weight vector is created, and the multiple costs of each edge are converted into a weighted cost using the weight vector. Furthermore, the worst individual in the population is replaced by the k-th shortest path to improve the search ability of the algorithm, where the k-th shortest path corresponds to the topology with the weighted cost. The experiments show the proposed algorithm could get better solutions and perform more steadily than the NSGA-II by visiting the same number of the edges.(3) The environment for some problems is dynamic. Similarly, the environment for MOSP problems is dynamic in some cases. For DMOSP problems, the proposed KSPNSGA for MOSP problems is modified, and DKSPNSGA is proposed. Namely, in each generation, some individuals in the population are replaced by some immigrated individuals, so that the algorithm could adapt to the new environment.