Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities

Lagrangian Heuristics for Large-Scale Dynamic Facility Location with Generalized Modular Capacities

0.00 Avg rating0 Votes
Article ID: iaor20171606
Volume: 29
Issue: 2
Start Page Number: 388
End Page Number: 404
Publication Date: May 2017
Journal: INFORMS Journal on Computing
Authors: , ,
Keywords: combinatorial optimization, heuristics, programming: dynamic, simulation
Abstract:

We consider the dynamic facility location problem with generalized modular capacities, a multiperiod facility location problem in which the costs for capacity changes may differ for all pairs of capacity levels. The problem embeds a complex cost structure and generalizes several existing facility location problems, such as those that allow temporary facility closing or capacity expansion and reduction. As the model may become very large, general‐purpose mixed‐integer programming (MIP) solvers are limited to solving instances of small to medium size. In this paper, we extend the generalized model to the case of multiple commodities. We propose Lagrangian heuristics, based on subgradient and bundle methods, to find good quality solutions for large‐scale instances with up to 250 facility locations and 1,000 customers. To improve the final solution quality, a restricted MIP model is solved based on the information collected through the solution of the Lagrangian dual. Computational results show that the Lagrangian‐based heuristics provide highly reliable results for all problem variants considered. They produce good quality solutions in short computing times even for instances where state‐of‐the‐art MIP solvers do not find feasible solutions. The strength of the formulation also allows the method to provide tight bounds on the optimal value. Data and the online appendix are available at https://doi.org/10.1287/ijoc.2016.0738.

Reviews

Required fields are marked *. Your email address will not be published.