A SUPPLY CHAIN APPROACH TO SHELF SPACE ALLOCATION 
 
 
 
 
 
 
Except where reference is made to the work of others, the work described in this thesis is 
my own or was done in collaboration with my advisory committee. This thesis does not 
include proprietary or classified information. 
 
 
 
 
 
_______________________  
Veysel Ugur Dalkilic 
 
 
 
 
 
 
 
 
Certificate of Approval: 
 
 
_____________________________   _____________________________ 
Emmett J. Lodree     Jeffrey S. Smith, Chair 
Assistant Professor     Professor 
Industrial and Systems Engineering   Industrial and Systems Engineering 
 
 
____________________________   ____________________________ 
Alice E. Smith      Joe F. Pittman 
Profesor      Interim Dean 
Industrial and Systems Engineering   Graduate School 
 
 
 
 
 
 
A SUPPLY CHAIN APPROACH TO SHELF SPACE ALLOCATION 
 
 
 
 
 
Veysel Ugur Dalkilic 
 
 
 
A Thesis 
 
 
Submitted to 
 
 
the Graduate Faculty of  
 
 
Auburn University 
 
 
in Partial Fulfillment of the  
 
 
Requirements for the  
 
 
Degree of 
 
 
Master of Science 
 
 
 
 
Auburn, Alabama 
August 4, 2007 
 
 iii
 
 
 
 
 
A SUPPLY CHAIN APPROACH TO SHELF SPACE ALLOCATION 
 
 
 
 
 
 
 
 
 
Veysel Ugur Dalkilic 
 
Permission is granted to Auburn University to make copies of this thesis at its discretion, 
upon request of individuals or institutions and at their expense. The author reserves all 
publication rights. 
 
 
 
 
 
 
______________________________ 
       Signature of Author 
 
 
 
       ______________________________ 
       Date of Graduation 
 
 
 
 
 
 
 
 
 
 
 
 
 iv
 
 
 
 
 
THESIS ABSTRACT 
 
 
A SUPPLY CHAIN APPROACH TO SHELF SPACE ALLOCATION 
 
 
 
 
Veysel Ugur Dalkilic 
 
 
 
Master of Science, August 4, 2007 
 (B.S.T.E., Istanbul Technical University, 2002) 
 
67 Typed Pages 
Directed by Jeffrey S. Smith 
 
The growing intensity of retail competition is forcing stores to strive for 
excellence in operations. In this environment, retailers have to balance the interconnected 
operations, such as transportation from warehouse, shelf space and backroom space 
allocations in a way that the overall profit is maximized. This study introduces an 
analytical model for optimally allocating shelf and backroom space among items with 
stochastic demands, and defining cycle time for each while considering transportation 
utilization between the warehouse and store. A constructive heuristic and Genetic 
Algorithm method are developed to solve the non-linear model. 72 different scenarios 
with 720 different problem instances are generated to compare heuristics and also to 
 v
analyze the significance of several factors (shelf space, backroom space, truck cost, and 
problems size) on the results. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 vi
 
 
 
 
 
ACKNOWLEDGEMENTS 
 
 
I would like to thank Dr. Jeffrey S. Smith for his valuable guidance and support 
through this research and Dr. Alice E. Smith and Dr. Emmett J. Lodree for their kind 
consent to serve on the thesis committee. I would also like to thank my wonderful family 
and friends for their endless support. Finally, I would like to express my deep gratitude 
all of the people, who have encouraged me towards my goals.  
 
 
 
 
 
 
 
 
 
 
 
 
 
 vii
Style manual or journal used Computers and Industrial Engineering    
Computer software used Microsoft ? Word XP       
 
 viii
 
 
 
 
 
TABLE OF CONTENTS 
LIST OF TABLES         x 
LIST OF IGURES         xi 
CHAPTER 1 INTRODUCTION       1 
CHAPTER 2 LITERATURE REVIEW      8 
CHAPTER 3 PROBLEM DEFINITION       16 
 3.1 Notation and Model Formulation      19 
CHAPTER 4 SOLUTION PROCEDURES      27 
 4.1 Heuristic Solution Methodology      28 
  4.1.1 Genetic Algorithm      28 
   4.1.1.1 Representation     29 
   4.1.1.2 Encoding and Decoding Decision Variables  29 
   4.1.1.3 Initial Population     32 
   4.1.1.4 Evaluation      32 
   4.1.1.5 Selection      33 
   4.1.1.6 Recombination     34 
   4.1.1.7 Mutation      34 
   4.1.1.8 Pseudo Code for GA     36 
  4.1.2 Constructive Heuristic      37 
 
 ix
CHAPTER 5 EXPERIMENTATION AND NUMERICAL RESULTS  40 
 5.1 Numerical Results        42 
  5.1.1 Fitness Value Comparison     43 
   5.1.1.1 Effect of Problem Size on RSGA Performance 47 
  5.1.2 Computational Effort Comparison    47 
CHAPTER 6 CONCLUSION AND FUTURE WORK    51 
REFERENCES         53 
APPENDIX EXAMPLE PROBLEM       56 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 x
 
 
 
 
 
LIST OF TABLES 
Table 1.1 Projected GP Values for Single Criteria Solutions    6 
Table 4.1 Heuristic Parameters       36 
Table 4.2 Notation for Constructive Heuristic     37 
Table 5.1 Factor Levels of Scenarios       40 
Table 5.2 Parameter Values Used in Problems     42 
Table 5.3 GA Parameters        43 
Table 5.4 Comparison of RSGA and CH      44 
Table 5.5 Comparison of CHSGA and RSGA     45 
Table 5.6 Comparison of MSGA and RSGA      46 
Table 5.7 Effect of Problem Size on RSGA Performance    47 
Table 5.8 Average Number of Iterations - RSGA     48 
Table 5.9 Average Number of Iterations - CHSGA     49 
Table 5.10 Average Number of Iterations - MSGA     50 
 xi
 
 
 
 
 
LIST OF FIGURES 
Figure 1.1 A Planogram Prepared by Spaceman Application Builder for the  
Alcoholic Beverages Section of a Grocery Store    5 
Figure 3.1 Inventory Level When Q
i
<c
i      
22
 
Figure 3.2 Inventory Level When 
ii
cQ ?       23 
 1
 
 
 
 
 
CHAPTER 1 
INTRODUCTION 
 
The growing intensity of retail competition due to the emergence of new 
technology and shifts in customer needs is forcing stores to strive for excellence in 
operations. Extremely narrow profit margins leave little room for inefficiency and waste, 
thus the retailer has to balance all of the interrelated operations, such as shelf space 
allocation (SSA), in-store replenishment (ISR) and transportation in a way that the 
overall profit is maximized. 
A store can be considered as real estate that is leased by a number of different 
items. The store does not have a sufficient display area for all of the items available in the 
market; therefore making the best use of the available space and allocating it among an 
optimum pool of items are very important. For example, there is no need to allocate 
excessive shelf space for a slow moving item; accordingly the item can be exchanged 
with a more profitable one or the allocated shelf space might be reduced.  
In addition, space-planning, and location of items within departments are very 
important to create the maximum sales from every square foot of the store. Field 
experiments (Corstjens and Doyle (1981), Dreze et al. (1994), and Desmet and Renaudin 
(1998)) have shown that changes in number of facings of a product can affect customer 
attention. A facing can be defined as the front surface of an item that is visible to the 
 2
customer. Altering the visibility of a product through changes in display area or location 
influences the probability of sales. Therefore, increased exposure and price reduction are 
two commonly used promotional activities. 
In most stores, shelves are not the only stock keeping locations (SKLs) within the 
store. Some stores have backrooms where any items may be stored, thus allowing the 
retailer to achieve the availability of the items with timely and frequent replenishments. 
Furthermore, this also allows the store to have a wide range of items displayed on the 
shelves. By the same token, a warehouse acts like a high-capacity backroom where a set 
of items stored and distributed to retailers. 
Consequently, there are three SKLs and two linkages in a typical retail supply 
chain. The objective of whole supply chain, maintaining logistics efficiency together with 
low inventory levels, should allow product availability and customer satisfaction. 
Therefore, the retailer has to balance many interrelated operations (when to order, how 
often to replenish, when to remove an item, when to introduce a new item, etc.) that often 
conflict. Consequently, trade-offs between the sales generated by the items and the other 
management decisions have to be examined well in order to survive in this competitive 
industry. 
The retailers can increase profit either by increasing sales or decreasing cost, both 
marketing strategies and promotional activities ensure increased sales so operational 
strategies are applied to respond to the emerging requirements. As a result, these two 
objectives should be combined to optimize the whole system. 
 
 3
The store shelf is the final inventory location where any item meets the customer. 
No matter what the space allocation decisions are, retailers usually draw unsteady traffic 
and sell more or less than what they expect; however, customer demand must be met. 
Eventually, the main concern of store manager is the availability of items on the shelf at 
the time customers wish to purchase. 
ISR is one of the major operational issues in supply chain systems. After all, 
supply chains are ultimately responsible for ensuring on-shelf availability of items. One 
of the reasons why customer will stop patronizing a particular store is because the store 
no longer has what the customer wants. The greatest customer service in the world won?t 
save a retailer that does not stock what the customer wants and has constant stock-out 
positions on key items. Stock-outs mean lost sales opportunities for retailers and 
suppliers alike. They also create customer and brand-loyalty defections. On the other 
hand, it is also essential to recognize weak performers to get them out of the store as 
quickly as possible because they are occupying the space that could be allocated to more 
profitable items. 
One of the challenges faced by retail stores is in controlling the total investment 
in inventories. The retailer wants to protect itself from facing stock-outs by having safety 
stock. Safety stock is additional inventory that is carried to buffer against uncertainties in 
supply and demand. For instance, a supplier may have a problem that causes a delivery 
from the warehouse to be delayed by one or two days. Demand variation may occur 
because customers may buy more than expected because the item gets more popular for a 
short time. 
 4
Controlling the flow of inventory has become more important than ever with the 
increase of local and global competition. Inventory is assumed to be the single and largest 
asset on the balance sheet for almost all retailers. Inventory control is an important factor 
both to get rid of stock-outs and to lower inventory holding cost.  
Re-order cycle time (RCT), called lead time, is an important factor that impacts 
inventory as well. It is the amount of time from the point at which the store determines 
the need to order to the point at which the inventory is on hand and available for use. 
New items are ordered when the inventory on hand is depleted to a predetermined level. 
Intuitively, the longer the lead time the greater the amount of inventory that the store 
have to carry. 
Turnover, which corresponds to the number of times a particular stock of items is 
sold and restocked during a given period of time, is used to determine the productivity of 
inventory. For example, if the retail store has an item that turns only twice a year, the 
store has to make a much higher profit on that item as it is only realizing the profit two 
times and yet paying holding costs to store the item the entire year. Contrast this with an 
item that store will sell three of per week or 156 per year and only need to pay to keep six 
on hand. The investment in the slow turning item is longer and therefore more costly. 
When items are delivered from the warehouse to the store, transportation cost is 
incurred. There has to be a balance between transportation and the inventory cost. As the 
lead time is increased the warehouse can take advantage of the slower deliveries by 
waiting to fill its trucks with additional units. On the contrary, frequent shipments from 
the warehouse to the store will lower average inventory levels and raise transportation 
costs. Ultimately, the goal is to ensure that store has the right item, in the right amount, at 
 5
the right place, at the right time, while decreasing inventory levels, and increasing 
inventory turns. 
To determine where items should be located on the shelves, retailers of all types 
generate maps known as planograms. A planogram is a diagram created mostly by 
commercial software packages (Spaceman, Apollo, and etc.) that illustrates exactly where 
every stock keeping unit (SKU) should be placed. Software packages require the user to 
input UPC codes, profit margins, turnover, size of the item packaging or actual pictures 
of the packaging, and other applicable information into the program. 
 
Figure 1.1 A Planogram Prepared by Spaceman Application Builder for the 
Alcoholic Beverages Section of a Grocery Store 
There are two major drawbacks of Spaceman. First one is that it allows user to 
allocate the space based on a single criteria, such as movement, sales, profit and so forth. 
Single criteria allocation might not give any optimum solution in terms of maximizing 
 6
profit. In order to determine the limitation of single-criteria solution, a problem with 7 
items was created (see appendix 1). Table 1.1 demonstrates the number of facings 
allocated to the items, and corresponding profit value when certain allocation criterion is 
applied by Spaceman. Also, a simple heuristic was developed. First, the items were 
sorted descending by gross profit (price-cost) per cubic foot. Then, the shelf was stocked 
with items respectively (starting from the most profitable item) until the daily demand of 
each item was reached. The allocation process ended when the shelf was completely full, 
or daily demand for all items was met. As Table 1.1 indicates, item-3 has the smallest 
gross profit per cubic foot value. Because of the limited capacity of shelf space, the 
number of facings for item-3 was found 0. The solution found by the heuristic is better 
than the solutions generated by Spaceman in terms of GP. 
Table 1.1 Projected GP Values for Single-Criteria Solutions 
Criteria\Product Facings P1 P2 P3 P4 P5 P6 P7 Projected GP 
Divide Equally 19 22 17 19 29 17 21 $20,489.00 
Movement 18 21 18 18 30 17 22 $20,307.00 
Sales 19 21 17 19 32 16 21 $20,202.00 
Profit 19 19 16 19 35 19 18 $19,943.00 
Market Share 19 22 17 19 29 17 21 $20,489.00 
Required Inventory 18 21 18 18 30 17 22 $20,307.00 
Force Minimum-As Is 21 22 17 19 26 17 21 $20,797.00 
Force Minimum-Minimize 21 22 17 19 26 17 21 $20,797.00 
Heuristic 23 24 0 23 26 24 24 $21,196.00 
 
The second problem with commercial package such as Spaceman is that 
transportation cost incurred because of the changes in frequency of replenishment from 
supplier is not considered. Still, Spaceman incorporates stock-out and holding costs while 
providing a user friendly interface, which make the software guide popular in industry. 
 7
This study has two major objectives. First, building a model for optimally 
allocating shelf and backroom space among the items, and defining cycle time for each 
while considering transportation utilization  between the warehouse and store, the 
replenishment process between backroom inventory and shelf inventory, holding costs 
and stock-out costs in the store. Second, developing a solution method to solve the 
proposed non-linear model, and evaluating the results of the method against a 
constructive heuristic solution produced using shelf space allocation rule based on 
profitability of items. In Chapter 2, major drawbacks of field experiments to estimate the 
parameters used in SSA models are discussed. An overview of four comprehensive SSA 
models and relevant literature are also provided. In Chapter 3, problem definition, 
assumptions and mathematical formulation are presented. In Chapter 4, two heuristics are 
developed to solve the model. In Chapter 5, 72 (2x3x2x6) different scenarios with 720 
different problem instances are generated to compare heuristics and also to analyze the 
significance of several factors (shelf space, backroom space, truck cost and problem size) 
on the results. Computational results are also shown.
 8
 
 
 
 
 
CHAPTER 2 
LITERATURE REVIEW 
 
Space allocated to an item or a group of items has positive influence on the 
probability of the purchase. For instance, if an item is given a large space, it is more 
likely to have the customer?s attention; therefore, altering the visibility of an item through 
changes in space and location should affect sales. In order to provide evidence to support 
this argument, field experiments have been conducted in space management concentrated 
on determining whether a relationship exists between the number of facings allocated to 
an item and that item?s sales. The term, elasticity, is widely used in SSA literature and 
can be defined as the measure of sensitivity of one variable to another. For example, 
space elasticity is defined as increase in sales when the number of facings is doubled or 
the decrease in sales when the number of facings is halved. 
Corstjens and Doyle (1981), Dreze et al. (1994), and Desmet and Renaudin 
(1998) conducted a series of experiments to measure the elasticities. Needed data was 
collected from retailers with high number of stores. Only the category (item group) 
elasticities have been estimated through these field experiments. However, space 
allocation decisions across and within categories can not be considered to be 
independent; in addition, elasticity parameters for each and every item within the store 
should be calculated in the evaluation process. 
 9
Experimental findings indicate that impulse buying categories have higher space 
elasticities; thus, increasing the dedicated space for them will also tend to increase the 
sales. On the other hand, Desmet and Renaudin (1998) discovered a number of item 
groups having almost no change in demand with respect to changes in number of facings. 
Moreover, Dreze et al. (1994) demonstrated that the number of facings allocated to an 
item was one of the less significant factors. Vertical location of the item was determined 
to be more significant than the number of facings. Motivated from these findings, we can 
expect that a store may have items with stochastic demand which is independent from 
allocated shelf space. 
The major drawbacks of the experimentations are time, cost and inadequacy. First 
off, if the cross elasticities are to be considered in the evaluation process, data collection 
will take so much time. Moreover, with multiple item introductions and changes in 
demand for individual brands, the optimal SSA would be outdated before it could ever be 
implemented. On the other hand, ignoring cross elasticities and considering only main 
effects in the allocation process can lead to a major sub-optimization. For instance, a 
significant promotion in a substitute brand can totally change the demand pattern for two 
substitute items. The cheaper item will receive more demand and the other item will not 
grab as much attention as it used to do no matter the number of facings is. Likewise, 
allocating shelf space based on sales, while ignoring or simplifying cost side, has the 
same consequence. Second, elasticity parameters for each item do not remain same and 
should be evaluated continuously. Third, it?s assumed that shelves are always kept full; 
however, the number of facings may change between two consecutive in-store 
 10
replenishments, thus the uncontrolled change in number of facings does not allow 
evaluating the space elasticity. 
On the contrary, commercial SSA programs for retail industry allocate shelf space 
according to traditional criteria such as profit, sales and so forth. They are driven by 
operational concerns at item level. These commercial systems use sales data, item and 
shelf dimensions, and some relatively simple heuristics for developing operational 
guidelines, which is easy to implement in practice. Moreover, these programs suggest 
plans based on guidelines set by user. 
The marketing community has formulated number of models by incorporating the 
demand rate as a function of the shelf space allocated to the item, after they recognized 
the relationship between number of facings and sales. Borin and et al. (1994) developed 
the most comprehensive model to date. The SSA problem was formulated as constrained 
optimization problem with two decision variables: assortment and allocation of space to 
the items in the assortment. Switching to substitute items in the event of stock-outs was 
considered in the demand function. Because of the non-linearities in the objective 
function a heuristic solution method based on simulated annealing was tested on a small 
problem with a known optimum (complete enumeration) as well as on a larger problem 
without known optimum. They compared the results of simulated annealing against a 
solution produced using shelf space allocation rule based on share of sales. 
Urban (1998) presented a model where the demand rate is a function of 
instantaneous inventory level on the shelf. Backroom and shelved inventory were 
distinguished; thus, there was a limited amount of displayed inventory that had an effect 
on sales and was subject to shelf-space cost. A fixed procurement cost and a holding cost 
 11
based on average inventory level were incorporated to the model as well. A greedy 
heuristic and a genetic algorithm (GA) were proposed for the solution to the problem. 
Exhaustive search was conducted for small problems. They compared the results of a 
greedy heuristic against the GA and a solution produced based on share of sales. Both the 
greedy heuristic and the GA performed well. 
Yang (1999) made simplifications to the model of Corstjens and Doyle (1981). 
First, the profit of any item was assumed to be linear with respect to the allocated number 
of facings for that item. In fact, this is against the fact that there is a diminishing increase 
in sales due to the increase in shelf space. Second, the availability constraint was 
removed. A heuristic, similar to the algorithm for solving the knapsack problem, was 
proposed after these simplifications. Shelf space was allocated according to a descending 
order of sales profit for each item per display area or length. Small size problems were 
created to get the optimum solutions by applying complete enumeration. For the purpose 
of comparing performance, the heuristic compared against enumeration. An improved 
heuristic was also developed and found to be very efficient. 
Hwang and et al. (2004) developed an integrated mathematical model for the 
shelf space allocation problem and inventory control problem with the aim of maximizing 
retailer?s overall profit.  The demand rate was shaped by space, cross-space and location 
elasticity parameters. The items were restocked from the backroom to the shelves 
instantaneously and the restocking cost was ignored. A gradient search heuristic and a 
genetic algorithm are proposed to solve the model. Comparison of the proposed solution 
procedures with a total enumeration was demonstrated. Compared to the gradient search, 
the genetic algorithm performed better and generated near-optimum solutions. 
 12
The major drawbacks of the above four comprehensive models are as follows: 
? Demand is assumed to be deterministic. Using deterministic demand in 
the model neglects the holding and stock-out costs caused by the variation 
in demand. The demand distribution for each item can be obtained by 
analyzing the point of sales (POS) data and forecasting decisions can also 
be integrated into the decision process. Finally, stochastic models would 
more accurately portray realistic inventory settings 
? The lost sales due to stock-outs were not incorporated into the cost 
function. Current shelf space models focus on space responsiveness and 
neglect issues of assortment and stock-outs. The existing models attempt 
to allocate space to shelves using only space elasticities which have been 
shown to be weak. Murphy (2000) stated that availability of the items in 
the backroom or warehouse is at very high level but yet there are still 
stock-outs. The reason can be attributed to poor in-store management such 
as shelf space allocation and in-store replenishment. (Gruen and et al., 
2002) 
? The items were restocked from the backroom into the shelves 
continuously; as a consequence, none of the models explicitly 
differentiates between the backroom inventory and the displayed 
inventory. 
? Transportation cost was not considered. Moreover, an item might trigger 
an order and this may cause less than truck load shipment; thus, the 
frequency of deliveries from warehouse influences transportation cost. 
 13
A comprehensive literature review on SSA models has recently been done by 
Urban (2004). Inventory control models incorporating inventory level dependent demand 
rate were split into two distinct streams: models in which the demand rate of an item is a 
function of the initial inventory level and those in which it is dependent on the 
instantaneous inventory level. Urban (2004) noted the lack of literature on models 
studying multi item case with stochastic demand. 
The model developed in this thesis does not fit any of the streams above because 
the demand of an item is not a function of either shelf space or location; instead, it?s a 
function of an appropriate probability distribution. It should be noted that, historical 
demand data can be used to model the probability distribution. Furthermore, it can be 
assumed that the change in demand of an item because of the change in shelf space and 
location is handled by variance of this distribution. 
Cachon (2001) studied the management of transportation, shelf space and 
inventory costs for a retailer that sells multiple items with stochastic demand. Contrary to 
the marketing literature, the demand rate for each item was assumed to be independent of 
shelf-space allocation. In order to maintain analytical tractability, the Poisson distribution 
was used for demand function and the stochastic variables in the cost function were 
replaced with their mean. He assumed that all demand during stock-outs was 
backordered, which is doubtful for most retailers. The objective was to choose a truck 
dispatching policy and a SSA and an inventory policy to minimize total expected cost per 
unit time. Three different truck dispatching policies were compared. In this 
experimentation dispatching trucks whenever the cumulative orders across the products 
equals a constant threshold performed better than the two periodic review policies. 
 14
Speranza and Ukovich (1994) analyzed the problem of finding the frequencies 
that minimize the sum of transportation an inventory costs for several items on the same 
link. Items were assigned different/same frequencies and joint-transportation was taken 
into consideration. Items partially shipped at different frequencies found to be cost 
effective when they shared the same truck with those whose shipment happened to be 
simultaneous. 
Lim and et al. (2004) indicated the lack of literature on heuristic solution methods 
to SSA problems. They developed two Metaheuristics, a Tabu Search and a hybrid of 
Squeaky-Wheel Optimization (SWO), and evaluated the performance of a number of 
heuristics including these two on the simplified problem proposed by Yang (1999). A 
new neighborhood move technique, ?many-to-many move? was introduced and found to 
be well suited to SSA problem. Combining a local search technique with SWO has given 
better results in terms of obtained profit value. 
In this study, the objective is to present a SSA model which incorporates 
stochastic demand (the impact of space elasticities due to impulse buying is not 
incorporated into the model) and joint transportation with different frequencies and to 
distinguish between backroom and shelf space introducing a new term called ?shelf 
stock-out?. Therefore, the articles of Cachon (2001), and Speranza and Ukovich (1994), 
establish a base to this study. A genetic algorithm with an efficient moving operator will 
be introduced and tested against a constructive heuristic method on randomly created test 
problems. A discussion on maintaining feasibility on SSA problems will be provided as 
well.
 15
 
 
 
 
 
CHAPTER 3 
PROBLEM DEFINITION 
 
Our interest is in retail outlets (stores) where customers locate one or more 
desired items on shelf space within the store, purchase those items, and leave the store. 
The retailer brings the items from a warehouse and displays the items for sale on the 
store?s shelves. Due to the number of different items available, the limited total shelf 
space, and the item delivery and stock-out costs, the retailer maintains a small inventory 
of items in the back of the store (backroom) and replenishes the shelves from this 
inventory on a periodic basis. Our concern is the allocation of shelf space and backroom 
space to specific items and the two replenishment operations (replenishment of the shelf 
from the backroom and replenishment to the store from the warehouse). 
A category is an assortment of items with independent demand sharing limited 
shelf and backroom space. Suppose that there are shelves in a store and N brands of items 
within a category are displayed on the shelves with limited capacity. Each of the items 
has inventory space in the backroom and the total backroom space for this certain 
category is limited as well. Using as little as possible inventory space for expensive items 
is one of the goals of the store to reduce inventory holding cost. Items on the shelf and in 
the backroom are subject to inventory holding cost and stock-out cost. 
 
 16
A category has multiple items with stochastic demand. Daily customer demand 
for item i is described by a random variable
i
X , with probability density function 
()
i
xf for i=1,?,N. 
The store is replenished from a warehouse via trucks.  L is the time period 
between when an order is placed and when the order is received at the store.  This time is 
assumed to be deterministic.  Each truck has capacity C in cubic feet, and costs $K per 
trip between the warehouse and the store.  The number of units of each product available 
at the warehouse as well as the number of trucks available is not limited.    
The shelves are periodically restocked from the backroom up to the capacity that 
has been allocated to the items. The time between two consecutive in-store 
replenishments is fixed. Daily in-store replenishment (ISR) is assumed to be realistic, 
because there are many items, which have very little space in a category resulting in 
frequent replenishments to maintain the availability of the items on the shelves. In 
addition to this, items need to be checked and re-arranged after the rush hour everyday to 
keep them accessible and visible. 
Stock-outs occur in two forms. Shelf stock-out, which may occur anytime 
between two consecutive ISR due to excessive demand, occurs when the on-shelf 
quantity is less than the demand quantity. This type of shelf stock-out may be a result of 
items available in the back of the retail store that have not been transferred to the shelf 
where consumers can purchase them.  Backroom stock-outs occur because the inventory 
on the shelf and in the back of the retail store has been completely depleted before the 
next order arrival in a cycle. We assume that empty shelves in the store result in lost sales 
opportunities and no backlogging is considered. 
 17
A cycle,
i
c , is defined for each item as the time period between two successive 
arrivals of orders from the warehouse. It is assumed that only one order can be placed for 
each item during a cycle.  Because of the availability of the products and the trucks at the 
warehouse, as soon as an order is placed, the required number of trucks is immediately 
dispatched; thus, the cycle time for each item must be bigger than the lead time. Multiple 
items having the same cycle times can be shipped together. This will allow reducing the 
inventory levels in the backroom as well as increasing transportation utilization. When 
the order arrives, a required amount of items go to shelves (another ISR), and the rest of 
them are accommodated in the store?s backroom as usual.  
The objective of this study is to build a model for optimally allocating shelf and 
backroom space among the items, and defining cycle time for each while considering 
transportation utilization between the warehouse and the store, the replenishment process 
between backroom inventory and shelf inventory, holding costs and stock-out costs in the 
store. The objective is to maximize the expected profit associated with the N items in the 
category. 
The assumptions of the model are as follows: 
? The system involves N brands of items within a category and each brand 
has a dedicated space on the shelf and in the backroom. 
? ISR of items is joint replenishment and takes place instantaneously and 
periodically. 
? Lead time is known and constant. 
? It is not necessary to display all N brands of items on the shelves (i.e., 
allocation of 0 shelf space for products is allowed). 
 18
? Demand for each item is based on a known continuous demand 
distribution and is not dependent on shelf space allocation or location. 
Moreover, these distributions do not change during the cycle. 
? Any demand which exceeds the on-shelf quantity induces a stock-out cost 
and no backorders are allowed. 
? All relevant costs of each product (stock-out cost, inventory holding cost, 
procurement cost and etc.) are known and constant. 
? No more than one outstanding order from the warehouse is allowed for 
each item. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 19
3.1 Notation and Model Formulation 
Each item has: 
X
i
 Random variable for daily demand with density function f(x
i
) 
H
i
 Random variable for average inventory level per cycle 
Y
i 
Random variable for shelf stock-out per day 
W
i 
Random variable for stock-out per cycle 
Z
i 
Random variable for items sold per day 
R
i
 Random variable for items sold per cycle 
Q
i 
Random variable for days of inventory in a cycle 
v
i
 Volume (in cubic feet) of item i 
e
i
 Unit stock-out cost for item i 
h
i
 Daily unit holding cost for item i 
g
i
 Unit sales price for item i 
p
i
 Unit purchase price for item i 
s
i
 Shelf space allocated to item i 
r
i
 
Maximum number of items that can fit into s
i
.  Note that 
?
?
?
?
?
?
=
i
i
i
v
s
r  
b
i
 Backroom space allocated to item i 
d
i
 
Maximum number of items that can fit into b
i
.  Note that 
?
?
?
?
?
?
=
i
i
i
v
b
d  
c
i
 Number of days between two consecutive order arrivals for item i 
 
Other notations used in the model are as follows: 
TP(s
i
,b
i
,c
i
) Objective function  
T Random variable for number of trucks used per cycle 
K Cost per delivery per truck 
C
 
Truck capacity (cubic feet) 
SC
 
Total shelf capacity (cubic feet) 
BC
 
Total backroom capacity (cubic feet) 
L Lead time (in days) 
N
 
Number of items in the category 
 
 
 
 
 20
Objective: 
()()[] [] [] TKEWEeHEhREpgc,b,sTP Max
N
1i
iiiiiiiiii
????=
?
=
  (1) 
Subject to: 
?
=
?
N
1i
i
SCs          (2) 
?
=
?
N
1i
i
BCb          (3) 
1,2,3,...Ni    L       c
i
=?        (4) 
0  c and,b,s
iii
?        (5) 
Consider the fact that demand is probabilistic and it is assumed to be independent 
from the availability of the product, so the expected demand per item per day is: 
[]
?
?
=
=
0x
iiii
i
dx)x(fxXE         (6) 
Thus; 
Total expected demand per item per cycle= [ ]
ii
cXE     (7) 
Assuming that the shelf is fully stocked, there are two factors which impact daily 
sales, namely, number of products on the shelf and the demand for the product. If 
i
X  is 
more than 
i
r , we can sell only 
i
r . Finally, the following relation is obtained: 
[]
??
??
=
?
=
=
?
=
+=
+=
i
iii
i
iii
r
0xrx
iiiiii
r
0xrx
iiiiiii
dx)x(frdx)x(fx           
dx)x(frdx)x(fxZE
     (8) 
[]
ii
rZE <  is always true.       (9) 
 21
(9) implies that stock-out (hereafter shelf stock-out) may occur anytime between 
two consecutive ISR due to excessive demand regardless of the availability of the 
products in the backroom. Then, expected shelf stock-out per item per day is as follows: 
From equations (6) and (8): 
[] [ ] []
() ()
()()
?
??
???
?
=
?
=
?
=
=
?
=
?
=
?=
?=
??=
?=
ii
iiii
i
iiii
rx
iiii
rxrx
iiiiii
r
0xrx
iiiiii
0x
iii
iii
dxxfrx          
dxxfrdxxfx          
dx)x(frdx)x(fxdx)x(fx          
ZEXEYE
   (10) 
[]
i
YE  is not used in objective function, however it is explicitly shown to explain 
the occurrence of shelf stock-out even though we have backroom inventory. 
The store may not have enough products to meet the total demand emerging in a 
cycle. Any demand, after all of the available products, 
ii
dr + , are depleted, will be not be 
satisfied. Thus if backroom stock-out occurs before the end of a cycle, the expected daily 
stock-out turns out to be []
i
XE  for each day that remains in that cycle. The expected 
number of days of inventory in a cycle, expected time in which a given replenish-up-to 
level ()
ii
dr +  will deplete to zero, is shown below in order to calculate the total expected 
stock-out per cycle: 
 []
()
[]
i
ii
i
ZE
dr
QE
+
=         (1) 
 22
One important thing is that, increasing backroom space will not change total 
expected stock-out, if []
ii
cQE ? . By the same token, the total expected stock-out in a 
cycle will always include []
ii
cYE ? . 
Finally, the expected number of items sold per cycle, [ ]
i
RE , can be written as: 
 []
[] [ ]
()
?
?
?
?
?
?
+
?
=
otherwise           dr
cQE if         cZE
RE
ii
iiii
i
      (12)  
Figure 3.1 and 3.2 demonstrate two possible situations that may occur for each 
item during a cycle. In Figure 3.1, number of days of inventory in a cycle is less than 
cycle time, whereas in Figure 3.2, it is greater than or equal to cycle time. 
 
Figure 3.1 Inventory Level When Q
i
<c
i 
r
i
+d
i 
Q
i
c
i 
time
 
inventory
 
 23
 
Figure 3.2: Inventory Level When 
ii
cQ ?  
It should be noted that an item might trigger an order and this may cause less than 
truck load shipment. Figure 3.1 indicates that stock-out cost might be preferred to enable 
less transportation costs.  
Let the inventory level be 
ii
dr + at the beginning of a cycle and E[R
i
] be the 
expected number of products sold during the cycle. Then, the expected inventory level at 
the end of the cycle is given by: 
[]
iii
REdr ?+          (13) 
Inventory level at the beginning of the cycle =
ii
dr +    (14) 
From equation (12), (13) and (14): 
[]
()[ ]
[]
()[]
?
?
?
?
?
?
?
?
?
?
?
?
?
?
+
?
?+
=
otherwise                       
2
QEdr
cQE if         
2
ccZEdr2
HE
iii
ii
iiiii
i
    (15) 
The expected procurement cost per item per cycle is calculated as follows: 
r
i
+d
i 
Q
i 
c
i 
inventory
 
time
 
 24
[]
ii
pRE          (16) 
The expected sales revenue per item per cycle is calculated as follows: 
[]
ii
gRE          (17) 
If []
ii
cQE ? , the total expected stock-out in a cycle, [ ]
i
WE , will be []
ii
cYE . On the 
contrary if []
ii
cQE < , the total expected stock-out in a cycle will be as follows: 
 
[] [][] [ ] [ ]( )
[] [][] []()
[] [][]
[] ()
iiii
iiii
iiiii
iiiiii
drcXE         
ZEQEcXE         
YEXEQEcXE         
QEcXEQEYEWE
+?=
?=
??=
?+=
   
Therefore; 
 []
[] [ ]
[] ()
?
?
?
?
?
?
+?
?
=
 otherwise    drcXE
cQE  if                      cYE
WE
iiii
iiii
i
     (18) 
The total expected stock-out can also be shown as follows: 
[] [] []
iiii
REcXEWE ?=        (19) 
Trucks are used to transport inventory from warehouse to store at the end of each 
cycle, c
i
. Each item can be shipped with those which have the same cycle time. As 
explained in more detail by Speranza and Ukovich (1994), the joint-transportation allows 
transportation utilization, therefore cheaper transportation costs. Total expected 
transportation cost per cycle is calculated as follows: 
Steps for the pseudo code are as follows: 
? Calculate the required number of trucks for each cycle 
? Calculate the total required number of trucks 
? Calculate the total expected transportation cost 
 25
[] 0TE =  
For (j=L; j<= ()
i
cmax ; j++) { 
  Capacity =0; 
For each item { 
  If (jc
i
== ) { 
   Capcity += [ ]
ii
vRE  
  } 
} 
[]TE += 
?
?
?
?
?
?
C
Capacity
 
} 
Total expected transportation cost per cycle = [ ]TKE    (20) 
Finally, the objective function can be shown as follows: 
()()[] [] [] []()[]TKEREcXEeHEhREpgc,b,sTP
N
1i
iiiiiiiiiiii
?????=
?
=
 
Where: 
[]
?
?
=
=
0x
iiii
i
dx)x(fxXE         (21) 
[]
??
=
?
=
+=
i
iii
r
0xrx
iiiiiii
dx)x(frdx)x(fxZE       (2) 
[]
()
[]
i
ii
i
ZE
dr
QE
+
=         (23) 
 26
[]
[] [ ]
()
?
?
?
?
?
?
+
?
=
otherwise           dr
cQE if         cZE
RE
ii
iiii
i
      (24) 
[]
()[ ]
[]
()[]
?
?
?
?
?
?
?
?
?
?
?
?
?
?
+
?
?+
=
otherwise                       
2
QEdr
cQE if         
2
ccZEdr2
HE
iii
ii
iiiii
i
    (25) 
and []TKE  (see pseudo code)       (26) 
The non-linearities and integrals in the objective function, and running a pseudo 
code program to get []TE  disallow a closed form solution. Therefore, two heuristic 
solution are developed to find near-optimum and/or optimum solutions. In order to 
calculate the expected values, such as [ ]
i
ZE  and [ ]TE , a computer program is developed. 
In Chapter 4, an adaptive optimization method called Genetic Algorithm (GA) is 
presented. A constructive heuristic solution is also provided to evaluate the performance 
of proposed GA.
 27
 
 
 
 
 
CHAPTER 4 
SOLUTION PROCEDURES 
 
The shelf space allocation problem (SSAP) can be regarded as allocating limited 
capacity of shelf space among the demanding brands in the assortment list in a way that 
the total profit of the category is maximized. The model in this paper also includes 
backroom space and cycle time as decision variables.  
Heuristics less often have been used in shelf space allocation studies and there is 
limited number of heuristic solutions in this area. Borin et al. (1994), Urban (1998), Yang 
(2001), and Tim et al. (2004) developed heuristic solutions to their models. Borin et al. 
used a heuristic solution based on simulated annealing (SA). They tested the heuristic on 
a small size problem, 6-item case, with a known optimum. Moreover, for a larger 
problem, 18-item case, the solution found by SA was compared against a common 
principle for shelf space allocation, in which the space allocated to a particular item is 
proportional to its sales. Urban developed a greedy heuristic and a genetic algorithm to 
solve his integrated model. He conducted an exhaustive search to obtain optimal 
solutions for 6-item case. Additional problems with 18 and 54 items were also generated, 
and both heuristic results compared with a solution produced using a shelf allocation rule 
based on share of sales. Yang simplified the non-linear model of Corstjens and Dolye 
(1981) and proposed a method which is similar to the algorithm used for solving a 
 28
knapsack problem. He tested the performance of the proposed algorithm against optimum 
solutions on small size problems. Tim et al. (2004) extended the model of Yang by 
integrating product groupings and nonlinear profit function, and improved Yang?s 
heuristic by introducing three new neighborhood moves. He developed two meta-
heuristics, Tabu Search and Squeaky-Wheel Optimization. Simulated problems in 
different sizes, between 10 and 100 items, were generated to test the performance of the 
adjustment neighborhood moves and the proposed algorithms. 
Since there is not any exact algorithm to solve SSAP proposed in this research, a 
hybrid heuristic method is applied with the aim of producing high-quality solutions in a 
reasonable time. In order to evaluate the performance of this method, a constructive 
heuristic is also applied to the same set of problems. There are not benchmarks available; 
therefore, both heuristics are experimented on randomly created problems with different 
sizes and the comparison is demonstrated in Chapter 5. 
 
4.1 Heuristic Solution Methodologies 
4.1.1 Genetic Algorithm 
The first approach to solve the problem is an adaptive optimization technique 
known as a genetic algorithm (GA). Each individual represents a potential solution to the 
problem and each solution is evaluated to give some measure of its ?fitness?. In a typical 
GA the following steps are performed: 
1. ? individuals (parents) are randomly generated forming the initial 
population solutions.  
 29
2. ? individuals (offspring) are created, through the use of 
recombination and mutation, using the parents that are selected uniformly 
randomly (i.e., not based upon fitness) from the population. 
3. The best ? survivors are chosen, based on their fitness values to 
form the current population, either from the offspring or the whole population,  
4. Repeat steps 2 and 3 until the stopping criteria is met. 
 
Therefore, over successive iterations, the best individual in the population is 
expected to approach to the global optimum. Problem specific modifications are as 
follows: 
 
4.1.1.1 Representation 
Phenotype is the actual representation of the decision variables (
i
s ,
i
b , and 
i
c ) as 
shown in previous chapter. On the other hand, genotype, the encoded representation of 
decision variables, is used for better implementation of the proposed heuristic. Genotypes 
facilitate simple crossover and mutation. Genotypes and phenotypes can be converted to 
each other as needed in evaluation step.  
 
4.1.1.2 Encoding and Decoding Decision Variables 
 
 
 
 
 30
Shelf space: 
 
Equation (2) in Chapter 3 indicates that total shelf space allocated to the items is 
less than or equal to maximum shelf space capacity. This constraint also enables free 
shelf space. In genotype representation, ?1? corresponds to maximum shelf space 
capacity, SC. [0,1] interval is divided into N+1 pieces. The first N pieces, ( 0k
1
? ), 
(
12
kk ? ),?, (
1NN
kk
?
? ), are the percentages of the shelf space allocated to the items. 
(
N
k1? ) is the percentage of empty shelf space.  
Calculating shelf space values for each item (genotype to phenotype): 
For (i=1; i<=N; i++){ 
 If(i==1){ 
  s
i
=SC(k
i
-0) 
 }else{ 
  s
i
= SC(k
i
 -k
i-1
) 
 } 
} 
0 1 
1
k  
2
k  
N
k  
1k...kk0
N21
?????    
phenotypes,...,s,s
N21
?  
genotype   k,...,k,k
N21
?  
? 
()
1
0kSC
s
1
1
?
=  
( )
1
kkSC
s
12
2
?
=  
Empty 
shelf space 
 31
Backroom space: 
 
Equation (3) in Chapter 3 indicates that total backroom space allocated to the 
items are less than or equal to maximum backroom space capacity. This constraint also 
enables free backroom space. In genotype representation, ?1? corresponds to maximum 
backroom space capacity, BC. [0,1] interval is divided into N+1 pieces. The first N 
pieces, ( 0l
1
? ), (
12
ll ? ),?, (
1NN
ll
?
? ), are the percentages of the backroom space 
allocated to the items. (
N
l1? ) is the percentage of empty backroom space.  
Calculating backroom space values for each item (genotype to phenotype): 
For (i=1; i<=N; i++){ 
 If(i==1){ 
  b
i
=BC(l
i
-0) 
 }else{ 
  b
i
= BC(l
i
 -l
i-1
) 
 } 
} 
0 1 
1
l  
2
l  
N
l  
1l...ll0
N21
?????    
phenotypeb,...,b,b
N21
?  
genotype   l,...,l,l
N21
?  
? 
()
1
0lBC
b
1
1
?
=  
( )
1
llBC
b
12
2
?
=  
Empty 
backroom 
space 
 32
Cycle Times: 
Phenotypes and genotypes are same. 
phenotype   c,...,c,c
N21
?  
genotype   c,...,c,c
N21
?  
 
4.1.1.3 Initial Population 
Each of the ? individuals in the initial population is randomly generated as 
follows: 
1. Generate N random numbers from the range [0,1], arrange these 
numbers in ascending order, and assign them as k
1
, k
2
, ?,k
N
, such that 
1k...kk0
N21
?????  
2. Generate N random numbers from the range [0,1], arrange these 
numbers in ascending order, and assign them as l
1
, l
2
, ?,l
N
, such that 
1l...ll0
N21
?????  
3. Randomly generate cycle time values (in days) from the range 
[0,m] where 1m ?  
 
4.1.1.4 Evaluation 
The process of evaluating the fitness values of an individual consists of the 
following steps: 
1. Convert to individual?s genotype to its phenotype as explained in 
representation 
 33
2. Evaluate the objective function 
In order to evaluate the objective function, first [ ]
i
ZE  is calculated by using 
probability density function values for a given demand distribution. The procedure can be 
described as the summation of the probability of each possible outcome (number of items 
sold per day) multiplied by its value. Then [ ]
i
QE , [ ]
i
XE , [ ]
i
HE ,  and []TE  are 
calculated respectively to get expected profit. 
 
4.1.1.5 Selection 
A 2-way tournament selection is adopted as the selection procedure. In this 
method, since the tournament size is 2, weak individuals have more chance to be 
selected. This approach consists of the following steps: 
1. Calculate the fitness values of each individual in the population 
2. Chose 2 individuals from the population at random 
3. Select the better of these 2 individuals based on their fitness values 
(parent 1) 
4. Repeat step 2 and 3 to select parent 2 
The procedure will give more chance to individuals with less fitness to be 
selected more frequently, hence it also implies that genetic diversity is increased and 
further exploration of the solution space is provided. This helps keep the diversity of 
population large, preventing premature convergence on poor solutions. 
 
 
 
 34
4.1.1.6 Recombination 
Two parents are chosen as described above in order to generate an offspring. The 
variables from each parent define the lower and upper bounds of the offspring variable, 
which is randomly selected within this interval. Each offspring variable is calculated as 
follows: 
())1,0(Ukkkk
1i2i1iinew
??+=  
() )1,0(Ullll
1i2i1iinew
??+=  
()
??
)1,0(Ucccc
1i2i1iinew
??+=  
This implementation is called convex crossover and ensures that the offspring 
inherits traits from both parents. 
 
4.1.1.7 Mutation 
Mutation is an important part of the search as it helps to prevent the population 
from stagnating at local optima. Furthermore, it should also guarantee obtaining any 
solution in the feasible search space. Each variable in an individual is mutated with a 
probability of ?f?. Each offspring variable is mutated as follows: 
if( () ( ) )1a,0Nk  &&  0a,0Nk
ii
?+?+ { 
()a,0Nkk
iinew
+=  
 else{ 
  ()a,0Nkk
iinew
?=  
 } 
 
 35
if( () ( ) )1a,0Nl  &&  0a,0Nl
ii
?+?+ {   
()a,0Nll
iinew
+=  
 else{ 
  ()a,0Nll
iinew
?=  
 } 
 
if(U(0,1)<n){ 
 1cc
iinew
+=  
}else{ 
 1cc
iinew
?=  
 if( 1c
inew
? ){ 
  1c
inew
=   
 } 
} 
where 0<j<1 
In mutation, maintaining feasibility for a variable is to go back to its previous 
value when it is outside the feasible region. The feasible region is between 0 and 1 for 
i
k  
and 
i
l ; on the other hand, 
i
c  has only a lower bound which is 1. Then, 
inew
k  and 
inew
l  
variables are calculated by adding or subtracting ( )a,0N  according to which boundary is 
violated. 
inew
c  is set to 1 if the mutated variable is less than 1. On the other hand, in 
 36
recombination, offspring always reside in feasible region no matter which parents are 
used for crossover operation. 
Table 4.1 Heuristic Parameters 
? Number of parents 
? Number of offspring 
t Stopping criteria, number of unsuccessful iterations 
z Number of maximum iterations 
f Mutation rate for each variable 
a Mutation parameter for shelf and backroom space 
n Mutation parameter for cycle time 
m Maximum value for initial cycle time 
 
4.1.1.8 Pseudo Code for GA 
Set ?, ?, t, z, f, a, n, and m 
Randomly generate initial population 
Calculate fitness values 
For each iteration until z { 
 For each offspring { 
  Select 2 parents 
  Create an offspring by recombination 
  Mutate the offspring 
 } 
 Calculate fitness values of offspring 
 Sort the total population descending based on fitness values 
 Assign first ? individuals as new parents 
 Terminate if no-improvement is made after t iterations 
} 
 37
In the proposed GA implementation, each individual (parent or offspring) 
represents how much space is allocated and what the cycle times are for each item. If the 
allocated space on the shelf for a particular item, 
i
s , is less than its unit volume, 
i
v , the 
item will not be placed on the shelf and 
i
s  will be added to the total free space. The same 
rule applies to the backroom space. Therefore, the heuristic enables product assortment 
and allocation decisions at the same time. 
 
4.1.2 Constructive Heuristic 
In order to evaluate the performance of above method, a constructive heuristic 
has also been developed.  
Table 4.2 Notation for Constructive Heuristic 
Y 
Total required shelf space to fulfill daily demand within 
i
3?  
[]()
?
=
+=
N
1i
iii
v3XEY ?  
i
j  
Profitability of an item based on expected daily demand, gross margin, 
and space requirement 
i
ii
ii
v
pg
]X[Ej
?
=  
J  
Total profitability of items 
?
=
=
N
1i
i
jJ  
 
Since the daily in-store replenishment is assumed, there is no need to place more 
than maximum daily demand on the shelf to avoid any stock-outs. It is assumed that 
maximum daily demand for any item remains in the 3 sigma range. If the total required 
space, Y, is more than SC the allocation is done based on profitability of an item per its 
cubic volume, 
i
j . On the contrary, if it?s less than SC, total required space is used to 
 38
allocate all of the items. Cycle times are assumed to be ?1 day?, resulting in daily 
shipments from warehouse to the backroom. Because of the daily transportation, there is 
no need to have any inventory in the backroom; thus, available backroom space is not 
used to allocate any item to minimize holding cost. The procedure for the constructive 
heuristic can be expressed as follows: 
Calculate Y , 
i
j, and J  
For each item i{ 
If ( SCY ? ){ 
  [ ]()
iIii
v?3XEs +=  
}else{ 
  
J
jSC
s
i
i
?
=  
} 
1c
0b
i
i
=
=
 
 } 
 TP(s
i
,b
i
,c
i
) 
It can be shown that the optimality of single criterion (such as sales, demand and 
profit) solution methods to allocate shelf space is problem dependent. For example, an 
item with a high demand is allocated more space if the allocation is done based on 
demand. However, this allocation might not give any optimum solution in terms of 
maximizing profit, if the gross margin of that item is relatively small. Consequently, 
selecting an appropriate solution method is vital on performance of the results. 
 39
The constructive heuristic developed in this study aims to avoid shortcomings of 
the single-criterion solutions. If the shelf space is scarce it allocates space among items 
based on gross margin, demand, and space requirements. On the contrary, if the shelf 
space is abundant, it does not allow the full space occupied by items resulting in 
unnecessary holding cost. 
Since the constructive heuristic does not guarantee an optimal solution, another 
heuristic methodology called genetic algorithm was developed. In the following chapter, 
in order to analyze the significance of several factors (shelf space, backroom space, truck 
cost and problem size) on the performance of both heuristics, an experiment with 720 
different problem instances is conducted. The problems are also solved with mixed 
seeded GA and constructive heuristic seeded to get improved results.  
 
 
 40
 
 
 
 
 
CHAPTER 5 
EXPERIMENTATION AND NUMERICAL RESULTS 
 
This chapter presents experimental results for the two algorithms that have been 
developed to solve the SSAP problem, which is described in detail in Chapter 4.  
Since the proposed model is unique, there are no known benchmarks available. In 
order to evaluate the performance of both heuristics in different retailer settings, an 
experiment is conducted. The factors are defined as shelf space (2 levels), backroom 
space (3 levels), truck cost (2 levels), and problem size (6 levels) (see Table 5.1). Since 
demand is stochastic, 10 instance of each problem are generated. A total 720 
(2x3x2x6x10) problems are randomly generated. Each row in Table 5.1 corresponds to 6 
different scenarios with different problem sizes, 8, 16, 32, 64, 128, and 256 respectively. 
Table 5.1 Factor Levels of Scenarios 
Scenario Truck Cost Shelf Space Backroom Space # of problems 
1-6 250 Small Small 60 
7-12 250 Small Medium 60 
13-18 250 Small Large 60 
19-24 250 Large Small 60 
25-30 250 Large Medium 60 
31-36 250 Large Large 60 
37-42 750 Small Small 60 
43-48 750 Small Medium 60 
49-54 750 Small Large 60 
55-60 750 Large Small 60 
61-66 750 Large Medium 60 
67-72 750 Large Large 60 
 
 41
In order to be realistic, the levels of shelf space and backroom space are created 
as a function of expected demand, unit volume, and problem size. Small and large shelf 
space sizes for each problem are generated as follows: 
Small size:  [] 5.0XESC
N
1i
i
??
?
?
?
?
?
=
?
=
 
Large size:   []2XESC
N
1i
i
??
?
?
?
?
?
=
?
=
 
Small, medium and large backroom space sizes for each problem are generated as 
follows: 
Small size:  [] 5.0XEBC
N
1i
i
??
?
?
?
?
?
=
?
=
 
Medium size:   []5XEBC
N
1i
i
??
?
?
?
?
?
=
?
=
 
Large Size:  []10XEBC
N
1i
i
??
?
?
?
?
?
=
?
=
 
Demand was assumed to be following Poisson distribution, which is discrete and 
positive, for all items. The Poisson distribution has one parameter, mean, which was 
generated as discrete U(10,30) for each item. 
The other parameter values used in problems are randomly generated as shown in 
Table 5.2. 
 
 
 
 
 42
Table 5.2 Parameter Values Used in Problems 
Parameters Value 
v
i
 Random(2,4) 
f
i
 Random(30,50) 
p
i
 Random(10,30) 
e
i
 g
i
- p
i
 
h
i
 
36500
p6
i
 
C 2700 
 
5.1 Numerical Results 
When testing heuristics, the right choice of values for the search parameters has a 
considerable effect on the performance of the procedure. As the problem type and size 
change, the parameters should be fine tuned in order to get better results. However, it is 
desirable to have those parameters independent from the problem size. Therefore, a 
considerable amount of time was spent to fine tune the parameters (see Table 4.1 and 
Table 5.3) for the GA. They were set once while ensuring good results and used 
throughout the experiments. ?a? is defined as a function of N, number of items, to avoid 
big jumps during the mutation process.  
It is most desirable to test and evaluate the proposed GA by comparisons with 
optimal solutions in respect to the solution quality and computational effort. However, 
because of the problem size (and search space size) of numerical examples in this study, 
complete enumeration was not applicable. Therefore, the best known solutions obtained 
for the problems were those determined using a constructive heuristic.  
In addition to the CH solution, each problem was solved 10 times with random 
initial seeds. This procedure is called random seeded GA (RSGA). Furthermore, CH 
solutions were used as initial population to study the significance of initial population on 
 43
performance. If half of the initial population is CH seeded, the method is called mixed 
seeded GA (MSGA). If the whole initial population is CH seeded, the method is called 
CH seeded GA (CHSGA). Each problem was also solved 10 times with MSGA and 
CHSGA. 
Table 5.3 GA Parameters 
Parameters Values 
? 30 
? 40 
t 400 
z 20,000 
a 0.128/N 
n 0.1 
m 10 
 
Normalization is not applied to the results, because other than main factors, there 
are also problem dependent factors, such as SC and BC. Thus, instead of performing an 
Anova analysis, we preferred to demonstrate whether one method is better than the other 
in terms of fitness values. Moreover, the average difference between the fitness values of 
each method as well as standard deviation of these differences was also provided. 
Computational effort was demonstrated in terms of number of function evaluations until 
the stopping criteria is met. 
 
5.1.1 Fitness Value Comparison 
In each table (Table 5.4-5.6) below, 2 (hereafter m1 and m2) of the 4 different 
methods are compared. Only the maximum solution of ten seeds is taken into 
consideration for RSGA, CHSGA and MSGA. 720 problems are broken into 12 main 
groups in which are 6 scenarios. 60 problems are analyzed in each row while 
 44
demonstrating comparison of fitness values. The following notation will be used in each 
table: 
?A? refers to the percentage of better m1 (stands for the first method and will be 
defined for each table) than m2 (stands for the second method and will be defined for 
each table) solutions for 60 problems.  
?B? refers to the average difference of the fitness values of m1 and m2 for 60 
problems. The difference is calculated as m1-m2. 
Table 5.4 Comparison of RSGA and CH 
m1 : RSGA, and m2 : CH 
FACTORS 
Scenario 
A B TC SC BC 
1-6 95% 1,216 250 small small 
7-12 100% 1,258 250 small medium 
13-18 100% 1,303 250 small large 
19-24 67% -351 250 large small 
25-30 43% -341 250 large medium 
31-36 25% -335 250 large large 
37-42 90% 1,048 750 small small 
43-48 90% 1,059 750 small medium 
49-54 97% 1,154 750 small large 
55-60 68% -325 750 large small 
61-66 57% -271 750 large medium 
67-72 53% -289 750 large large 
1-72 74% 427       
 
Compared to CH, RSGA performs better for 534 problems (74% of the 
problems). Average difference for these problems is 427. On the other hand, CH 
solutions are better for 186 problem instances (26% of the problems).  
 45
It can be shown that larger shelf space will reduce the daily stock-outs, and less 
truck cost will maintain more frequent shipments from warehouse resulting in smaller 
cycle times. Since CH tries to allocate maximum daily demand on the shelf and assigns 
cycle time as ?1? for each item, larger shelf space and less truck cost will enable CH to 
perform better. As the result of Table 5.4 indicates, the success rate and average 
difference (negative) in problems with large shelf space (scenarios 19-36 and 55-72). 
Besides, the average success rate for CH is found to be better in scenarios where truck 
cost is assigned 250, and shelf space is defined as large. Consequently, it can be noted 
that shelf space has significant effect on the performance of CH. 
Table 5.5 Comparison of CHSGA and RSGA 
m1 : CHSGA, and m2 : RSGA 
FACTORS 
Scenario 
A B TC SC BC 
1-6 83% 1,405 250 small small 
7-12 77% 1,362 250 small medium 
13-18 73% 1,405 250 small large 
19-24 42% 353 250 large small 
25-30 80% 342 250 large medium 
31-36 75% 339 250 large large 
37-42 77% 1,632 750 small small 
43-48 68% 1,591 750 small medium 
49-54 68% 1,537 750 small large 
55-60 32% 334 750 large small 
61-66 50% 272 750 large medium 
67-72 47% 291 750 large large 
1-72 64% 905       
 
 
 
 46
Table 5.6 Comparison of MSGA and RSGA 
m1 : MSGA, and m2 : RSGA 
FACTORS 
Scenario 
A B TC SC BC 
1-6 85% 1,393 250 small small 
7-12 75% 1,369 250 small medium 
13-18 75% 1,383 250 small large 
19-24 40% 353 250 large small 
25-30 78% 342 250 large medium 
31-36 75% 338 250 large large 
37-42 75% 1,657 750 small small 
43-48 68% 1,585 750 small medium 
49-54 68% 1,562 750 small large 
55-60 32% 334 750 large small 
61-66 52% 278 750 large medium 
67-72 47% 297 750 large large 
1-72 64% 908       
 
Table 5.5 and Table 5.6 demonstrate the comparison of modified heuristics and 
RSGA for 720 problems. Both CHSGA and MSGA are expected to perform better than 
RSGA, because the initial populations contain moderately good solutions. The quality of 
solutions is improved for 461 (64%) problems. However, there are still 259 (36%) 
problems where the RSGA performs better than CHSGA and MSGA. Recombination and 
mutation operators play important role in the performance of any genetic algorithm 
method. Convergence to an optimum solution will be achieved only by mutation, if the 
diversity of the initial population is not ensured. Therefore, premature convergence will 
be inevitable. Consequently, the solution quality will be dependent on the initial 
population when CHSGA and MSGA are used.  
 
 47
5.1.1.1 Effect of Problem Size on RSGA Performance 
 Another significant factor on RSGA?s performance is problem size. As shown in 
Table 5.7, success rate tends to diminish as the problem size increases. For a particular 
scenario (TC, SC and BC are at a level), it can be shown that order quantity from 
warehouse increases as the number of items increases. Therefore, CH is likely to utilize 
truck capacity resulting in less transportation cost when large orders are placed. 
Consequently, decrease in success rate should also be attributed to transportation 
utilization and increase in number of decision variables. 
Table 5.7 Effect of Problem Size on RSGA Performance 
Problem size Success Rate 
8 100% 
16 95% 
32 78% 
64 83% 
128 51% 
256 36% 
 
5.1.2 Computational Effort Comparison 
The choice of the stopping criteria is one of the key factors which decides the 
time complexity as well as the quality of the solutions. Thus, the stopping criteria should 
enforce fast convergence while retaining the quality of the solution to an acceptable 
value. The proposed stopping criteria in this study allows 20,000 iterations unless there is 
no improvement in any 400 consecutive iterations.  
Computational effort is determined in terms of number of iterations executed 
until the stopping criteria is met. Since, the initial population of RSGA is randomly 
generated; it consists of relatively poor solutions. Hence, the computational results 
 48
provided in this section demonstrate the average number of iterations to reach the CH 
solutions as well as the best solutions found so far (if RSGA is better than CH). On the 
other hand, only the average number of iterations, until the stopping criteria is met, is 
provided for CHSGA and MSGA, since, the initial population for those includes CH 
solutions. 
In Table 5.8, only the problems, where RSGA outperforms CH, are taken into 
account. Column ?A? refers to the average number of iterations until the stopping criteria 
is met. Column ?B? refers to the average number of iterations to reach the CH solutions. 
It takes 991 iterations (for RSGA) on the average to reach the corresponding CH 
solutions. Furthermore, the average number of iterations is 6,559 at convergence.  
Table 5.8 Average Number of Iterations - RSGA 
FACTORS 
Scenario 
A B TC SC BC 
1-6 5,405 563 250 small small 
7-12 5,609 622 250 small medium 
13-18 5,870 566 250 small large 
19-24 7,662 1,516 250 large small 
25-30 7,184 1,848 250 large medium 
31-36 6,476 279 250 large large 
37-42 5,256 752 750 small small 
43-48 6,167 899 750 small medium 
49-54 5,762 1,141 750 small large 
55-60 7,807 1,153 750 large small 
61-66 9,343 1,464 750 large medium 
67-72 9,591 1,801 750 large large 
1-72 6,559 991       
 
 
 
 49
Table 5.9 and Table 5.10 show the average number of iterations required for 
modified heuristics for 720 problems. Column ?A? refers to the average number of 
iterations until the stopping criteria is met. Both CHSGA and MSGA converge faster than 
RSGA, since they start from moderately good solutions. The average number of iterations 
for CHSGA and MSGA to attain convergence are 3,427 and 3,396 respectively.  
It should be noted that increasing the first stopping criteria, which is ?maximum 
number of unsuccessful iterations?, could also improve the solution performance of GA.  
Table 5.9 Average Number of Iterations - CHSGA 
FACTORS 
Scenario 
A TC SC BC 
1-6 3,197 250 small small 
7-12 4,287 250 small medium 
13-18 4,549 250 small large 
19-24 2,574 250 large small 
25-30 2,874 250 large medium 
31-36 3,242 250 large large 
37-42 3,390 750 small small 
43-48 4,218 750 small medium 
49-54 4,314 750 small large 
55-60 2,557 750 large small 
61-66 2,722 750 large medium 
67-72 3,203 750 large large 
1-72 3,427       
 
 
 
 
 
 
 50
Table 5.10 Average Number of Iterations - MSGA 
FACTORS 
Scenario 
A TC SC BC 
1-6 3,240 250 small small 
7-12 4,131 250 small medium 
13-18 4,432 250 small large 
19-24 2,286 250 large small 
25-30 2,995 250 large medium 
31-36 2,975 250 large large 
37-42 3,436 750 small small 
43-48 4,417 750 small medium 
49-54 4,430 750 small large 
55-60 2,324 750 large small 
61-66 2,940 750 large medium 
67-72 3,144 750 large large 
1-72 3,396       
 
As a result, after solving 720 randomly generated problems, shelf space and 
problem size found to be more significant factors on the performance of proposed GA. 
CH seeded initial population has contributed to the GA, but this also gave rise to 
premature convergence because of similar individuals in current population. Performance 
of the CH was found to be dependent on problem type. It should be noted that the 
randomness among problems within each scenario is not enough to compare solution 
methods. Therefore, a wide variety of problem types should be taken into consideration 
in order to get a true comparison.
 51
 
 
 
 
 
CHAPTER 6 
CONCLUSIONS AND FUTURE WORK 
 
This thesis studied the problem of shelf and backroom space allocations while 
explicitly considering stochastic demand and transportation costs. This is an important 
problem that is encountered in a wide variety of practical situations where space is 
scarce. A new model was proposed including holding cost and occurrence of stock-out 
(especially while items are available in the backroom).  
Since there was not any exact algorithm to solve SSAP proposed in this research, 
a hybrid heuristic method was applied with the aim of producing high-quality solutions. 
In order to evaluate the performance of this method, a constructive heuristic was also 
applied the same problem. There were not benchmarks available; thus, both heuristics 
were experimented on randomly generated 720 problems. The heuristic parameters were 
set once and used throughout the experiments. GA performed better solutions for 
instances where the shelf space was small. It can be noted that in real life situations, the 
shelf space is usually scarce and each item has a lead time more than a day because of the 
lot-size and geographical limitations. The performance of CH solution is found to be 
problem dependent. It is observed that true comparison of different solution methods can 
only be valid, if wide variety of problems is taken into consideration. Not only problem 
size but also the other constraints should be evaluated. 
 52
 
The followings can be suggested for further studies: 
1) Proposed model has practical relevance in a variety of situations; thus 
efforts must be made to apply the model on related problems. In this way, 
the performance of heuristic can be evaluated with existing benchmark 
problems. 
2) Different selection, recombination and mutation operators can be applied 
to increase the performance of GA. 
3) Growing manufacturing companies tend to use the available space for 
machinery and try to facilitate the warehouse space until the new business 
starts paying off. This model can also be implemented to a manufacturing 
plant where there are Kanban system and limited backroom capacity. 
 53
 
 
 
 
 
REFERENCES 
Borin, N., Farris, W. P., and Freeland, J. R. (1994). A model for determining retail 
product category assortment and shelf space allocation, Decision Sciences, Vol. 25, No. 
3, 359-383. 
 
Cachon, G. (2001). Managing a retailer?s shelf space, inventory and transportation, 
Manufacturing and Service Operations Management, Vol. 3, No. 3, 211-229. 
 
Speranza, M. G., Ukovich, W. (1994). Minimizing transportation and inventory costs for 
several products on a single link, Operations Research Society of America, Vol. 42, No. 
5, 879-894. 
 
Desmet, P., and Renaudin, V. (1998). Estimation of product category sales 
responsiveness to allocated shelf space, International Journal of Research in Marketing, 
Vol. 15, No. 5, 443-457. 
 
Doyle, P., and Cortjens, M. (1981). A model for optimizing retail space allocations, 
Management Science, Vol. 27, No. 7, 822-834. 
 
 54
Dr?ze, X., Hoch, S. J., and Purk, M. E. (1994). Shelf management and space elasticity, 
Journal of Retailing, Vol. 70, No. 4, 301-326. 
 
Gruen, T. W., Corsten, D. S., Bharadvaj, S. (2002). Retail out of stocks: A world wide 
examination of extent, causes, and consumer responses. 
 
Hwang, H., Choi, B., Lee, M. J. (2005). A model for shelf space allocation and inventory 
control considering location and inventory level effects on demand, International Journal 
of Production Economics, Vol. 97, No. 2, 185-195. 
 
Lim, A., Brian, R., Zhang, X. (2004). Metaheuristics with local search techniques for 
retail shelf space optimization, Management Science, Vol. 50, No. 1, 117-131. 
 
Murphy, J. V. (2000). Empty shelves mean lost sales for retailers, but tech solutions offer 
help, Global Logistics and Supply Chain Strategies. 
 
Urban, T. L. (1998). An inventory-theoretic approach to product assortment and shelf 
space allocation, Journal of Retailing, Vol. 74, No. 1, 15-35. 
 
Urban, T. L. (2005). Inventory models with inventory-level-dependent demand: A 
comprehensive review and unifying theory, European Journal of Operational Research, 
No. 162, 792-804. 
 
 55
Yang, M. H., and Chen, W. C. (1999). A study on shelf space allocation and 
management, International Journal of Production Economics, No. 60-61, 309-317. 
 
Yang, M. H. (2001). An efficient algorithm to allocate shelf space, European Journal of 
Operational Research, Vol. 131, No. 1, 107-118. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 56
 
 
 
 
 
APPENDIX  
EXAMPLE PROBLEM 
Relevant parameter definitions (from Spaceman manual): 
Term Definition 
Reg movement The unit sales or case sales of a product for a specific period 
Width The distance from one side of a unit to the other side 
Price The retail price for a merchandized item 
Cost The cost per item of a product 
Projected GP Projected gross profit is the gross profit you can expect to earn if 
you maintain the current schedules and stock on shelves presently 
depicted on your planogram 
 
Problem input parameters: 
 
Product Width 
(inches) 
Price Cost Reg movement (daily demand) 
1 9 $38 $16 23 
2 8 $36 $18 24 
3 10 $36 $17 25 
4 9 $40 $18 23 
5 6 $39 $15 26 
6 10 $36 $13 24 
7 8 $36 $19 25 
 
Period:  49 days 
Shelf width: 1,200 inches