Use este identificador para citar ou linkar para este item: http://www.monografias.ufop.br/handle/35400000/437
Título: Resolução do problema de programação de ônibus urbano utilizando a metaeurística LNS.
Autor(es): Ribeiro, Klevison Daniel de Oliveira
Orientador(es): Silva, Gustavo Peixoto
Membros da banca: Silva, Gustavo Peixoto
Gomes, Helton Cristiano
Reis, Allexandre Fortes da Silva
Palavras-chave: Problema de programação de veículos
Pesquisa operacional
Programação de ônibus urbano
Transporte público
Data do documento: 2017
Referência: RIBEIRO, Klevison Daniel de Oliveira. Resolução do problema de programação de ônibus urbano utilizando a metaeurística LNS. 2017. 57 f. Monografia (Graduação em Engenharia de Controle e Automação) - Escola de Minas, Universidade Federal de Ouro Preto, Ouro Preto, 2017.
Resumo: O transporte público é um sistema amplamente utilizado pela população, principalmente por aqueles que residem nos grandes perímetros urbanos. Como esse sistema tem um grande impacto no dia-a-dia de milhões de pessoas, ele precisa estar em constante melhora. Uma das etapas da operação do sistema de transporte público é a programação dos veículos que irão realizar as viagens previstas na tabela de horários. Esta alocação pode ser realizada de forma manual pelas empresas, entretanto, o uso de métodos de otimização pode implicar num melhor aproveitamento da frota e uma consequente redução nos custos das empresas. Com base nesse cenário, neste trabalho foi desenvolvida uma versão da heurística Large Neighborhood Search (LNS) para resolver o Problema de Programação de Veículos (PPV). Ao solucionar o PPV, pretende-se definir a quantidade mínima de veículos em operação, assim como o detalhamento das atividades de cada veículo em operação. Este detalhamento especifica quais as viagens serão realizadas por quais veículos, o tempo de espera nos terminais e as possíveis viagens ociosas realizadas. A solução para o problema foi construída inicialmente com a busca gulosa, posteriormente foram adaptados métodos de remoção e inserção das viagens aos veículos e finalmente foi implementada a heurística LNS. Foram realizados testes computacionais com dados reais de uma série de empresas que operam na região metropolitana de Belo Horizonte, MG. Os resultados foram comparados com aqueles obtidos por um modelo exato baseado em Algoritmos de Fluxo em Redes. Os resultados se mostraram promissores, visto que na maioria dos casos a diferença entre a solução aproximada e a solução ótima foi pequena.
Resumo em outra língua: The Public Transportation System is largely used by people, mostly those who live in the metropolitan areas. Therefore, this process needs to be in constant improvement, because it will impact millions of people daily. One of the steps that make the Public Transportation System is the Vehicle Scheduling that will execute the trips contained in the schedule table. This allocation can be done manually by the companies, however, the use of optimization methods can imply on better use of the fleet and consequently reduce costs. Based on this scenario, in this project was developed one version of the metaheuristic Large Neighborhood Search (LNS) to resolve the Vehicle Scheduling Problem (VSP). To solve the VSP, must be defined the minimum quantity of vehicles, as the detail of activities of the bus used in solution. This details show which trip will be done by which vehicle, the waiting time in the terminals and the idle trips realized. The initial solution on this work was build with basic greedy insertion, after that the removing and insertion heuristics were implemented and finally the LNS was build. Computational tests were made with real data from some companies that operate in Belo Horizonte, MG. The results were compared with one ArcGen model and showed up promising, since in most cases the difference between solutions was little.
URI: http://www.monografias.ufop.br/handle/35400000/437
Licença: Autorização concedida à Biblioteca Digital de TCC da UFOP pelo autor(a), 06/04/2017, com as seguintes condições: disponível sob Licença Creative Commons 4.3 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.
Aparece nas coleções:Engenharia de Controle e Automação

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
MONOGRAFIA_ResoluçãoPRoblemasProgramação.pdf2,44 MBAdobe PDFVisualizar/Abrir


Este item está licenciado sob uma Licença Creative Commons Creative Commons