FenixEdu™

Dissertação

{pt_PT=Flight Time and Cost Minimization in Complex Routes} {} EVALUATED

Detalhes: {pt=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., en=The present work formalizes and addresses the Flying Tourist Problem (FTP), a NP-hard problem that occurs as a generalization of the Traveling Salesman Problem (TSP), and whose goal is to find the best schedule, route, and set of flights, for any given unconstrained multi-city flight request. In fact, despite the current existence of numerous flight search applications, most of them lack the ability to properly address unconstrained multi-city flight requests, since this problem is generally not tractable. In accordance, the main goal of this research is to develop a methodology that allows an efficient resolution of this rather demanding problem. To accomplish this, different heuristics and meta-heuristic optimization algorithms were considered, including the Ant Colony Optimization and the Simulated Annealing, allowing the identification of solutions in real-time, even for large instances. The developed methods were integrated into a web application prototype, allowing a fast resolution of user-defined requests. In particular, the implemented system was evaluated using different criteria, including the quality of its optimization system; the utility of the devised problem; and its performance compared to other similar systems. Furthermore, when comparing the developed system to the only known (but not-disclosed) alternative, it was shown that the developed application provides the cheapest and the best-recommended solutions, respectively 95% and 74% of the times. As a result, upon the planning of a complex multi-city trip, the developed system showed to allow the user to save a significant amount of time and money.}
Keywords: {pt=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., en=Flying Tourist Problem, Traveling Salesman Problem, Combinatorial Optimization, Ant Colony Optimization, Simulated Annealing, Web Application.}

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