Optimization of public transport networks: Reinforcement learning for smart mobility

Abstract

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.

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.