A general corridor method-based approach for capacitated facility location

Abstract

The Capacitated Facility Location Problem (CFLP) is a well-known optimisation problem with applications in a number of fields, such as distribution system planning, telecommunication network design, and supply chain design. The goal of this paper is to present a matheuristic algorithm based on the corridor method, to develop a general algorithm for a number of variants of the CFLP. The algorithm exploits solutions obtained via Lagrangean relaxation and builds corridors around such solutions via the introduction of constraints around the incumbent solution, used to limit the size of the solution space explored at each iteration. A thorough exploration of the neighbourhoods induced by the corridors is carried out using a mixed integer programming (MIP) solver. More precisely, we solve to (near) optimality over 500 benchmark instances, using the single-source as well as the multi-source formulations, both in the nominal variant, i.e. the deterministic version of the problem, and the robust variant, i.e. the version obtained when using robust optimisation to model the uncertainty of the problem parameters. The performance of the algorithm is highly competitive when compared with the best approaches proposed in the literature for each variant of the CFLP, especially considering that the algorithm has not been designed with a specific CFLP formulation in mind.

Keywords:

• location
• matheuristic
• corridor method
• robust optimisation

Disclosure statement

No potential conflict of interest was reported by the authors.

Supplemental data

Supplemental data for this article can be accessed at https://doi.org/10.1080/00207543.2019.1636320.

Additional information

Funding

Research Reported in this paper was partially funded by the Spanish Ministry of Economy and Competitiveness. Grant No. ECO2014-52925-P.