FenixEdu™

Dissertação

Flying Tourist Problem - An Integer Linear Programming Approach EVALUATED

Detalhes: O presente trabalho aborda o ”Flying Tourist Problem” (FTP) cujo principal objectivo é determinar o melhor agendamento, rota e conjunto de voos que permitem realizar um itinerário que percorre várias cidades, sem restrições, e realizada exclusivamente com uso de voos comerciais. O trabalho desenvolvido apresenta uma formulação linear inteira com o objectivo de encontrar soluções ótimas para este problema. Esta formulação foi posteriormente integrada no CPLEX e os resultados assim adquiridos foram comparados com sistemas idênticos existentes. Os resultados obtidos mostram que, ao contrário de outros sistemas existentes, este está capacitado para de forma consistente obter o resultado ótimo. Com o objectivo de melhorar a eficiência na resolução de problemas de grande dimensão, este sistema foi posteriormente integrado com um algorítmo de optimização metaheurístico. O FTP foi posteriormente adaptado a um problema idêntico pelo que foi formulado o ”Generalized Flying Tourist Problem” (GFTP). Este problema é uma generalização do FTP cujo principal objectivo é determinar o caminho de um grafo que percorre todos os subconjuntos de cidades constituintes. Comparativamente ao FTP, e em problemas de dimensão semelhante, o GFTP apresenta uma redução no custo total de 46%. Numa fase final, foram analisadas formulações multi-objectivo destes dois problemas, respectivamente o ”Multi-objective Flying Tourist Problem” (MO-FTP) e o ”Multi-objective Generalized Flying Tourist Problem” (MO-GFTP). Ambas formulações apresentam vantagens face ao FTP em termos de tempo de viagem. Em particular, comparativamente ao FTP, o MO-FTP e o MO-GFTP apresentaram, respectivamente, decréscimos de 52% e 80% no tempo de viagem.
Keywords: Problema do Caixeiro Viajante, Programação Linear Inteira, Optimização Combinatória

Discussão: novembro 27, 2019, 16:30