Research And Implementation Of Bus Crew-scheduling Algorithm Based On Set-covering Problem

With the rapid development of urban economy and rapid expansion of population, city scale expands unceasingly, traffic demand also increases ceaselessly, and traffic congestion is very prominent. Development of public transport is one of the most important ways to solve this problem. And a fair and reasonable crew-scheduling plan is more meaningful for transferring personnel staffs'activeness, improving work efficiency, has important significance to improve social benefits of the public transport.Bus scheduling problem based on vehicle schedule, aimed at least duties and minimum cost. It focuses on how to arrange a group of bus crew reasonable to complete established vehicle schedule, ensure that each vehicle task be done by only one crew. This problem is recognized as NP-hard problem, the study of it has important realistic significance and theoretical value.The thesis first introduces the development of the crew-scheduling problem and explains the definitions of the crew-scheduling problem. Established the mathematical model with set-covering based on the research on constraint and complexity of crew-scheduling problem. As the column generation algorithm does not need to repeat all the columns inspection, just do optimal inspection for selected subset.thus we use column generation algorithm to solve the model of crew-scheduling problem. Then, combined with the Beijing public transportation actual data, also with the aid of the c# language and mathematical modeling software Lingo 11.0, the thesis realize the column generation algorithm, work out bus crew-scheduling plan. Finally, compare to the artificially operating crew-scheduling, found the optimization effect is remarkable, and proved that this method is feasible.