Please use this identifier to cite or link to this item:
http://hdl.handle.net/1843/48214
Type: | Tese |
Title: | A matheuristic algorithm for the multiple-depot vehicle and crew scheduling problem |
Other Titles: | Um algoritmo matheurístico para o problema de programação de veículos e tripulações com múltiplas garagens |
Authors: | Emiliana Mara Lopes Simões |
First Advisor: | Lucas de Souza Batista |
First Co-advisor: | Marcone Jamilson Freitas Souza |
First Referee: | Geraldo Robson Mateus |
Second Referee: | Mauricio Cardoso de Souza |
Third Referee: | Claudio Barbieri da Cunha |
metadata.dc.contributor.referee4: | André Luiz Maravilha Silva |
Abstract: | 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. |
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. |
Subject: | Engenharia elétrica Algoritmos Modelos matemáticos Otimização Transportes coletivos |
language: | eng |
metadata.dc.publisher.country: | Brasil |
Publisher: | Universidade Federal de Minas Gerais |
Publisher Initials: | UFMG |
metadata.dc.publisher.department: | ENG - DEPARTAMENTO DE ENGENHARIA ELÉTRICA |
metadata.dc.publisher.program: | Programa de Pós-Graduação em Engenharia Elétrica |
Rights: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/48214 |
Issue Date: | 13-Jul-2022 |
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.