Please use this identifier to cite or link to this item: http://hdl.handle.net/10316/31684
Title: Extensões do problema do caixeiro viajante
Authors: Oliveira, André Filipe Maurício de Araújo 
Orientador: Santos, José Luis Esteves dos
Keywords: Problema do caixeiro viajante; Otimização combinatória; Otimização multi-objetivo; Travelling salesman problem; Combinatorial optimization; Multi-objective optimization
Issue Date: 22-Jun-2015
Place of publication or event: Coimbra
Abstract: Esta dissertação tem como objetivo o estudo do problema do caixeiro viajante, um problema clássico de otimização combinatória. Apesar da sua simples descrição, o problema do caixeiro viajante é um problema NP-Difícil, não existindo até à data um algoritmo ótimo e eficiente para a sua resolução. Inicialmente será feito um estudo do problema nas suas variantes simples e múltipla (onde são considerados vários caixeiros). Em seguida será estudado o problema do caixeiro viajante multi-objetivo, também nas suas variantes simples e múltipla. Na otimização multi-objetivo o conceito de solução ótima é substituído pelo conceito de eficiência, deixando de haver um valor ótimo único para o problema. É introduzida a noção de dominância de forma a determinar o conjunto das soluções eficientes sendo este o objetivo na resolução de problemas multi-objetivo. Para cada um dos problemas abordados, serão referidas diversas variantes e formulações, bem como diversos algoritmos presentes na literatura para a sua resolução. Posteriormente são propostos novos algoritmos com o objetivo de resolver cada um dos problemas abordados. São apresentados resultados computacionais para cada método implementado, de forma a analisar o desempenho dos algoritmos propostos.
This thesis aims to study the travelling salesman problem, a classical problem of combinatorial optimization. Despite its simple description, the traveling salesman problem is NP-Hard, not existing, so far, an optimum and eficient algorithm to solve it. We start by studying the problem in its single and multiple variants (where multiple salesman are considered). Furthermore, we will study the multi-objective travelling salesman problem, also in its single and multiple variants. In multi-objective optimization, the concept of optimal solution is replaced by the concept of eficiency, ceasing to be a single optimal value to the problem. We introduce the notion of dominance in order to determine the set of eficient solutions which is the main purpose when solving a multi-objective problem. For each of the problems addressed, several variants and formulations will be referred, as well as several algorithms in the literature for their resolution. Afterward, new algorithms are proposed with the aim of solving each one of the problems addressed. For each implemented method, computational results are shown, in order to analyze the performance of the proposed algorithms.
Description: Dissertação de Mestrado em Matemática, área de Especialização em Estatística, Otimização e Matemática Financeira, apresentada à Faculdade de Ciências e Tecnologia da Universidade de Coimbra
URI: http://hdl.handle.net/10316/31684
Rights: openAccess
Appears in Collections:FCTUC Matemática - Teses de Mestrado

Files in This Item:
File Description SizeFormat
Tese_AndreOliveira.pdf1 MBAdobe PDFView/Open
Show full item record

Page view(s) 50

391
checked on Sep 22, 2020

Download(s) 10

1,537
checked on Sep 22, 2020

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.