Solving the multi-commodity capacitated multi-facility Weber problem using Lagrangean relaxation and a subgradient-like algorithm

Abstract

The Multi-commodity Capacitated Multi-facility Weber Problem (MCMWP) is concerned with locating I-capacitated facilities in the plane in order to satisfy the demands of J customers for K commodities so that the total transportation cost is minimized. We propose a Lagrangean relaxation scheme and a subgradient-like algorithm based on the relaxation of the capacity and commodity bundle constraints. The resulting subproblem is a variant of the well-known Multi-facility Weber Problem and it can be solved by using column generation and branch-and-price on an equivalent set covering formulation, which is accurate but extremely inefficient. Therefore, we devise different strategies to increase the efficiency. They mainly benefit from the effective usage of the lower and upper bounds on the optimal value of the Lagrangean subproblem. On the basis of extensive computational tests, we can say that they increase the efficiency considerably and result in accurate Lagrangean heuristics.

Keywords:

• multi-commodity facility location allocation
• Lagrangean relaxation
• discrete approximation

Acknowledgements

We thank the two anonymous referees for their valuable comments, which have helped improve this article. This research was supported by the Turkish Scientific and Technological Research Council (TÜBİTAK) Research Grant No: 107M462, and Galatasaray University Scientific Research Projects Grant No: 07.402.014, 10.402.001 and 10.402.019. The first author acknowledges the partial support of National Graduate Scholarship Program for PhD Students awarded by TÜBİTAK.