An improved genetic algorithm for the large-scale rural highway network layout (Q1718009)

Summary: For the layout problem of rural highway network, which is often characterized by a cluster of geographically dispersed nodes, neither the Prim algorithm nor the Kruskal algorithm can be readily applied, because the calculating speed and accuracy are by no means satisfactory. Rather than these two polynomial algorithms and the traditional genetic algorithm, this paper proposes an improved genetic algorithm. It encodes the minimum spanning trees of large-scale rural highway network layout with Prufer array, a method which can reduce the length of chromosome; it decodes Prufer array by using an efficient algorithm with time complexity \textit{o(n)} and adopting the single transposition method and orthoposition exchange method, substitutes for traditional crossover and mutation operations, which can effectively overcome the prematurity of genetic algorithm. Computer simulation tests and case study confirm that the improved genetic algorithm is better than the traditional one.