GRASP heuristics for the product-to-shelf allocation problem in supermarkets

This work analyzes the supermarket shelf space allocation problem from a two-dimensional perspective, defining the vertical and horizontal positions and the linear footage occupied by each item to maximize profit margins. The goal is to balance the financial returns of retailers and suppliers by applying Category Management concepts. A GRASP-based metaheuristic is proposed, divided into two phases: constructive and local search. In the constructive phase, the aim is to generate feasible, high-quality solutions, allowing the temporary insertion of infeasible solutions to expand the search space. In the local search phase, the parameter $\alpha \in [0, 11]$ controls the degree of randomness, where larger values make the algorithm less greedy. At each GRASP iteration, the constructive heuristic runs up to the limit $\mathit{maxIt}$, updating the penalty of certain blocks using parameters $\beta_j \in [0, 2]$ (where $j=1, \dots, 6$). Computational tests were developed in Python on a Windows 11 environment (Intel Core i7-12700, 16 GB DDR5 RAM). Instances were built using real data and images from the edible oils category across four scenarios: olive oils, specialty oils, soybean oil, and an integrated approach combining all three. In the integrated model, module width and quantity vary within predefined intervals, causing categories to compete for available space, which differs from the individual resolution with fixed spaces. All instances had an execution time under 80 seconds. The configuration $(\beta_1, \beta_2, \beta_3, \beta_4, \beta_5, \beta_6) = (0.980, 0.990, 1.005, 0.995, 1.200, 0.995)$ yielded the best performance. Individual resolution produced results similar to the integrated model when space was properly partitioned. In both scenarios, products were structured without item overlap and with minimal shelf slack, maximizing display area utilization and enhancing consumer aesthetic perception.