A decomposition approach for the integrated vehicle-crew-roster problem with days-off pattern

• The objective of this paper is the research on optimization methodologies for a complete integration of vehicle scheduling, crew scheduling and driver rostering problems so as to develop efficient algorithms.
• We have modeled the integrated vehicle-crew-roster problem as a new integer linear programming problem.
• We have developed a heuristic approach based on Benders decomposition to solve the problem.
• Computational experience was performed using data from two bus companies in Portugal as well as random data available in the literature.
• Computational results show that the presented approach outperforms the traditional sequential approach regarding the reduction of operational costs and driver rosters balance.

The integrated vehicle-crew-roster problem with days-off pattern aims to simultaneously determine minimum cost vehicle and daily crew schedules that cover all timetabled trips and a minimum cost roster covering all daily crew duties according to a pre-defined days-off pattern. This problem is formulated as a new integer linear programming model and is solved by a heuristic approach based on Benders decomposition that iterates between the solution of an integrated vehicle-crew scheduling problem and the solution of a rostering problem. Computational experience with data from two bus companies in Portugal and data from benchmark vehicle scheduling instances shows the ability of the approach for producing a variety of solutions within reasonable computing times as well as the advantages of integrating the three problems.