Research On Crew Scheduling By Generate-and-select Approach

Efficient crew scheduling could provide huge saving in Public TransportationSystems. However, crew scheduling problem has been tangled with lots of laboragreement rules determined by the government, the transport operators and the localorganizations. So the crew scheduling problem is a hard combinatorial problem,specifically a NP-hard problem, which has been research deeply and thoroughly.In China, the public transportation system (including the airplane, passenger lines,the subway and bus system) has a few special labor requirements, for example, meal breakis normally required to be taken during the conventional time ranges for lunch or dinner,which is called a Chinese meal break rule (CMR) to distinguish from the western ones,and makes the existed crew scheduling approaches encounter difficulty. So lots ofapproaches among the western main researches have been unable to be directly used forcrew scheduling problem in general Chinese public system. In the other hand, theresearches in this area in china developed late and not quite practical yet. This situationhas made the usage of computer in crew scheduling practice encountered lots of obstacles,and basically relied on simulating manual schedulers which could be quite difficult get theoptimal solution considering the crew and the vehicle’s full usage efficiency and laboragreements.Based on the ‘generating and selecting’ approach to solve the crew schedulingproblem，this paper proposes an approach to handle the CMR in the phase of ‘generating’.Taking advantages of the characteristics of CMR and problem domain knowledge, aheuristic-based approach is first proposed to select some promising relief opportunities(ROs), based on which a shift generation approach is then devised to generate a large setof potential shifts that satisfy the CMR. Experimental results from12groups of real-worldproblem instances demonstrate the success of the proposed approach, which can greatlyreduce the number of potential shifts generated. Therefore, it is suggested that large scalecrew scheduling problems with Chinese meal break rules could be solved efficiently.