Developing new formulations and relaxations of single stage capacitated warehouse location problem (SSCWLP): Empirical investigation for assessing relative strengths and computational effort

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2005.11.028 Byline: R.R.K. Sharma, V. Berry Keywords: Location; Transportation; Distribution Abstract: In literature, single/multistage warehouse location problems have been attempted by Geoffrion and Graves [A.M. Geoffrion, G.W. Graves, Multicommodity distribution system design by Benders decomposition, Management Science 2 (1974) 82-114] and Sharma [R.R.K. Sharma, Modeling a fertilizer distribution system, European Journal of Operational Research 51 (1991) 24-34] among others and they have given completely different formulations. We use the formulation style given by Sharma and Sharma [R.R.K. Sharma, K.D. Sharma, A new dual based procedure for the transportation problem, European Journal of Operational Research 122 (3) (2000) 96-109] to develop variety of constraints that link real and 0-1 integer variables; thus developing many formulations of single stage capacitated warehouse location problem (SSCWLP). We relax the integer constraints on 0-1 variables to obtain their relaxations. Later we conduct an empirical investigation to find that there exist relaxations which give better bounds than the 'strong' relaxation of SSCWLP. We also find that SSCWLP when formulated using the style due to Sharma [R.R.K. Sharma, Modeling a fertilizer distribution system, European Journal of Operational Research 51 (1991) 24-34] takes significantly less computational time for optimal solution compared to the time taken to reach optimality for the SSCWLP problems when formulated using the style due to Geoffrion and Graves [A.M. Geoffrion, G.W. Graves, Multicommodity distribution system design by Benders decomposition, Management Science 2 (1974) 82-114]. Finally we conducted an experimental investigation on 100 problems of SSCWLP problems each of sizes 25x25x25, 50x50x50 and 100x100x100 and this establishes that the effectiveness of 'capacity' constraints proposed in this paper is particularly strong. Author Affiliation: Department of Industrial and Management Engineering, Indian Institute of Technology Kanpur, PO-IIT, Kanpur 208 016, India Article History: Received 11 June 2003; Accepted 30 November 2005