Dissertação

Optimisation of Periodic Train Timetables EVALUATED

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.
Horários de comboios periódicos, Otimização, Periodic Event Scheduling Problem, SAT, Aprendizagem por reforço

Maio 29, 2018, 14:30

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Ernesto José Marques Morgado

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Ricardo Lopes de Saldanha

SISCOG

Especialista