0160-5682/86 $3.00 + 0.00 Copyright © 1986 Operational Research Society Ltd

J. Opl Res. Soc. Vol. 37, No.4, pp. 413-422, 1986

Printed in Great Britain. All rights reserved

A Dynamic Programming Approach for Product Selection and Supermarket Shelf-Space Allocation FRED S. ZUFRYDEN Graduate School of Business, University of Southern California A dynamic programming approach is proposed to select optimally among a given set of products and allocate integer shelf-space units to the selected products in supermarkets. The approach is designed to consider general objective-function specifications that account for space elasticity, costs of sales, and potential demand-related marketing variables. The optimization is subject to constraints due to product supply availability, 'block' product allocation and operational requirements. A primary focus is on the development of a tractable model approach that can effectively be implemented on a microcomputer. A discussion of applications and computational experience on a microcomputer is provided to support the practical applicability of the optimization approach. Key words: dynamic programming, marketing, optimization, resource allocation, retailing

INTRODUCTION How best to allocate finite and scarce retail shelf-space among alternative product offerings is a critical operational decision that is faced by all retailers. This decision directly relates to the profitability of a retailing organization as it affects both the cost and the revenue side of the operation. On the one hand, space allocation influences the perceptibility, and hence the demand and sales revenue, from particular product items. It also influences various costs, including those of transportation, ordering, holding and reshelving, and out-of-stock costs associated with particular product items. In this study, a dynamic programming approach is proposed to aid retailers optimally to select products to be sold and to allocate shelf space to the chosen product items. The model seeks to determine the best allocation of product items to a retailer's scarce available space so as to maximize an objective function that is stated in terms of revenues and costs of product sales. A unique aspect of the proposed formulation is its applicability to any separable functional specifications of demand and cost equations for individual product items. The approach also incorporates realistic constraints, including supply availability restrictions, operational constraints on desired minimum and maximum shelf-space assignments, and allocations by blocks of units. Moreover, product allocations are determined in terms of the required integer solutions. A major focus of this study is on developing a tractable model that can be practically implemented by a retailer on a microcomputer. The paper describes applications of the model, including its flexibility for providing evaluations of additions and deletions of product items. The paper also provides a discussion of computational experience on an I.B.M. P.C. to support the tractability and practical applicability of the optimization approach.

LITERATURE REVIEW Over the past two decades, there have been a number of approaches that have been proposed to aid retailers in their shelf-space allocation decisions. Among these, various commercial approaches have been used within the retailing industry that have entailed the use of relatively simple heuristic rules. Here, the essential concern has been on the development of operational rules and guidelines designed to permit retailers easily to implement decisions of shelf-space allocation in practice. For example, an early approach, by Lee, 1 involved an evaluation of marginal returns to space allocation without any constraint on total shelf space. Subsequent industry 413

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. 37, No. 4

models advocated shelf-space allocation in direct proportion to a product's sales or profitability (e.g. PROGALI in Malsagne, 2 O.B.M. in Monshouwer 3, and Cifrino 4 ). Because the latter approaches utilize heuristic rules, they are not true optimization models. They involve very limited constraint structures as they merely consider total space restrictions. Furthermore, they cannot be used for product selection. Other approaches have included D.P.P. (direct product profitability), based on the criterion of unit contribution to overhead and profits (e.g. McKinsey 5 ). Other commercial systems have focused essentially on the cost side. For example, SLIM (Store Labor and Inventory Management), provides a method of allocating shelf space so as to minimize overall store-stocking expenses. 6 Another industry system, COSMOS, 7 incorporates the notions of the D.P.P. approach and bases optimal space assignments on direct product profitability computations and projections of rate of movement and sales for individual products. Among the limitations shared by the above approaches is the reliance on essentially product costs and static margins, and the ignorance of space elasticity effects on product demand. Various studies, while not focusing on the problem of space allocation per se, have experimentally attempted to measure shelf-space elasticities (e.g. see Curhan 8·9 for a review of these). Among the results from these studies is the suggestion of the variability of shelf-space elasticities across certain defined product classes (e.g. Brown and Tucker 10 ). However, the existence of a relationship between sales and space allocation has not been generally confirmed experimentally (e.g. Cox 11 ). Based on the often contradictory and inconclusive results in this research area, Curhan 8 has concluded that "the impact on unit sales of changes in shelf space is very small relative to the effects of variables other than shelf space". Only a few studies have sought to develop optimization models. Anderson and Amato 12 describe the application of an algorithm to solve the problem of selecting brands within a product group and allocating shelf space among the chosen brands within the group. Another study, by Hansen and Heinsbroek, 13 proposed an algorithm to maximize total profits by selecting a set of products among alternatives and allocating them to available shelf space, taking into account constraints of total space, minimum allocations and integer solutions. The algorithm is based on a generalized Lagrange multiplier technique which produces 'near optimum' allocation solutions. 14 A recent study by Corstjens and Doyle 15 provides the most comprehensive treatment of the shelf-space optimization problem to date. It simultaneously considers four key determinants of the shelf-space-store profitability equation: product-space elasticities, inter-product cross elasticities, product profit-margins and product costs, including those associated with inventory and handling. An essential advantage of the model over the earlier ones is its explicit consideration of 'cross elasticities' between the products within a retail store, to account for substitutability and complementarity of product offerings, as well as space 'main effects' within the specification of product-demand relationships. However, the case illustration that is provided involves a very small problem consisting of only five product groups. Unfortunately, the consideration of 'crosselasticities' at the individual product level would be impossible in practice due to the overwhelming number of cross-elasticity terms that would need to be estimated. The authors 15 apply a generalized signomial mathematical programming solution procedure based on an algorithm developed by Gochet and Smeers. 16 However, the solution approach does not provide the required integer solutions. In addition, it cannot consider non-linear functions other than of polynomial form (e.g. such as S-shaped curves which are common in marketing). Moreover, the authors do not provide any discussion of the computational efficiency of their technique for solving problems of relatively large size. The authors report that even their small problem, consisting of five product groups, requires 290 iterations through a branch-and-bound procedure to reach a solution. Corstjens and Doyle 17 have also recently provided a theoretical model that extends to dynamic space-allocation decisions over time. However, this model extension sacrifices a number of important features of their previous model 15 and appears less relevant from a practical application standpoint. The constraints are considerably simplified as they include only a total space constraint, but they ignore product supply and allocation bound constraints. Another drawback of this model extension is that cost functions are no longer explicitly considered within the model formulation. 414

F. S. Zufryden-Allocation of Supermarket Shelf-Space

MODEL FORMULATION We now turn to a discussion of the optimization model components and its formulation as a mathematical programme. First consider the objective function of the model. It is based on the demand for and costs of the various potential product items to which retail space is to be allocated. A general product demand function is posited that is based on any arbitrary specification. It is assumed that demand for product j (j = 1, 2, ... , J) is a function of a vector x1 = (s1 , xiJ, x 21 , ... , xlJ). The vector includes space allocated to product item j, s1 , as well as other variables xiJ (i = 1, 2, ... , I and j = 1, 2, ... , J) that may affect product demand (e.g. retail price, advertising, retail promotions, store characteristics and/or any other variables that may be relevant to a particular market situation). Thus, the unit demand for brand j is functionally defined as: (1)

As was previously noted, past experimental studies have suggested that space probably has a much more minimal effect on demand and sales than do other marketing variables. However, non-space variables, although they are likely to have a much more profound effect on demand than allocated space, have not been included in previous model formulations. The proposed function (1) suggests a form that can potentially include any desired relevant marketing variables in addition to the space variable. However, in the interest of tractability and practical utilization, the model formulation considers space allocation 'main effects' but ignores the explicit consideration of space 'cross-elasticities'. Based on (1), the total gross margin function over all products may be specified in terms of the space allocated to each product and other demand-explanatory variables as: (2)

where m1 is the margin rate for product j. In turn, relationships for the cost C1 of each product} may be defined as a function of product demand, which in turn is a function of the vector x1 . The specifications of the cost equations may be arbitrarily chosen. However, the parametrization of the cost equations should reflect costs of product item sales, including ordering, holding and out-of-stock costs (see Corstjens and Doyle 15 ). The total cost, over all products, is then obtained by summing costs over the individual product items as: (3)

Given the above components of the objective function, the following now describes the formulation of the shelf-space allocation problem as a mathematical programme. Consider the problem of optimally allocating shelf space in a particular section (e.g. paper towel, or coffee section) of a supermarket. Assume that there is a given finite facing area available for the allocation. Because it may be assumed that shelf depth is fixed, facing area rather than space volume allocation is considered. Assume that the total shelf area is subdivided into rectangular grids or 'slots' such that the size of each product package to be allocated can be stated as multiples of the 'slot' area unit values. Given that non-space variables are set to levels that correspond to the prevailing or anticipated market situation according to some specified market scenario, the problem becomes one of determining the optimal collection of product items and the number of slots to be allocated to each of the chosen product items. This involves the maximization of the following net profit-margins objective by choice of s1 for each product j: (4)

where, for notational convenience, Ql~1 ) = Ql~1 , x;1, x;1, . .. , x;1), and the xijs are fixed values of the non-space demand-explanatory variables. 415

Journal of the Operational Research Society Vol. 37, No. 4

The maximization is subject to: (5) (6) (7) sj

= 0, ~, 2~, ... , etc.,

j

= 1, 2, ... , J,

(8)

with ~~

1 and integer,

j = 1, 2, ... , J.

In the above, (5) restricts the sum of space allocations to a total number, T, of available area slots. Equation (6) provides operational constraints that may be imposed by a retailer to ensure desired minimum and maximum slot allocations for each product j. For example, a new product might be assigned minimal space to provide initial consumer exposure and awareness. As another example, a nominal quantity of a prestige product may be carried for the exclusive reason that it adds to a retailer's quality image. Because there may be production or supply constraints, equation (7) provides upper bounds Aj for the availability of each product j. Constraint (8) specifies the incremental allocation rules to be used for each product. This permits the allocation to each product j on the basis of increments, or blocks, of magnitude ~ ~ 1 in view of the physical size of product packages or for aesthetic reasons. For example, if a particular paper-towel product is 'twin-packed', then the product may be allocated to the facing area in block units of two. As another example, six-pack cans of a soft drink may be allocated to shelf space such that the cans may be viewed in blocks of three- or two-can units, depending on how the six-packs are actually stacked on the shelves. Generally, for aesthetic reasons, it is desired to allocate shelf space to product items or brands as uniform and complete columns. Thus, if the distance between the bottom and top of a shelf accommodates the vertical stacking of three cans, then (8) permits the consideration of shelf allocations in incremental block units of three. Thus, (8) provides a useful constraint type that has been ignored in past optimization approaches.

DYNAMIC PROGRAMMING FORMULATION It may be noted that realistic formulations of (4)-(8) will involve non-linear objective functions. Given that a goal of the present study is to permit any specifications of the demand and cost functions, the geometric programming techniques suggested by Corstjens and Doyle 15 will not generally be applicable. For example, the latter technique cannot consider demand equations based on a multivariate logistic regression (see Lilien 18 ) or other more complex non-linear forms. Moreover, it will not provide the required integer solutions. Dynamic programming appears to provide an effective solution technique that meets the requirements of the shelf-space allocation problem. Among its advantages is that it can easily handle arbitrary objective function specifications, as long as they are separable in the control variables, and it is especially well suited to handle integer solutions. For this reason, dynamic programming has been shown useful in other marketing applications (see Zufryden 19- 21 ). For the purposes of the subsequent illustrations, cost and demand functions that are similar in form to those proposed by Corstjens and Doyle 15 will be used. However, it should be kept in mind that the proposed solution approach is not restricted to any specific functional forms. Thus, the following demand equations are defined for each product j: (9)

where {3 0j, rxj and f3us are constant coefficients. In particular, rxj is the space elasticity for product

j, and the f3us are the elasticities associated with each demand explanatory variable xu· 416

F. S. Zufryden-Allocation of Supermarket Shelf-Space

It is noted that (9) is a space 'main effects' version of the Corstjens and Doyle 15 demand model, which additionally considers non-space variables. Using the previous notational conventions, (9) may be rewritten in a form similar to that in Hansen and Heinsbroek 13 as: Q/sj) =

t/1/Ji,

j = 1, 2, ... , J,

(10)

where t/Jj is stated in terms of fixed levels of the non-space variables as:

t/Jj =

fl x ~u,

j

=

1, 2, ... , J.

(11)

The cost function for each product item j is defined, as in Corstjens and Doyle, 15 as: Cj(sj)

=

yjQ/sj)"j,

j

=

1, 2, ... , J,

(12)

where yj and (Jj are constant coefficients. In particular, (Jj is the cost elasticity related to increased sales of product j. Corstjens and Doyle 15 discuss the estimation of the cost model parameters so as to reflect relevant costs of sales, including procurement costs (i.e. order processing and transportation), holding costs (i.e. storage, insurance and deterioration), as well as out-of-stock costs. A 'forward' dynamic programming method is now developed which defines each product item j as a 'stage' in the decision process. Let bj = 'state' variable representing number of slot areas left after the decision to include sj slots to product j at stage j; Fj(bj) =optimal cumulative net profit margin at stage j, under an optimum space-allocation policy resulting in state bj; ,h(bj, sj) =incremental net profit margin from allocating sj slots to product j at stage j and resulting in state bj.

In the above illustrative case, _h(bj, sj) is computed as: (13)

Given the above definitions, the following dynamic programming recursive relationship may be developed: Fj(bj) =Max [,h(bj, sj) (sjl

+ FJ- 1 (bj_ 1 )],

j = 1, 2, ... , J,

(14)

subject to {C}, where {C} is a constraint set that may be stated as: 1, 2, ... , J,

(15)

Uj,

j = 1, 2, ... , J,

(16)

sj ~ (Aj/t/Jj) 11";,

j = 1, 2, ... , J,

(17)

... , etc., j = 1, 2, ... , J,

(18)

sj ~ bj _ 1 ~ T, Lj ~ sj

sj = 0,

~, 2~, 3~,

~

j

=

with ~?

1 and integer, j = 1, 2, ... , J.

Note that (15)-(18) correspond to (5)-(8) respectively, with (17) obtained from (7) and (10). The dynamic solution is initialized by specifying the starting condition, prior to any space-allocation decisions, as: F0 (T) = 0.

(19)

Then (14) is computed recursively over stages j = 1, 2, ... , J using the relation bj = bj-l- sj. At each stage j, the maximization is taken over integer values satisfying the constraint set {C}. Once the last stage J is reached, the final solution is obtained by backtracking to identify each sj value. 417

Journal of the Operational Research Society Vol. 37, No. 4 ILLUSTRATIONS OF APPLICATIONS Sample problems that are based on simulated data are now described to illustrate applications of the dynamic programming approach. Suppose that a retailer is considering the selection of a set among 10 alternative product items to be simultaneously allocated to a total of 40 available facing-area slots. Assume that the display area consists of two parallel shelves, each accommodating the vertical stacking of two units, so that the total area is 10 slots in length by 4 slots in height. The retailer also wishes to consider the potential subsequent addition of an 11th product to his offerings. Using as guidelines the cost and space elasticity parameters provided in Corstjens and Doyle, 15 a Monte Carlo simulation programme was designed and used to generate the parameters of the components of the objective function. Table I provides the simulated parameters that were generated for 10 products, and also those corresponding to an additional, assumed new, product, whose subsequent addition to the shelves is also to be evaluated. Assume that each of products 1 to 5 has a size equivalent to one slot, while the other 5 are 'twin-packed' (e.g. as in some paper-towel brands) and occupy two adjacent slots each. Allocation constraints are now specified. Products 1 to 5 must be allocated to shelf space by columns, i.e. in slot increments of 2, with a minimum of 2 and a maximum not to exceed 10 slots per product item. The 'twin-packed' products (items 6 to 10), if selected, must also be allocated in columns of 2 (i.e. in 4-slot increments) and cannot exceed a maximum of 12 slots per product item. Assume that the supply for all products is sufficient to meet upper bound constraints for each product item, with the exception of product 10, whose availability is only adequate to supply a maximum of 8 slots (i.e. the upper bound for product 10 is reduced from 12 to 8). Table 2 provides a summary of the optimal shelf-space allocation solution to the above sample problem with the dynamic programming method. The net profit-margin contributions from the specified allocations, as well as the constraint bounds and search increments, are also shown. It is noted that all 10 products have been selected for inclusion in this case. It is also observed that products 2, 3, 5 and 10 have solutions that coincide with a constraint boundary. Although TABLE I. Summary of simulated model parameters Product

(j)

ljljmj

(Xj

Yj

bj

I 2 3 4 5 6 7 8 9 10 II*

1995.5 575.0 262.8 1682.3 1010.2 1470.9 1814.4 1790.7 850.2 1641.8 983.5

0.183 0.129 0.137 0.191 0.155 0.178 0.159 0.122 0.177 0.190 0.162

101.3 74.6 135.0 84.9 110.6 106.6 51.9 100.0 72.6 44.7 91.3

0.980 0.815 0.815 0.843 0.830 0.910 0.935 0.867 0.970 0.936 0.814

*Product II is a new product to be subsequently evaluated.

TABLE 2. Summary of optimal

she!f~space

allocation

Constraints

Product item

Slots allocated

Net profit margin

Min

Max

Increment

I 2 3 4 5 6 7 8 9 10

4 2 2 6 2 4 4 4 4 8

2177.99 497.52 51.47 1983.50 927.80 1505.97 2073.23 1788.52 807.65 2125.41

2 2 2 2 2 0 0 0 0 0

10 10 10 10 10 12 12 12 12 8

2 2 2 2 2 4 4 4 4 4

Total

40

$13939.06

418

F. S. Zufryden-Allocation of Supermarket Shelf-Space TABLE 3. Summary of optimal shelf-space allocation when a new product is added Constraints

Product item

Slots allocated

Net profit margin

Min

Max

Increment

I 2 3 4 5 6 7 8 9 10 II

4 2 0 6 2 4 4 4 4 8 2

2177.99 497.51 0.00 1983.50 927.80 1505.97 2073.23 1788.52 807.65 2125.41 939.60

0 0 0 0 0 0 0 0 0 0 0

8 8 8 8 8 12 12 12 12 12 8

2 2 2 2 2 4 4 4 4 4 2

40

$14827.18

Total

this suggests that an unconstrained problem might lead to a different and a superior solution, it was found that a complete relaxation of all range constraints produced identical results to those shown in Table 2. A useful aspect of dynamic programming technique is its consideration of problems in successive stages. With this feature, the addition of new products to a current product configuration may be evaluated in a computationally efficient manner by simply considering additional stages. This feature also permits the evaluation of solution sensitivity to constraint changes. Since the Fj(b1) values and information linking to previous stages may be stored in computer memory, such evaluations will generally not require the allocation problem to be completely resolved. Consider the potential addition of product 11 to the retailer's offerings. Asssume that product 11 is individually packed and is to be allocated in block units of size 2. Table 3 provides a summary of the optimal shelf-space allocation that was obtained by merely adding stage 11 in this case. For this illustration, constraint minimums have been relaxed to allow for the potential elimination of unprofitable products. In effect, it is observed that the solution now suggests the elimination of product 3, while the allocations for the other products remain the same. The overall effect of adding product 11, and the corresponding shelf allocation, is observed to be beneficial in this case, as it is shown to lead to an overall net total profit-margin increase of $888. Since no boundary constraint is binding, the optimal solution shown in Table 3 corresponds to that of an unconstrained problem. As another example, if product 9 becomes unavailable in a future period, after the addition of product 11, the problem can be re-evaluated by setting both the minimum and maximum allocation bounds for the product to 0 and partially resolving the dynamic programming problem from stage 9. In this instance, the solution indicates an increased space allocation to product 7 to make up for the deletion of product 9 (see Table 4).

TABLE 4. Summary of optimal shelf-space allocation after availability constraint change Constraints

Product item

Slots allocated

Net profit margin

Min

Max

Increment

I 2 3 4 5 6 7 8 9 10 II

4 2 0 6 2 4 8 4 0 8 2

2177.99 497.51 0.00 1983.50 927.80 1505.97 2164.57 1788.52 0.00 2125.41 939.60

0 0 0 0 0 0 0 0 0 0 0

8 8 8 8 8 12 12 12 0 12 8

2 2 2 2 2 4 4 4 4 4 2

Total

40

$14110.87

419

Journal of the Operational Research Society Vol. 37, No. 4 COMPUTATIONAL EXPERIENCE The computational efficiency of the dynamic programming approach was tested on an I.B.M. P.C. with problems of various forms and sizes that were simulated by a Monte Carlo technique as above. A source program in I.B.M.'s BASICA language was compiled in machine code and was subsequently used for the tests. Here, the effects of three variables were examined with respect to computer solution time: (a) the number of products, (b) the total available slots, and (c) the range of allocation constraint boundaries. Each test problem was defined by a specification of one of four levels on each of the number of products to be evaluated (10, 20, 30 or 40), and the total number of slots available (20, 40, 80 or 160). Because the imposition of allocation range constraints reduces computational requirements, four alternative range constraints (0-5, 0-10, 0-15 or 0-20) were also considered. A unit block increment (i.e. ~ = 1) was assumed for all products. The resulting full factorial design led to a total of 4 x 4 x 4 = 64 test problems. The computing times ranged from around 4 seconds for the smallest problem to a little over 2 min for the largest test problem that was considered (see Table 5 for sample computational times for selected test problems). To study the responsiveness of computing time relative to the three variables, a surface response methodology was used to develop a relationship of computational time (T) as a function of total number of products (P), total number of slots available (S), and the upper bound constraint (U). This methodology has been applied extensively to analyse and simplify complex experiments and simulations in industrial applications, and has also been shown useful in marketing studies (see Green et al. 22 ). In this study, the methodology was implemented by fitting a curve to the 64 observations of P, S, U and corresponding observed computational time values. A general polynomial function (see Curhan 8 ) was found to provide an extremely good fit to the data. Table 6 provides a summary of the estimation, by regression analysis, of the parameters of the corresponding log-linearized model: ln(T)

=

ln(c 0 )

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

(20)

It may be noted that the c; parameters are all statistically significant, and that the corresponding log-transformed variables explain over 99% of the variation in the dependent variable. Judging from the derived elasticity parameters, it is noted that increases in the number of products have the greatest influence on computational time. The next greatest influence is from the level of total available slots. The upper bound of the allocation range constraint appears to have a sign_ificant but lesser impact than the other two variables. Although the sequential nature of the dynamic programming approach makes it possible to use disk storage for larger problems, random access memory (RAM) was exclusively used in order to TABLE

5. Sample computing times* for test problems Available slots

Number of products

20

40

10

4"

7"

14"

20

8"

15"

30"

58"

30

13"

24"

47"

I' 31"

40

17"

34"

1'05"

2' 06"

80

160 27"

*Based on range constraints (0 to U;) with U; = 20 (j = I, 2, ... , J). TABLE. 6. Estimation of parameters Q( the log· linear relationship of computing time to indepen· dent variables

Variable

Coefficient (c;)

T-ratio

Con st. In (P) In (S) In (U)

-6.13913* 1.10633 0.95105 0.68901

-10.13 14.83 12.75 9.24

R 2 = 99.2% *c0 = 0.002157.

420

F. S. Zufryden-Allocation of Supermarket Shelf-Space TABLE

7. Estimated computing times* for larger problems

Available slots

Number of products

200

400

600

800

50

3' 19"

6' 24"

9' 25"

12' 23"

75

5' 11"

10' 02"

14' 48"

19' 23"

100

7' 08"

13' 47"

20' 16"

26' 39"

125

9'08"

17' 39"

25' 57"

34'07"

*Based on range constraints (0 to U;) with Uj = 20 (j = I, 2, ... , J). Estimates obtained from (20) and Table 6 parameters.

maximize computational efficiency. Because the I.B.M. P.C.'s Microsoft BASIC currently restricts RAM usage to 64 Kbytes, problems exceeding 50 products x 200 slots could not be considered with the available BASIC version. However, as other versions exist that can utilize up to 640 K of RAM, it is of interest to use (20) to project beyond the size of the test problems (see Table 7). For example, it is estimated that a problem with 125 products and 800 slots could be solved in about 34 min. Predictive evaluations, basedon additional test problems, showed estimated times to be, on average, within 6% of actual times. The computational results are encouraging but suggest problem-size limitations. Thus, it is not realistic to consider microcomputer-based dynamic programming to allocate space to all products of a supermarket simultaneously. However, it appears to offer an effective and practical approach for optimally allocating space within particular supermarket sections. As the test problems all involved lower bounds LJ = 0 and 4 = I increments, the times reported in Table 7 could be significantly reduced with coarser block unit incrementation or by narrowing the allocation bound constraints. In addition, the utilization of other microcomputers can also provide substantial computational time-savings. For example, preliminary experimentation with an I.B.M. A.T. suggested that significant decreases in computational time (by about 60% or more) can be achieved with the new generation of A.T. machines. A new computer code is currently being tested on an I.B.M. A.T. that stores intermediate computational results on a hard disk to accommodate large problems. To date, problems involving 125 products x 2000 slots and upper bounds of 20 slots have been solved in about 25 min. With the continuing enhancements in computer techn~logy, the future prospects of the proposed microcomputer-based technique appear even more promising. CONCLUSION A dynamic-programming model approach has been described that can be used to select product items and optimally allocate them to scarce retail shelf-space in a supermarket. The advantages of the approach over previously proposed optimization methods are that it is not constrained by any specific objective function form and produces required integer solution results. In addition, it can consider constraints allocation range restrictions, supply availability and block unit assignment constraints. Electronic means now exist for measuring retail sales and shelf-space allocations. Thus, a number of research firms (e.g. the A.B.A. Scan Data Systems Group in Los Angeles) are currently using electronic point-of-sales data capture methods as a basis for providing guidelines to their retailer clients for analysing and improving shelf-space utilization. As these methods become more widespread, the data required to estimate the demand and cost functions needed to implement the model will become routinely available. This study has demonstrated that the dynamic programming approach can efficiently be implemented on a microcomputer to solve problems of realistic size. Forthcoming hardware and software developments promise to enhance the solution speed even more, while permitting the consideration of larger-size problems. It is expected that microcomputer-based approaches, such as that which has been proposed, will play an important role in enhancing retailer profitability through improved shelf-space allocation decisions in the future. 421

Journal of the Operational Research Society Vol. 37, No. 4

REFERENCES 1. W. LEE (1961) Space management in retail stores and implications to agriculture. In Marketing Keys to Profits in the 1960's (W. K. DovA, Ed.), pp. 523-533. American Marketing Association, Chicago, Ill. 2. R. MALSAGNE (1972) La productivite de !a surface de vente passe maintenant par l'ordinateur. Travail Meth. No. 274, 3-8. 3. T. MoNSHOUWER, A. OosTEROM and J. RoVERS (1966) Het belan van weloverwogen assortiments-beheer. Het Levensmiddelenbedriff 385-393. 4. Chain Store Age (1963) Cifrino's space yield formula: a breakthrough for measuring product profit. 39, 83. 5. MCKINSEY-GENERAL FooD STUDY (1963) The Economics of Food Distributors. General Food, New York. 6. Chain Store Age (1965) Shelf allocation breakthrough. 41, 77-88. 7. COSMOS Training and Installation Manual (1969) National Association of Food Chains, Washington, D.C. 8. R. C. CURHAN (1973) Shelf space allocation and profit maximization in mass retailing. J. Mktg 37, 54-60. 9. R. C. CURHAN (1972) The relationship between shelf space and unit sales in supermarkets. J. Mktg 36, 406-412. 10. W. BROWN and W. T. TucKER (1961) The marketing center, vanishing shelf space. Atlanta Econ. Rev. 9-13. 11. K. K. Cox (1970) The effect of shelf space upon sales of branded products. J. Mktg Res. 7, 55-80. 12. E. ANDERSON and H. N. AMATO (1974) A mathematical model for simultaneously determining the optimal brand collection and display-area allocation. Opns Res. 22, 12-21. 13. P. HANSEN and H. HEINSBROEK (1979) Product selection and space allocation in supermarkets. Eur. J. Opns Res. 3, 58-63. 14. H. EvERETT (1963) Generalized Lagrange multipliers method for solving problems of optimal allocation of resources. Opns Res. 11, 399-417. 15. M. CoRSTJENS and P. DOYLE (1981) A model for optimizing retail space allocations. Mgmt Sci. 27, 822-833. 16. W. GoCHET and Y. SMEERS (1979) Reversed geometric programming: a branch-and-bound method involving linear subproblems. Opns Res. 7, 982-996. 17. M. CoRSTJENS and P. DoYLE (1983) A dynamic model for strategically allocating retail space. J. Opt Res. Soc. 34, 943-951. 18. G. LILIEN (1979) Advisor 2: modeling the marketing mix for industrial products. Mgmt Sci. 25, 191-204. 19. F. ZUFRYDEN (1974) Optimizing local radio reach. J. Advert. Res. 14, 63-68. 20. F. ZuFRYDEN (1975) On the dual optimization of media reach and frequency. J. Busin. 48, 558-570. 21. F. ZUFRYDEN (1975) Media scheduling and solution approaches. Opt Res. Q. 26, 283-295. 22. P. GREEN, J.D. CARROLL and D. GOLDBERG (1981) A general approach to product design optimization via conjoint analysis. J. Mktg 45, 17-37.

422