Vertical Decomposition Approach to Solve Single Stage Capacitated Warehouse Location Problem (SSCWLP)

Priyanka Verma, R. R. K. Sharma

.

DOI: 10.4236/ajor.2011.13013                

Abstract

Single Stage Capacitated Warehouse Location Problem (SSCWLP) has been attempted by few researchers in the past. These are Geoffrion and Graves [1], Sharma [2], Sharma [3] and Sharma and Berry [4]. In this paper we give a “vertical decomposition” approach to solve SSCWLP that uses Lagrangian relaxation. This way SSCWLP is broken into two versions of capacitated plant location problem (the CPLP_L and CPLP_R) by relaxing the flow balance constraints. For CPLP_R, we use well known Lagrangian relaxations given in literature (Christofides and Beasley [5] and Nauss [6]); and adopt them suitably for solving CPLP_L. We show theoretically in this paper that SSCWLP can be more efficiently solved by techniques of vertical decomposition developed in this paper than the method available in literature (Sharma and Berry [4]). Encouraging computational study is reported in this paper.

Keywords

Single Stage Capacitated Warehouse Location Problem, Linear Programming Relaxation, Lagrangian Relaxation, Vertical Decomposition

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	A. M. Geoffrion and G. W. Graves, “Multicommodity Distribution System Design by Benders Decomposition,” Management Science, Vol. 20, No. 5, 1974, pp. 822-844. doi:10.1287/mnsc.20.5.822
[2]	R. R. K. Sharma, “Modeling a Fertilizer Distribution System,” European Journal of Operational Research, Vol. 51, No. 1, 1991, pp. 24-34. doi:10.1016/0377-2217(91)90142-I
[3]	R. R. K. Sharma, “Food Grains Distribution in the Indian Context: An Operational Study,” In: A. Tripathi and J. Rosenhead, Eds., Operations Research for Development, New Age International Publishers, New Delhi, 1996, pp. 212-227.
[4]	R. R. K. Sharma and V. Berry, “Developing New Formulations and Relaxations of Single Stage Capacitated Ware- house Location Problem (SSCWLP): Empirical Investigation for Assessing Relative Strengths and Computational Effort,” European Journal of Operational Research, Vol. 177, No. 2, 2007, pp. 803-812. doi:10.1016/j.ejor.2005.11.028
[5]	N. Christofides and J. E. Beasley, “Extensions to a Lagrangean Relaxation Approach for the Capacitated Warehouse Location Problem,” European Journal of Operational Research, Vol. 12, No. 1, 1983, pp. 19-28. doi:10.1016/0377-2217(83)90179-0
[6]	R. M. Nauss, “An Improved Algorithm for the Capacitated Facility Location Problem,” Journal of Operational Research Society, Vol. 29, No. 12, 1978, pp. 1195-1201.
[7]	M. T. Melo, S. Nickel and F. Saldanha-da-Gama, “Facility Location and Supplychain Management—A Review,” European Journal of Operational Research, Vol. 196, No. 2, 2009, pp. 401-412. doi:10.1016/j.ejor.2008.05.007
[8]	K. S. Hindi and T. Basta, “Computationally Efficient Solution of a Multiproduct, Two-Stage Distribution-Loca- tion Problem,” The Journal of the Operational Research Society, Vol. 45, No. 11, 1994, pp. 1316-1323.
[9]	A. Klose, “An LP-Based Heuristic for Two-Stage Capacitated Facility Location Problems,” The Journal of the Operational Research Society, Vol. 50, No. 2, 1999, pp. 157-166.
[10]	S. Tragantalerngsak, J. Holt and M. R?nnqvist, “An Exact Method for the Two-Echelon, Single-Source, Capacitated Facility Location Problem,” European Journal of Operational Research, Vol. 123, No. 3, 2000, pp. 473-489. doi:10.1016/S0377-2217(99)00105-8
[11]	E. Eskigun, R. Uzsoy, P. V. Preckel, G. Beaujon, S. Krishnan and J. D. Tew, “Outbound Supply Chain Network Design with Mode Selection, Lead Times and Capacitated Vehicle Distribution Centers,” European Journal of Operational Research, Vol. 165, No. 1, 2005, pp. 182-206. doi:10.1016/j.ejor.2003.11.029
[12]	E. Melachrinoudis and H. Min, “Redesigning a Warehouse Network,” European Journal of Operational Research, Vol. 176, No. 1, 2007, pp. 210-229. doi:10.1016/j.ejor.2005.04.034
[13]	R. Z. Farahani and N. Asgari, “Combination of MCDM and Covering Techniques in a Hierarchical Model for Facility Location: A Case Study,” European Journal of Operational Research, Vol. 176, No. 3, 2007, pp. 1839-1858. doi:10.1016/j.ejor.2005.10.039
[14]	E. Melachrinoudis, A. Messac and H. Min, “Consolidating a Warehouse Network: A Physical Programming Approach,” International Journal of Production Economics, Vol. 97, No. 1, 2005, pp. 1-17. doi:10.1016/j.ijpe.2004.04.009
[15]	B. B. Keskin and H. üster, “A Scatter Search-Based Heuristic to Locate Capacitated Transshipment Points,” Computers & Operations Research, Vol. 34, No. 10, 2007, pp. 3112-3125. doi:10.1016/j.cor.2005.11.020
[16]	G. Cornuejols, R. Sridharan and J. M. Thizy, “A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem,” European Journal of Operational Research, Vol. 50, No. 3, 1991, pp. 280-297. doi:10.1016/0377-2217(91)90261-S