A Bus Crew Scheduling Problem with Eligibility Constraints and Time Limitations

In this study, the authors consider a real life crew scheduling problem (CSP) of a public bus transportation authority, where the objective is to determine the optimal number of different types of crew members with a minimum cost that cover a given set of tasks regarding working and spread time limitations. Each driver has a spread time limit from the start time to the end time of his/her shift, including the idle times. Additionally, a driver cannot exceed the maximum total working time limit. The processing times of the tasks assigned to each driver are included in his/her working time, as well as the sequence-dependent setup times. As the study is inspired from a real life CSP, the tasks can require different types of vehicles that require different crew capabilities. Therefore, there are several crew classes based on the competencies required to use certain vehicle types inducing eligibility constraints in the problem. The authors formulate a Tactical Fixed Job Scheduling Problem based binary programming model for the problem. In the formulation, the authors consider only processing times of tasks as working time. In order to avoid defining an additional sequence control variable that explodes the model size and in turn ruins solution performance, the authors develop an iterative valid inequality generation scheme, which eliminates task sequences exceeding the total working time when setup times are included. The performance of the developed model is investigated through a comprehensive experimentation and the numerical results are reported. The results show that the authors optimal seeking solution procedure is quite effective in terms of solution time for instances with up to 120 tasks.


  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01636366
  • Record Type: Publication
  • Files: TRIS
  • Created Date: May 26 2017 11:31AM