  This article presents a matheuristic algorithm for the single-source
capacitated facility location problem (SSCFLP) and its variants: SSCFLP with K
facilities (SSCKFLP), SSCFLP with contiguous service areas (CFLSAP), and SSCFLP
with K facilities and contiguous service areas (CKFLSAP). The algorithm starts
from an initial solution, and iteratively improves the solution by exactly
solving large neighborhood-based sub-problems. The performance of the algorithm
is tested on 5 sets of SSCFLP benchmark instances. Among the 272 instances, 191
optimal solutions are found, and 35 best-known solutions are updated. For the
largest set of instances with 300-1000 facilities and 300-1500 customers
(Avella and Boccia 2009), the proposed algorithm outperforms existing methods
in terms of the solution quality and the computational time. Furthermore, based
on two geographic areas, two sets of instances are generated to test the
algorithm for solving SSCFLP and its variants. The solutions found by the
proposed algorithm approximate optimal solutions or the lower bounds with
average gaps of 0.07% for SSCFLP, 0.22% for CFLSAP, 0.04% for SSCKFLP, and
0.13% for CKFLSAP.
