Otimização de rotas para realização de pesquisas de preços em supermercados

Abstract

In the city of Londrina/PR, the basket of goods price inflation is monthly researched and published by the Núcleo de Pesquisas Econômicas Aplicadas (NUPEA) from Universidade Tecnológica Federal do Paraná (UTFPR). In this research prices are collected on the last workday of the current month in 12 different supermarkets scattered throughout the city. The distribution of routes between travelers must be evenly balanced considering the total time cost assigned to each researcher. In order to solve this problem, a hill-climbing based algorithm to search for a solution of a Multiple Asymmetric Traveling Salesman Problem is proposed. The solution to this particular problem must consider the division of the routes between 𝑘 number of researchers and the minimization of total time of the 𝑘 routes. The first step to this algorithm is to generate an initial solution with another algorithm called Stochastic Nearest Neighbor and slice it in sub-routes in a way that each one of them has a time cost lower than 180 minutes. The algorithm has three different neighborhood structures based in random insertion of points, random points swap and a random choice between one of the two other methods. The number of iterations is an input parameter of the problem and after going through all iterations the algorithm returns the best global solution it could find. Besides the real-world instance, the algorithm’s performance was evaluated in 19 instances from tsplib95 instance library. After which, it was possible to see that the algorithm performs better in small instances and its computational cost grows exponentially with the number of points with no significant improvement of the global solution. Applied to the basket of good price inflation research, the algorithm found a solution with 3 travelers with total time cost of 368 minutes in which the biggest route takes 125 to complete.