Paias, Ana Maria Duarte Silva Alves,1963-Oliveira, Marta Guerreiro Duarte Mesquita de,1961-Teixeira, Raquel Maria Pinheiro2016-09-132016-09-1320162016http://hdl.handle.net/10451/24658Tese de mestrado em Estatística e Investigação Operacional, apresentada à Universidade de Lisboa, através da Faculdade de Ciências, 2016O problema do caixeiro viajante (TSP) é um problema com diversas aplicações na medida em que muitas das situações da vida real podem ser modeladas como um problema do caixeiro viajante. Deste modo, ao longo dos anos, o TSP tem sido dos mais estudados em Investigação Operacional. Nesta dissertação é estudada uma variante do TSP, nomeadamente o problema do caixeiro viajante com selecção de hotéis (TSPHS), o qual tem igualmente diversas aplicações práticas. Dados um conjunto de clientes a visitar e um conjunto de potenciais hotéis para pernoitar, sendo conhecidas as distâncias entre clientes e entre clientes e hotéis, o TSPHS consiste em determinar uma rota que visite todos os clientes começando e acabando num mesmo hotel pré-definido. A rota deverá ser tal que possa ser dividida em percursos com duração não superior a um dado limite de tempo inferior a um dia. Por outro lado, cada percurso deverá ter início e fim em algum dos hotéis disponíveis, não tendo necessariamente que ser o mesmo. O objetivo é minimizar o número de percursos e simultaneamente a distância total percorrida. Sendo o TSPHS uma extensão do TSP, ele é também um problema NP-difícil, pelo que a existência de métodos heurísticos como auxílio à resolução destes problemas é fundamental. Nesta dissertação são apresentadas duas meta-heurísticas baseadas em algoritmos genéticos combinados com um procedimento de pesquisa local, que considera oito operadores de vizinhança, e um algoritmo de perturbação de soluções. Foram testados vários parâmetros por forma a obter os melhores resultados para as instâncias de referência utilizadas. Os resultados obtidos foram comparados com os resultados de outros autores. Para uns casos são obtidas melhores soluções para outros não.The traveling salesman problem (TSP) has many applications since there are many reallife situations which can be modeled as a traveling salesman problem. Thus, over the years, TSP has been one of the most studied problems in Operational Research. This thesis addresses a variant of TSP, namely the traveling salesman problem with hotel selection (TSPHS). The TSPHS has also many practical applications. Given a set of customers to be visited and a set of potential hotels to spend the night, the TSPHS consists in determining one route starting and ending in one given hotel that visits all customers. The route is divided into trips lasting no more than a given limit of time. Moreover, each trip must begin and end at any of the available hotels, not necessarily the same. The goal is minimize the number of trips and simultaneously the total traveled distance. Being the TSPHS an extension of the TSP, it is also an NP-hard problem, so the development of heuristic methods as an aiding tool to solve these problems is crucial. This thesis proposes two meta-heuristics based on genetic algorithms combined with a local search procedure which uses eight neighborhood operators and a solution perturbation algorithm. Various parameters were tested in order to obtain the best results for the used benchmark instances. The results obtained were compared with results of other authors. For some cases are obtained better solutions for others not.porCaixeiro viajante com seleção de hotéisMeta-heurísticasAlgoritmos genéticosPesquisa localmaster thesis201330431