Solving Public Transit Scheduling Problems

• Author(s): Mesquita, Marta ; Moz, Margarida ; Paias, Ana ; Paixão, José ; Pato, Margarida Vaz ; Respício, Ana
• Date: 2008
• Persistent ID: http://hdl.handle.net/10400.5/1425
• Origin: Repositório da UTL
• Subject(s): binary linear programming; vehicle scheduling; crew scheduling; driver rostering; multi-objective problems
• Document Type: Other
• Language: English

Description

Operational planning within public transit companies has been extensively tackled but still remains a challenging area for operations research models and techniques. This phase of the planning process comprises vehicle scheduling, crew scheduling and rostering problems. In this paper, a new integer mathematical formulation to describe the integrated vehicle-crew-rostering problem is presented. The method proposed to solve this multi-objective problem is a sequential algorithm considered within a preemptive goal programming framework that starts from the solution of an integrated vehicle and crew scheduling problem and ends with the solution of a driver rostering problem. Feasible solutions for the vehicle and crew scheduling problem are obtained by combining a column generation scheme with a branch-and-bound method. These solutions are the input of the rostering problem, which is tackled through a mixed binary linear programming approach. An application to real data of a Portuguese bus company is reported and shows the importance of integrating the three scheduling problems.