Use este identificador para citar ou linkar para este item:
http://hdl.handle.net/1843/SLSS-7WMJMD
Tipo: | Dissertação de Mestrado |
Título: | Algoritmo para programação integrada de veículos e tripulações no sistema de transporte público por ônibus |
Autor(es): | Emiliana Mara Lopes Simoes |
Primeiro Orientador: | Geraldo Robson Mateus |
Primeiro Coorientador: | Marcone Jamilson Freitas Souza |
Primeiro membro da banca : | André Gustavo dos Santos |
Segundo membro da banca: | Sebastián Alberto Urrutia |
Resumo: | Este trabalho aborda dois dos problemas envolvidos no processo de planejamento do Sistema de Transporte Público de Ônibus Urbano: o Problema de Programação de Veículos (PPV) e o Problema de Programação de Tripulações (PPT). O PPV consiste em criar uma rotina diária de operação para uma frota de veículos, dado um conjunto de viagens a serem obrigatoriamente realizadas. Na resolução do PPT são definidas as jornadas diárias de trabalho para motoristas e cobradores, de maneira que todos os deslocamentos dos veículos estejam sob responsabilidade de alguma tripulação. O objetivo é reduzir os custos envolvidos em tais atividades, fazendo o melhor aproveitamento da frota e da mão-de-obra, mas ao mesmo tempo obedecendo à legislação trabalhista e as regras operacionais vigentes.Normalmente, devido à complexidade destes problemas, eles são resolvidos separadamente e seqüencialmente (abordagem seqüencial tradicional, ou seja, primeiro resolve-se o PPV e logo em seguida o PPT). Porém, dada a forte dependência entre PPV e PPT, espera-se que a resolução integrada dos mesmos possa proporcionar considerável redução dos custos. Assim, dadas as expectativas atuais acerca dessa nova metodologia, neste trabalho é desenvolvida uma heurística, baseada na metaheurística Busca Local Iterada, para resolução do Problema de Programação Integrada de Veículos e Tripulações (PPVT). No PPVT as rotinas de operação dos veículos e as jornadas de trabalho das tripulações são definidas simultaneamente. Trata-se de um problema altamente combinatório e que se enquadra na classe de problemas NP-difíceis, não havendo, portanto, algoritmos em tempo polinomial para encontrar soluções ótimas.Com o intuito de analisar o desempenho da abordagem integrada, PPV e PPT também são resolvidos de forma iterativa, seqüencial tradicional e independente (PPV e PPT são resolvidos separadamente, em qualquer ordem e de forma a não se relacionarem). Para validar os métodos propostos são apresentados experimentos com dados reais de uma empresa de transporte público da cidade de Belo Horizonte. Os resultados encontrados confirmam as expectativas e mostram que as soluções geradas pela heurística integrada são melhores do que as obtidas de forma seqüencial. |
Abstract: | This work deals with two of the problems involved in the planning process of the public mass transit: the Vehicle Scheduling Problem (VSP) and the Crew Scheduling Problem (CSP). The VSP is a way to create a daily operation routine for a fleet of vehicles, given a set of trips required to be performed. In the resolution of CSP the daily work duty for the drivers and collectors are defined, so that all displacements of the vehicles are in charge of a crew. This paper aimed to investigate how to reduce costs involved in such activities for the best use of the fleet and labor force, but also comply with the public policies of labor laws and operational rules.These problems has been usually treated separately and sequentially due to their complexity (traditional sequential approach, in other words, first VSP is solved and then CSP). However, since there is a strong dependence between VSP and CSP, it is expected that the integrated resolution of them could provide considerable cost reduction. Thus, given the current expectations about this new methodology, in this work heuristics are developed, based on the Iterated Local Search metaheuristic to solve the Integrated Vehicle and Crew Scheduling Programing (VCSP). In the VCSP the routines of vehicle operation and the crew work duty are defined simultaneously. This is a highly combinatorial problem, which is inserted in the class of NP-hard problems, having not polynomial-time algorithms to find optimal solutions.To analyze the efficiency of the performance of the integrated approach, both VSP and CSP are solved in the traditional sequential and independent way (VSP and CSP are solved separately, in any order and in an unrelated way). The proposed methods were validated with real data from a Public Transport Company of Belo Horizonte city. The results obtained signalize that the solutions generated by the integrated heuristics are better than those obtained in sequential order. |
Assunto: | Otimização combinatória Computação Transporte de mercadorias Modelos matemáticos |
Idioma: | Português |
Editor: | Universidade Federal de Minas Gerais |
Sigla da Instituição: | UFMG |
Tipo de Acesso: | Acesso Aberto |
URI: | http://hdl.handle.net/1843/SLSS-7WMJMD |
Data do documento: | 21-Ago-2009 |
Aparece nas coleções: | Dissertações de Mestrado |
Arquivos associados a este item:
Arquivo | Descrição | Tamanho | Formato | |
---|---|---|---|---|
emilianamaralopessimoes.pdf | 1.7 MB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.