Aplicação da meta heurística variable neighborhood search na otimização de escalas de motoristas de transporte público urbano

Abstract

O presente trabalho aborda o Problema de Programação de Tripulação de ônibus urbano (PPT) o qual consiste em determinar jornadas diárias de trabalho para tripulantes que conduzirão uma frota em operação com o menor custo possível e atendendo restrições operacionais e trabalhistas. O PPT é uma etapa muito importante no planejamento operacional do Sistema de Transporte Público visto que o custo operacional representado pelas escalas de trabalho compõe uma parcela significativa nos custos totais de uma empresa do ramo. A redução dos custos das escalas de trabalho afeta não só as empresas operadoras, mas também os usuários deste serviço, pois com esta redução há a possibilidade de um maior investimento na qualidade do transporte público e a redução dos preços dos bilhetes. Estes custos estão estritamente relacionados às normas operacionais impostas pelas empresas e legislações trabalhistas. Quando se considera uma abordagem de solução exata que utiliza o modelo matemático de programação linear inteira o qual é considerado de alta complexidade, o PPT não pode ser resolvido em tempo computacional viável quando se trata de problemas de médio e grande porte. Assim, devido à complexidade computacional para se obter uma solução utilizando métodos exatos, neste trabalho considera-se um método pertencente a uma classe alternativa de métodos de solução, denominada meta heurística, mais especificamente, a busca em vizinhança variável (Variable Neighborhood Search – VNS), que para evitar ótimos locais realiza trocas sistemáticas de estruturas de vizinhança no espaço de busca. A implementação proposta é testada com os dados reais de uma empresa de médio porte e os resultados são comparados com o cenário atual da empresa.

The following work present the Crew Scheduling Problem (CSP) of urban buses that consist in determine the daily work schedules for the crew, that will be responsible to lead an operation fleet in the most economical way and meeting all the operational restrictions. The CSP is a very important step in the operational planning of the Public Transport System as the operating cost represented by crew schedules make up a significant portion of the total costs of a company in the sector. The reduction costs of work schedules affect not only the operating companies, but also the users of this service, because with this reduction there is the possibility of greater investment in the quality of public transport and the reduction of ticket prices. These costs are strictly related to the operational standards required by companies and labor legislation. When considering an exact solution approach that uses mathematical model of integer linear programming which is considered high complexity, the CSP can not be solved in a viable computational time when it is related to medium or larger problems. Due to that computational complexity, to be able to obtain a solution utilizing exact methods, in this work it is considered the utilization of the belonged method into an alternated class of solution methods named as metaheuristic, more specifically, Variable Neighborhood Search (VNS), that to avoid from local optimal, realize a systematic changes on the neighborhood structures inside the research space. The solution proposal presented is tested with real data, that was taken from a medium sized company and the results are compared to the current situation of the company.