Spatial Decomposition and Hybrid Optimization for the Online Order Batching Problem under Logistic Constraints

• Carlos V. Dantas Araújo UFC
• Jailon W. B. Oliveira da Silva UFC
• Pablo L. Braga Soares UFC

DOI: https://doi.org/10.5753/eniac.2025.13614

Resumo

Este trabalho aborda o Problema de Loteamento de Pedidos Online, desafio central na otimização de centros de distribuição. A abordagem híbrida proposta combina aprendizado de máquina não supervisionado (clusterização baseada em densidade espacial) com Têmpera Simulada Multi-Start para convergência rápida a soluções de alta qualidade. Validada em 144 instâncias de benchmark dos conjuntos Albareda-Sambola e Henn, o método alcança soluções com gap médio de 7.9% em relação ao estado da arte, enquanto reduz o tempo computacional em 93.2% em comparação ao mesmo. A técnica resolve instâncias grandes (n=250) em menos de 60 segundos, demonstrando viabilidade para operações logísticas em tempo real.

Referências

Albareda-Sambola, M., Alonso-Ayuso, A., Molina, E., and de Blas, C. S. (2009). Variable neighborhood search for order batching in a warehouse. Asia-Pacific Journal of Operational Research, 26(05):655–683.

Cals, L., Zhang, X., Dijkman, R. M., and van Dorst, M. (2020). An application of deep reinforcement learning to online order batching in a warehouse.

Gil-Borrás, S., Pardo, E. G., Alonso-Ayuso, A., and Duarte, A. (2020). Grasp with variable neighborhood descent for the online order batching problem. Journal of Global Optimization, 78(2):295–325.

Gil-Borrás, S., Pardo, E., Alonso-Ayuso, A., and Duarte, A. (2019). New vns variants for the online order batching problem. In Variable Neighborhood Search. ICVNS 2018, volume 11328 of Lecture Notes in Computer Science. Springer, Cham.

Henn, S. (2012). Algorithms for on-line order batching in an order picking warehouse. Computers & Operations Research, 39(11):2549–2563.

Kirkpatrick, S., Gelatt, C. D., and Vecchi, M. P. (1983). Optimization by simulated annealing. Science, 220(4598):671–680.

MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proceedings of the fifth Berkeley symposium on mathematical statistics and probability, 1(14):281–297.

Nicolai, B. M., Verboven, P., Scheerlinck, N., Verdijck, G., and Van Impe, J. F. (2014). Shelf life modelling for first-expired-first-out warehouse management. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 372(2017):20130306.

Pérez-Rodríguez, R., Hernández-Aguirre, A., and Jöns, S. (2015). A continuous estimation of distribution algorithm for the online order-batching problem. The International Journal of Advanced Manufacturing Technology, 79:569–588.

Petersen, C. G., Siu, C., and Heiser, D. R. (2004). The effect of warehouse cross aisles on order picking efficiency. International Journal of Production Research, 42(10):1927–1942.

Ross, S. M. (2014). Introduction to Probability Models. Academic Press, 11th edition.