Track: Operations Research

Abstract

This paper presents an improved mathematical model to solve the driver’s scheduling problem for mass transit system, specific for small and medium size problems. The addition of valid inequalities generated by an extended analysis of the behavior presented in the results founds by solving previous mathematical models for the crew scheduling problem regarding the Megabus public transportation system, assures a more profound revision of the conduct when compared with the results found in the industry and previous investigations. Since every real problem have specific constrains that can worsen the solution process, the structure of the crew scheduling problem has been characterized regarding specific crew options and timetables. Any change can worsen the solution times and computational effort with only few new additions in the crew, change in work times limits or number of tasks for each test system. This is the main goal with the proposed constraints shown in this work, one of them presents interesting results, especially related with the topology and the size of the test system solved in this work which when compared with real systems, shows a better behavior than presented in previous works, resulting in a new approach to find the solution. This work uses the language C++ with the commercial solver Cplex to prove the new constrains, resulting in reduced computational time, and computational effort and presenting a new improved model which is proved using small and medium test systems built using real data and available in the specialized literature.