Two Stage Capacitated Facility Location Problem: Lagrangian Based Heuristics

1. 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 & Berger (2003), Klose & Drexl (2004) and Melo, Mickel & 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 & 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 & Boccia (2007) presented 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 & Drexl (2005) considered 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 & 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 & Galvão (1998), Sun, Ducati and Armentano (2007) and Sun (2008). Caserta & 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 & 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 & Chang (2008) presented two local-search based metaheuristics for the multisource capacitated facility location problem.