FenixEdu™

Dissertação

Flight Time and Cost Minimization in Complex Routes EVALUATED

Detalhes: 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.
Keywords: 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.

Discussão: novembro 19, 2018, 15:15