Track: Operations Research

Abstract

In this work is present a novel integer linear programming formulation to solve an operation planning problem in public transport systems. The proposed model is flexible and it works by adding or removing specific constraints for the operation, depending on the laws of the corresponding country and the policies of a particular company . The formulation proposed in this work models a generic version of the Bus Driver Rostering Problem, which has a considerable amount of issues to be considered, mostly due to the complexity of the personnel management and their assignment of the daily duty. The main issues taken into account in the model are the specific work conditions, labor regulations for each country, companies’ internal policies and available staff. These are included as sets of hard constraints of the problem. In the literature, it was observed that there is a lack of general mathematical models representing this class of problems. Consequently, most of the published research related to this problem concern the development of heuristic solutions. Moreover, two-phase hybrid approaches combining heuristic and exact methodologies, for the first and second stage, respectively,  are not able to ensure optimal solutions.  In this study, the model is tested on three different scenarios: (i) benchmark instances, (ii) newly proposed benchmark instances simulating the operation of a transport company varying the types of shifts and available staff, and (iii) real case of a public transport company of a Bus Rapid Transit (BRT) system in Colombia. Computational experiments show that a mixed integer programming (MIP) solver is capable of obtaining optimal solutions for each of the aforementioned scenarios in reasonable computing times.