Aplicação do Problema do Comprador Viajante em uma lista de compras

Abstract

O problema do comprador viajante (TPP - Traveling Purchaser Problem), possui várias aplicações no mundo real, e neste trabalho iremos explorar sua aplicação na solução de uma lista de compras de supermercado. Por se tratar de um problema NP-Difícil, generalização do TSP, grande parte da literatura se concentra em heurísticas, porém também é feito um breve estudo sobre os algoritmos exatos. O foco deste trabalho está na busca e apresentação dos melhores parâmetros para o algoritmo (heurística) implementado, a partir da literatura existente, utilizando-se de experimentos com instâncias de testes previamente solucionadas para fins de comparação.

The Traveling Purchaser Problem (TPP) has several applications in the real world, and in this work we will explore its application in the solution of a supermarket shopping list. Because it is an NP-Hard problem, TSP generalization, much of the literature focuses on heuristics, but a brief study is also made on exact algorithms. The focus of this work is on the search and presentation of the best parameters for the algorithm (heuristic) implemented, from the existing literature, using experiments with previously solved test instances for comparison purposes.