Clustering-LNS: Hybrid Methodology for the Single Row Facility Layout Problem

• 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.13642

Resumo

Este trabalho introduz uma metodologia híbrida para o Problema de Arranjo Físico em Linha Única (SRFLP), combinando aprendizado não supervisionado com a meta-heurística de Busca em Vizinhança Ampla (LNS). A abordagem proposta utiliza algoritmos de clusterização para analisar a matriz de custos do problema, gerando uma solução inicial de alta qualidade que guia a LNS. O método foi testado em 128 instâncias de benchmark, demonstrando alto desempenho. Para instâncias clássicas (n ≤ 110), o método proposto encontrou consistentemente soluções de qualidade igual ao estado da arte. Em instâncias de grande escala (n ≤ 500), alcançou as melhores soluções conhecidas em aproximadamente 40% dos casos, com um gap médio inferior a 1% nos demais.

Referências

Amaral, A. R. and Letchford, A. N. (2013). A polyhedral approach to the single row facility layout problem. Mathematical Programming, 141(1-2):453–477.

Anjos, M. F., Kennings, A., and Vannelli, A. (2005). A semidefinite optimization approach for the single-row layout problem with unequal dimensions. Discrete Optimization, 2(2):113–122.

Anjos, M. F. and Yen, G. (2009). Provably near-optimal solutions for very large single-row facility layout problems. Optimization Methods and Software, 24(4-5):805–817.

Bishop, C. M. (2006). Pattern recognition and machine learning. springer.

Blum, C. and Roli, A. (2003). Metaheuristics in combinatorial optimization: Overview and conceptual comparison, volume 35. ACM.

Garey, M. R. and Johnson, D. S. (1979). Computers and intractability: A guide to the theory of np-completeness.

Hastie, T., Tibshirani, R., and Friedman, J. (2009). The elements of statistical learning: data mining, inference, and prediction. Springer.

Kothari, R. and Ghosh, D. (2014a). An efficient genetic algorithm for single row facility layout. Optimization Letters, 8(2):679–690.

Kothari, R. and Ghosh, D. (2014b). A scatter search algorithm for the single row facility layout problem. Journal of Heuristics, 20(2):125–142.

Ng, A. Y., Jordan, M. I., and Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 14:849–856.

Rubio-Sánchez, M., Gallego, M., Gortázar, F., and Duarte, A. (2015). Grasp with path relinking for the single row facility layout problem. Knowledge-Based Systems, 89:303–313.

Shaw, P. (1998). Using constraint programming and local search methods to solve vehicle routing problems. In International Conference on Principles and Practice of Constraint Programming, pages 417–431. Springer.

Von Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and computing, 17(4):395–416.