Dissertação

{en_GB=Optimization of Public Transport Routes by Means of AI Techniques} {} EVALUATED

{pt=O serviço de transportes públicos é uma parte importante no funcionamento de uma cidade. À medida que o trânsito aumenta, a necessidade de otimizar o serviço torna-se mais evidente. A optimização de rotas de autocarros, que apresenta uma complexidade combinatorial elevada, não pode ser resolvido, em tempo útil, usando métodos matemáticos exatos. Ao criar métodos capazes de desenhar rotas otimizadas, todo o sistema de transporte de autocarros beneficia de um aumento de qualidade relevante. No nosso trabalho, procuramos na literatura existente, por métodos usados em outros problemas de roteamento em busca de um método promissor para o Problema do Roteamento de Autocarros. Desenvolvemos uma versão do algoritmo da Colônia de Formigas que é capaz de, dada a distribuição de passageiros pelas paragens de autocarro de uma rede, computar uma rota de autocarro. Com a intenção de estender o algoritmo para operar com múltiplos autocarros, apresentamos também uma versão multi-autocarro que testamos, também, usando o mesmo problema de referência., en=The bus transportation service is an important part of a cities infrastructure and, as transit keeps increasing, the need to optimize this service grows. The optimization of bus routes, which is a complex combinatorial problem, commonly known as the Bus Routing Problem, cannot be solved through exact mathematical methods in useful time. By creating methods that are able to design optimized bus routes, the overall public transportation service quality would improve greatly. We researched the literature for methods that had already been applied to other routing problems, looking to find a good candidate method for the Bus Routing problem. We developed a version of an Ant Colony Algorithm that was able to, given a network and the distribution of passengers, compute a bus route, using one bus. With the intention of expanding our algorithm to work with multiple buses, we also presented an extended multi-bus version and tested it on the same reference problem.}
{pt=Algoritmo da Colônia de Formigas, Problema do Roteamento de Autocarros, Problema do caminho mais curto, Problemas de Roteamento, Problema do Roteamento Urbano, Otimização de Rotas de Autocarros, en=Ant Colony Algorithm, Bus Routing Problem, Shortest Path Problem, Routing Problems, Urban Bus Network Design, Bus Network Optimization}

Dezembro 5, 2019, 13:0

Orientação

ORIENTADOR

Fernando Henrique Côrte-Real Mira da Silva

Departamento de Engenharia Electrotécnica e de Computadores (DEEC)

Professor Auxiliar