Algoritmo para programação integrada de veículos e tripulações no sistema de transporte público por ônibus - Emiliana Mara Lopes Simoes (2009)
This work deals with two of the problems involved in the planning process of the public mass transit: the Vehicle Scheduling Problem (VSP) and the Crew Scheduling Problem (CSP). The VSP is a way to create a daily operation routine for a fleet of vehicles, given a set of trips required to be performed. In the resolution of CSP the daily work duty for the drivers and collectors are defined, so that all displacements of the vehicles are in charge of a crew. This paper aimed to investigate how to reduce costs involved in such activities for the best use of the fleet and labor force, but also comply with the public policies of labor laws and operational rules.These problems has been usually treated separately and sequentially due to their complexity (traditional sequential approach, in other words, first VSP is solved and then CSP). However, since there is a strong dependence between VSP and CSP, it is expected that the integrated resolution of them could provide considerable cost reduction. Thus, given the current expectations about this new methodology, in this work heuristics are developed, based on the Iterated Local Search metaheuristic to solve the Integrated Vehicle and Crew Scheduling Programing (VCSP). In the VCSP the routines of vehicle operation and the crew work duty are defined simultaneously. This is a highly combinatorial problem, which is inserted in the class of NP-hard problems, having not polynomial-time algorithms to find optimal solutions.To analyze the efficiency of the performance of the integrated approach, both VSP and CSP are solved in the traditional sequential and independent way (VSP and CSP are solved separately, in any order and in an unrelated way). The proposed methods were validated with real data from a Public Transport Company of Belo Horizonte city. The results obtained signalize that the solutions generated by the integrated heuristics are better than those obtained in sequential order.