We consider Two-echelon Single Source Capacitated Facility Location Problem (TSCFLP). TSCFLP is a variant of Capacitated Facility Location Problem (CFLP), which has been an important issue in both academic and industrial aspects.
Given a set of possible facility (warehouse / plant) locations, a set of customers, TSCFLP is a decision problem to find a set of facility locations to open and to determine an allocation schedule that satisfies the demands of the customers and the capacity constraints of the facilities. The objective is to minimize the overall cost which is the sum of open and operational costs of facilities (warehouse / plant) and transportation costs from plants to customers via warehouses. It can be shown that TSCFLP is strongly NP-hard. For TSCFLP, few algorithms are known, which are heuristics.
We propose a disaggregated version of the standard mixed integer programming formulation of TSCFLP. We also provide a class of valid inequalities. Branch-and-price algorithm with cutting plane method is used to find an optimal solution. Efficient branching strategy compatible with subproblem optimization is also provided. We report computational results of tests on 15 randomly generated instances.
