In this study, a Lagrangean heuristic based on Lagrangean relaxation and subgradient optimization is proposed for the two-stage modular capacitated facility location problem. The objective is to minimize the cost of locating and operating plants and warehouses, plus the cost of transporting goods at both echelons to satisfy the demand of customers. The difference of our study from the two-stage capacitated facility location problem is the existence of multiple capacity levels as a candidate for each plant in the problem. Each capacity level has a minimum production capacity which has to be satisfied to open the relevant capacity level. Obviously, a single capacity level can be selected for an opened facility location. In the second echelon, the warehouses are capacitated and have unique fixed and variable costs for opening and operating. Multiple sourcing is allowed in both transportation echelons.
Firstly, we develop a mixed integer linear programming model for the two-stage modular capacitated facility location problem. Then we develop a Lagrangean heuristic to solve the problem efficiently. Our Lagrangean heuristic consists of three main components: Lagrangean relaxation, subgradient optimization and a primal heuristic. Lagrangean relaxation is employed for obtaining the lower bound, subgradient optimization is used for updating the Lagrange multipliers at each iteration, and finally a three-stage primal heuristic is created for generating the upper bound solutions.
At the first stage of the upper bound heuristic, global feasibility of the plants and warehouses is inspected and a greedy heuristic is executed, if there is a global infeasibility. At the next stage, an allocation heuristic is used to assign customers to warehouses and warehouses to plants sequentially. At the final stage of the upper bound heuristic, local feasibilities of the plants are investigated and infeasible capacity levels are adjusted if necessary.
In order to show the efficiency of the developed heuristic, we have tested our heuristic on 280 problem instances generated randomly but systematically. The results of the experiments show that the developed heuristic is efficient and effective in terms of solution quality and computational effort especially for large instances.
| Identifer | oai:union.ndltd.org:METU/oai:etd.lib.metu.edu.tr:http://etd.lib.metu.edu.tr/upload/3/12609534/index.pdf |
| Date | 01 May 2008 |
| Creators | Sevinc, Selim |
| Contributors | Meral, Sedef |
| Publisher | METU |
| Source Sets | Middle East Technical Univ. |
| Language | English |
| Detected Language | English |
| Type | M.S. Thesis |
| Format | text/pdf |
| Rights | To liberate the content for public access |
Page generated in 0.0021 seconds