A Bus Crew Scheduling Problem with Eligibility Constraints and Time Limitations

Abstract

In this study we 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 our 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. We formulate a Tactical Fixed Job Scheduling Problem based binary programming model for the problem. In the formulation we 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 we 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 our optimal seeking solution procedure is quite effective in terms of solution time for instances with up to 120 tasks. © 2017 Elsevier B.V. All rights reserved.