Research Of Crew Scheduling Problem Based On Parallel Genetic Algorithm

With the rapid development of urbanization and motorization in China,the contradiction between traffic supply and demand becomes more and more serious.An important way to solve this problem is to develop public transport.As the core content of the public transportation system,operation schedule and dispatch is the basic guarantee for the realization of operational tasks.Crew scheduling is an important part of the operation scheduling and dispatching work of public transport enterprises,which plays a decisive role in efficiency and operation cost of public transport.Scientific and reasonable scheduling plan can improve the quality of service,but also can effectively reduce the operating costs of enterprises.Bus crew scheduling problem is recongnized NP-hard problem,and the difficulty of the problem lies in finding the optimal solution or approximate optimal solution in a reasonable time.The optimal solution is usually obtained by integer programming method.But in practical problems,integer programming method is hard to guarantee the solving time when the sacle of the problem is large.Although the heuristic algorithm can not find the optimal result,it can balance the solving time and the solution quality.As a kind of heuristic algorithm,genetic algorithm has good global search ability and parallel ability,but the algorithm also has the disadvantages of low convergence rate and premature convergence.In order to overcome the shortcoming of genetic algorithm,Optimal Solution of Corse-Grained Parallel Model based on Hama(H-OSCGPM)is designed to improve the efficiency and quality of traditional genetic algorithm.The content and innovation of this paper are as follows:Firstly,this paper introduces the crew scheduling problem in the filed of public transportation,reveals the difficulties in solving the problem,and summarizes the existing research results of the problem.Then,this paper establishes a mathematical baseed on the existing research results.Secondly.Crew Scheduling Orirented Genetic Algorithm(CSOGA)is desigenecd to improve the performance and guarantee the quality of the parallel algorithm in the serial iterative.CSOGA improves the mutan operation of the tradinal genetic algorithm,and the effeetiveness of the algorithm was verified by an instance.Then,parallel computational model H-OSCGPM:s designed based on the idea of coarse grained parallel.In addition,the migration strategy and the interactive processing of messages are described in detail,and the number individual migration and migration interaction cycle of H-OSCGPM is determined under different population size.Finally,six representative lines of Beijing Bus Group are selected and verified in this paper.The results of the serial and parallel algorithms of this paper are compared and analyzed.The results show that the H-OSCGPM is more efficient and effective.The speedup can respectively reach to 3.47,2.96,2.96,2.45,2.34 and 3,20 under the premise of improving the quality of the solution.And the speedup is positively correlated with the size of the problem.The larger the scale of the problem is,the higher the speedup is.In summary,the parallel genetic algoritnm can find optimal solution in reasonable time.And the parallel algorithm provides theoretical support for the application in other fields.