Repositório Digital

A- A A+

Exact and metaheuristic algorithms for the urban transit routing problem

.

Exact and metaheuristic algorithms for the urban transit routing problem

Mostrar registro completo

Estatísticas

Título Exact and metaheuristic algorithms for the urban transit routing problem
Outro título Algoritmos exatos e metaheur´ısticos para o problema de roteamento de transporte urbano
Autor Fiss, Bruno Coswig
Orientador Ritt, Marcus Rolf Peter
Data 2012
Nível Graduação
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Ciência da Computação: Ênfase em Ciência da Computação: Bacharelado.
Assunto Informatica : Transportes
Simulacao : Trafego
[en] Metaheuristics
[en] Mixed integer programming
[en] Urban transit routing problem
Resumo O problema de roteamento de transporte urbano consiste em encontrar rotas satisfatórias para transporte público em uma cidade ou região. Cenários urbanos se tornam mais complexos com o passar do tempo, tornando o planejamento de rotas uma tarefa proibitivamente difícil, cujos resultados são frequentemente insatisfatórios, com altos custos e tempos de viagem. Nós propomos uma formulação MIP exata para o problema e obtemos resultados ótimos, que até então não eram conhecidos, para casos de teste usados na literatura. Nós também desenvolvemos um algoritmo genético multiobjectivo para resolver o problema com mais qualidade e eficiência do que com técnicas atuais. Testamos nossas soluções com cenários reais e artificiais publicados anteriormente e obtemos resultados superiores.
Abstract The urban transit routing problem (UTRP) consists of finding satisfying routes for public transportation within a city or region. Urban scenarios get more complex as time goes by, making the design of routes an overwhelming task whose results are often unsatisfactory, with high costs and travel times. We develop an exact MIP formulation for the problem and obtain best solutions, which were previously unknown, for common benchmarks. We also develop a multi-objective genetic algorithm to solve thie problem with higher quality and more efficiently than with current techniques. We benchmark our solutions on generally available real and artificial test cases and achieve better results.
Tipo Trabalho de conclusão de graduação
URI http://hdl.handle.net/10183/54127
Arquivos Descrição Formato
000855747.pdf (531.8Kb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.