Dissertação
{en_GB=Optimisation of Periodic Train Timetables} {} EVALUATED
{pt=A presente tese de mestrado tem como foco o problema da otimização de horários de comboios periódicos do mundo real, e de grande dimensão, no que diz respeito a três objetivos distintos: minimizar o tempo total de viagem, maximizar a robustez do horário (i.e. a capacidade que o horário demonstra para absorver atrasos e evitar a sua propagação quando sujeito a perturbações), e minimizar a quantidade de relaxação efetivamente aplicada ao produzir soluções aproximadas para problemas sem solução (para os quais as respetivas restrições são previamente relaxadas). Para este problema preconizamos duas abordagens, ambas suportadas por um solucionador de SAT. Uma consiste num método exato baseado numa procura binária e numa heurística que, combinadas, produzem soluções ótimas. Outra constitui um método aproximado que recorre a técnicas de aprendizagem por reforço, em conjunto com SAT, para obter soluções otimizadas para problemas de maiores dimensões. Os resultados apresentados realçam as vantagens e inconvenientes de cada uma das abordagens e validam a sua aplicabilidade aos três objetivos anteriormente referidos. Ademais, é também apresentada uma comparação da eficácia destes métodos com outras abordagens do estado-da-arte. Os resultados sugerem que o potencial das técnicas de aprendizagem automática e SAT, quando usadas em conjunto neste domínio, se encontra ainda numa fase muito precoce, revelando contudo desde já resultados muito promissores. De facto, os resultados do nosso método posicionam-se entre o estado-da-arte em alguns problemas disponíveis publicamente para avaliação., en=In this MSc thesis we focus on the optimisation of real-world, large-sized periodic train timetables with respect to three distinct objectives: minimising the total travel time, maximising the timetable robustness (i.e. the timetable capacity to absorb delays and prevent their propagation when subjected to disturbances), and minimising the amount of relaxation effectively used while obtaining approximate solutions for infeasible problems (whose constraints are previously relaxed). We propose two approaches to this problem, both supported by a SAT solver. One is an exact method based on a binary search and an heuristic which, combined, produce optimal solutions. The other is an approximate method which uses reinforcement learning in conjunction with SAT to obtain optimised solutions for bigger problems. The results that we present highlight the strengths and weaknesses of each method and validate their applicability to the three aforementioned objectives. Furthermore, a performance comparison with other state-of-the-art approaches is given. Our results suggest that the joint potential of machine learning and SAT techniques in this field is still in its beginnings but already providing up-and-coming outcomes, actually positioning the results of our method amongst the state-of-the-art on some publicly available benchmarking problems.}
maio 29, 2018, 14:30
Publicação
Obra sujeita a Direitos de Autor
Orientação
ORIENTADOR
Departamento de Engenharia Informática (DEI)
Professor Associado
