PT
Desenhar uma rede pública de transportes eficiente é um problema complexo (NP-difícil) que envolve,
entre outros, a escolha de paragens, dos melhores trajectos, a definição de horários e frequências, tendo
em conta múltiplos factores em conflito. Dada a complexidade, a busca por soluções óptimas é preterida
em favor do uso de métodos heurísticos (regras gerais de decisão) e recurso a conhecimento especializado,
que permitem encontrar soluções satisfatórias. Esta dissertação foca-se na otimização da rede de
transportes da Carris, em Lisboa, explorando a aplicação de mecanismos de aprendizagem reforçada (AR)
para resolver uma parte deste problema: encontrar melhores trajectos entre várias paragens, servidas por
um número variável de linhas – um problema de roteamento de veículos. Através do algoritmo Multi-task
Vehicle Routing Solver with Mixture-of-Experts, treinaram-se dois modelos. Os resultados foram
comparados com os da rede Carris e com os do algoritmo de economias de Clarke e Wright. A AR
demonstra potencial para “aprender” boas heurísticas e encontrar melhores soluções que as atuais, tendo
o modelo minimizado a distância em linha recta do menor troço da rede. No entanto, a complexidade da
mobilidade urbana é ainda um desafio, tendo sido necessário efectuar simplificações para modelar este
problema. Apesar das limitações, tais como os baixos recursos computacionais e a natureza estática dos
dados, esta análise demonstra que através da integração da informação de trânsito e do desenvolvimento
de algoritmos mais abrangentes, a AR tem o potencial de melhorar a eficiência destas redes e construir
soluções que se ajustem dinamicamente aos diferentes constrangimentos diários.
EN
Designing an efficient public transport network is a complex problem (NP-hard) that involves, among other
factors, selecting stops, determining the most optimal routes, and defining schedules and frequencies, all
while considering multiple conflicting factors. Given this complexity, the pursuit of optimal solutions is
often set aside in favor of heuristic methods (general decision rules) and expert knowledge, which allow
for identifying satisfactory solutions. This dissertation focuses on optimizing Lisbon’s Carris public
transport network by exploring the application of reinforcement learning (RL) mechanisms to address part
of this problem: finding more optimal routes between several stops served by a variable number of lines
– a vehicle routing problem. Two models were trained using the Multi-task Vehicle Routing Solver with
Mixture-of-Experts algorithm. The results were compared with the Carris network and the results given
by the Clarke and Wright Savings algorithm. RL shows potential in learning good heuristics and finding
better solutions than the current ones, as the model minimized the straight-line distance of the shortest
segment of the network. However, the complexity of urban mobility remains a challenge, requiring
simplifications to model this problem effectively. Despite limitations such as low computational resources
and the static nature of the data, this analysis demonstrates that by integrating traffic information and
developing more comprehensive algorithms, RL can improve the efficiency of these networks and create
solutions that dynamically adjust to different daily constraints.
