An iterated local search algorithm for the traveling purchaser problem

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 para a competitividade e versatilidade do algoritmo em relação a outros métodos heurísticos usados na literatura.