Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/48214
Full metadata record
DC Field | Value | Language |
---|---|---|
dc.contributor.advisor1 | Lucas de Souza Batista | pt_BR |
dc.contributor.advisor1Lattes | http://lattes.cnpq.br/9418849740691899 | pt_BR |
dc.contributor.advisor-co1 | Marcone Jamilson Freitas Souza | pt_BR |
dc.contributor.referee1 | Geraldo Robson Mateus | pt_BR |
dc.contributor.referee2 | Mauricio Cardoso de Souza | pt_BR |
dc.contributor.referee3 | Claudio Barbieri da Cunha | pt_BR |
dc.contributor.referee4 | André Luiz Maravilha Silva | pt_BR |
dc.creator | Emiliana Mara Lopes Simões | pt_BR |
dc.creator.Lattes | http://lattes.cnpq.br/3640621133389140 | pt_BR |
dc.date.accessioned | 2022-12-19T18:29:07Z | - |
dc.date.available | 2022-12-19T18:29:07Z | - |
dc.date.issued | 2022-07-13 | - |
dc.identifier.uri | http://hdl.handle.net/1843/48214 | - |
dc.description.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. | pt_BR |
dc.description.resumo | This thesis addresses the multiple-depot vehicle and crew scheduling problem (MDVCSP). In MDVCSP, we deal with two NP-hard problems in an integrated way: the multiple-depot vehicle scheduling problem (MDVSP) and the crew scheduling problem (CSP). For solving the MDVCSP, we define the vehicles' operational routine and the workdays of the crews of a public bus transport system with multiple depots simultaneously. Given the difficulty of solving real-world instances of the MDVCSP using exact mathematical methods, we propose a matheuristic algorithm for solving it. This matheuristic algorithm, named ILS-MDVCSP, combines two strategies into an iterated local search (ILS) based framework: a branch-and-bound algorithm for solving the MDVSP and a variable neighborhood descent (VND) based algorithm for treating the associated CSPs. We compared the proposed ILS-MDVCSP with five approaches in the literature that use the same benchmark test instances. We also solved a real-world problem of one of Brazil's largest cities. For this problem, we proposed a formulation based on a time-space network to address the MDVSP subproblem. The results obtained showed the effectiveness of ILS-MDVCSP, mainly to deal with real-world and large-scale problems. The algorithm was able to solve the largest instances from the literature, for which there was no reported solution. Regarding the run time, as the instances' size increases, our approach becomes substantially less costly than the others from the literature. For the Brazilian instances, the ILS-MDVCSP saved, on average, the use of 25 vehicles per day and reduced on average by 16% the daily operational time of the vehicles considering four depots together. | pt_BR |
dc.description.sponsorship | CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico | pt_BR |
dc.description.sponsorship | FAPEMIG - Fundação de Amparo à Pesquisa do Estado de Minas Gerais | pt_BR |
dc.description.sponsorship | CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior | pt_BR |
dc.language | eng | pt_BR |
dc.publisher | Universidade Federal de Minas Gerais | pt_BR |
dc.publisher.country | Brasil | pt_BR |
dc.publisher.department | ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA | pt_BR |
dc.publisher.program | Programa de Pós-Graduação em Engenharia Elétrica | pt_BR |
dc.publisher.initials | UFMG | pt_BR |
dc.rights | Acesso Aberto | pt_BR |
dc.subject | Iterated local search | pt_BR |
dc.subject | Matheuristic | pt_BR |
dc.subject | Multiple-depot vehicle and crew scheduling | pt_BR |
dc.subject | Public transportation | pt_BR |
dc.subject | Time-space network | pt_BR |
dc.subject | Variable neighborhood descent | pt_BR |
dc.subject.other | Engenharia elétrica | pt_BR |
dc.subject.other | Algoritmos | pt_BR |
dc.subject.other | Modelos matemáticos | pt_BR |
dc.subject.other | Otimização | pt_BR |
dc.subject.other | Transportes coletivos | pt_BR |
dc.title | A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem | pt_BR |
dc.title.alternative | Um algoritmo matheurístico para o problema de programação de veículos e tripulações com múltiplas garagens | pt_BR |
dc.type | Tese | pt_BR |
dc.identifier.orcid | https://orcid.org/0000-0003-0036-7120 | pt_BR |
Appears in Collections: | Teses de Doutorado |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem.pdf | 2.12 MB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.