Approaches to Solve MID_CPLP Problem: Theoretical Framework and Empirical Investigation

Renduchintala Raghavendra Kumar Sharma, Pritee Agarwal

Department of Industrial and Management Engineering, Indian Institute of Technology, Kanpur, India.
Department of Mathematics and Statistics, Indian Institute of Technology, Kanpur, India.

DOI: 10.4236/ajor.2014.43014                

Abstract

In two-stage warehouse location problem, goods are moved from plants to warehouses at stage-1 (which are larger sized warehouses), and from there to warehouses at stage-2 (which are smaller sized warehouses); and finally to the markets. We aim to minimize the sum of location costs of the warehouses at stage-1 and stage-2; plus the total distribution cost of goods to the markets. In this paper two-stage capacitated warehouse location problem (TSCWLP) is vertically decomposed into the smaller problems, which is attained by relaxing the associated flow balance constraints. This leads to three different versions of Capacitated Plant Location Problem (CPLP) referred as RHS_CPLP, MID_CPLP and LHS_CPLP (Verma and Sharma REF _Ref387068711 \r \h [1]). In this paper MID_CPLP is reduced to RHS_CPLP and a single constraint 0-1 Knapsack problem by relaxing a difficult constraint. Interesting results and conjectures are given. Later two more valid constraints are added to MID_CPLP which are relaxed further to get additional results.

Keywords

TSCWLP, Location, Transportation, Distribution

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Verma, P. and Sharma, R.R.K. (2008) Two Stage Capacitated Warehouse Location Problem: Conceptual Scheme of the Vertical Decomposition Approach. Proceedings of the 4th International Conference on Logistics and Supply Chain Management 2008, PSG College of Technology Coimbatore and Central Michigan University, USA.
[2]	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
[3]	Sharma, R.R.K. (1991) Modeling a Fertilizer Distribution System. European Journal of Operational Research, 51, 2434. http://www.sciencedirect.com/science/article/pii/037722179190142I http://dx.doi.org/10.1016/0377-2217(91)90142-I
[4]	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://www.sciencedirect.com/science/article/pii/S037722170600018X http://dx.doi.org/10.1016/j.ejor.2005.11.028
[5]	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://www.scirp.org/journal/PaperInformation.aspx?paperID=7698#.U01DvHbedk4 http://dx.doi.org/10.4236/ajor.2011.13013
[6]	Sahin, G. and Sural, H. (2007) A Review of Hierarchical Facility Location Models. Computers and Operations Research, 34, 2310-2331. http://www.sciencedirect.com/science/article/pii/S0305054805002959 http://dx.doi.org/10.1016/j.cor.2005.09.005
[7]	ReVelle, C.S. and Eiselt, H.A. (2005) Location Analysis: A Synthesis and Survey. European Journal of Operational Research, 165, 1-19. http://www.sciencedirect.com/science/article/pii/S0377221704002139
[8]	ReVelle, C.S., Eiselt, H.A. and Daskin, M.S. (2008) A Bibliography for Some Fundamental Problem Categories in Discrete Location Science. European Journal of Operational Research, 184, 817-848. http://www.sciencedirect.com/science/article/pii/S037722170700080X
[9]	Brandeau, M.L. and Chiu, S.S. (1989) An Overview of Representative Problems in Location Research. Management Science, 35, 645-674. http://pubsonline.informs.org/doi/abs/10.1287/mnsc.35.6.645 http://dx.doi.org/10.1287/mnsc.35.6.645
[10]	Sharma, R.R.K. (1996) Chapter 5. Foodgrains Distribution in the Indian Context: An Operational Study. In: Tripathy, A. and Rosenhead, J., Eds., Operations Research for Development, New Age International Publishers, Ahmedabad, New Delhi, 212-227.
[11]	Sharma, R.R.K. and Namdeo, S. (2005) Two Stage Capacitated Warehouse Location Problem: Developing New Strong Constraints. Proceedings of 5th International Conference on Operational Research for Development: ICORD V, Jamshedpur, Jamshedpur, 19-21 December 2005, 330-333.
[12]	Sharma, R.R.K. and Sharma, K.D. (2000) A New Dual Based Procedure for the Transportation Problem. European Journal of Operational Research, 122, 611-624. http://www.sciencedirect.com/science/article/pii/S0377221799000818 http://dx.doi.org/10.1016/S0377-2217(99)00081-8
[13]	Verma, P. and Sharma, R.R.K. ( 2007) Vertical Decomposition Approach to Solve Single Stage Capacitated Warehouse Location Problems. Proceedings of the IEEE International Conference on Industrial Engineering and Engineering Management (IEEM), Singapore, 2-4 December 2007, 907-911. http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4419323&tag=1
[14]	Cornuejols, G., Sridharan, R. and Thizy, J.M. (1991) A Comparison of Heuristics and Relaxations for the Capacitated Plant Location Problem. European Journal of Operational Research, 50, 280-297. http://www.sciencedirect.com/science/article/pii/037722179190261S http://dx.doi.org/10.1016/0377-2217(91)90261-S
[15]	Christofides, N. and Beasley, J.E. (1983) Extensions to a Lagrangean Relaxation Approach for the Capacitated Warehouse Location Problem. European Journal of Operational Research, 12, 19-28. http://www.sciencedirect.com/science/article/pii/0377221783901790 http://dx.doi.org/10.1016/0377-2217(83)90179-0
[16]	Nauss, R.M. (1978) An Improved Algorithm for Capacitated Plant Location Problem. Journal of Operational Research Society, 29, 1195-1201. http://www.palgrave-journals.com/jors/journal/v29/n12/abs/jors1978263a.html http://dx.doi.org/10.1057/jors.1978.263