Dissertação

{en_GB=Flying Tourist Problem - An Integer Linear Programming Approach} {} EVALUATED

{pt=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., en=This work addresses the Flying Tourist Problem (FTP), which aims to find the best schedule, route, and set of flights for a given unconstrained multi-city flight request. The developed work proposes an Integer Linear Programming formulation with the intent of finding optimal solutions. This formulation was implemented in CPLEX and evaluated comparing its results and performance to other similar systems. The obtained results show that, contrary to the existing systems, this optimization system invariably finds the optimal solution. Moreover, to improve the computational performance for large instances, this system is integrated with a metaheuristic optimization algorithm. Furthermore, the FTP was adapted to a similar problem and the Generalized Flying Tourist Problem (GFTP) arised. This problem is a generalization of the FTP whereby it is required to find the best route in a graph which visits all specified subsets of cities. Considering similar size instances, this variation presents a cost decrease of 46% when compared to the FTP. Finally, multi-objective variations of both problems, the Multi-objective Flying Tourist Problem (MO-FTP) and the Multi-objective Generalized Flying Tourist Problem (MO-GFTP), were characterized and formulated. Both present advantages to the FTP concerning the travel time. In fact, compared to the FTP, the MO-FTP and the MO-GFTP presented, for same sized instances, decreases of 52% and 80%, respectively, in the traveling time.}
{pt=Problema do Caixeiro Viajante, Programação Linear Inteira, Optimização Combinatória, en=Traveling Salesman Problem, Integer Linear Programming, Combinatorial Optimization}

Novembro 27, 2019, 16:30

Orientação

ORIENTADOR

Vasco Miguel Gomes Nunes Manquinho

Departamento de Engenharia Informática (DEI)

Professor Associado

ORIENTADOR

Nuno Filipe Valentim Roma

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

Professor Auxiliar