Research Of Bus Crew Scheduling Problem Based On Parallel Ant Colony Algorithm With Hama

This paper studies of bus crew scheduling problem, and discusses the corresponding mathematical model and solving algorithm. Due to the disadvantage of time consumed, two interaction strategies parallel ant colony algorithm are established to improve the efficiency on today’s cutting-edge platform Hama. The main work is summarized as follows:Firstly. This paper studied the status of the bus crew scheduling problem, and analyses the three kinds of integrated scheduling methods. Also this paper discusses the principle of ant colony algorithm and parallel ant colony algorithm. At last the technical route is determined.Secondly, on the basis of the study Hama platform, This paper puts forward two kinds of scheduling problem in parallel ant colony algorithm to solve the bus driving model: coarse-grained master-slave parallel ant colony algorithm model and the optimal solution of coarse-grained parallel ant colony algorithm model.The two model chosees MMAS algorithm as basic.The coarse-grained master-slave parallel ant colony algorithm model used in the pheromone matrix as interactive content, and send information in master-slave mode;The Coarse-grained parallel optimal solution takes the current optimal solution of child ant colony and the ant path as interactive content.Two parallel ant colony algorithm model is established in order to improve the solution efficiency and better results are obtainedFinally, This paper does empirical analysis on the typical bus lines. The test environment is four sets of virtual organization parallel computing cluster.The experimental results show that, on a single machine running, general ant colony algorithm to solve the results compared with line actual situation, can reduce the use of a class type;On cluster running, two kinds of parallel algorithm has better efficiency, compared with general ant colony algorithm.The coarse-grained master-slave mode and coarse-grained optimal solution interaction mode could get 2.90 and 3.41 in the speedup. But The coarse-grained master-slave mode havs better quality in solving than t coarse-grained optimal solution interaction mode. Because the previous one uesed the strategy of pheromone matrix interaction, which can make the search space bigger.This paper studies the parallel ant colony algorithm based on Hama and the parallel ant colony interaction designing, which has a certain guiding significance.