A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem

Abstract

Esta tese aborda o problema de programação de veículos e tripulações com múltiplas garagens (MDVCSP). No MDVCSP, lidamos com dois problemas NP-difíceis de forma integrada: o problema de programação de veículos com múltiplas garagens (MDVSP) e o problema de programação de tripulações (CSP). Para solucionar o MDVCSP, definimos simultaneamente a rotina operacional dos veículos e as jornadas de trabalho das tripulações de um sistema de transporte coletivo por ônibus com múltiplas garagens. Dada a dificuldade de resolver instâncias do mundo real do MDVCSP usando métodos matemáticos exatos, propomos um algoritmo matheurístico para resolvê-lo. Este algoritmo matheurístico, nomeado ILS-MDVCSP, combina duas estratégias em uma estrutura baseada em busca local iterada (ILS): um algoritmo branch-and-bound para resolver o MDVSP e um algoritmo baseado no VND (método de descida em vizinhança variável) para tratar os CSPs associados. Comparamos o ILS-MDVCSP proposto com cinco abordagens da literatura que utilizam o mesmo conjunto de instâncias para teste. Também resolvemos um problema real de uma das maiores cidades do Brasil. Para este problema, propusemos uma formulação baseada em uma rede tempo-espaço para resolver o subproblema MDVSP. Os resultados obtidos mostraram a eficácia do ILS-MDVCSP, principalmente para lidar com problemas do mundo real e de grande escala. O algoritmo foi capaz de resolver as maiores instâncias da literatura, para as quais não havia solução relatada. Em relação ao tempo de execução, à medida que o tamanho das instâncias aumenta, nossa abordagem torna-se substancialmente menos onerosa que as demais da literatura. Para as instâncias brasileiras, o ILS-MDVCSP economizou, em média, o uso de 25 veículos por dia e reduziu em média 16% o tempo operacional diário dos veículos considerando quatro garagens juntas.