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

• Ano de defesa: 2022
• Autor(a) principal: Emiliana Mara Lopes Simões
• Tipo de documento: Tese
• Tipo de acesso: Acesso aberto
• Idioma: eng
• Instituição de defesa: Universidade Federal de Minas Gerais; Brasil; ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA; Programa de Pós-Graduação em Engenharia Elétrica; UFMG
• Palavras-chave em Português: Iterated local search; Matheuristic; Multiple-depot vehicle and crew scheduling; Public transportation; Time-space network; Variable neighborhood descent; Engenharia elétrica; Algoritmos; Modelos matemáticos; Otimização; Transportes coletivos
• Link de acesso: http://hdl.handle.net/1843/48214; https://orcid.org/0000-0003-0036-7120

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.