A computational study of a decomposition approach for the dynamic two-level uncapacitated facility location problem with single and multiple allocation.

Abstract

This work presents a computational study for two variants of a dynamic or multi-period two-level uncapacitated facility location problem. In this problem, first-level plants serve different demand patterns of scattered clients over a planning horizon via second-level facilities. In the first variant, second-level facilities can be supplied by only one of the plants (single assignment); whereas, in the second, they can be served by more than one of the first-level plants (multiple allocation). As the demands vary over time, the different operating settings for plants and facilities, and client assignments need to be sought in each period to serve demands at minimal installation and transportation costs. Since both problem variants arise naturally in the context of logistics systems, it is of interest to have solution methods at hand for practitioners and researchers. To provide such a tool, this work presents an efficient decomposition approach to solve the two problem variants. It relies on Benders decomposition reformulations combined with a greedy randomized adaptive search procedure and different Benders cut separation procedures. The devised solution framework outperformed CPLEX and its Benders built-in algorithm on solving two different challenging large-scale instance sets.