Developing Strong and Hybrid Formulation for the Single Stage Single Period Multi Commodity Warehouse Location Problem: Theoretical Framework and Empirical Investigation

R. R. K. Sharma, Parag Tyagi, Vimal Kumar, Ajay Jha

Department of Industrial & Management Engineering, IIT, Kanpur, India.

DOI: 10.4236/ajor.2015.53010                

Abstract

We note that the Single Stage Single Period Multi Commodity Warehouse Location Problem (SSSPMCWLP) has been first attempted by Geoffrion and Graves [1], and that they use the weak formulation (in context of contribution of this paper). We give for the first time “strong” formulation of SSSPMCWLP. We notice advantages of strong formulation over weak formulation in terms of better bounds for yielding efficient Branch and Bound solutions. However, the computation time of “strong” formulation was discovered to be higher than that of the “weak” formulation, which was a major drawback in solving large size problems. To overcome this, we develop the hybrid strong formulation by adding only a few most promising demand and supply side strong constraints to the weak formulation of SSSPMCWLP. So, the formulations developed were put to test on various large size problems. Hybrid formulation is able to give better bound than the weak and takes much less CPU time than the strong formulation. So, a kind of trade off is achieved allowing efficiently solving large sized SSSPMCWLP in real times using hybrid formulation.

Keywords

SSUWLP, SSSPMCWLP, Strong and Weak Constraints, Hybrid Formulation, RMIP

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Geoffrion, A.M. and Graves, G.W. (1974) Multicommodity Distribution System Design by Benders Decomposition. Management Science, 20, 822-844. http://dx.doi.org/10.1287/mnsc.20.5.822
[2]	FCI (Food Corporation of India) Official Website. http://fciweb.nic.in/
[3]	ReVelle, C.S. and Eiselt, H.A. (2005) Location Analysis: A Synthesis and Survey. European Journal of Operational Research, 165, 1-19.
[4]	Sharma, R.R.K. (1991) Modelling a Fertilizer Distribution System. European Journal of Operational Research, 51, 24-34. http://dx.doi.org/10.1016/0377-2217(91)90142-I
[5]	Sharma, R.R.K. and Berry, V. (2007) Developing New Formulations and Relaxations of Single Stage Capacitated Warehouse Location Problem (SSCWLP): Empirical Investigation for Assessing Relative Strengths and Computational Effort. European Journal of Operational Research, 177, 803-812. http://dx.doi.org/10.1016/j.ejor.2005.11.028
[6]	Drezner, T., Drezner, Z. and Salhi, S. (2002) Solving the Multiple Competitive Facilities Location Problem. European Journal of Operational Research, 142, 138-151. http://dx.doi.org/10.1016/S0377-2217(01)00168-0
[7]	Kouvelis, P., Rosenblatt, M.J. and Munson, C.L. (2004) A Mathematical Programming Model for Global Plant Location Problem: Analysis and Insights. IIE Transactions, 36, 127-144. http://dx.doi.org/10.1080/07408170490245388
[8]	Keskin, B.B. and Üster, H. (2007) A Scatter Search-Based Heuristic to Locate Capacitated Transhipment Points. Computers & Operations Research, 34, 3112-3125. http://dx.doi.org/10.1016/j.cor.2005.11.020
[9]	Hindi, K.S. and Basta, T. (1994) Computationally Efficient Solution of a Multiproduct, Two-Stage Distribution Location Problem. The Journal of the Operational Research Society, 45, 1316-1323.
[10]	Hindi, K.S., Basta, T. and Pienkosz, K. (2006) Efficient Solution of a Multi-Commodity, Two-Stage Distribution Problem with Constraints on Assignment of Customers to Distribution Centres. International Transactions in Operations Research, 5, 519-527. http://dx.doi.org/10.1111/j.1475-3995.1998.tb00134.x
[11]	Sharma, R.R.K. and Verma, P. (2012) Hybrid Formulations of Single Stage Uncapacitated Warehouse Location Problem: Few Theoretical and Empirical Results. International Journal of Operations and Quantitative Management (IJOQM), 18, 53-69.
[12]	Montoya-Torres, J.R., Aponte, A. and Rosas, P. (2011) Applying GRASP to Solve the Multi-Item Three-Echelon Uncapacitated Facility Location Problem. Journal of the Operational Research Society, 62, 397-406. http://dx.doi.org/10.1057/jors.2010.134
[13]	Elson, D.G. (1972) Site Location via Mixed-Integer Programming. The Journal of Operational Research Society, 23, 31-43. http://dx.doi.org/10.1057/jors.1972.4
[14]	Pirkul, H. and Jayaraman, V. (1998) A Multi-Commodity, Multi-Plant, Capacitated Facility Location Problem: Formulation and Efficient Heuristic Solution. Computers & Operations Research, 25, 869-878. http://dx.doi.org/10.1016/S0305-0548(97)00096-8
[15]	Verma, P. and Sharma, R.R.K. (2011) Vertical Decomposition Approach to Solve Single Stage Capacitated Warehouse Location Problem (SSCWLP). American Journal of Operations Research, 1, 100-117. http://dx.doi.org/10.4236/ajor.2011.13013
[16]	Sharma, R.R.K. and Agarwal, P. (2014) Approaches to Solve MID_CPLP Problem: Theoretical Framework and Empirical Investigation. American Journal of Operations Research, 4, 142-154. http://dx.doi.org/10.4236/ajor.2014.43014
[17]	Sharma, R.R.K. (1996) Food Grains Distribution in the Indian Context: An Operational Study. In: Tripathy, A. and Rosenhead, J., Eds., Operations Research for Development, Chapter 5, New Age International Publishers, New Delhi, 212-227.
[18]	Sharma, R.R.K. and Muralidhar, A. (2009) A New Formulation and Relaxation of the Simple Plant Location Problem. Asia-Pacific Journal of Operational Research, 26, 1-11. http://dx.doi.org/10.1142/S0217595909002122