Lagrangian Bounds and a Heuristic for the Two-Stage Capacitated Facility Location Problem

Introduction

The two-stage capacitated facility location problem can be defined as follows: a single product is produced at plants and then transported to depots, both having limited capacities. From the depots the product is transported to customers to satisfy their demands. The use of the plants/depots incurs a fixed cost, while transportation from the plants to the customers through the depots results in a variable cost. We need to identify what plants and depots to use, as well as the product flows from the plants to the depots and then to the customers such that the demands are met at a minimal cost.

Facility location problems have numerous applications and have been widely studied in the literature, see the review publications by Daskin, Snyder, and Berger (2003), Klose and Drexl (2004), and Melo, Mickel, and Saldanha-da-Gama (2009) and the references therein. Various applications of the facility location in supply chain optimization and management are presented in Wang (2011) and Minis et al. (2011). In Sahin and Süral (2007) the review of the hierarchical facility location models is presented focusing on applications and formulations of the problem. In what follows we focus more on solution approaches and techniques to solve facility location problems.

Various exact approaches have been proposed for the location problems. For example, Avella and Boccia (2007) presented a mixed dicut inequalities based formulation, a family of minimum knapsack inequalities of a mixed type, containing both binary and continuous (flow) variables for the capacitated problem and developed a branch and cut and price algorithm to deal with large scale instances. Klose and Drexl (2005) presented a new lower bound for the capacitated facility location problem based on partitioning the plant set and employing column generation. The use of valid inequalities in a branch-and-bound framework for capacitated facility location problem was studied in Aardal (1998). Osorio and Sánchez (2009) use a dual surrogate analysis to fix variables in the capacitated case.

Approximate approaches can be roughly divided into two large groups: metaheuristics and Lagrangian based techniques. Metaheuristic approaches to the problem like tabu search, GRASP, are discussed in Filho and Galvão (1998), Sun, Ducati, and Armentano (2007), and Sun (2008). Caserta and Quiñonez (2008) studied a cross entropy-based metaheuristic algorithm for the capacitated facility location problem. An algorithm for large instances is presented in Barahona and Chudack (2005), they used a heuristic procedure that produces a feasible integer solution and used a Lagrangian relaxation to obtain a lower bound on the optimal value. Chyu and Chang (2008) presented two local-search based metaheuristics for the multisource capacitated facility location problem.

A Lagrangian based heuristic for solving the capacitated plant location problem with side constraints was presented in Sridharan (1991). Approaches and relaxations proposed in the literature for the capacitated facility location problem are compared in Cornuejols, Sridharan, and Thizy (1991). Ramos and Sáenz (2005) applied the Fenchel cutting planes methodology to capacitated facility location problems and compared the results with a Lagrangian relaxation. Görtz and Klose (2009) presented a branch and bound method based on Lagrangian relaxations and subgradient optimization for solving large instances of the capacitated facility location problem.