Multi-period facility location and capacity expansion with modular capacities and convex short-term costs

Abstract

In this paper, we consider a multi-period facility location problem with capacity expansion motivated by the real-world problem of establishing hydrogen production infrastructure in Norway. The problem is formulated using modular capacities that capture economies of scale in production costs. The costs of opening a facility are represented by concave long-term costs, while the production costs of each capacity level are given by convex short-term costs. In our model, we allow only one expansion during the planning horizon, and have to observe limits on minimum production quantities. The objective is to minimize the sum of investment, expansion, production, and distribution costs while satisfying customer demand. To solve the problem we implement a solution method based on Lagrangian relaxation. The lower bound is calculated using a dynamic programming approach. To obtain an upper bound solution, we develop a greedy heuristic that converts the solution to the Lagrangian dual into a feasible solution. The approach is tested on different problem instances based on real-world data. The results show that our solution method based on Lagrangian relaxation outperforms Gurobi in terms of run time for all tested instances. Our Lagrangian based approach also always finds good or even near-optimal solutions, whereas Gurobi fails to find feasible solutions for some of the larger instances.