Track: Operations Research

Abstract

Generation of work shifts is an important issue in Bus Rapid Transit Systems, due to the impact caused by the costs of hiring drivers to carry out the routes. The generation of shifts consists of putting together work schedule blocks, in order to cover the operation of the routes specified by the transport system, in this case, the routes of the Colombian West-Center Metropolitan Area. To solve this problem, a two-phase solution methodology was proposed, based on a Column Generation Algorithm that combines the work blocks, minimizing the number of shifts. The study presents a comparison of the results obtained with the manual programming and the proposed methodology in real-world instances (Megabús, Colombia). The results show that the methodology reaches feasible solutions in reasonable computing times, and outperforms all the proposed solutions by skilled practitioners, decreasing the total number of shifts. Moreover, the algorithmic solution allows the coordinators to focus in the contingencies presented during the operation of the massive transit system; as shown in computational results, a task requiring approximately 8 hours of coordinator’s work (feeder and main routes), the methodology schedules the daily operation in 8 minutes. Note that the algorithm generates less work shifts than the manual programming, reducing the operational costs of the company. Additionally, the number of mixed shifts is also reduced, a scenario where drivers with the most expensive license (C3), will be scheduled for services requiring only C2 license.