Exact and metaheuristic algorithms for the urban transit routing problem

Abstract

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.

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.