Bernardino, RaquelKapancioglu, Tomás Silva2024-04-012024-04-012024-03Kapancioglu, Tomás Silva (2024). “An iterated local search algorithm for the traveling purchaser problem”. Dissertação de Mestrado. Universidade de Lisboa. Instituto Superior de Economia e Gestãohttp://hdl.handle.net/10400.5/30504Mestrado Bolonha em Métodos Quantitativos para a Decisão Económica e EmpresarialThe Traveling Purchaser Problem (TPP) is a generalization of the Traveling Salesman Problem (TSP) in which a list of items must be acquired by visiting a subset of markets. The objective is to minimize the total cost sustained along the route, including purchasing and traveling costs. Due to the NP-hard nature of the problem, solving the TPP in an exact manner is computationally challenging, implying the need for heuristic approaches in order to obtain quality solutions efficiently. This study proposes an algorithm based on the metaheuristic Iterated Local Search (ILS), complemented by a route configuration procedure that adjusts the subset of markets in the solution. The algorithm is tested in benchmark instances, providing a performance comparison with other methods. The computational experiment for the asymmetric instances reveals the effectiveness and efficiency of the algorithm, outperforming previously published results with statistical significance. Additional experiments are presented for the symmetric instances, pointing to the competitiveness and versatility of the algorithm in relation to other heuristic approaches used in the literature.O problema do comprador viajante é uma generalização do problema do caixeiro viajante, no qual uma lista de itens tem de ser adquirida ao visitar um subconjunto de mercados. O objetivo consiste em minimizar o custo total que inclui os custos de compra dos itens e os custos de deslocação. Trata-se de um problema NP-difícil, pelo que resolvê-lo de forma exata é ineficiente em termos computacionais, implicando a necessidade de recorrer a métodos heurísticos de modo a obter soluções de qualidade de forma eficiente. Este estudo propõe um algoritmo baseado no conceito metaheurístico de pesquisa local iterativa, complementado com um procedimento de configuração de rota que ajusta o subconjunto de mercados da solução. O algoritmo é testado em instâncias de referência, proporcionando uma comparação de desempenho com outros resultados na literatura. A experiência computacional para as instâncias assimétricas revela a eficácia e eficiência do algoritmo, obtendo melhores resultados com significância estatística. São apresentadas experiências computacionais adicionais para as instâncias simétricas, apontando a competitividade e versatilidade do algoritmo em relação a outros métodos heurísticos usados na literatura.engTraveling purchaser problemMetaheuristicsIterated local searchRoute configurationProblema do comprador viajanteMeta-heurísticasPesquisa local iterativaConfiguração de rotamaster thesis