Variable fixing mip heuristics for solving multiple depot vehicle scheduling problem with heterogeneous fleet and time windows

The multiple depot heterogeneous fleet vehicle scheduling problem (MDHFVSP) consists of allocating vehicles for predetermined trips groups, taking into account multiple depots, the capacity of these depots, different types of vehicles as well as trips of various demands and vehicles with different capacities. The main objective of a transportation system planning is to reduce costs, implementation and/or operation costs, reducing vehicle utilization and minimizing fuel and crew costs. This thesis proposes a new variant of the MDHFVSP that considers the application of time windows (MDHFVSP-TW). We used a time-space network (TSN) to perform the modeling of MDHFVSP-TW, along with two methodologies to reduce its size and, therefore, its complexity. Along with size reduction methods, a mixed integer programming (MIP) heuristic with variable fixation was presented. Its operation is based on the use of the solution for this problem with relaxed variables as a basis for the removal of arcs from the problem, reducing its size and enabling its resolution in reasonable computational time. Extensive tests were performed for a collection of randomly generated instances. Subsequently, a case study arising from a real instance from a Brazilian city is presented. The computational results showed that the proposed heuristic and size reduction methods obtained good performance, providing high-quality solutions in an adequate computational time.O problema de programação de veículos com múltiplos depósitos e frota heterogênea (MD-HFVSP) consiste em alocar veículos para realização de grupos de viagens pré-determinadas, levando em consideração múltiplas garagens, a capacidade dessas garagens, diferentes tipos de veículos assim como viagens de diversas demandas e veículos com diferentes capacidades. O objetivo principal de um planejamento de sistema de transportes é reduzir os custos, de implementação e/ou de operação, diminuindo a utilização dos veículos e minimizando os gastos com combustível e tripulações. Nessa dissertação é proposta uma nova variante do MDHFVSP que considera a aplicação de janelas de tempo (MDHFVSP-TW). Foi utilizada timespace network(TSN) para realizar a modelagem do MDHFVSP-TW, juntamente com duas metodologias para redução do seu tamanho e, por conseguinte, da sua complexidade. Juntamente com os métodos de redução de tamanho, uma heurística baseada em programação linear mista (MIP) com fixação de variáveis foi apresentada, cujo funcionamento baseia-se na utilização da solução do problema com variáveis relaxadas como base para a remoção de arcos, reduzindo seu tamanho e possibili- tando sua resolução em tempo computacional admissível. Testes extensivos foram realizados para uma coleção de instâncias geradas aleatoriamente. Posteriormente, foi apresentado um estudo de caso para uma instância real proveniente de uma cidade do Brasil. Os resultados computacionais demonstraram que a heurística e os métodos de redução de tamanho obtiveram boa performance, proporcionando soluções de alta qualidade em um tempo computacional admissível