Two Stage Capacitated Facility Location Problem: Lagrangian Based Heuristics

Two Stage Capacitated Facility Location Problem: Lagrangian Based Heuristics

Igor Litvinchev (Nuevo Leon State University - UANL, Mexico), Miguel Mata (Nuevo Leon State University - UANL, Mexico), Lucero Ozuna (Nuevo Leon State University - UANL, Mexico), Jania Saucedo (Nuevo Leon State University - UANL, Mexico) and Socorro Rangel (São Paulo State University – UNESP, Brazil)
DOI: 10.4018/978-1-4666-2086-5.ch014
OnDemand PDF Download:
No Current Special Offers


In the two-stage capacitated facility location problem, a single product is produced at some plants in order to satisfy customer demands. The product is transported from these plants to some depots and then to the customers. The capacities of the plants and depots are limited. The aim is to select cost minimizing locations from a set of potential plants and depots. This cost includes fixed cost associated with opening plants and depots, and variable cost associated with both transportation stages. In this work two different mixed integer linear programming formulations are considered for the problem. Several Lagrangian relaxations are analyzed and compared, a Lagrangian heuristic producing feasible solutions is presented. The results of a computational study are reported.
Chapter Preview

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.

Complete Chapter List

Search this Book: