Dissertação

Flight Time and Cost Minimization in Complex Routes EVALUATED

O presente trabalho formaliza e aborda um problema a que se designou Problema do Turista Voador, que ocorre como uma generalização do conhecido Problema do Caixeiro Viajante, e cujo objectivo é determinar o melhor agendamento, rota e conjunto de voos que permitem cumprir um itinerário que passa por várias cidades, sem restrições, e realizada apenas com base em voos comerciais. O principal objectivo deste trabalho é o desenvolvimento de uma metodologia eficiente para a resolução deste problema. Para concretizar este objectivo, considerou-se algoritmos de optimização baseados em técnicas de Optimização por colónia de formigas e Tempera Simulada, o que permite a determinação de soluções em tempo real, mesmo para problemas de grande dimensão. Os métodos desenvolvidos foram integrados e prototipados num serviço de internet, permitindo a resolução de problemas reais definidos pelo utilizador. O sistema implementado foi avaliado usando diferentes critérios, incluindo a qualidade do seu sistema de optimização; a utilidade do problema proposto; e o seu desempenho quando comparado com outros sistemas semelhantes. Além disso, ao comparar o sistema desenvolvido com a única alternativa (não aberta) actualmente existente, verificou-se que em 95% das vezes a solução encontrada é a mais barata e que em 74% das vezes corresponde à melhor solução recomendada. Consequentemente, o sistema desenvolvido oferece vantagens significativas no planeamento de viagens envolvendo várias cidades, permitindo poupar quantidades significativas de tempo e dinheiro.
Problema do Turista Voador, Problema do Caixeiro Viajante, Optimização Combinatória, Optimização por colónia de formigas, Tempera Simulada, Serviço de internet.

Novembro 19, 2018, 15:15

Publicação

Obra sujeita a Direitos de Autor

Orientação

ORIENTADOR

Nuno Filipe Valentim Roma

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

Professor Auxiliar

ORIENTADOR

Luís Manuel Silveira Russo

Departamento de Engenharia Informática (DEI)

Professor Auxiliar