The solution to the route selection problem of transit was converted to minimum spanning tree (MST) problem. Compared with the classic MST algorithm, an improved genetic algorithm is introduced to search the minimum spanning trees based on the graphic theory. This algorithm uses binary code to represent the problem of minimum spanning trees and uses the depth first search method to determine the connectivity of the graph. The corresponding fitness function, single parent transposition operator, single parent reverse operators and controlling evolutionary strategies are designed to improve its speed and efficiency. In comparison with traditional algorithms, it can acquire a set of minimum spanning trees during one genetic evolutionary process, make decision-department consider synthetically the various factors to do comprehensive evaluation and decision-making.
展开▼