Abordagens de otimização para o problema de compras em lote de múltiplos produtos em diferentes comércios eletrônicos

Abstract

The problem of purchasing multiple items from various suppliers involves minimizing the acquisition cost of a set of items available from different suppliers. Factors such as shipping costs, item availability, price, and quantity offered by each supplier are considered. This is a combinatorial optimization problem with exponential execution time. In this research, the suppliers are online retailers, and we consider that the problem must be solved on a Web server. The goal was to find mechanisms capable of solving the problem while reducing the computational cost compared to deterministic approaches, aiming to analyze the applicability of the proposed methods in the context of Web applications. To manage this complexity, four heuristic optimization approaches that approximate the minimum cost were proposed, implemented, and evaluated. These approaches were compared to the exact solution of the problem, obtained through Integer Linear Programming, whose computational complexity grows exponentially with the increase in the search space. The heuristic approaches investigated were: Greedy approach, Greedy Reduction, Divide and Conquer, and Genetic Algorithm. To evaluate the performance of these approaches, experiments were conducted with purchase orders containing different quantities of products. Two datasets were used: the real dataset, which reflects the stock context of 177 e-commerce stores, and the synthetic dataset, which replicates all records from the real dataset and expands them to ensure that all suppliers have all products in stock. The results of the experiments, including convergence times and solution values, were analyzed to compare the investigated approaches. Overall, all heuristics converged to solutions more quickly than the exact approach. The Greedy approach achieved the shortest convergence times, although it produced solutions with higher prices compared to Greedy Reduction and Divide and Conquer. Greedy Reduction presented the lowest prices in most experiments but took longer than the other approaches. Divide and Conquer, in most cases, achieved prices close to those of the Greedy approach, lower than those of Greedy Reduction, with execution times longer than the Greedy approach and shorter than Greedy Reduction. The proposed Genetic Algorithm proved unsuitable for solving the problem, as the majority of its solutions failed to converge toward the optimal result within the time constraints considered.