Track: Operations Research

Abstract

The difficulties encountered in the solution processes and automation regarding the bus driver problem, has brought mathematical approximations and solutions in real life applications, especially when the system requires those kinds of implementations to find the response in shorter times and less computational effort. The high mathematical complexity found in each mathematical representation of the real problem used by the operating system calls for a novel application of each mathematical representation in one structured algorithm, one that supports the driver scheduling and rostering problem, giving the optimal solution based in good quality factible basic starting points found by the search algorithm to reduce the amount of time and computational memory used. In this work, a first approximation of the combined mathematical model is proposed to analyze the driver scheduling and rostering considering a schedule classification, considers the necessary conditions to fit the bases of 3 different types of approaches to the BDSP problem. The proposed model considers characteristics and especial behaviors found in solutions shown in previous works published in the specialized literature and real-life problems, such as the Integra S.A bus driver problem, to create the necessary changes in the mathematical representation to adapt the new valid inequalities to the real problem behavior and ensure its only used when the problems consider it necessary for the real problem. This being the focus point to implement disjunctive valid inequalities in the final proposal. The improve model is solved with a genetic algorithm to start the solution process and reduce the search space. Since the proposed disjunctive valid inequalities can be activated or deactivated depending on the variables value, the amount of constrains is reduced to improve the computational behavior and ensures the solution of medium type problems. Then the found solution is given to a Branch and Cut technique to find the optimal solution, considering all the reduce conditions found before. To prove the efficiency of the proposed model and algorithm, two test systems were use, starting with small test systems to prove test the mathematical model and its new representation, then it is tested with a medium type of problem, which can be found in the specialized literature, to test the computational efficiency. In each test the algorithm can find the optimal solution of each problem and reduce the time-effort ration when compared with previous works.