A Hybrid Genetic Algorithm and Simulated Annealing Approach for the Uncapacitated Facility Location Problem

Abstract

The Uncapacitated Facility Location Problem (UFLP), a well-known NP-hard combinatorial optimization problem, aims to minimize the costs associated with opening facilities and servicing customers. This study proposes a hybrid metaheuristic algorithm integrating Genetic Algorithm (GA) and Simulated Annealing (SA) to address UFLP. The proposed approach integrates the global exploration capabilities of GA with the local search effectiveness of SA to achieve robust optimization performance. By combining elite preservation, uniform crossover, and a systematic local search mechanism, the proposed algorithm effectively balances exploration and exploitation, allowing it to escape local optima while efficiently exploring large solution spaces. Extensive computational experiments were conducted on 15 different UFLP benchmark instances show that the hybrid algorithm consistently achieves optimal solutions for small and medium-sized problems. For larger instances (capa, capb, capc), the algorithm maintains competitive performance with minimal gaps from optimal values. Comparative analysis with other optimization algorithms shows that the proposed hybrid approach provides superior solution quality, especially for large instances. The effectiveness of the method is highlighted by its ability to achieve smaller gaps with more consistent solutions compared to existing algorithms, making it a promising approach for complex binary optimization problems.