0160-5682/87 $3.00 + 0.00 Copyright © 1987 Operational Research Society Ltd

J. Opl Res. Soc. Vol. 38, No. 2, pp. 201-203, 1987 Printed in Great Britain. All rights reserved

New Computational Results with a Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation FRED S. ZUFRYDEN Graduate School of Business, University of Southern California, USA This study reports on new computational results relating to a dynamic programming approach that optimally selects among a given set of products and allocates integer shelf-space units to the products in supermarkets. The computational results are reported for large problems that have been solved on an IBM-PC AT microcomputer. Key words : dynamic programming, marketing, optimization, resource allocation, retailing

INTRODUCTION A recent paper in this journal' reported on a microcomputer-based dynamic programming approach for product selection and retail shelf-space allocation in supermarkets. The model determines the best allocation of product items to a retailer's available shelf-space so as to maximize a profitability objective, of general form, that is stated in terms of revenues and costs of product sales. The approach also incorporates constraints including supply availability, operational constraints on minimum and maximum shelf-space assignments, and allocations by blocks of units. Moreover, product allocations are determined in terms of the required integer solutions. The approach defines each product to be considered as a 'stage' and the shelf-space that remains to be allocated at each stage as a 'state' variable within a forward dynamic-programming formulation. The previous paper' reported on preliminary computational experience, on an IBM-PC microcomputer, with a computer code that was confined exclusively to the usage of random access memory (RAM) and was necessarily limited to problems of small size. This study reports on computational results based on a new code, implemented on an IBM-PC AT, which overcomes RAM capacity restrictions by storing intermediate computations in random-access files, on hard disk. This accommodates problems of much larger size than those reported in the previous paper, 1 with greater computational speed. COMPUTATIONAL EXPERIENCE As in Zufryden, 1 the computational speed of the new code was tested by means of shelf-space allocation problems of various sizes that were simulated by a Monte-Carlo technique. The new dynamic-programming code was compiled from an IBM BASICA source program. As before, the effects of three variables were examined with respect to computer solution time: (a) the number of products to be allocated to a given total available shelf-space, (b) the total available shelf-space, stated in terms of a total number of slots, and (c) an upper bound on the maximum number of shelf-space slots allocated to any product. Each problem involved the optimal allocation of slots to each product so as to maximize a profitability objective function subject to given allocation constraints. Large test-problems were defined by specifying one of three levels of the number of products to be allocated (l 00, 125 and 150), and four levels of the total number of shelf-space slots available (500, 1000, 1500 and 2000). Moreover, alternative maximum slot-allocation bounds (20, 25 and 201

Operational Research Society is collaborating with JSTOR to digitize, preserve, and extend access to Journal of the Operational Research Society. ® www.jstor.org

Journal of the Operational Research Society Vol. 38, No. 2 TABLE

I. Computational times for selected problems*

Available slots Number of products

100 125 150

500

1000

1500

2000

6'01" 7'38" 9'19"

10' 57" 13' 53" 16'50"

15'30" 19'40" 24'02"

25'18" 30'48"

*Based on constraints restricting allocation of each product between 0 and a maximum of 20 slots. ·

30) were also considered. Given this design, a total of 3 x 4 x 3 = 36 large test-problems were developed. Dynamic programming solutions to these problems, on an AT microcomputer, led to computational times ranging from 6 min, for the smallest problem, to about 43 min for the largest one. Table 1 provides a comparison of computational times for selected test-problems on an IBM-PC AT. To study the responsiveness of computing time relative to the variables, a surface response methodology was used, as in Zufryden, 1 to develop a relationship of computational time ( T) as a function of the total number of products (P), the total number of shelf-space slots available (S) and the allocation upper-bound constraint (U). A general polynomial function was estimated, from the test problem observations, to relate P, S and U to computational time as the dependent variable. Table 2 provides a summary of the estimated model. This model is noted to fit the empirical data very well and provides a useful forecasting equation. Thus, the model parameters, which provide elasticity measures corresponding to each independent variable, are all statistically significant, and the log-transformed independent variables explain 99.6% of the variation in the dependent variable. As in previous results with the IBM-PC, 1 the coefficients in Table 2 suggest that computational time is most sensitive to the number of products to which shelf-space is to be allocated. The next greatest influence is due to the level of total available shelf-space slots. The allocation upper-bound constraint appears to have a significant but lesser impact than the other two variables. To provide a contrast with previous results, the small problems reported in Zufryden 1 were solved on the AT machine using both the previous code and the new one. Because the previous code performs all its computations in RAM and does not store intermediate results on disk file, it performs somewhat faster. For example, the largest problem reported in Zufryden, 1 involving 40 products x 160 slots and an upper bound of20 slots (solved on the PC in 2 min and 6 s), required 48 s on the AT with the previous code, and about 51 s with the new one. The use of intermediate hard-disk storage increased total computational time by only about 6%. CONCLUSION The sequential nature of dynamic programming lends itself to the storage of intermediate computational results on a peripheral storage device in the case of large problems. Here, the use of a hard-disk drive, or of a virtual disk on computers with extended RAM storage, appears to ·provide the most efficient means to store arrays that link solutions of a particular stage to those of previous ones. Once the final stage is reached and the optimal objective function value is obtained, the optimal allocation solution, corresponding to each product, is easily obtained by backtracking over previous stages on the basis of stored results. 2. Estimation of parameters of the log-linear relationship of computing time to independent variables

TABLE

Variable* Constant ln(P) ln(S) ln(U) R 2 =99.6% *The estimated ln(T) = ln(c0)

Coefficient (c,)

T-ratio

-6.8313 1.0768 0.8646 0.7961

-15.53 16.39 20.00 11.39

log-linearized

equation

is:

+ c 1ln(P) + c2 ln(S) + c3 ln(U).

202

F. S. Zufryden-Allocation of Shelf-Space in Supermarkets

The results reported here have shown that, with the use of recent microcomputer technology, dynamic programming provides a practical approach for solving retail shelf-space allocation problems of large and realistic size. This study suggests that it is now possible to use microcomputers for solving optimization problems that were once only within the domain of mainframes.

REFERENCE 1. F. ZUFRYDEN (1906) A dynamic programming approach for product selection and supermarket shelf-space allocation. J. Opt Res. Soc. 37, 413-422.

203