Nesta tese, nós apresentamos uma compilação de três artigos de otimização aplicados no contexto de transporte urbano de ônibus. O principal objetivo foi estudar e implementar heurísticas com base em Pesquisa Operacional para otimizar problemas de (re)escalonamento de veículos off-line e on-line considerando várias garagens e frota heterogênea. No primeiro artigo, foi proposta uma abordagem heurística para o problema de escalonamento de veículos múltiplas garagens. Acreditamos que as principais contribuições são o método de geração de colunas para grandes instâncias e as técnicas de redução do espaço de estados para acelerar as soluções. No segundo artigo, adicionamos complexidade ao considerar a frota heterogênea, denotada como multiple depot vehicle type scheduling problem (MDVTSP). Embora a importância e a aplicabilidade do MDVTSP, formulações matemáticas e métodos de solução para isso ainda sejam relativamente inexplorados. A principal contribuição desse trabalho foi o método de geração de colunas para o problema com frota heterogênea, já que nenhuma outra proposta na literatura foi identificada no momento pelos autores. Na terceira parte desta tese, no entanto, nos concentramos no reescalonamento em tempo real para o caso de quebras definitivas de veículos. A principal contribuição é a abordagem eficiente do reescalonamento sob uma quebra. A abordagem com redução de espaço de estados, solução inicial e método de geração de colunas possibilitou uma ação realmente em tempo real. Em menos de cinco minutos, reescalonando todas as viagens restantes. / In this dissetation we presented a three articles compilation in urban bus transportation optimization. The main objective was to study and implement heuristic solutions method based on Operations Research to optimizing offline and online vehicle (re)scheduling problems considering multiple depots and heterogeneous fleet. In the first paper, a fast heuristic approach to deal with the multiple depot vehicle scheduling problem was proposed. We think the main contributions are the column generation framework for large instances and the state-space reduction techniques for accelerating the solutions. In the second paper, we added complexity when considering the heterogeneous fleet, denoted as "the multiple-depot vehicle-type scheduling problem" (MDVTSP). Although the MDVTSP importance and applicability, mathematical formulations and solution methods for it are still relatively unexplored. We think the main contribution is the column generation framework for instances with heterogeneous fleet since no other proposal in the literature has been identified at moment by the authors. In the third part of this dissertation, however, we focused on the real-time schedule recovery for the case of serious vehicle failures. Such vehicle breakdowns require that the remaining passengers from the disabled vehicle, and those expected to become part of the trip, to be picked up. In addition, since the disabled vehicle may have future trips assigned to it, the given schedule may be deteriorated to the extent where the fleet plan may need to be adjusted in real-time depending on the current state of what is certainly a dynamic system. Usually, without the help of a rescheduling algorithm, the dispatcher either cancels the trips that are initially scheduled to be implemented by the disabled vehicle (when there are upcoming future trips planned that could soon serve the expected demand for the canceled trips), or simply dispatches an available vehicle from a depot. In both cases, there may be considerable delays introduced. This manual approach may result in a poor solution. The implementation of new technologies (e.g., automatic vehicle locators, the global positioning system, geographical information systems, and wireless communication) in public transit systems makes it possible to implement real-time vehicle rescheduling algorithms at low cost. The main contribution is the efficient approach to rescheduling under a disruption. The approach with integrated state-space reduction, initial solution, and column generation framework enable a really real-time action. In less than five minutes rescheduling all trips remaining.

Nesta tese, nós apresentamos uma compilação de três artigos de otimização aplicados no contexto de transporte urbano de ônibus. O principal objetivo foi estudar e implementar heurísticas com base em Pesquisa Operacional para otimizar problemas de (re)escalonamento de veículos off-line e on-line considerando várias garagens e frota heterogênea. No primeiro artigo, foi proposta uma abordagem heurística para o problema de escalonamento de veículos múltiplas garagens. Acreditamos que as principais contribuições são o método de geração de colunas para grandes instâncias e as técnicas de redução do espaço de estados para acelerar as soluções. No segundo artigo, adicionamos complexidade ao considerar a frota heterogênea, denotada como multiple depot vehicle type scheduling problem (MDVTSP). Embora a importância e a aplicabilidade do MDVTSP, formulações matemáticas e métodos de solução para isso ainda sejam relativamente inexplorados. A principal contribuição desse trabalho foi o método de geração de colunas para o problema com frota heterogênea, já que nenhuma outra proposta na literatura foi identificada no momento pelos autores. Na terceira parte desta tese, no entanto, nos concentramos no reescalonamento em tempo real para o caso de quebras definitivas de veículos. A principal contribuição é a abordagem eficiente do reescalonamento sob uma quebra. A abordagem com redução de espaço de estados, solução inicial e método de geração de colunas possibilitou uma ação realmente em tempo real. Em menos de cinco minutos, reescalonando todas as viagens restantes. / In this dissetation we presented a three articles compilation in urban bus transportation optimization. The main objective was to study and implement heuristic solutions method based on Operations Research to optimizing offline and online vehicle (re)scheduling problems considering multiple depots and heterogeneous fleet. In the first paper, a fast heuristic approach to deal with the multiple depot vehicle scheduling problem was proposed. We think the main contributions are the column generation framework for large instances and the state-space reduction techniques for accelerating the solutions. In the second paper, we added complexity when considering the heterogeneous fleet, denoted as "the multiple-depot vehicle-type scheduling problem" (MDVTSP). Although the MDVTSP importance and applicability, mathematical formulations and solution methods for it are still relatively unexplored. We think the main contribution is the column generation framework for instances with heterogeneous fleet since no other proposal in the literature has been identified at moment by the authors. In the third part of this dissertation, however, we focused on the real-time schedule recovery for the case of serious vehicle failures. Such vehicle breakdowns require that the remaining passengers from the disabled vehicle, and those expected to become part of the trip, to be picked up. In addition, since the disabled vehicle may have future trips assigned to it, the given schedule may be deteriorated to the extent where the fleet plan may need to be adjusted in real-time depending on the current state of what is certainly a dynamic system. Usually, without the help of a rescheduling algorithm, the dispatcher either cancels the trips that are initially scheduled to be implemented by the disabled vehicle (when there are upcoming future trips planned that could soon serve the expected demand for the canceled trips), or simply dispatches an available vehicle from a depot. In both cases, there may be considerable delays introduced. This manual approach may result in a poor solution. The implementation of new technologies (e.g., automatic vehicle locators, the global positioning system, geographical information systems, and wireless communication) in public transit systems makes it possible to implement real-time vehicle rescheduling algorithms at low cost. The main contribution is the efficient approach to rescheduling under a disruption. The approach with integrated state-space reduction, initial solution, and column generation framework enable a really real-time action. In less than five minutes rescheduling all trips remaining.

Nesta tese, nós apresentamos uma compilação de três artigos de otimização aplicados no contexto de transporte urbano de ônibus. O principal objetivo foi estudar e implementar heurísticas com base em Pesquisa Operacional para otimizar problemas de (re)escalonamento de veículos off-line e on-line considerando várias garagens e frota heterogênea. No primeiro artigo, foi proposta uma abordagem heurística para o problema de escalonamento de veículos múltiplas garagens. Acreditamos que as principais contribuições são o método de geração de colunas para grandes instâncias e as técnicas de redução do espaço de estados para acelerar as soluções. No segundo artigo, adicionamos complexidade ao considerar a frota heterogênea, denotada como multiple depot vehicle type scheduling problem (MDVTSP). Embora a importância e a aplicabilidade do MDVTSP, formulações matemáticas e métodos de solução para isso ainda sejam relativamente inexplorados. A principal contribuição desse trabalho foi o método de geração de colunas para o problema com frota heterogênea, já que nenhuma outra proposta na literatura foi identificada no momento pelos autores. Na terceira parte desta tese, no entanto, nos concentramos no reescalonamento em tempo real para o caso de quebras definitivas de veículos. A principal contribuição é a abordagem eficiente do reescalonamento sob uma quebra. A abordagem com redução de espaço de estados, solução inicial e método de geração de colunas possibilitou uma ação realmente em tempo real. Em menos de cinco minutos, reescalonando todas as viagens restantes. / In this dissetation we presented a three articles compilation in urban bus transportation optimization. The main objective was to study and implement heuristic solutions method based on Operations Research to optimizing offline and online vehicle (re)scheduling problems considering multiple depots and heterogeneous fleet. In the first paper, a fast heuristic approach to deal with the multiple depot vehicle scheduling problem was proposed. We think the main contributions are the column generation framework for large instances and the state-space reduction techniques for accelerating the solutions. In the second paper, we added complexity when considering the heterogeneous fleet, denoted as "the multiple-depot vehicle-type scheduling problem" (MDVTSP). Although the MDVTSP importance and applicability, mathematical formulations and solution methods for it are still relatively unexplored. We think the main contribution is the column generation framework for instances with heterogeneous fleet since no other proposal in the literature has been identified at moment by the authors. In the third part of this dissertation, however, we focused on the real-time schedule recovery for the case of serious vehicle failures. Such vehicle breakdowns require that the remaining passengers from the disabled vehicle, and those expected to become part of the trip, to be picked up. In addition, since the disabled vehicle may have future trips assigned to it, the given schedule may be deteriorated to the extent where the fleet plan may need to be adjusted in real-time depending on the current state of what is certainly a dynamic system. Usually, without the help of a rescheduling algorithm, the dispatcher either cancels the trips that are initially scheduled to be implemented by the disabled vehicle (when there are upcoming future trips planned that could soon serve the expected demand for the canceled trips), or simply dispatches an available vehicle from a depot. In both cases, there may be considerable delays introduced. This manual approach may result in a poor solution. The implementation of new technologies (e.g., automatic vehicle locators, the global positioning system, geographical information systems, and wireless communication) in public transit systems makes it possible to implement real-time vehicle rescheduling algorithms at low cost. The main contribution is the efficient approach to rescheduling under a disruption. The approach with integrated state-space reduction, initial solution, and column generation framework enable a really real-time action. In less than five minutes rescheduling all trips remaining.

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens. / There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens. / There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.

Existem vários problemas clássicos na área de pesquisa operacional que trabalham com o tema vinculado à designação de veículos em um sistema logístico, entre eles o Problema de Escalonamento de Veículos com Múltiplas Garagens (MDVSP). Esses modelos são largamente utilizados e representam uma das etapas essenciais para o planejamento de trânsito em massa (HAGHANI e BANIHASHEMI, 2002). Tratando-se de sistemas logísticos reais, dificilmente encontra-se um ambiente onde os veículos devem partir e chegar a uma única garagem, por isso torna-se necessário o planejamento das seqüências de viagens de modo a reduzir os custos de deslocamentos com o aproveitamento das múltiplas garagens distribuídas geograficamente. Infelizmente, considerando a complexidade exponencial do MDVSP, muitas vezes sua aplicação torna-se inviável na solução de problemas reais. Por essa razão, poucos trabalhos abordam o MDVSP de modo a conseguir solucionar o problema para uma grande quantidade de viagens e garagens. A maioria das pesquisas trabalha com instâncias inferiores a 500 viagens e quatro garagens, mostrando-se pouco aplicáveis. Esse estudo refere-se a um trabalho de pesquisa operacional que aborda soluções de problemas de escalonamento de veículos com múltiplas garagens (MDVSP) considerando sua aplicabilidade em sistemas reais. Tendo em vista a complexidade exponencial do MDVSP, nesse estudo optou-se por tratar o problema através de uma abordagem baseada na redução do espaço de estados e na utilização de heurísticas. Durante essa pesquisa três procedimentos de redução do espaço de estados foram adotados. Os resultados apontam que é possível reduzir em até 98% o número de variáveis nesses problemas sem comprometer uma solução satisfatória ou ótima. Além dos procedimentos de redução do espaço de estados, foi desenvolvido um procedimento de buscar a solução do MDVSP. Através desse último procedimento foi possível resolver o MDVSP com até 3000 viagens e oito garagens. Sendo assim, nesse estudo desenvolveram-se modelos que servem para o planejamento de um sistema logístico através da aplicação de cenários, com vistas a permitir a geração e análise de alternativas de escalonamento. Objetivou-se com isso, fornecer ao sistema logístico um modelo amplo que permita a escolha da ação mais conveniente e eficiente a ser tomada em modelos compostos por diversas garagens. / There are many classics problems in operations research concerning optimal assignment vehicles in logistical system. The multiple depot vehicle scheduling problem (MDVSP) is one of them. This problem is largely used to represent and solve mass transit planning (HAGHANI e BANIHASHEMI, 2002). Considering a real logistical system, it is very difficult to find out a situation where the vehicles must leave and come to only one depot. In general, the shipping company has several depots located at different sites in a network. In this way, it is strongly necessary to reduce cost through the planning of sequence trips taking into account multiple depots geographically distributed. Unfortunately, the exponential complexity of the MDVSP reduces, in the most cases, the applicability of this problem in the real world. For this reason, few researchers address the MDVSP to solve real world problems considering a large number of trips and depots. The majority of the research dealing with the MDVSP works with instances lower than 500 trips and four depots, what can be considered a major constraint for its practical use. The main objective of this work is to solve the MDVSP for very large instances. A state space reduction approach combined with heuristic procedures are developed to obtain a realistic way of solving this complex problem. In this research, three state space reduction procedures were developed. The results appointed that is possible to reduce until 98% of variables in the MDVSP without jeopardizing an optimal solution. Furthermore, heuristic procedures were developed to obtain solutions without relaxing any realworld constraint of the problem. The solution procedure developed was compared with wellknown available instances. The method is able to solve the MDVSP with 3000 trips and eight depots in less than 11 minutes. Although the solution process does not obtain the best solution in all tested instances, it is by far the quickest.