Matheuristic Fixed Set Search Applied to the Two-Stage Capacitated Facility Location Problem

Abstract

This paper addresses the Two-Stage Capacitated Facility Location Problem (TSCFLP), a challenging optimization problem with significant applications in supply chain network design. The need for effective solution methods arises from the problem’s large-scale complexity and the strong influence of spatial and capacity constraints on solution quality. We propose a twofold contribution: first, an adaptive greedy algorithm that generates high-quality initial solutions, achieving markedly better results than traditional constructive heuristics at comparable computational costs; and second, the adaptation of the Matheuristic Fixed Set Search (MFSS) to the TSCFLP. Computational experiments on standard benchmark instances show that MFSS is highly competitive with state-of-the-art methods, while demonstrating improved robustness by consistently reaching high-quality solutions across multiple runs. In addition, this work introduces geographically realistic instances—beyond the synthetic datasets used in previous research—and demonstrates that these experiments reveal regional cost dependencies and spatial utilization patterns, underscoring the practical value of MFSS in supporting real-world distribution network design. Overall, the findings emphasize that the main strength of MFSS lies in its flexible architecture, which combines solution quality, consistency, and ease of adaptation to related facility location variants.