STUDY OF GRASP ALGORITHMS APPLIED TO A PRODUCT DISTRIBUTION PROBLEM: A CASE STUDY

This work addresses the problem of product distribution of a dairy company located in Angicos/RN, modeled as a Traveling Salesman Problem (PCV), one of the best known NP-hard formulations in the literature of Combinatorial Optimization. Six distinct simulations were considered: a single route with 48 cities and five sub-routes containing 36, 24, 12, 7 and 6 cities, respectively. The instances were based on real data obtained via
Google Maps®, considering as optimization criteria both the total distance traveled (in kilometers) and the total travel time (in minutes).
To solve the problem, three variations of the GRASP (Greedy Randomized Adaptive Search Procedure) algorithm were developed and evaluated, followed by a local search phase based on the Lin-Kernighan function. The three variants differ in the strategy of constructing the Candidate Restricted List (LRC): the first uses fixed size with random selection (Grasp1); the second applies roulette selection (Grasp2); and the third adopts a quality criterion for the inclusion of candidates (Grasp3). The results obtained were compared with solutions already reported in the literature and showed that the proposed approaches are competitive. The analysis of the experiments indicated that the GRASP algorithms were able to match or surpass previous solutions in several instances, even establishing a new lower limit for one of the simulations. However, it was also observed that the algorithms reached their best solution in only one of the 20 runs for most scenarios