Generate-and-Solve applied to the Order Picking Problem

This work addresses the Order Selection Problem (OSP), a Combinatorial Optimization problem proposed by Mercado Livre during the first optimization challenge organized by the Brazilian Society of Operational Research (SOBRAPO). In summary, the objective is to maximize the ratio of the number of items collected to the number of selected aisles, while respecting minimum and maximum item constraints. We applied the hybrid Generate-and-Solve framework, which combines a Biased Random-Key Genetic Algorithm (BRKGA) as a reduced-instance generator with an Integer Linear Programming model to solve them. Our approach explores promising subsets of aisles to work with a linear model, reduce the problem’s computational complexity, and ensure high-quality solutions. Computational experiments with twenty instances showed that the heuristic converged to the optimal solution found by the exact approach in four cases, and in the remaining instances, both approaches yielded similar results, thus demonstrating the effectiveness of the proposed method.