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

Abstract

This paper introduces a hybrid methodology for the Single Row Facility Layout Problem (SRFLP), combining unsupervised learning with the Large Neighborhood Search (LNS) metaheuristic. The proposed approach uses clustering algorithms to analyze the problem’s cost matrix, generating a high-quality initial solution that guides the LNS. The method was tested on 128 benchmark instances, demonstrating high performance. For classical instances (n ≤ 110), the proposed method consistently found solutions matching the state-of-the-art quality. In large-scale instances (n ≤ 500), it achieved the best-known solutions in approximately 40% of cases, with an average gap below 1% in the remaining instances.

References

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.