Novas abordagens para a resolução integrada dos problemas de geração da tabela de horários e de escalonamento de veículos com frota heterogênea

Abstract

Nesta tese são propostas três novas abordagens para a resolução do problema integrado de geração de tabela de horários e escalonamento de veículos com frota heterogênea. Duas delas são modelos de Programação Linear Inteira (PLI), com o objetivo de otimizar simultaneamente esses problemas tendo como base uma rede tempo-espaço (TSN, do inglês Time-Space Network ). A terceira é uma nova meto- dologia de inserção de janelas de tempo para os modelos de PLI propostos, a partir de pequenas alterações na estrutura da TSN. Para validar esses modelos foram uti- lizadas instâncias reais, advindas do sistema de transporte público da cidade de Santa Maria, RS, Brasil, e aleatórias de grande porte. O modelo com aplicação das janelas de tempo, denominado VTSP-TW (do inglês Vehicle Type Scheduling Pro- blem with Time Windows ), possibilitou redução substancial no número de veículos, se comparado ao escalonamento realizado na prática. Além disso, comparando-se com outras abordagens disponíveis na literatura, o mesmo gerou rede de menor dimensão e resolveu instâncias de grande porte em tempo computacional inferior, despontando como uma proposta alternativa à aplicação de janelas de tempo ao es- calonamento de veículos com frota heterogênea. Os resultados dos modelos de PLI também indicaram significativas reduções no número de veículos, podendo contri- buir para o aprimoramento da tomada de decisão no planejamento do transporte público. O modelo VTSP-SCT (do inglês Vehicle Type Scheduling Problem with Sequential Changes of Timetable ) resolveu instâncias de 5000 viagens e três tipos de veículos na otimalidade, com apoio do software IBMQR ILOGQR CPLEXQR Opti- mization Studio V12.5. Já o modelo VTSP-CCT (do inglês Vehicle Type Scheduling Problem with Combinatorial Changes of Timetable ) necessitou de suporte heurístico para resolver as instâncias de grande porte. Assim, desenvolveu-se e aplicou-se a ele a técnica de Geração de Colunas, que possibilitou a resolução dessas instâncias e gerou resultados iguais ou melhores do que aqueles proporcionados pelo VTSP-SCT. Os resultados das três abordagens propostas indicam que as mesmas podem contri- buir para a otimização do planejamento do transporte público, tendo em vista que levam a economias significativas no número de veículos escalonados. Além disso, como os intervalos de ajuste da tabela de horários são bastante curtos, obtém-se al- terações sutis, modificando minimamente a rotina dos passageiros, o que possibilita a aplicação dessas abordagens ao contexto real.

In this thesis we propose three new approaches to solve in a integrated way the timetable generation problem and the vehicle-type scheduling problem. Two of them are Integer Linear Programming (ILP) models aiming at simultaneously optimizing these problems based on a time-space network (TSN). The third one is a new methodology for inserting time windows to the proposed ILP models, based on small changes in the TSN structure. To validate these models we applied real instances from a public transportation system of the city of Santa Maria, RS, Brazil, and large random instances. The model with time window application, defined as VTSP-TW (Vehicle Type Scheduling Problem with Time Windows), enabled sub- stantial reduction of vehicle numbers, compared to vehicle scheduling performed in practice. Moreover, comparing with other approaches available in the literature, the VTSP-TW generated smaller networks and solved large instances with less compu- tational time, emerging as an alternative to the application of time windows to the vehicle-type scheduling problem. The ILP models results also showed significant reductions in the vehicle numbers, which may contribute to the improvement of decision making in the public transport planning. The VTSP-SCT (Vehicle Type Scheduling Problem with Sequential Changes of Timetable) solved instances with 5000 service trips and three types of vehicles with optimal solution, supported from IBMQR ILOGQR CPLEXQR Optimization Studio V12.5. In contrast the VTSP-CCT (Vehicle Type Scheduling Problem with Combinatorial Changes of Timetable) re- quired heuristic support to solve large instances. Thus, we developed and applied a Column Generation algorithm, which enabled the resolution of these instances gen- erating equal to or better results than those provided by the VTSP-SCT. The results of the three proposed approaches indicate that they may contribute to optimizing the public transport planning leading to significant savings in terms of scheduled vehicles. Moreover, as the timetable changes are fairly short, it is slightly modified, minimally modifying the passengers routine, which enables the application of these approaches to real context.