Utilize este identificador para referenciar este registo: http://hdl.handle.net/10451/20053
Título: Meta-heurísticas para o problema do traveling purchaser
Autor: Bernardino, Raquel Monteiro de Nobre Costa
Orientador: Paias, Ana Maria Duarte Silva Alves, 1963-
Palavras-chave: Problema do traveling purchaser
Meta-heurísticas
Algoritmos genéticos
Pesquisa local
Biased random key genetic algorithm
Teses de mestrado - 2015
Data de Defesa: 2015
Resumo: Dados um conjunto de mercados potenciais, uma lista de itens e um depósito, o problema do traveling purchaser (PTP) consiste em determinar uma rota de custo mínimo começando e acabando no depósito e que contenha um subconjunto de mercados de forma a ser possível adquirir todos os itens da lista. Conhecem-se os itens disponíveis em cada mercado, bem como o respetivo custo de aquisição, e o custo de deslocação entre cada par de mercados e entre cada mercado e o depósito. Note-se que cada item é vendido em pelo menos um mercado, caso contrário o problema seria impossível. A cada rota está associado um custo que é a soma dos custos de deslocação e de aquisição. O PTP tem inúmeras variantes mas nesta dissertação apenas será estudada a variante do PTP sem capacidades. Pretende-se adquirir uma unidade de cada item e cada mercado tem disponível no máximo uma unidade. O PTP pertence à classe de problemas NP-difícil, sendo essa a principal razão pela qual se recorre a métodos heurísticos para o resolver. Nesta dissertação são apresentadas três meta-heurísticas, cada uma composta por um algoritmo genético seguido de um procedimento de pesquisa local. Os três algoritmos genéticos representam as diferentes hierarquias de decisão associadas a ambas as partes do problema: rota e aquisição. A pesquisa local é baseada em técnicas de add e drop. Para comparar os métodos propostos foram utilizadas instâncias de referência. Na generalidade dos casos o valor das soluções obtidas recorrendo às meta-heurísticas têm um desvio inferior a 1% relativamente ao valor da solução ótima tendo estas soluções sido obtidas num tempo computacional razoável. Comparativamente a métodos propostos por outros autores, as meta-heurísticas resolvem as instâncias de teste num tempo computacional inferior e oferecem soluções para casos de estudo que os outros métodos não conseguiam resolver.
Given a set of markets, a list of items and a depot, the traveling purchaser problem (TPP) consists in determining one route with a minimal cost that satisfies the following conditions: it begins and ends in the depot and we need to be able to buy all the items in the list in the subset of markets that belong to the route. We know which items are sold in each market and their cost, and the cost of traveling between each pair of markets and between each market and the depot. Every item must be sold in at least one market or otherwise the problem would be impossible. Each route has a cost, which is the sum of the traveling cost with the purchase cost. There are several variants of the TPP but in this thesis we will study the uncapacited version. We only wish to buy a copy of each item which is the maximum quantity available in each market. The TPP belongs to the class of NP-hard problems and this is the main reason why heuristic methods are used to solve the problem under study. In this thesis we present three meta-heuristics, each one composed by a genetic algorithm and a local search procedure. The three genetic algorithms represent the several ways we can decide which part of the problem is more important: route, purchase or route and purchase. The local search procedure is based on add and drop techniques. To compare the meta-heuristics we used benchmark instances. In the majority of cases we obtained solutions with a gap lower than 1% regarding the optimal solution within a reasonable computational time. Comparing with methods proposed by other authors, ours are able to solve the benchmark instances in less time and can find solutions to instances that the other methods could not.
Descrição: Tese de mestrado, Estatística e Investigação Operacional (Investigação Operacional), Universidade de Lisboa, Faculdade de Ciências, 2015
URI: http://hdl.handle.net/10451/20053
Designação: Mestrado em Estatística e Investigação Operacional (Investigação Operacional)
Aparece nas colecções:FC - Dissertações de Mestrado

Ficheiros deste registo:
Ficheiro Descrição TamanhoFormato 
ulfc114347_tm_Raquel_Bernardino.pdf1,7 MBAdobe PDFVer/Abrir


FacebookTwitterDeliciousLinkedInDiggGoogle BookmarksMySpace
Formato BibTex MendeleyEndnote Degois 

Todos os registos no repositório estão protegidos por leis de copyright, com todos os direitos reservados.