O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público.
| dc.contributor.advisor | Silva, Gustavo Peixoto | pt_BR |
| dc.contributor.author | Martins, Leandro do Carmo | |
| dc.contributor.referee | Silva, Gustavo Peixoto | pt_BR |
| dc.contributor.referee | Freitas, Alan Robert Resende de | pt_BR |
| dc.contributor.referee | Ribeiro, Glaydston Mattos | pt_BR |
| dc.contributor.referee | Ferreira, Anderson Almeida | pt_BR |
| dc.date.accessioned | 2017-04-17T17:50:27Z | |
| dc.date.available | 2017-04-17T17:50:27Z | |
| dc.date.issued | 2017 | |
| dc.description | Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. | pt_BR |
| dc.description.abstract | Este trabalho propõe o desenvolvimento da heurística Adaptive Large Neighborhood Search (ALNS) para resolver o Problema de Programação de Tripulações (PPT) do Sistema de Transporte Público. O PPT consiste em determinar o número mínimo de tripulações necessário para conduzir todas as viagens previstas na programação dos veículos, definida anteriormente. Os dados de entrada do PPT são as viagens a serem realizadas por cada veículo da frota em operação, definida na etapa anterior, assim como as regras operacionais da empresa, as leis trabalhistas e os acordos vigentes para a categoria. A solução deste problema é um conjunto de sequências de viagens. Cada sequência é uma jornada de trabalho, ou seja, a programação das atividades a serem executadas por uma dada tripulação ao longo de um dia de trabalho. As jornadas devem satisfazer as leis trabalhistas, os acordos sindicais e ainda as regras operacionais da empresa. Como o problema é NP-difícil, casos reais de grande porte são normalmente resolvidos por metaheurísticas. A heurística ALNS tem como objetivo minimizar os custos fixos e variáveis de uma programação completa das tripulações, satisfazendo todas as restrições mencionadas. Os custos fixos são representados pelo número de jornadas (tripulações) e os custos variáveis são calculados em função do total de horas extras e do número de duplas pegadas. A ALNS inicia sua busca a partir de uma solução viável e opera com diferentes métodos de “destruição” e “reparo” da solução corrente para obter uma solução de melhor qualidade. Inicialmente, um peso é atribuído a cada método de destruição e reparo. Estes pesos são ajustados dinamicamente, baseados no desempenho de cada método ao longo da busca, com o intuito de encontrar o par de métodos mais eficiente. Vários métodos diferentes de destruição e reparo tem sido propostos na literatura para resolver o Problema de Roteamento de Veículos. Alguns destes métodos clássicos foram adaptados ao PPT e outros foram propostos pela primeira vez neste trabalho. A heurística foi implementada e testada com dados reais de várias empresas que operam na região metropolitana da cidade de Belo Horizonte, MG. Os parâmetros foram refinados e os resultados obtidos superaram alguns métodos da literatura e a solução adotada pela empresa. | pt_BR |
| dc.description.abstracten | This dissertation proposes the development of Adaptive Large Neighborhood Search (ALNS) heuristic to solve the Crew Scheduling Problem (CSP) from Public Transportation Systems. The CSP consists of determining a minimum number of crews required to conduct all planned trips in the vehicle scheduling, previously defined. The CSP input data are the trips to be performed by each vehicle in the fleet in operation, defined in the previous step, as well as the company’s operating rules, labor laws and existing agreements for the category. The solution of this problem is a sequence set of drivers’ activities. Each sequence is called a work shift, that is, a schedule of the activities to be performed by a crew member over a working day. The shifts must meet several requirements due to labor laws, union agreements and yet the operational rules of the company. Since the problem is NP-hard, real cases are usually solved through metaheuristics. The ALNS heuristic has as objective to minimize fixed and variable costs of a complete schedule, satisfying all the constraints mentioned above. The fixed costs are represented by the number of shifts, and the variable costs are calculated depending on the overtime and split duties amount. The ALNS starts from a feasible solution and operates with different methods of “destruction” and “repair” of the current solution aiming to get a better solution. A weight is initially assigned to each destroy and repair methods. Those weights are dynamically adjusted based on the performance of each method along the search aiming to find the most efficient pair of methods. Several different destroy and repair operators have been proposed in the literature to solve the Vehicle Routing Problem. In this work, some classical methods were adapted to the CSP, and others methods were proposed for the first time. The implementation was tested with real data from several companies operating in a metropolitan area of Belo Horizonte city, in Brazil. The parameters were tuned and the results outperformed some methods of literature and the solution adopted by the company. | pt_BR |
| dc.identifier.citation | MARTINS, Leandro do Carmo. O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público. 2017. Dissertação (Mestrado em Ciência da Computação) - Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto, Ouro Preto, 2017. | pt_BR |
| dc.identifier.uri | http://www.repositorio.ufop.br/handle/123456789/7614 | |
| dc.language.iso | pt_BR | pt_BR |
| dc.rights | aberto | pt_BR |
| dc.rights.license | Autorização concedida ao Repositório Institucional da UFOP pelo(a) autor(a) em 05/04/2017 com as seguintes condições: disponível sob Licença Creative Commons 4.0 que permite copiar, distribuir e transmitir o trabalho desde que sejam citados o autor e o licenciante. Não permite o uso para fins comerciais nem a adaptação. | pt_BR |
| dc.subject | Programação heuristica | pt_BR |
| dc.title | O uso da heurística Adaptive Large Neighborhood Search para resolver o Problema de Programação de Tripulações do Transporte Público. | pt_BR |
| dc.type | Dissertacao | pt_BR |