RETAIL SPATIAL DESIGN WITH A RACETRACK AISLE NETWORK
CONSIDERING REVENUE AND ADJACENCIES
Except where reference is made to the work of others, the work described in this
dissertation is my own or was done in collaboration with my advisory committee.
This dissertation does not include proprietary or classified information.
________________________
Haluk Yapicioglu
Certificate of Approval:
__________________________________
Robert L. Bulfin
Professor
Industrial and Systems Engineering
__________________________________
Alice E. Smith, Chair
Professor
Industrial and Systems Engineering
__________________________________
Kevin R. Gue
Associate Professor
Industrial and Systems Engineering
__________________________________
Bryan A. Norman
Associate Professor
Industrial and Systems Engineering
__________________________________
George T. Flowers
Dean
Graduate School
RETAIL SPATIAL DESIGN WITH A RACETRACK AISLE NETWORK
CONSIDERING REVENUE AND ADJACENCIES
Haluk Yapicioglu
A Dissertation
Submitted to
the Graduate Faculty of
Auburn University
in Partial Fulfillment of the
Requirements for the
Degree of
Doctor of Philosophy
Auburn, Alabama
December 19, 2008
iii
RETAIL SPATIAL DESIGN WITH A RACETRACK AISLE NETWORK
CONSIDERING REVENUE AND ADJACENCIES
Haluk Yapicioglu
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
VITA
Haluk Yapicioglu, son of Hatice Zulal Zuhal and M. Ali Yapicioglu, was born in
July, 1976, in Ankara, Turkey. He graduated from Ankara Ayranci High School in 1993
and Anadolu University with a Bachelor of Science degree in Industrial Engineering in
June 1997. In September 1998, he entered Middle East Technical University and
graduated with a Master of Science degree in Industrial Engineering in May 2001. During
his Master of Science study, he had worked as a teaching assistant in the Department of
Industrial Engineering at Anadolu University, Turkey for three years. He completed his
military service in March 2002. He started the Ph.D. program of Industrial and Systems
Engineering at Auburn University in January 2003. He is a student member of
INFORMS, IIE and IEEE.
v
DISSERTATION ABSTRACT
RETAIL SPATIAL DESIGN WITH A RACETRACK AISLE NETWORK
CONSIDERING REVENUE AND ADJACENCIES
Haluk Yapicioglu
Doctor of Philosophy, December 19, 2008
(M.S., Middle East Technical University, May 2001)
(B.S. Anadolu University, Turkey, July 1997)
178 Typed Pages
Directed by Alice E. Smith
In this dissertation, a novel model for the retail store design problem is proposed.
The new approach consists of placing departments in a racetrack configuration within the
store subject to area and shape constraints. The objective function considers the area
allocated to each department, contiguity of the departments to the aisle network,
adjacency requirements among departments and revenues. The revenue generated by a
department is a function of the area of the department and exposure of the department to
the aisle network. The aisle network is comprised of two components: the racetrack,
which serves as the main travel path for the customers, and the egress aisles. First, the
proposed model is simplified using two assumptions: zero aisle area and known
department area requirements. To solve the simplified model, three different solution
approaches are developed. These are a mixed integer nonlinear programming
vi
formulation, a constructive heuristic and tabu search. The performances of the solution
approaches are investigated using example problems. Based on the insights gained from
the simplified model and the solution approaches developed, solution approaches and a
general optimization framework for the model with variable department areas and an
aisle network with non-zero area is provided.
vii
ACKNOWLEDGEMENTS
I would like to express my gratitude to my advisor, Dr. Alice E. Smith for her
invaluable supervision and support. I consider working with her as privilege and great
honor.
I also would like to extend great many thanks to my committee members, Dr.
Robert L. Bulfin, Dr Kevin R. Gue and Dr. Bryan A. Norman, for their valuable insights
and challenging questions. This research never could have been completed without their
contributions.
I am so glad that Dr. Jeffrey S. Smith has offered me several research
opportunities which have helped me to improve my researcher skills.
Finally, my deepest thanks goes to my parents, Zuhal and M. Ali Yapicioglu, who
brought me to this world, and ever since I was a little child never deprive me of their
endless love and support. Especially my father, without his encouragement I would never
been able to come to Auburn and pursue my degree.
viii
Style manual or journal used: IIE Transactions
Computer software used: Java 5.0, Eclipse 3.1, MATLAB, Microsoft Word, Excel,
PowerPoint and Visio
ix
TABLE OF CONTENTS
Page
LIST OF TABLES............................................................................................................ xii
LIST OF FIGURES ......................................................................................................... xiv
I. INTRODUCTION........................................................................................................... 1
1.1. Research Objectives................................................................................................. 5
1.2. Major Contributions................................................................................................. 5
1.3. Organization of the Dissertation.............................................................................. 7
II. LITERATURE REVIEW............................................................................................... 8
2.1. Literature Survey on Facility Layout....................................................................... 8
2.1.1. The quadratic assignment problem (QAP) ..................................................... 10
2.1.2. Mixed integer nonlinear programming approach (MINLP) ........................... 11
2.1.3. Slicing tree ...................................................................................................... 14
2.1.4. Space filling curves......................................................................................... 16
2.1.5. Flexible bay structure...................................................................................... 17
2.1.6. Graph theoretic approaches............................................................................. 18
2.1.7. Multiple objectives.......................................................................................... 20
2.1.8. Controlling department shapes ....................................................................... 21
2.2. Retail Space Allocation Models................................................................................. 22
2.2. Retail Space Allocation Models ............................................................................ 22
2.2.1. Related studies ................................................................................................ 23
2.2.2. Analysis and discussion .................................................................................. 29
2.3. Literature Survey on Tabu Search ......................................................................... 30
III. RETAIL SPACE ALLOCATION PROBLEM .......................................................... 34
3.1. Nomenclature......................................................................................................... 37
3.2. Model..................................................................................................................... 38
x
3.2.1. Objective function........................................................................................... 38
3.2.2. Constraints ...................................................................................................... 39
3.3. Description of the Objective Function................................................................... 40
3.4. Handling the REL Scores ...................................................................................... 43
IV. MIXED INTEGER PROGRAMMING FORMULATION OF THE RACETRACK
LAYOUT .......................................................................................................................... 45
4.1. Nomenclature......................................................................................................... 45
4.2. Pictorial Representation of the Model Variables................................................... 47
4.3. Model..................................................................................................................... 48
4.4. Computational Experience..................................................................................... 51
4.5. Limitations of the MIP Model ............................................................................... 56
V. HEURISTIC PROCEDURES FOR THE RETAIL STORE DESIGN PROBLEM.... 59
5.1. A Constructive Heuristic for the Retail Store Layout Problem............................. 59
5.2. Example ................................................................................................................. 63
5.3. Solution Representation for the Tabu Search Algorithm....................................... 66
5.4. Tabu Search for Retail Store Design ..................................................................... 69
5.5. Experimentation..................................................................................................... 75
5.6. Assessment of the Solution Quality for the Constructive Heuristic and the Tabu
Search............................................................................................................................ 81
5.7. Analysis and Discussion ........................................................................................ 85
VI. VARIABLE DEPARTMENT AREAS ...................................................................... 88
6.1. On the choice of the revenue function................................................................... 88
6.2. Tabu Search for Retail Spatial Design with Flexible Department Areas .............. 93
6.3 Experimentation.................................................................................................... 103
6.4. Varying the available store area........................................................................... 115
6.5. Conclusion ........................................................................................................... 126
VII. CONCLUSIONS AND FUTURE RESEARCH..................................................... 128
7.1. Conclusions.......................................................................................................... 128
7.2. Future Research ................................................................................................... 131
REFERENCES ............................................................................................................... 134
xi
APPENDIX I: Example Problem Data for the MIP Formulation................................... 142
APPENDIX II: Example Problem Data for Heuristics................................................... 146
APPENDIX III: Example Problem Data and Results from Chapter VI ......................... 152
xii
LIST OF TABLES
Table 1.1. Eight largest department stores in US by sales.................................................. 2
Table 2.1. Closeness ratings.............................................................................................. 19
Table 3.1. REL ratings and corresponding scores. ........................................................... 44
Table 4.1. Solution times for the example problems. ...................................................... 54
Table 4.2. Degree of constraint satisfaction for the 8 department problem...................... 56
Table 5.1. Ordered list of departments with respect to closeness ratings......................... 63
Table 5.2. Final assignment of departments to layers....................................................... 63
Table 5.3. Summary of the results for the constructive heuristic. .................................... 66
Table 5.4. Test case configurations................................................................................... 77
Table 5.5. The best solutions found by the tabu search.................................................... 77
Table 5.6. Comparison of the constructive heuristic against the tabu search................... 82
Table 5.7. Component-wise comparison of the constructive heuristic against the tabu
search. ....................................................................................................................... 83
Table 5.8. Comparison of best and average performances of TS with theoretical upper
bounds....................................................................................................................... 83
Table 6.1. Best solutions found, n = 12. ......................................................................... 107
Table 6.2. Best solutions found, n = 20 .......................................................................... 107
Table 6.3. Average execution time in seconds. .............................................................. 109
Table 6.4. Evaluation of the quality of the solutions, n = 12.......................................... 109
Table 6.5. Evaluation of the quality of the solutions, n = 20.......................................... 111
Table 6.6. Average aisle width. ...................................................................................... 113
Table 6.7. Performance evaluation with respect to average. .......................................... 114
Table 6.8. Comparison of average aisle widths n = 12................................................... 119
Table 6.9. Comparison of average aisle widths n = 20................................................... 119
Table 6.10. Comparison of results for n = 12. ................................................................ 120
Table 6.11. Evaluation of the quality of the solutions, n = 12........................................ 122
Table 6.12. Comparison of average results for n = 20.................................................... 123
Table 6.13. Comparison of best results for n = 20.......................................................... 123
Table 6.14. Evaluation of the quality of the solutions, n = 20........................................ 126
Table A1. Department data, n = 8................................................................................... 142
Table A2. Revenue data, n = 8........................................................................................ 142
Table A3. Department data, n = 10................................................................................. 143
Table A4. Revenue data, n = 10...................................................................................... 143
Table A5. Department data, n = 16................................................................................. 144
Table A6. Revenue data, n = 16...................................................................................... 145
Table A7. Area, Revenue and Aspect Ratio Data for n = 16.......................................... 146
Table A8. Adjacency Ratings and Scores for n = 16...................................................... 147
Table A9. Area, Revenue and Aspect Ratio Data for n = 17.......................................... 148
xiii
Table A10. Adjacency Ratings and Scores for n = 17.................................................... 149
Table A11. Area, Revenue and Aspect Ratio Data for n = 20........................................ 150
Table A12. Adjacency Ratings and Scores for n = 20.................................................... 151
Table A13. Revenue data for n = 12............................................................................... 152
Table A14. Revenue data for n = 20............................................................................... 153
Table A15. Summary of runs for configuration: FE3, n = 12, store area: 25.5?17........ 159
Table A16. Summary of runs for configuration: AE3, n = 12, store area: 25.5?17. ...... 159
Table A17. Summary of runs for configuration: RE3, n = 12, store area: 25.5?17. ...... 160
Table A18. Summary of runs for configuration: FE0, n = 12, store area: 25.5?17........ 160
Table A19. Summary of runs for configuration: AE0, n = 12, store area: 25.5?17. ...... 160
Table A20. Summary of runs for configuration: RE0, n = 12, store area: 25.5?17. ...... 160
Table A21. Summary of runs for configuration: FE1, n = 20, store area: 25.5?17........ 161
Table A22. Summary of runs for configuration: AE1, n = 20, store area: 25.5?17. ...... 161
Table A23. Summary of runs for configuration: RE1, n = 20, store area: 25.5?17. ...... 161
Table A24. Summary of runs for configuration: FE0, n = 20, store area: 25.5?17........ 161
Table A25. Summary of runs for configuration: AE0, n = 20, store area: 25.5?17. ...... 162
Table A26. Summary of runs for configuration: RE0, n = 20, store area: 25.5?17. ...... 162
Table A27. Area allotments for store areas 16?24, 17?25.5 and 18?27, n = 12............ 162
Table A28. Area allotments for store areas 16?24, 17?25.5 and 18?27, n = 20............ 163
xiv
LIST OF FIGURES
Figure 2.1. A slicing tree (left) and the corresponding layout (right) (Tam, 1992).......... 15
Figure 2.2. Space filling curves (Adopted from Bozer et al. 1994).................................. 16
Figure 2.3. FLEXBAY representation.............................................................................. 17
Figure 2.4. A planar graph (left) and the corresponding layout (right). ........................... 18
Figure 3.1. The grid layout. .............................................................................................. 34
Figure 3.2. The free form layout....................................................................................... 35
Figure 3.3. Racetrack layout. ............................................................................................ 36
Figure 3.4. Partition of the store area to zones with respect to traffic density.................. 42
Figure 4.1. Pictorial representation of the model variables. ............................................. 48
Figure 4.2. Optimal layout of 8 department problem. ...................................................... 55
Figure 4.3. Optimal layout of 10 department problem. .................................................... 55
Figure 4.4. Best known layout of 16 department problem Store area: 14?10. ................ 56
Figure 5.1. Definition of zones for the constructive heuristic. ......................................... 60
Figure 5.2. Resultant layout for n = 16. ............................................................................ 64
Figure 5.3. Resultant layout for n = 17. ............................................................................ 65
Figure 5.4. Resultant layout for n = 20. ............................................................................ 65
Figure 5.5. Partition of the store area................................................................................ 67
Figure 5.6. Solution representation and corresponding layout. ........................................ 68
Figure 5.7. The initial solution: department sequence (a), partitioning (b), permutation
neighborhood (c) and partitioning neighborhood (d)................................................ 71
Figure 5.8. Zone definitions of the store for the two different settings. ........................... 76
Figure 5.9. The best layout obtained by tabu search for Test Case 1. .............................. 78
Figure 5.10. The best layout obtained by tabu search for Test Case 2. ............................ 78
Figure 5.11. The best layout obtained by tabu search for Test Case 3. ............................ 79
Figure 5.12. The best layout obtained by tabu search for Test Case 4. ............................ 79
Figure 5.13. The best layout obtained by tabu search for Test Case 5. ............................ 80
Figure 5.14. The best layout obtained by tabu search for Test Case 6. ............................ 80
Figure 5.15. Test Cases 1 and 2: fitness vs. number of iterations..................................... 84
Figure 5.16. Test Cases 3 and 4: fitness vs. number of iterations..................................... 84
Figure 5.17. Test Cases 5 and 6: fitness vs. number of iterations..................................... 84
Figure 5.18. The best layout obtained by tabu search for Test Case 1, without penalty
function. .................................................................................................................... 87
Figure 5.19. The best layout obtained by tabu search for Test Case 3, without penalty
function. .................................................................................................................... 87
Figure 6.1. Solution representation and the corresponding layout. .................................. 94
Figure 6.2. The initial solution: permutation (a), partitioning (b), permutation
neighborhood (c) and partitioning neighborhood (d)................................................ 96
Figure 6.3. Overall optimization procedure.................................................................... 103
xv
Figure 6.4. Number of allowed non-improving moves vs. average fitness function...... 106
Figure 6.5. Fitness, revenue, adjacency and ARP vs. number of iterations, n = 12. ...... 113
Figure 6.6. Fitness, revenue, adjacency and ARP vs. number of iterations, n = 20. ...... 114
Figure 6.7. Increase in area allotments as a percentage of minimum required area....... 118
Figure 6.8. The best layouts obtained for n = 12, F
f
, aspect ratio enforced.................... 122
Figure 6.9. The best layouts obtained for n = 20, F
f
, aspect ratio enforced.................... 124
Figure A1. Best solution found, configuration: FE3, n = 12, store area: 25.5?17. ........ 153
Figure A2. Best solution found, configuration: AE3, n = 12, store area: 25.5?17......... 154
Figure A3. Best solution found, configuration: RE3, n = 12, store area: 25.5?17. ........ 154
Figure A4. Best solution found, configuration: FE0, n = 12, store area: 25.5?17. ........ 155
Figure A5. Best solution found, configuration: AE0, n = 12, store area: 25.5?17......... 155
Figure A6. Best solution found, configuration: RE0, n = 12, store area: 25.5?17. ........ 156
Figure A7. Best solution found, configuration: FE1, n = 20, store area: 25.5?17. ........ 156
Figure A8. Best solution found, configuration: AE1, n = 20, store area: 25.5?17......... 157
Figure A9. Best solution found, configuration: RE1, n = 20, store area: 25.5?17. ........ 157
Figure A10. Best solution found, configuration: FE0, n = 20, store area: 25.5?17. ...... 158
Figure A11. Best solution found, configuration: AE0, n = 20, store area: 25.5?17....... 158
Figure A12. Best solution found, configuration: RE0, n = 20, store area: 25.5?17. ...... 159
1
I. INTRODUCTION
A department (retail) store is ?a retail establishment which specializes in selling a
wide range of products without a single predominant merchandise line?. In general, retail
stores are organized as product groups (also referred to as departments) such as apparel,
furniture, appliances, paint, hardware, toiletries, cosmetics, photographic equipment,
jewelry, toys, and sporting goods (Levy and Weitz, 1999). According to the 2002
Economic Census data, the retail trade sector has the third largest impact (14%) on gross
domestic product (GDP), after wholesale trade (22%) and manufacturing (18%)
(http://www.census.gov/econ/census02/data/us/US000.HTM). However, nearly all of the
published work on facilities design and material handling planning has focused on
manufacturing facilities. Considering the important share of the retail trade in US GDP,
this study models and solves an important and common service sector facility layout
problem, the retail store layout problem.
In this study, the terms retail store and department store are used to refer to the
US Census?s general merchandise store definition, however the modeling approach can
be generalized to any type of store in this classification. General merchandise stores
constitute the third largest subsector in the retail trade sector with a 14% share, totaling
more than 40,000 establishments with nearly $450 billion in annual sales
2
(http://www.census.gov/econ/census02/data/us/US000_44.HTM). Overall, they provide
employment opportunities for more than 2.5 million people. To illustrate, the eight
largest department stores reported in Store magazine?s special report (2005) are listed in
Table 1.1.
Throughout the 20
th
century, department stores have experienced many drastic
changes (Davis et al., 2000). At the beginning of the 20
th
century, consumers had to visit
numerous different stores on an ordinary shopping trip. This situation changed when
retailers took advantage of railroads and refrigeration technology to offer a greater variety
under one roof. These first examples of department stores were generally located in city
centers, making them accessible to the masses (Davis et al., 2000). The birth of
department stores including Macy?s and JC Penney was in this era.
Table 1.1. Eight largest department stores in US by sales.
Company
2004
Revenues (in
thousands)
Number of
stores
Sales per
store
Sears $36,099,000 1,970 $18,324,365
JCPenney $18,424,000 1,078 $17,090,909
Federated $15,630,000 454 $34,427,312
May $14,441,000 1,157 $12,481,417
Kohl?s $11,700,600 589 $19,865,195
Dillard?s $7,528,600 329 $22,918,112
Nordstrom $7,131,388 180 $39,618,822
Saks $6,437,277 381 $16,895,740
With the development of suburban living after the Second World War, rural area
malls were born. The malls were places where a number of small specialty stores and one
or two large department stores were situated together to serve broad customer needs.
3
Department stores attracted customers and offered a price advantage, while the smaller
stores offered more variety in a specific product line with better customer service (Davis
et al., 2000). Thus, malls were able to provide the customer with both convenience and
variety at the same time.
During the 1960?s, the base of the competition among retailers shifted from
convenience and variety to price. Discount stores (e.g. Wal-Mart, K-Mart and Target)
offered bargain prices and greater product variety at the expense of reduced quality of
service and ambiance (Davis et al., 2000).
Consumer pressure on department stores for lower prices with even greater
product variety led to the rise of ?category killers? in the 1980s. Chain stores like Toys
?R? Us, Home Depot, Circuit City and Staples are examples of chains formed to meet this
new challenge (Davis et al., 2000). Additionally, club stores like Costco and Sam?s
emerged in this period. Club stores charge a small annual fee to consumers to let them
shop at cheaper prices, and also create customer loyalty through the membership
perception.
The last step of the retail store evolution sequence is retail wars. Since the
category killers and club stores capture the majority of the retail trade pie, the remaining
retailers started to emphasize the entertainment aspect of shopping by providing
customers with all kinds of entertainment activities (Davis et al., 2000). Malls blending
shopping with other activities like dining, theaters and playgrounds for children are the
latest trend in the retail sector. In addition to this new design concept in malls,
4
department stores also redesigned their physical appearances to create a more enjoyable
shopping environment.
In today?s retailing world, there is fierce competition between regular department
stores, category killers and the others. As mentioned previously, the two most important
arsenals in this competition are price and differentiation. As is well known, competition
based only on pricing does not provide a sustainable competitive edge. One of the
department store chains that achieved a competitive edge by differentiating itself from the
others is Kohl?s. Kohl?s success is attributed to three features: Kohl?s locates its stores
away from malls, its product line is composed of brand names, and it applies a unique
design for its layout, which is the racetrack. The racetrack is cited as a distinguishing
factor in the rapid growth of Kohl?s. The success of the racetrack layout has caused it to
be implemented by two of Kohl?s most important rivals, JC Penney and Sears (Hajewski,
2005).
This research includes a model and a solution approaches for the retail store
layout problem. The model considers the revenue generated by the departments and
adjacency requirements among the departments as the objective function(s), subject to a
set of aspect ratio constraints for the departments, a set of area constraints and a set of
aisle constraints. More specifically, the retail store is required to have an aisle structure
which is in the shape of a racetrack. Departments are to be placed within and around the
racetrack. The racetrack provides the main pathway for customers and access to the
different departments. It is connected to the outer rim of the store via one entrance aisle
which provides the only access in to the store from the outside. In this model, aisling is
5
considered a means not only for transport but also for revenue enhancement. Thus, the
location and the area allocated to the racetrack is an important consideration in the model.
The proposed model includes both binary and continuous decision variables with
nonlinear terms in the objective function as well as in the constraint set. The model is
combinatorial since the optimization of the layout inherently includes the sequencing of
the departments within and around the racetrack. The model also has continuous
components since area is allocated to the departments. The racetrack constraint is
extremely difficult to express and enforce mathematically as shown later in Chapter IV.
Thus, heuristic approaches are developed to solve the model.
1.1. Research Objectives
The research objectives of this study can be listed as follows:
? Develop a model and or/models that capture the notion of revenue generation vis
a vis layout in retail stores,
? Quantify the aisle area allocation and,
? Design and develop appropriate solution procedures.
1.2. Major Contributions
The most important contribution of this research is the development of a series of
models describing revenue generation in department stores in conjunction with layout.
The spatial design of such facilities is usually accomplished through rules of thumb,
using qualitative measures. However, the rich body of literature in manufacturing
6
facilities design can be adapted to the retail space allocation problem. This study is an
important milestone in an attempt to realize this opportunity. The models introduced
herein not only consider revenue generation, but also adjacency satisfaction, which has
been a popular criterion used in facility design problems. Thus, the decision maker is
given the flexibility of weighting the importance of these two criteria in the final
decision.
The second contribution of this research is the way aisling is handled. In most cases, the
problem of aisling is viewed as a secondary concern and left until after the construction
of the block layout. Although this approach might be useful for manufacturing facilities
and for the sake of simplicity, it is not the case in retail settings. In retailing, aisles can be
a way of revenue enhancement, especially when used as a display area to increase sales
of promotional items. In addition, since aisles dictate the sojourn path of the customers,
they can be used to draw attention to different departments to encourage spontaneous
purchases. In this study, the location and the area of the aisles are determined
simultaneously with the design of the block layout.
The solution representation developed does not require the departments to be
rectangular. Rather, the proposed approach allows departments to have non-convex
shapes like L or U. There are some other representations based on discretization of the
overall facility space, however, the flexibility of having non-convex shapes in a
continuous representation is, to the best of our knowledge, novel.
7
1.3. Organization of the Dissertation
The organization of the dissertation is as follows. In Chapter II, an extensive
literature survey on facility layout, retail shelf space allocation and tabu search is
provided. Chapter III introduces the mathematical model for the retail facility space
allocation problem. To illustrate the problems associated with the application of
mathematical modeling approach to the problem at hand, a mixed integer programming
formulation of the problem and computational experience are provided in Chapter IV. In
Chapter V, a simplified version of the model introduced in Chapter III where the areas of
the departments are assumed to be constant with zero aisle area is discussed. Also in
Chapter V, a constructive heuristic, encoding and decoding schemes specifically designed
for the problem and the tabu search implementation are presented to solve the simplified
model. The performance of the two heuristics are discussed on a set of example
problems. In Chapter VI, a revenue model addressing the diminishing marginal returns
with respect to the area of departments is introduced. Using the revenue model and two
example problems, the model presented in Chapter III is considered for the variable
department areas and non-zero aisle area cases. To solve the model, the solution
representation and decoding/encoding mechanisms developed in Chapter V are modified
and utilized in a tabu search framework. The dissertation concludes with future research
directions provided in Chapter VII.
8
II. LITERATURE REVIEW
This chapter contains the relevant literature regarding the research and is divided
into three sections: review of the facility layout problem, review of the shelf space
allocation problem and, a brief introduction to tabu search.
2.1. Literature Survey on Facility Layout
In today?s world, products are made available to consumers through a series of
integrated activities. Raw materials coming from suppliers are transformed into products,
and shipped to warehouses and/or distribution centers, then the distribution centers
dispatch the goods to retailers, and finally retailers sell these goods to the consumer. This
whole set of activities involving the flow of goods, money and information (associated
with the flow of goods) is called the supply chain (Chopra and Meindl, 2006). The supply
chain and almost all components of the supply chain have been extensively studied.
There is a vast amount of literature on facility location and site selection, (Francis et al,
1992, Owen and Daskin, 1998, ReVelle and Eiselt, 2006, Snyder, 2006) manufacturing
facility layout, (Kusiak and Heragu, 1987, Francis et al. 1992, Meller and Gau, 1996a,
Tompkins et al. 2003) warehouse design and operation (Rouwenhorst et al. 2000, Gu et
al. 2006), logistics (Chen and Paulraj, 2004) and material
handling network problems (Beamon, 1998, Tompkins et al., 2003) for manufacturing
facilities and warehouses. However, at the retailer?s tier, there is an apparent lack of
9
research especially in designing a layout. Although there are several studies regarding the
site selection problem (Eiselt et al., 1993, Drezner, 1994, Drezner 1995, Drezner 1998),
effects of the shopping environment (Kumar and Karande, 2000) and shelf space
allocation (reviewed thoroughly in Section 2.2), the problem of allocating the retail space
to the different departments (product groups) of the store and providing means for the
customers to access those departments have remained relatively untouched. Allocating an
adequate space to the departments and placing related departments close to each other
have substantial impact on the retailer?s profitability, as the former assures enough space
for products in a category (i.e. department) and the latter encourages ?impulse
purchases?. In the marketing literature, there are many different definitions of the term
impulse purchase, however, for the purposes of this research we can define impulse
purchases as purchases that are not planned beforehand (Kollat and Willet, 1967).
To the best of our knowledge, the only published work in the area of retail facility
layout design is by Peters et al. (2004). They investigate the effects of different layout
configurations on the expected travel distance between two points in a layout and the
expected tour length for a random shopping list. After addressing the importance of
impulse purchases in retail settings, they develop a model to determine the product
locations in a store which has a serpentine layout (e.g. customers entering the store travel
through a single aisle, which travels through all departments) so as to maximize the
expected revenue. Their model operates on a layout where the locations of the aisles and
the set of possible department locations are known. Therefore the Peters et al. (2004)
10
model is an assignment model and does not attempt to determine the exact dimensions
and locations of the departments.
Since the objective of this research is to formulate and solve the problem of block
layout for retail stores, the remainder of this section gives a brief review of the facility
layout literature. Although the objectives considered in retail store design are different
than those in manufacturing layouts, formulations and representations used in
manufacturing layouts provide valuable insights to the problem at hand.
2.1.1. The quadratic assignment problem (QAP)
The facility layout problem is formulated as a quadratic assignment problem by
Koopman and Beckman (1957). The QAP formulation assumes that the area and shape
requirements of the departments are identical and material handling costs between
departments are linear with respect to the amount of flow (f) and the distance between
departments (c). Under these assumptions, the QAP is formulated as follows:
????
=
ijkl
klijjlik
xxcfz Minimize (2.1)
s.t.
1=
?
n
i
ij
x , ?i; (2.)
1=
?
n
j
ij
x , ?j; (2.3)
{}1,0?
ij
x , ?i, j. (2.4)
11
where,
. department to department from flow ofunit a ofcost
, department to department from flow material
otherwise. 0
location toassigned is department if 1
ljc
kif
ji
x
jl
ik
ij
?
?
?
=
The QAP is an NP-complete problem; there is no known polynomial time
algorithm to solve it to optimality (Meller and Gau, 1996a). Misevicius (2005) reports
that problem instances with n > 30 are impractical to solve optimally. Hence, heuristic
procedures are extensively used in solving the QAP. Among those, tabu search (Skorin-
Kapov, 1990, Taillard, 1991 and Misevicius, 2005), simulated annealing (Kirkpatrick et
al., 1983) and genetic algorithms (Tate and Smith, 1995a) are to name a few. A
comprehensive survey on QAP formulations and solution approaches can be found in
Burkard et al. (1997). QAPLIB is a webpage that posts the most recent developments on
the QAP (Burkard et al., 2002). A recent survey by Loiola et al. (2007) reports that there
are nearly 400 articles on different formulations, exact, heuristic and metaheuristic
solution methods for the QAP.
2.1.2. Mixed integer nonlinear programming approach (MINLP)
The mixed integer model for solving the unequal area facility layout model is
introduced by Montreuil (1990) as follows:
( )
??
?+?=
ij
y
j
y
i
x
j
x
iijij
ddddcfz Minimize (2.5)
s.t.
12
()
u
iii
l
i
LxxL ??? '", ?i (2.6)
()
u
iii
l
i
WyyW ??? '" , ?i (2.7)
()()
iiiii
Ayyxx =?? '"'",?i (2.8)
xii
Bxx ??? "'0, ?i (2.9)
yii
Byy ??? "'0, ?i (2.10)
()
2
"'
ii
x
i
xx
d
+
= , ?i (2.11)
()
2
"'
iiy
i
yy
d
+
= , ?i (2.12)
( )
x
ijij
zMxx ?+? 1'" , ?i and j, i ? j (2.13)
( )
y
ijij
zMyy ?+? 1'" , ?i and j, i ? j (2.14)
1=+++
y
ji
y
ij
x
ji
x
ij
zzzz , ?i and j, i < j (2.15)
0, ?
y
i
x
i
dd , ?i (2.16)
0",',",' ?
iiii
yyxx , ?i (2.17)
integer 1/0,
y
ij
x
ij
zz ?i and j, i ? j (2.18)
where,
13
( )
()
()
facility. theof width andlength ,
, department of area
, department of width on the boundsupper andlower ,
, department oflength on the boundsupper andlower ,
otherwise. 0
, department above lies department if 1
otherwise. 0
, department ofleft the tolies department if 1
, department ofcorner northwest theof scoordinate ","
, department ofcorner southeast theof scoordinate ','
, department of centroid theof scoordinate ,
yx
i
u
i
l
i
u
i
l
i
y
ij
x
ij
ii
ii
y
i
x
i
BB
iA
iWW
iLL
ji
z
ji
z
iyx
iyx
idd
?
?
?
=
?
?
?
=
Montreuil?s model minimizes the total material flow cost subject to non-
overlapping constraints, area and shape constraints. In this formulation, department
shapes are to be rectangular, and the distance between departments is measured from
department centroids, using rectilinear distances. Meller et al. (1999) and Konak et al.
(2006) report that even for problems with a relatively small number of departments
(number of departments, n > 5) the MIP model is very difficult to solve to optimality due
to the binary variables involved. Further, the exact representation of area and shape
constraints requires the use of nonlinear terms which adds more complexity to the model.
Lastly, in order to solve the model above as a MIP formulation, the absolute value
function in the objective function has to be linearized at the expense of an addition of n(n
? 1) more variables. To overcome these difficulties, several improvements are made. For
instance, aspect ratio constraints are given as lower and upper bounds on edge lengths, as
in equations (2.6) and (2.7). Both Montreuil (1990) and Meller (1999) define surrogate
constraints for the area requirements, which fail to enforce the exact area requirements,
14
the latter being the tighter ones. Sherali et al. (2003) also attempt to reformulate the MIP
model, introducing valid inequalities, reducing problem symmetry, and reconsidering
disjunctive (no overlap of departments) constraints. As a result of these efforts, they
reach a substantial reduction in computation times and thus are able to solve problem
instances with up to nine departments optimally.
2.1.3. Slicing tree
The slicing tree representation is introduced to the facility layout literature by
Tam (1992). In a slicing tree, the leaves represent the departments, and the remaining
nodes belong to the slicing operators. Assuming area requirements are known for the
departments, guillotine cuts are performed, starting from the root node of the slicing tree
until all the cuts are completed. Tam (1992) defines four different slicing operators,
namely left, right, bottom and up. Although two operators (vertical and horizontal) seem
sufficient at first, Tam (1992) uses two operators to define vertical and horizontal cuts, to
ascertain the positioning of the departments with respect to the slicing operators. For
example, in Figure 2.1, the vertical cut ?right? places departments 1, 2 and 3 to the left of
the layout while the remaining departments stay on the right. Had the vertical cut
operator been ?left?, then departments 1, 2 and 3 would be on the right side of the layout,
while departments 4, 5 and 6 would be on the left.
15
R
LB
U1 U4
6532
1
4
5
6
2
3
Figure 2.1. A slicing tree (left) and the corresponding layout (right) (Tam, 1992).
In Tam?s approach, the structure of the slicing tree is determined beforehand
using a clustering technique and it is kept constant. The search is performed by switching
the cut operators. The aspect ratio constraints are added to the objective function as a
linear penalty term. The resultant model is solved using simulated annealing.
The main drawback of Tam?s work is that the sequence of the departments and
the structure of the slicing tree remains fixed throughout the search, leading to the
evaluation of only a small fraction of the solution space. Identifying this shortcoming,
Tam and Chan (1998) extended Tam?s work that allows modifications in both the tree
structure and the sequence of the departments, using parallel genetic algorithms. Wu and
Appleton (2002) also use the slicing tree representation to optimize both the layout and
the aisle structure of the facility by selecting the pick up/drop off locations and a subset
of guillotine cuts as the aisle network where department dimensions are given. Unlike
centroid to centroid rectilinear distances as in Tam (1992) and Tam and Chan (1998), Wu
and Appleton (1998) employ aisle distances in calculating material handling cost. The
total material handling cost penalized by accessibility requirement of the departments
serves as the fitness function of Wu and Appleton?s genetic algorithm.
16
2.1.4. Space filling curves
Space filling curves were introduced to the facility layout literature by Bozer et al.
(1994) in an attempt to extend Armour and Buffa?s CRAFT (1963) to multiple floor
facility layout problems (MULTIPLE). A space filling curve is a single continuous line,
which visits contiguous, equal area grids. Given the area requirements and the sequence
of the departments a layout is constructed assigning the grids to the departments
according to the sequence. For example, for a sequence 1-2-3-4-5 with area requirements
of 15, 10, 9, 7 and 9 respectively, the layout in Figure 2.2 can be constructed following
the curve depicted.
1111333355
1111333355
1112234455
1122224455
1122224445
Figure 2.2. Space filling curves (Adopted from Bozer et al. 1994).
Bozer et al. (1994) define a separate curve for each floor. Departmental areas are
constrained from above and below and given an initial layout; pair-wise exchanges in the
sequence of departments are used as the improvement method. Unlike CRAFT,
departments do not necessarily have to have the same size and/or be adjacent to be
exchanged in MULTIPLE. This gives MULTIPLE much more flexibility in pair-wise
exchanges, leading to a better search of the solution space. The pair-wise exchanges
continue in a greedy fashion, selecting the best improving pair-wise exchange among the
17
feasible set of pair-wise exchanges, until no improving exchange can be found.
Feasibility of an exchange is determined with regard to area requirements and the shape
constraints of the departments to be exchanged. Of course, this steepest-descent scheme?s
success highly depends on the initial layout and the choice of pair-wise exchanges. To
overcome this limitation in the later work of Meller and Bozer (1996), the space filling
curve is used in a simulated annealing algorithm (SABLE).
2.1.5. Flexible bay structure
The flexible bay structure (FLEXBAY) representation was introduced by Tong
(1991). In FLEXBAY, the allocation of departments is done by allowing guillotine cuts
in one direction to obtain bays, and perpendicular cuts within bays to obtain departments.
Although it is more restrictive than the slicing tree representation, the bay structure easily
lends itself to aisling, hence the FLEXBAY representation is extensively used in the
unequal area facility layout literature (Tate and Smith, 1995, Arapoglu et al., 2001,
Alagoz et al, 2002, Kulturel-Konak, 2002, Kulturel-Konak et al., 2004). A 13-department
example organized in four vertical bays is represented in Figure 2.3.
G
A
F
H
B
E
C
D
J
I
K
L
M
Figure 2.3. FLEXBAY representation.
18
Most of the previous work employing the FLEXBAY structure uses heuristic
methods in solving the problem. Tate and Smith (1995) and Arapoglu et al. (2001) use
GA, Kulturel-Konak (2002) and Kulturel-Konak et al. (2004) use TS. In a later paper,
Konak et al. (2006) provide a mathematical programming formulation. With the
enhancements of the formulation proposed in the paper, the mathematical programming
approach is able to improve upon best known solutions of well-known test problems from
the literature.
2.1.6. Graph theoretic approaches
Application of graph theoretic approaches to the facility layout problem dates
back to the 1960s (Tompkins et al.). In the graph theoretic approach, a graph G(V, E),
whose vertices, V, representing departments and edges, E, representing adjacencies, is
assumed. G is said to be planar if no edge crosses any other edge. G has a corresponding
layout only if it is planar. If there is an edge connecting two departments (nodes) in G,
then those departments in the corresponding layout are adjacent (In Figure 2.4, node 9
denotes the exterior of the facility). G and the corresponding layout are duals of each
other, since given one, the other can be easily obtained.
1
4
7
2
9
5
8
3
6
1
5
6
4
3
2
78
Figure 2.4. A planar graph (left) and the corresponding layout (right).
19
The weights of the edges represent the desirability of adjacency among
departments and can be determined by Muther?s Systematic Layout Planning (SLP)
procedure (Muther, 1973). In order to quantify closeness requirements, the rating scheme
provided in Table 2.1. is used in SLP. These ratings are then converted into numerical
values and used as edge weights, generally using an exponential scale (Askin and
Standridge, 1993).
Table 2.1. Closeness ratings.
Value Closeness
A Absolutely Necessary
E Especially Important
I Important
O Ordinary
U Unimportant
X Not Desirable
After edge weights are determined, the problem reduces to finding the set of those
edges to maximize the summation of closeness ratings subject to the planarity constraint.
This problem is called the weighted maximal planar graph (WMPG) problem and is NP
hard (Osman, 2006). To solve the WMPG problem, branch and bound (B&B) procedures,
B&B with Lagrangean relaxation, LP based formulations and metaheuristics such as TS,
SA, and GRASP have been proposed in the literature.
There are other methods that use closeness ratings in the optimization of the
layout like ALDEP (Automated Layout Design Program) (Seehof and Evans, 1967)
which uses an idea similar to space filling curves and CORELAP (Computerized
20
Relationship Layout Planning, Lee and Moore, 1967) which attempts to maximize a
closeness rating within the facility subject to dimension constraints.
2.1.7. Multiple objectives
The facility layout problem?s ultimate objective is to find the most efficient
arrangement of the departments. However, as the survey so far suggests, it is not an easy
task. There is not a single model, objective function or a particular approach agreed upon
or proven superior to the remaining models and approaches. Even worse, the definition of
?efficient arrangement of the departments? changes from approach to approach, some
researchers define the efficiency by a material handling point of view, while others define
it as the degree of the adjacency satisfaction achieved by a layout. Solution
representations, constraint sets and objective functions, are all tailored to the specifics of
the problem at hand. Thus, while creating a rich body of literature, there are numerous
disagreements and differences among alternative formulations. Addressing this deficit,
Rosenblatt (1979) proposed the first known multiple objective model for the facility
layout problem, using an objective function which is a combination of material handling
cost and total closeness rating in a QAP. The solution procedure is a heuristic one, based
on altering the weights associated with the two objectives, thus obtaining a set of
alternative layouts. Dutta and Sahu (1982) also use the formulation of Rosenblatt, with a
different heuristic. Meller and Gau (1996b) define a robust layout as one providing the
minimal deviation from the different objective functions? absolute optimal and present an
algorithm based on Tam?s SA (1992) to identify those solutions. Kulturel-Konak et al.
21
(2002) consider both material handling cost and the cost of relayout in their paper
addressing the problem of facility expansion and relayout.
2.1.8. Controlling department shapes
In facility layout, shape of the departments obtained is one of the characteristics
that determines the quality of the overall layout. Usability of the area depends on the final
shape of the departments. Rectangular departments that are too narrow and/or
departments with non-rectangular shapes can be difficult to utilize. Bozer et al. (1994)
claim the best shape for a department is square, which is not far from reality. Satisfaction
of shape requirements are either included in the constraint set or are incorporated into the
objective function in the form of a penalty term. There are three widely used shape
constraints.
The first is, upper and lower bounds on width and height (Montreuil, 1990): In
Montreuil?s MIP formulation, the shapes of the departments are controlled by upper and
lower bounds on the lengths of the widths of the rectangular departments (Tompkins et
al. 2003).
Second, if the departments are rectangular, then the upper and lower bounds on
the length and width of the departments can also be formulated by defining an aspect
ratio, ?, as follows: ( ) ( )wlwl ,min,max=? where l is the length and w is the width of a
department.
The last one of the aspect ratio constraints is the most generalized version.
Assuming that the ideal shape of a department is square, the aspect ratio constraint is
22
given by AP 4=? where P is the perimeter and A is the area of the department (Bozer
et al., 1994). This formulation does not require departments to be rectangles and it is
more sensitive to the irregularities in the shape of a department than other aspect ratios
developed for non-rectangular department shapes (Bozer et al., 1994).
The aspect ratio given by ( ) ( )wlwl ,min,max=? increases more than the aspect
ratio given by AP 4=? as the length/width ratio of the department increases provided
that the enclosed area is constant. For instance, for a department with an area of four
square units both aspect ratios evaluate to the value of one if the shape of the department
is square. However, when the length of the department is increased to four units, the
aspect ratio is calculated as ( ) ( ) 41/4,min,max === wlwl? with the first formulation,
while the second formulation yields 25.144/104 === AP? .
2.2. Retail Space Allocation Models
Space allocation models for retail stores have almost exclusively pertained to
shelf space allocation (SSA). The most important difference between the model presented
in Chapter III and shelf space allocation models is that in shelf space allocation the
decision variables are in one dimension only (i.e. the length of shelf space allocated to a
product). However, the studies in shelf space allocation can still provide insights for the
problem at hand as they are the dominant models specifically developed for the retail
store design problem.
23
2.2.1. Related studies
The most cited work in SSA is by Corstjens and Doyle (1981). Their model
considers profit margins, space elasticities of the items, and the cross elasticities among
products on the revenue side, and procurement, carrying costs and out-of-stock costs on
the operating side. The resultant model is as follows:
? ?? ?
=
?
==
?
=
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
K
i
K
ij
j
jiii
K
i
K
ij
j
jiii
iij
iii
ij
i
ssssw
1 11 1
max
??
???
?
?
??? (2.19)
s.t.
*
1
Ss
K
i
i
?
?
=
(2.0)
KiQss
i
K
ij
j
jii
ij
i
,...,1
*
1
=?
?
?
=
?
?
? (2.1)
Kisss
U
ii
L
i
,...,1=?? (2.2)
Kis
i
,...,10 =? (2.3)
where
w
i
Selling price of product i
?
?
=
=
K
ij
j
jiii
ij
i
ssq
1
?
?
?
Demand for product i
i
?
Space elasticity for product i
s
i
Shelf space allocated to product i
24
ij
?
Cross elasticity between product i and product j
i
?
Demand multiplier for product i
i
?
Aggregate cost of product i
i
?
Operating cost elasticity of product i (Economies of scale)
*
S Available shelf space
*
i
Q Production availability limit for product i
U
i
L
i
ss , Lower and upper bounds on shelf space for product i
The most important drawback of the model above is that in its original form, it
does not allow selecting a set of products from a larger pool of products. That is, the
product mix needs to be determined beforehand. However, the model has proved to
produce superior results compared to commercial optimization models available at the
time of study. In another study, it is reported that this kind of optimization package is
only used for designing the shelves (i.e. to obtain the planograms) and nothing more is
expected by category and/or store managers from such software (Xavier et al., 1994).
Another important result mentioned by Corstjens and Doyle (1981) is that the cross
effects have a significant impact on maximizing the expected profit. In essence, the
introduction of cross elasticities is what makes the model perform better than competing
methods.
Yang (2001) transforms Corstjens and Doyle?s model into a multi-constraint
knapsack formulation by removing the elasticity terms, and introducing integer decision
25
variables to represent the number of facings (facings represent how many of the products
should be facing straight out toward the customer) that each product has on the shelves.
With these modifications the model becomes
??
==
=
n
i
m
k
ikik
xpP
11
max (2.4)
st
,,...,1,
1
mkTxa
k
n
i
iki
=?
?
=
(2.5)
,,...,1,
1
niUxL
m
k
iiki
=??
?
=
(2.6)
.,...,1,,...,1integerand0 mknix
ik
==?
p
ik
Unit profit of product i allocated to shelf k
x
ik
Amount of product i allocated to shelf k
a
i
Unit face length of product i
T
k
Capacity of shelf k
L
i
, U
i
Lower and upper bounds on number of facings for product i
Yang proposes a heuristic for the solution of the problem since the knapsack
problem is known to be NP hard (Yang, 2001). Yang?s heuristic first arranges the
products in descending order according to their (p
ik
/a
i
) ratio and then assigns the
minimum allowable number of facings to the shelves. In the second pass, excess shelf
capacity is assigned to the products from the ordered set of products. The heuristic is
shown to obtain solutions within 98% of the optimal solutions obtained by complete
enumeration at one third of the time required by enumeration. However, Yang?s problem
26
formulation does not take into account the most important component of Corstjens and
Doyle?s model, which is the cross elasticities among the products.
Another extension to Corstjens and Doyle?s model is by Bookbinder and Feyrouz
(2001). Instead of using sale price and aggregate cost of the product, they introduced the
direct product profitability (DPP) which reflects the true contribution of products to the
profitability. DPP is calculated considering any deals, promotions or discounts
attributable to a particular product as well as distribution costs (warehousing,
transportation, etc.) traceable to the individual item (Bookbinder and Feyrouz, 2001).
In another study, Cachon and Kok (2006) approach the problem from a different
point of view: instead of considering the products? profit margins individually, they
introduce the term ?shopping basket?. The shopping basket defines the set of goods that
the consumer wants to buy in a single trip to a store. According to Cachon and Kok, if a
consumer cannot fulfill his or her shopping basket in a particular store, that store would
not be considered in subsequent shopping trips. Thus, some products have to be offered
to the consumer by the retailer even if their profit margins are smaller than other
products. However, many retail stores employ a policy called category management
which allows the store to decide the product assortment of each department independent
of the remaining departments. Hence, Cachon and Kok proposed a model and a solution
approach which measure the profits over the shopping basket leading to higher expected
profits for the retailer than the category management approach.
Hwang et al. (2005) consider the SSA problem in conjunction with the inventory
control problem. Their model also takes into account the location of the shelves as it is
27
proved to be an important factor in a product?s demand. In the model, shelves have
assigned weights to represent the effect of shelf location on demand. On the procurement
side, the model explicitly considers purchasing costs, inventory holding costs, display
costs and ordering costs. The objective function is very similar to that of Corstjens and
Doyle?s (1981), with two more sets of decision variables (
?
=
j
iji
xx where x
i
is the total
number of facings that product i has on display and x
ij
is the number of facings that
product i has on shelf j and Q
i
is the order quantity for product i).
Yang and Chen (1999) modify the demand function of Corstjens and Doyle?s
model by changing the continuous variable s
i
(shelf space allocated to product i) to the
number of facings,
x
i
. They solve the shelf space allocation model in three stages: first,
available shelf space is allocated to departments, then the shelf space allocated to a
department is partitioned into different categories of the department, and finally, shelf
spaces allocated to categories are further divided among individual items. Thus, the
problem becomes easier to solve, and the solution obtained by this method is only 1%
worse than the optimal solution of the problem and the method is about 7,500 times faster
than the optimal solution procedure for an 8,000 item problem (Yang and Chen, 1999).
Urban (1998) approaches the SSA from an inventory theoretic point of view. He
points out that even if most of the models proposed formulate demand as a function of the
allocated shelf space, they do not take into account the impact of the depletion of items
on shelves. He proposes a different demand formulation that considers backroom
inventory and inventory on the shelf. Based on this demand formulation and using selling
28
price, and procurement costs, inventory holding costs and display costs he develops a
mixed integer nonlinear model. As a solution method, he uses a generalized reduced
gradient (GRG) method. In order to determine the optimal product assortment, the model
is solved by using GRG and all products available to the retailer, then the product with
smallest contribution to the overall profit is removed and model is re-solved with the
remaining assortment. This solution process continues until there is no improvement in
the total profit figure.
Mart?n-Herr?n and Taboubi (2003) use game theory to formulate the problem of
SSA. In their formulation there are two competing brands and a retailer who decides the
amount of shelf space allocated to each brand. Their results suggest that shelf-space
allocation is affected by retail margins and goodwill levels of the competing brands (i.e.
the brand image which is controlled by advertising decisions), and that the most shelf
space is given to the brand with the highest retail margin and the highest brand image.
Irion et al. (2004) consider the shelf space allocation problem on a smaller scale,
i.e. at the category level. The profit formulation includes direct product costs, restocking
costs, replenishment costs and the cost of including a product in the assortment. With the
introduction of cross elasticities among products, the model becomes a mixed integer
nonlinear optimization model. Instead of solving the original model by heuristic
approaches, the authors transformed the model into an approximating mixed integer
problem (MIP) formulation by using a piecewise linearization technique. The authors
conclude that the MIP formulation does not provide the optimal solution but they assert
29
that it is computationally efficient and can be used in real world problems involving
thousands of products.
2.2.2. Analysis and discussion
From the literature survey, it can be concluded that the two most important
considerations in shelf space allocation are the amount of space allocated to departments,
to categories and to individual products, and the cross effects among departments,
categories and/or products. It is widely accepted that an increase in demand is not directly
proportional to an increase in shelf space however Yang (2001) suggests that a linear
relationship can be assumed within the upper and lower bounds on shelf space;
U
i
L
i
ss ,.
Yang and Chen (1999) also claim it is common practice in retail store planning for space
allocation and assortment decisions to be made at different levels (e.g. decide
departments to include and allocate space, and then choose categories and allocate
department space to categories, and lastly choose products in a category).
Similar to the shelf space allocation models, the model proposed in this
dissertation uses diminishing returns in revenue with respect to area. However, the model
formulation provided in Chapter III does not include the mathematical formulation of this
relationship. In Chapters IV and V, it is assumed that the area requirements of the
departments are known and constant. Then, in Chapter VI, we introduce revenue
formulations considering diminishing returns with respect to area. The model implicitly
assumes that the department mix is known (i.e. the lower bounds on all departments? area
requirements are greater than zero). The cross elasticities among departments are not
30
considered explicitly but are used implicitly through the REL score evaluation included
in the objective function.
2.3. Tabu Search
Tabu Search (TS) was introduced to the combinatorial optimization literature by
Fred Glover (Glover 1986, Glover 1988, Glover 1989, Glover and Laguna 1997, Reeves
1995). The word ?tabu? or ?taboo? comes from the Polynesian language Tongan, where
it refers to things that are not to be touched (Glover, 1998). As the name suggests, the
procedure is mainly based on ?prohibiting? or disallowing certain moves in a systematic
way ensuring that recently visited solutions cannot be reached again (cycling avoidance).
Avoiding cycling in this manner gives the TS the ability of more comprehensive search
of the solution space, without getting trapped in local optima. TS has successful
implementations in many combinatorial, NP-hard optimization problems including
quadratic assignment (Taillard, 1991), unequal area facility layout (Kulturel-Konal et. al,
2004), vehicle routing (Taillard et. al, 1997), redundancy allocation (Kulturel-Konak et.
al, 2003) job shop scheduling (Barnes and Chambers, 1995), and weighted maximal
planar graphs (Osman, 2006).
Glover (1995) suggests that in order for a search method to be classified as
intelligent, it needs to have two properties: adaptive memory and responsive exploration.
The adaptive memory concept is that the choices made during the search need to rely on
the information collected. The use of past experience to direct the search is the most
important distinction of TS from other evolutionary computation techniques. During the
31
course of a TS, sometimes a move that worsens the objective function value is accepted
as a part of the search strategy, which can yield more information than a ?lucky? random
choice that leads to a better solution. Intentional selection of worsening moves to gain
better understanding of the fitness landscape is referred to as ?responsive exploration?
(Glover, 1995).
The memory is the most distinctive feature of the TS. Glover and Laguna (1997)
define the four dimensions of TS memory as recency, frequency, quality and influence.
Recency defines the recent search trajectory, and it is the main element in cycling
prevention. Frequency provides a more general look at the overall search history and is
mostly used for the diversification; it also referred to as long term memory. Quality refers
to the ability of judging how good a solution compared to the incumbent and is generally
applied in the form of aspiration criteria. Influence can be thought of as another
aspiration criterion as it helps to evaluate/compare candidate solutions based on other
qualities, such as how different two solutions in structure are from each other (Glover,
1995).
In TS, memory may be implemented as explicit and/or attributive (Glover and
Laguna, 1997). When using explicit memory, complete solutions are stored, and this is
generally used to keep a set of elite solutions for the long term memory. The attributive
memory stores the information about solution attributes that changed in moving from one
solution to another, and is used for short term memory.
For an optimization problem min f(x) subject to Xx? , and XxN ?)( the TS
procedure is given as follows:
32
Procedure Tabu Search {
Find an initial solution Xx ?
0
, set
0
xxx
bestcurrent
== , and initialize memory;
Intensification Phase
While (termination condition is not met) {
Genrate )(
current
xN ;
Choose the best )(
currentnew
xNx ? such that
new
x is not tabu or
satisfies aspiration criterion;
Move from
current
x to
new
x , i.e. set
newcurrent
xx = ;
If
current
x is better than
best
x , then set
currentbest
xx = ;
Update recency based memory (tabu classifications), frequency
based memory and/or critical event memory (elite solutions);
} End While
} End Intensification Phase
Diversification Phase {
If termination condition is satisfied, then stop
Using frequency based memory and/or critical event memory, find a new
starting point
current
x , return to intensification phase
} End Diversification Phase
} End Procedure
Here, X represents the solution space, f(x) is the function to be optimized, and
N(x) is the neighborhood of solution x. After an initial solution is obtained, intensification
follows. During intensification, the neighborhood of
current
x is constructed. The
neighborhood of a solution, N(x), is defined as the subset of the search space, X, that can
be obtained by a single move operator applied to x. The size of the neighborhood depends
on the solution representation and the definition of the move operator. Once the
neighborhood is generated, the best solution within the neighborhood that is reached by a
non-tabu move (the one providing the most improvement on the objective function or in
the case of all non-improving neighbors, the one that least worsens the objective
function) is set as
current
x . If there exists a solution within the neighborhood with a better
fitness (objective function) value than
best
x , the move to that solution is accepted even if
33
the move is tabu. This mechanism favoring better solutions at the expense of a breaking
tabu status of a move is called aspiration criteria. After
current
x is updated, the short and
the long term memory are updated. The update of short term memory involves invoking
tabu status for the most recent move and revoking the tabu status of the oldest move in
the tabu list. The update of memory completes an iteration of the intensification phase.
The termination condition for the intensification phase is generally either the completion
of a fixed number of iterations or a number of iterations without improvement to the best
known solution (Gendreau and Potvin, 2005).
The diversification phase is invoked when
best
x ?s objective function value has not
been improved for a certain number of consecutive cycles in the intensification phase.
The long term memory helps to identify poorly investigated as well as promising regions
of the solution space and directs
current
x to those regions. Once a new solution is initiated,
another cycle of the intensification phase begins.
34
III. RETAIL SPACE ALLOCATION PROBLEM
In the retail world, most companies use one of three layout types: the grid, the
free form and the racetrack (Levy and Weitz, 2001). Each of these has their advantages
and disadvantages, as discussed in subsequent sections.
A grid layout is mostly preferred by groceries and drugstores. It provides the most
efficient use of space by minimizing the area allocated to the aisles, however; it fails to
create an enjoyable shopping environment (Levy and Weitz, 2001). The grid layout is
especially advantageous for consumers who buy many products of different kinds during
one shopping trip. An example grid layout is given in Figure 3.1.
Receiving & Storage
Fruits Vegetables
Of
fi
ce
&
Cu
sto
m
er
Se
r
v
i
c
e
C
h
e
c
kout
s
Entrance & Exit
Of
fi
ce
&
Cu
sto
m
er
Se
r
v
i
c
e
C
h
e
c
kout
s
Figure 3.1. The grid layout.
35
Since the bulk of the display and storage is achieved through multi-story shelves,
the layout problem of the grid can be approximated by the shelf space allocation problem.
The details of the shelf space allocation problem were given in Section 2.2.
A free form layout is generally adopted by retailers working with high profit
margins like specialty stores or within the departments of large stores (Levy and Weitz,
2001). The most important feature of free form layout is a pleasant shopping atmosphere,
created by sparse arrangement of the merchandise. Thus, the free form allows customers
to browse and spend more time within the store, promoting impulse purchases. The
inefficient allocation of space to the merchandise is accommodated by high profit
margins and revenue from impulse purchases. Figure 3.2 illustrates a typical layout
designed according to the free form.
R
ece
iv
in
g &
St
ora
g
e
D
r
ess
i
ng
R
oom
s
En
t
r
an
c
e
& E
x
it
D
i
s
p
lay
W
i
nd
ow
Di
spl
a
y
W
i
n
dow
Jeans Casual Wear
Un
de
r
w
ea
r
Dresses Handbags
Checkout
Counter
Feature
Feature
Pants
Tops
Accessories
Tops
R
ece
iv
in
g &
St
ora
g
e
D
r
ess
i
ng
R
oom
s
En
t
r
an
c
e
& E
x
it
D
i
s
p
lay
W
i
nd
ow
Di
spl
a
y
W
i
n
dow
Un
de
r
w
ea
r
Figure 3.2. The free form layout.
The racetrack layout was not a new idea when it was popularized in the late
1980?s by Kohl?s department stores. However, steady growth of Kohl?s department stores
36
throughout the 1990?s is attributed to its racetrack layout as well as careful planning of
the product assortment (Scardino, 2003). In the 1990?s, Kohl?s department stores
increased sales by 23% annually making Kohl's the only brick-and-mortar retailer on the
list of the 25 fastest growing big companies of Forbes magazine (Tatge, 2004).
Entrance & Exit Entrance & Exit
Inf
a
nt
To
ddl
er
Ch
ild
ren
Ma
ter
n
i
t
y
Me
n
Wo
me
n
Coo
k
ware
Beddi
n
g
Hom
e
Paint
Electronics Toys
A
p
p
lia
n
c
es
Auto Care
La
w
n
&
Ga
r
d
e
n
Jewelry
Books
Checkout Checkout
C
h
ec
ko
ut
Misses
Health& Beauty
Inf
a
nt
To
ddl
er
Ch
ild
ren
Ma
ter
n
i
t
y
Me
n
Wo
me
n
Coo
k
ware
Beddi
n
g
Hom
e
Paint
A
p
p
lia
n
c
es
Auto Care
La
w
n
&
Ga
r
d
e
n
Books
C
h
ec
ko
ut
Misses
Figure 3.3. Racetrack layout.
The main advantage the racetrack provides is that it allows shoppers to move past
all of a store's merchandise in an easy and flowing manner. Larry Montgomery, the CEO
of Kohl?s, believed that customers could spend less time in his stores but still buy more
items when products were arranged in a simple and logical manner in an environment
that was attractive to the eye (http://www.answers.com/topic/larry-montgomery). His
claim was strengthened when the racetrack layout was also employed in other department
store chains including JC Penney (Black, 2003) and Kmart (Lewison and Balderson,
1999).
37
Although the racetrack layout is quite popular in the retailing sector, mathematical
modeling of this type of layout has lagged. In the next section, a model addressing the
retail store layout problem with a racetrack aisle structure is presented.
3.1. Nomenclature
n: Number of departments.
A: Area of the store (constant).
i, j: Department indexes; i = 1,2,? n; j = 1,2,? n.
k: Zone index, k = 1, 2, ?, K (A zone is a subsection of the store defined with
respect to the racetrack, as explained in section 3.3)
i
R: Revenue generated by department i.
i
R : Upper bound on the revenue generated by department i.
i
A: Area allocated to department i.
I
A : Available area inside the racetrack.
O
A : Available area outside the racetrack.
a
A: Area allocated to the aisles.
ij
c : Desirability of adjacency of department i to department j, i ? j.
i
? : Aspect ratio of department i.
i
? : Maximum aspect ratio of department i.
?
?
?
=
otherwise.,0
,departmenttoadjacentisdepartmentif,1 ji
x
ij
38
density fic with trafassociated zone of Ranking : kz
k
, k?
purchase impulse with associated department of Ranking : id
i
, i?
?
?
?
=
otherwise ,0
zonein is department if ,1 ki
y
ik
, ki,?
?
?
?
?
?
=
k
k
k
z
k
zonefor low isdensity trafficIf,3
zonefor moderate isdensity trafficIf,2
zonefor highest theisdensity trafficIf,1
?
?
?
?
?
=
i
i
i
d
i
departmentfor importance low of are purchases impulse If,3
departmentfor importance moderate of are purchases impulse If,2
departmentfor importancehigh of are purchases impulse If,1
3.2. Model
The model presented below assumes the department mix (i.e. departments to be
included within the store) is known. Another input associated with the departments is the
adjacency requirements among departments. The objective function and the constraints of
the model are given in sections 3.2.1 and 3.2.2. respectively.
3.2.1. Objective function
max Z = ?R (3.1)
?
=
=
n
i
i
RR
1
where (3.2)
()[]
?
=
?+
=
K
k
ikik
i
i
dzy
R
R
1
,0max1
,i? (3.3)
39
() ()
????
????
=>
?
=>
+
=>
?
=>
+
?
??
==
n
i
n
ij
ij
n
i
n
ij
ij
n
i
n
ij
ijij
n
i
n
ij
ijij
p
cc
xcxc
REL
REL
11
11
*
1
? (3.4)
where
?
ij
c represents a negative REL score.
3.2.2. Constraints
*
4
i
i
i
A
P
?? ,i? (3.5)
i
L
i
AA ?
,i? (3.6)
a
L
a
AA ?
(3.7)
AAA
a
n
i
i
=+
?
=1
(3.8)
O
i
n
i
i
AyA =
?
=1
(3.9)
()
I
i
n
i
i
AyA =?
?
=
1
1
(3.10)
UaL
www ?? (3.1)
?
?
?
=
otherwise ,0
department oadjacent t is department if ,1 ji
x
ij
jiji >? ;,
?
?
?
=
otherwise ,0
rimouter in the is department if ,1 i
y
i
,i?
Constraints (3.5) impose the aspect ratio requirements for each department.
Constraints (3.6) and (3.7) ensure that the areas allocated to the departments and to the
aisles are larger than the lower bounds. At first, it will be assumed that the area
40
requirements for the departments are constant and the aisle area is zero. However, to
make the definition of the model complete, this set of constraints is also included in the
model declaration. Constraint (3.8) ensures that the total department and aisle area cannot
exceed the area of the store. Constraints (3.9) and (3.10) ensure that the area allocated to
the departments to the outer rim and to the inner region do not exceed the area available
to the outer rim and the inner region, respectively. Lastly, constraint (3.11) guarantees
that the width of the aisle is within the pre-specified limits.
Another constraint, which is not expressed mathematically, is that the layout has
to have a racetrack aisle that divides the total area into two partitions. One of the
partitions lies outside the aisle but inside the boundaries of the store, whereas the second
partition is inside the rectangular aisle area and also has a rectangular shape. The
enforcement of this constraint is achieved by the solution representation and decoding
mechanisms, explained in Chapter V.
Finally, the store entrance will be placed on the midpoint of the lower horizontal
edge of the facility.
3.3. Description of the Objective Function
In the model presented in Section 3.2, revenue generated by the departments is
represented as a function of three sets of variables:
? The area allocated to departments and the aisle,
? Location of the department within the store, and,
? Percent REL score achieved by the layout (discussed in detail below).
41
The sales of a store broadly fall into two categories: planned purchases and unplanned
purchases. Planned purchases constitute the portion of the sales that the customers come
to shop with the intention of buying. Impulse purchases on the other hand, can be defined
as those purchases that are not planned before the shopping event occurs (Kollat and
Willet, 1967). Decisions leading to these unplanned purchases are made within the store,
and are affected by in-store stimuli (Inman et al., 2007). The notion of impulse purchase
has been studied from various perspectives including descriptive studies (Bellenger et al.,
1978), effects of space allocation, promotion, price and advertising (Wilkinson et al,
1982), customer characteristics and customer activities (Kollat and Willet, 1967 and
Inman et al., 2007) and the effects of product display and environmental variables (Fiore
et al. 2000). The marketing literature suggests that different lines of products have
different impulse purchase rates. For example, Bellenger et al. (1978) found that the
percentage of impulse purchases are 27% for women?s lingerie and 62% for costume
jewelry. Hence, by placing the departments with higher impulse purchase rates in high
customer traffic zones of the store, it is possible to increase sales revenue.
The customer traffic within a store is another issue investigated by marketing
researchers. Traffic density within a retail store can be defined as the number of visits to
a certain zone of the store by customers. The customer traffic density throughout the store
is not uniform; certain zones of a store have denser traffic than others. Empirical studies
(Larson et al., 2005), stochastic models (Farley and Ring, 1966) and agent-based
modeling applications (Batty, 2003) support this fact.
42
Zone 2
Zone 3
Zone 1
Zone 2
Figure 3.4. Partition of the store area into zones with respect to traffic density.
Considering these two facts of retail settings, we define two sets of ratings, one
for the zones of the store area denoted by z, with respect to traffic density, the other is for
the departments denoted by d, with respect to the likelihood of impulse purchases. Under
these classifications, the store area is divided into three zones, namely, high traffic zones
(z
k
= 1), medium traffic zones (z
k
= 2) and low traffic zones (z
k
= 3). An example
partitioning of the retail space is depicted in Figure 3.4. By the same manner,
departments are grouped into three classes, high impulse purchase departments (d
i
= 1),
medium impulse purchase departments (d
i
= 2) and low impulse purchase departments (d
i
= 3). The number of different zones and the number of department classes can be
increased if more precision is desired and supported. Note that all the numbers used in the
definitions of
ik
dz and are ordinal numbers. They are ranking only; no scale is implied.
These rankings then can be used to measure the deviation of the departments? actual
location from their advantageous location which is formulated as ( )
ik
dz ? . If department
i would benefit from a high traffic zone ( )1=
i
d and is placed in a low traffic zone
()3=
k
z , the deviation would be positive, which indicates a missed revenue opportunity.
43
On the other hand, if department i would not benefit from a high traffic zone ()3=
i
d and
is placed in a high traffic zone ( )1=
k
z , the deviation would be negative. Situating such a
department in a high traffic zone would not be a missed revenue opportunity. Thus, for
department i, the deviation from its desired location can be measured by
()
ik
dz ?,0max .
The expected revenue generated by a department depends on two factors: the area
of the department and the department?s location in the store. As the area of a department
increases, the revenue generated by the department increases as well. In equation (3.3),
i
R represents the expected revenue given the area allocated to a department. It is defined
as the upper bound on revenue generated by department i since the actual revenue
generated by a department also depends on its location within the store. The
mathematical representation of diminishing returns is discussed in detail in Chapter VI.
For the sake of simplicity, we assume that the areas of the departments and hence
i
R are
constant in Chapters IV and V.
3.4. Handling the REL Scores
In this model, the REL scores that are used are provided in Table 3.
Corresponding closeness ratings, denoted by c
ij
in Table 3.1, are determined using an
exponential scale, as suggested by Askin and Standridge (1993).
44
Table 3.1. REL ratings and corresponding scores.
Rating Definition c
ij
A Absolutely Necessary 125
E Especially Important 25
I Important 5
O,U Ordinary Closeness 1
X Undesirable -25
XX Prohibited -125
Table 3.1 summarizes the scores assigned to each rating. By using the values from
Table 3.1 and the procedure defined below, the efficiency, ?, of the given layout, p, is
calculated.
Step 1: Calculate REL
*
as the maximum possible REL score:
????
?
=+=
?
?
=+=
+
?=
1
11
1
11
*
n
i
n
ij
ij
n
i
n
ij
ij
ccREL (3.12)
The formula above assumes an ideal layout from the adjacency point of view. If
all departments need to be adjacent (remote) are adjacent (remote) then the layout can
achieve REL
*
(absolute efficiency).
Step 2: Then, for the given layout p, calculate the REL score
() ()
????
?
=+=
?
?
=+=
+
??=
1
11
1
11
1
n
i
n
ij
ijij
n
i
n
ij
ijij
p
xcxcREL (3.13)
Step 3: The efficiency, ?, of the layout p then becomes
*
REL
REL
p
=?
(3.14)
45
IV. MIXED INTEGER PROGRAMMING FORMULATION OF THE
RACETRACK LAYOUT
In this chapter, a mixed integer formulation of the problem is presented. The MIP
formulation of the racetrack layout is adapted from the MIP formulation of Montreuil?s
(Montreuil, 1990) given in Section 2.1.2. In order to preserve the linearity in the
constraints, auxiliary variables are introduced. The chapter starts with the definition of
the variables used in the model, followed by a pictorial representation of the variables.
Next, the model is introduced and computational performance of the model is examined.
CPLEX 9.1 is used to solve the MIP model.
4.1. Nomenclature
ik
R Revenue of department
i when located in zone k
()','
ii
yx Southwest corner coordinates of department i
()","
ii
yx Northeast corner coordinates of department i
( )','
yx
RR Southwest corner coordinates of the racetrack
( )","
yx
RR Northeast corner coordinates of the racetrack
( )
yx
BB , Northeast corner of the facility
u
i
l
i
LL ,
Lower and upper bounds on the length of department i along the x axis
46
u
i
l
i
WW ,
Lower and upper bounds on the width of department i along the y axis
u
i
l
i
PP ,
Lower and upper bounds on the perimeter of department i
M Sufficiently big, positive number.
,,,,
?+?+
ikikikik
yyxx
Nonnegative variables used for absolute value conversion
?
?
?
=
otherwise 0,
axis thealongracetrack theinside is department if ,1 xi
I
x
i
i?
?
?
?
=
otherwise 0,
axis thealongracetrack theinside is department if ,1 yi
I
y
i
i?
?
?
?
=
racetrack theofeast the tois department if 0,
racetrack theof west the tois department if ,1
i
i
R
x
i
i?
?
?
?
=
racetrack theofnorth the tois department if 0,
racetrack theofsouth the tois department if ,1
i
i
R
y
i
i?
?
?
?
=
otherwise. 0,
department of west the tois department if,1 ij
Z
x
ij
.;, jiji ??
?
?
?
=
otherwise. 0,
department ofsouth the tois department if,1 ij
Z
y
ij
.;, jiji ??
?
?
?
=
otherwise 1,
axis on theracetrack with thecongruent edgean has department if ,0 xi
Q
y
ik
.4,3,2,1;,...,2,1;, ==? kniki
?
?
?
=
otherwise 1,
axis on theracetrack with thecongruent edgean has department if ,0 yi
Q
x
ik
.4,3,2,1;,...,2,1;, ==? kniki
47
In this model, the length of the department refers to the dimension of the
department along the x axis and the width of the department refers to the dimension of the
department along the y axis.
4.2. Pictorial Representation of the Model Variables
In this MIP model, the store area is partitioned into three distinct zones with
respect to customer traffic density. Similar to the model formulation in Chapter III,
departments have different impulse purchase likelihoods. Departments with high impulse
purchase chances are best located along the portion of the racetrack where the traffic
density is high. To measure in which zone a department is located, two sets of binary
variables
x
ik
Q and
y
ik
Q (i = 1, 2, ? n; k = 1, 2, 3, 4) are used.
To better understand the formulation above, refer to Figure 4.1. Since department
i lies within the racetrack and its upper left corner?s y coordinate is equal to the
racetrack?s upper left corner?s y coordinate ( ""
yi
Ry = ), it can be verified mathematically
that department i has exposure to the racetrack along the x axis from within the racetrack.
That is, 1
2
=
x
i
Q where k = 2 while 0=
x
ik
Q for k = 1, 3, 4 and 0 =
y
ik
Q for k = 1, 2, 3, 4
since department i's exposure to the racetrack only occurs on the northern horizontal part
of the racetrack from the inside.
48
Q
i2
x
Dept i
Q
i1
x
Q
i4
x
Q
i3
x
Q
i1
y
Q
i2
y
Q
i3
y
Q
i4
y
R
x
?, R
y
?
(R
x
?, R
y
?)
(x
i
?, y
i
?)
(x
i
?, y
i
?)
(0, 0)
(B
x
, B
y
)
Figure 4.1. Pictorial representation of the model variables.
Throughout the example cases, it is assumed that the traffic density is the highest
at the southern horizontal portion of the racetrack, is medium at eastern and western
portions of the racetrack, and is lesser at the northern portion of the racetrack. Thus, if
1=
x
ik
Q for k = 1, 2 then department i is in the lowest traffic zone, 1=
x
ik
Q for k = 3, 4 then
the department i is in the highest traffic zone. 1=
y
ik
Q for k = 1, 2, 3, 4 means that the
department is in the moderate traffic zone.
4.3. Model
() ()
????
====
?+?=
n
ik
y
ikik
n
ik
x
ikik
QRQRZ
1
4
11
4
1
11max (4.1)
s.t.
u
iii
l
i
LxxL ??? '" i? (4.2)
u
iii
l
i
WyyW ??? '" i? (4.3)
49
()
u
iiiii
l
i
PyyxxP ??+?? '"'"2 i? (4.4)
( )
x
i
x
ixi
MIRMRx +?+? 1'" i? (4.5)
x
i
x
ixi
MIMRRx ??? "' i? (4.6)
xii
Bxx ??? "'0 i? (4.7)
( )
x
iix
IMxR ?+? 1'' i? (4.8)
( )
x
ixi
IMRx ?+? 1"" i? (4.9)
( )
y
i
y
iyi
MIRMRy +?+? 1'" i? (4.10)
y
i
y
iyi
MIMRRy ??? "' i? (4.11)
yii
Byy ??? "'0 i? (4.12)
( )
y
iiy
IMyR ?+? 1'' i? (4.13)
( )
y
iyi
IMRy ?+? 1"" i? (4.14)
( )
x
ijij
ZMxx ?+? 1'" .;, jiji ?? (4.15)
( )
y
ijij
ZMyy ?+? 1'" .;, jiji ?? (4.16)
1?+++
x
ji
y
ij
x
ji
x
ij
ZZZZ .;, jiji W):
,
W
L
f
=? (5.6)
f
I
I
A
W
?
= (5.7)
IfI
WL ?= (5.8)
Here, the width of the outer bay takes two different values. To be more precise,
2)(
I
y
LLw ?= (5.9)
2)(
I
x
WWw ?= (5.10)
where w
x
> w
y
.
69
5.4. Tabu Search for Retail Store Design
The proposed model is solved using tabu search (TS). The details are as follows:
1. Solution Representation: Solutions are represented as explained in Section 5.5.
The initial solution (department sequence) and the bay breaks (cut points) are
generated randomly and the fitness value is calculated by the fitness function
explained below.
2. Move operator: Two different move operators are used.
i. Swap: The swap operator exchanges the places of the two departments located
in the i
th
and j
th
position in the department sequence. After the swap,
If i, j are in the outer bay then no change occurs in the upper and the lower
bays.
If i, j are in the upper bay then no change occurs in the outer and the lower
bays.
If i, j are in the lower bay then no change occurs in the outer and the upper
bays.
If i, j are either in the upper or in the lower bay then no change occurs in
the outer bay.
With every other combination of i and j all departments? coordinates have to
be recalculated. The swap operator does not affect the number of departments
allocated to each bay.
70
ii. Re-partite: The re-partite operator is used to change the number of
departments allocated to each bay. After the swap operator is applied, the
newly obtained department sequence is coupled with every possible partition
combination to obtain new solutions. For example, for the 16 department
problem there are 120 possible partitioning schemes. (1-2, 1-3, 1-4, ?, 15-
16). Partitioning 1-2 means that there is one department in the outer bay,
another department in the upper bay and the remaining departments are in the
lower bay.
3. Tabu List Entries: In the tabu list, entire solutions are kept. The size of the tabu
list is constant and it is determined experimentally.
4. Neighborhood Definition: The neighborhood of a given solution is considered in
two different dimensions: department sequence and partitioning. In the first stage,
partitioning is kept constant and from a given department sequence, all other
department sequences that can be reached by a single swap operation are
considered. (The number of solutions that can be reached using the swap operator
is ()21?nn .)
In the second stage, the department sequence is kept constant and the search is
performed in the partition neighborhood. The number of solutions that can be
reached by changing the partition is ( )( ) 221 ?? nn . Since the fitness value
obtained for the same department sequence varies greatly with the baybreak
combination used, it is necessary to evaluate a given department sequence with all
possible baybreak combinations. Thus, the number of different solutions that can
71
be reached from any given solution is ( ) ( ) 421
2
?? nnn if a complete
neighborhood is searched for both swap and partitioning.
ABCDE 2 4
(a)
BACDE 1 2
CBADE 1 3
DBCAE 1 4
EBCDA 2 3
ACBDE 2 4
ADCBE 3 4
AECDB
ABDCE
ABEDC
ABCED
(c)
(b)
(d)
Figure 5.7. The initial solution: department sequence (a), partitioning (b), permutation
neighborhood (c) and partitioning neighborhood (d).
5. Fitness Function: The fitness function is the same as the objective function except
for one penalty term added to reduce the quality of solutions that have
departments violating the aspect ratio constraint. The fitness function is given in
equation 5.5.
6. Aspiration Criteria: If a solution within the neighborhood has a better fitness
function than the best solution encountered so far, a move to that solution is
allowed even if the move is tabu.
7. Candidate List Strategies: For this problem, ( ) ( ) 421
2
?? nnn distinct solutions
can be reached from any given solution. However, some of these solutions are not
72
promising in the sense that they are not likely to have better fitness. For example,
if there are too few departments assigned to the outer bay, aspect ratios of the
departments violate their limits. This occurs when the first bay break occurs too
early. Thus, eliminating candidate solutions that have the first bay break too early
without fully evaluating them can speed up the search process. A simple method
is proposed to determine the location of the first bay break. The pseudo code of
the method is given below.
Nomenclature:
stepat bay outer theof Area:
th O
j
jA
stepat region inner theof Area:
th I
j
jA
step at region inner theofLength :
thI
j
jL
step at region inner theof Width :
thI
j
jW
stepat bay outer in the departmentsmallest theof Area:
min th
j
jA
pointcut First :
1
cp
),max(
axis on located if stepat departmentsmallest of ratioAspect :
axis on located if stepat departmentsmallest of ratioAspect :
min y
j
x
jj
y
j
x
j
yj
xj
???
?
?
=
73
Procedure setCutPoint1{
Calculate total area, A;
for( j = 0; j < n; j++){
j
o
j
AA =+ ;
calculate w
x
, w
y
;
),max(
)/,min()/,max(
)/,min()/,max(
min
minmin
minmin
y
j
x
j
yyyy
y
j
xxxx
x
j
j
jj
jj
wAwwAw
wAwwAw
???
?
?
=
=
=
if(
minmin
1?
>
jj
?? ){
cp
1
= j -1;
break;
}end if
}end for
return cp
1
;
}end procedure
With this procedure, the width of the widest possible outer bay that does not lead
to the violation of aspect ratio of the smallest department of the outer bay is determined.
Thus, at least for the departments in the outer bay, the aspect ratio violation is avoided.
Another advantage of the procedure is that the size of the partition neighborhood is
drastically reduced using this procedure.
To further reduce the number of solutions in the neighborhood, randomization is
used for the permutation neighborhood. In order to decide whether the swap operator is
applied to the current solution, a uniform random number, U(0, 1) is compared against a
threshold value. If the threshold value is larger than the uniform random number, a swap
is performed and the resultant department sequence coupled with all possible baybreak
combinations (the reduced combination set obtained through the procedure defined
earlier) are evaluated. Otherwise the resultant department sequence is dropped from
74
consideration along with the associated baybreak combinations that otherwise would be
considered. The pseudo code for the neighborhood generation is given below. The
threshold value is determined experimentally as well.
Procedure tabuSearchNeighborhoodGeneration (Solution CURRENT ){
Initialize neighborhood array nArray;
for ( i = 0; i < n ? 1; i++){
for ( j = i + 1; j < n; j++){
if (U(0,1) < threshold){
Departments dP ? swap departments i, j of CURRENT;
cp = setCutPoint1(); (See Figure 17)
for (cp
1
= cp; cp
1
< n ? 2; cp
1
++ ){
for (int cp
2
= cp
1
+1; cp
2
< n; cp
2
++){
cutPoint
1
= cp
1
;
cutPoint
2
= cp
2
;
nArray.add(Solution(dP, cutPoint
1
,
cutPoint
2
));
} end if
}end for
}end for
}end for
}end for
sort nArray;
return nArray;
}end procedure
Given the determination of the first cut point and the definition of the
neighborhood generation procedure, the tabu search algorithm designed to solve the retail
store design problem is given as follows:
75
Procedure tabuSearch{
initialize moves, CURRENT, tabuListSize;
BEST ? CURRENT;
initialize tabuList, nArray;
for (i = 0; i < moves; i++){
nArray ? tabuSearchNeighborhoodGeneration(CURRENT);
for(j = 0; j < nArray.size(); j++){
if(nArray [j].fitness > BEST.fitness){ //Aspiration Criteria
CURRENT ? nArray [j];
BEST ? CURRENT;
tabuList.add(CURRENT);
while(tabuList.size() > tabuListSize)
tabuList.remove(oldest entry));
break;
}end if
if(nArray [j] is not a tabu){
CURRENT = nArray [j];
tabuList.add(CURRENT);
while(tabuList.size() > tabuListSize)
tabuList.remove(oldest entry));
break;
}end if
}end for
}end for
BEST.printSolution();
}end procedure
5.5. Experimentation
Experiments are performed using three different data sets with n = 16, 17 and 20,
with two different layout configurations. The sixteen department problem is the base
case, whereas the seventeen department problem is designed to investigate the effect of
size among departments and lastly, the twenty department problem is designed to
investigate the effects of increasing number of departments. The data for these problems
are provided in Appendix II. The difference between the two layout configurations is that
the zone with the densest traffic and the zone with the sparsest traffic are swapped
76
(Figure 5.8). Thus six different test cases are obtained as illustrated in Table 5.4. The tabu
search is coded in Java 5.0 and run with following parameters:
To terminate the search from a given initial solution, the number of non-
improving moves is recorded. If for a certain number of consecutive moves the best
known solution (BEST) has not been improved, the search terminates. Every time BEST
is updated, the non-improving solution counter starts from zero again. The threshold
value for the number of consecutive non-improving moves is determined experimentally
and set at 500. At each move attempt, the number of solutions evaluated depends on two
factors: the initial value of the first cut point (i.e. the value obtained from the
setCutPoint1() method) and the degree of randomization (i.e. the value of the evaluation
threshold). Due to these two reasons and the termination criterion, predetermining the
exact number of function evaluations is not possible. The last two parameters of the tabu
search, the evaluation threshold and the length of the tabu tenure are also determined
experimentally and set at 0.3 and 50, respectively. As stated previously, tabu list entries
compose of entire solutions.
(a) (b)
Figure 5.8. Zone definitions of the store for the two different settings.
Zone 2
Zone 3
Zone 1
Zone 2
one 1
Zone 3
Zone 2
Zone 3
Zone 1
Zone 2
Zone 1
77
Table 5.4. Test case configurations.
Test Case # of departments, zone definitions
1 16, Figure 5.8(a)
2 16, Figure 5.8(b)
3 17, Figure 5.8(a)
4 17, Figure 5.8(b)
5 20, Figure 5.8(a)
6 20, Figure 5.8(b)
By using these six test cases, we investigate:
? the interactions between the assignments of departments to the zones and level of
adjacency satisfaction,
? effects of department sizes, and,
? average execution time with respect to problem size.
Each of the six test cases are run with identical settings of tabu search for 500 trials
each. The results are summarized in Table 5.5 and the layouts obtained are provided in
Figures 5.9 through 5.14. In addition, average execution times per run for the test cases
grouped by the number of departments are calculated as 86.2 seconds, 253.3 seconds and
281.4 seconds for n = 16, 17 and 20.
Table 5.5. The best solutions found by the tabu search.
Test Case Encoding Baybreaks Revenue Adjacency
Aspect Ratio
Penalty Fitness
1 3 7 6 0 1 11 9 8 13 10 12 14 15 2 5 4 11, 13 584.67 0.82 1.00 481.09
2 1 7 9 2 6 12 10 13 3 11 15 5 4 8 0 14 11, 14 583.00 0.83 1.00 486.79
3 10 5 9 16 11 14 0 2 13 15 12 8 3 1 4 7 6 11, 14 574.33 0.78 1.00 446.54
4 16 9 13 15 5 10 12 2 0 3 14 6 7 4 1 11 8 11, 14 579.00 0.78 1.00 450.90
5 16 2 5 15 0 8 1 3 18 7 12 17 11 13 19 14 4 10 9 6 12, 16 916.50 0.78 1.00 708.98
6 1 7 4 19 12 17 6 16 18 10 13 8 9 2 5 15 14 0 3 11 12, 17 876.83 0.82 1.00 717.75
The entries in the above table are given in equations 5.2 through 5.5.
78
Figure 5.9. The best layout obtained by tabu search for Test Case 1.
Figure 5.10. The best layout obtained by tabu search for Test Case 2.
79
Figure 5.11. The best layout obtained by tabu search for Test Case 3.
Figure 5.12. The best layout obtained by tabu search for Test Case 4.
80
Figure 5.13. The best layout obtained by tabu search for Test Case 5.
Figure 5.14. The best layout obtained by tabu search for Test Case 6.
81
5.6. Assessment of the Solution Quality for the Constructive Heuristic and the Tabu
Search
In this section, we first compare the performances of the constructive heuristic
with the tabu search, followed by an assessment of both procedures against a theoretical
upper bound for each case. Note that we used only three example cases for the
constructive heuristic, and these cases correspond to test cases one, three and five of the
test cases for the tabu search. The upper bounds are calculated by:
?
=
=
n
i
ii
Ar
1
U
Revenue (5.11)
()[]
????
??
?
=+=
?
?
=+=
+
?
=+=
??
?
???+++
=
1
11
1
11
1
11
251251525125
U
251251525125
Adjacency
n
i
n
ij
ij
n
i
n
ij
ij
n
i
n
ij
ijijijijijij
cc
xxxxxx
(5.12)
s.t.
63
1
11
125
??
??
?
=+=
nx
n
i
n
ij
ij
????
?
=+=
?
=+=
???
1
11
125
1
11
25
63
n
i
n
ij
ij
n
i
n
ij
ij
xnx
??????
?
=+=
?
=+=
?
=+=
????
1
11
25
1
11
125
1
11
5
63
n
i
n
ij
ij
n
i
n
ij
ij
n
i
n
ij
ij
xxnx
????????
?
=+=
?
=+=
?
=+=
?
=+=
?????
1
11
5
1
11
25
1
11
125
1
11
1
63
n
i
n
ij
ij
n
i
n
ij
ij
n
i
n
ij
ij
n
i
n
ij
ij
xxxnx
()
()63
2
1
1
11
125
??
?
?
??
?
=+=
?
n
nn
x
n
i
n
ij
ij
82
()
()
????
?
=+=
?
?
=+=
?
???
?
?
1
11
125
1
11
25
63
2
1
n
i
n
ij
ij
n
i
n
ij
ij
xn
nn
x
Where
?
?
? =
=
otherwise. ,0
, if ,1 kc
x
ij
k
ij
and, finally the upper bound for the aspect ratio penalty:
()
n
sn ?
=
U
Penalty RatioAspect where s = 0. (5.13)
then, the upper bound on the fitness function becomes:
()( )( )( )
UUUU
Penalty RatioAspect AdjacencyRevenueFitness = (5.14)
In Table 5.6, comparison of the constructive heuristic with the tabu search is
provided. The execution time for the constructive heuristic is less than a second;
however, the tabu search is better than the constructive heuristic in terms of the fitness
values obtained across all three cases. In order to make the comparison between the
constructive heuristic and the tabu search, the average performance of the tabu search is
used rather than the best performance.
Table 5.6. Comparison of the constructive heuristic against the tabu search.
Fitness Found Deviation from Average Fitness Improvement of TS
n Revenue Adjacency Aspect Ratio Fitness by Heuristic Upper Bound Found by TS over Heuristic
16 595.00 0.88 1.00 522.32 264.46 49.4% 467.94 76.9%
17 629.00 0.90 1.00 563.79 197.45 65.0% 428.61 117.1%
20 925.50 0.88 1.00 816.28 419.68 48.6% 674.13 60.6%
Upper Bound on:
Next, we compare the performances of the constructive heuristic with tabu search
in terms of the components of the fitness function. Results are summarized in Table 5.7.
For the first two test cases, the constructive heuristic outperforms the tabu search in the
revenue component, but tabu search is superior in adjacency satisfaction, aspect ratio
83
penalty and in overall fitness. For the last example case, the tabu search is superior across
all components of the fitness function.
Table 5.7. Component-wise comparison of the fitness function for the constructive
heuristic and the tabu search.
n Constructive TS Constructive TS Constructive TS Constructive TS
16 595.00 584.67 0.55 0.82 0.81 1.00 264.46 481.09
17 629.00 574.33 0.49 0.78 0.65 1.00 197.45 446.54
20 893.50 916.50 0.59 0.78 0.80 1.00 419.68 708.98
Revenue FitnessAspect Ratio PenaltyAdjacency
After asserting the fact that the tabu search performs better than the constructive
heuristic at a cost of prolonged execution time, we proceed with the analysis of the
performance of the tabu search. For the remaining three test cases the upper bounds are
calculated and performance of the tabu search is assessed using the best solutions found
as well as the average performance in each test case. The results are summarized in
Tables 5.8.
Table 5.8. Comparison of best and average performances of TS with theoretical upper
bounds.
Best Fitness Deviation from Average Fitness Deviation from
Test Case Revenue Adjacency Aspect Ratio Fitness Found by TS Upper Bound Found by TS Upper Bound
1 595.00 0.88 1.00 522.32 481.09 7.9% 467.94 10.4%
2 595.00 0.88 1.00 522.32 486.79 6.8% 472.88 9.5%
3 629.00 0.90 1.00 563.79 446.54 20.8% 428.61 24.0%
4 629.00 0.90 1.00 563.79 450.90 20.0% 428.24 24.0%
5 925.50 0.88 1.00 816.28 708.98 13.1% 674.13 17.4%
6 925.50 0.88 1.00 816.28 717.75 12.1% 685.01 16.1%
Upper Bound on:
For the six test cases, the improvements on the fitness as a function of the number
of iterations are given in Figures 5.15 through 5.17.
84
200
250
300
350
400
450
500
0 200 400 600 800 1000
t
F(
t
)
Test Case 1
Test Case 2
Figure 5.15. Test Cases 1 and 2: fitness vs. number of iterations.
200
250
300
350
400
450
500
0 100 200 300 400 500 600 700 800 900 1000
t
F(
t
)
Test Case 3
Test Case 4
Figure 5.16. Test Cases 3 and 4: fitness vs. number of iterations.
300
350
400
450
500
550
600
650
700
750
0 100 200 300 400 500 600 700
t
F(
t
)
Test Case 5
Test Case 6
Figure 5.17. Test Cases 5 and 6: fitness vs. number of iterations.
When we examine Figures 5.15 through 5.17 we can verify that approximately the
first 200 iterations are the iterations where the improvement in the fitness value is the
steepest, then the rate of improvement gradually decreases.
85
To determine the effects of the candidate list strategies we used Test Case 1 as a
test bed and performed tabu search by excluding candidate list strategies. That is, we
removed the randomization which is used to reduce the number of different sequences in
the permutation neighborhood and instead of using the setCutPoint1() method, we
evaluated all possible bay break combinations. As a result, we obtained a significant
reduction in average fitness value (460.98 compared to the previous 467.94 for Test Case
1, p = 6.63E?08) and the average execution time is increased by nearly twelve times, to
991 seconds per run from the previous 86 seconds per run. Both methods are able to
reach the same best known solution, that is, eliminating candidate list strategies from the
search procedure does not yield a better fitness value than that obtained with the
implementation of candidate list strategies.
5.7. Analysis and Discussion
When we examine Table 13, it is observed that the deviations from the theoretical
upper bound for the tabu search algorithm can be as high as 24% and 27% for the best
and average fitness, respectively. There are several reasons explaining these deviations:
? The fitness function used for directing the search considers revenue generation
simultaneously with adjacency satisfaction, whereas in calculating the upper
bounds for the test cases, each component of the fitness function is treated one at
a time. For example, in Test Case 1, department A?s zone preference is given as
d
i
= 1, however; the loss caused by placing department A in Zone 2 is
overwhelmed by the increase in the adjacency satisfaction caused by department
86
A being adjacent to department P. Similar trade-offs can be observed for
numerous departments? placements across all test cases.
? Restrictions on the search space imposed by the racetrack requirement and the
modified FLEXBAY representation: This can be verified by examining test cases
1 and 2, 3 and 4, and 5 and 6 together. In each of these pairs, the department data
used are identical, but there are minute increases in fitness values of the best
solutions found in all pairs in favor of the zone assignments given in Figure 5.8.b.
This situation is not a coincidence; it is caused by the elimination of the entrance
aisle from the middle of the most valuable zone of the store.
? Penalizing of layouts having departments violating their aspect ratio constraints:
The effect of the penalty function is the most apparent in Test Cases 3 and 4. This
data set includes two small departments, the areas of which are eleven times
smaller than the largest department (departments M and F which are one sq. unit
versus department N which is eleven sq. units). To find a layout that satisfies the
aspect ratio constraint for all departments, tabu search compromises the revenue
and the adjacency satisfaction aspects of the fitness function. To verify this, the
tabu search algorithm is run with the objective of revenue generation multiplied
by the adjacency maximization, relaxing the aspect ratio constraints, using the
same parameters as in Section 5.5. Fitness values of 513.01 for Test Case 1 and
534.65 for Test Case 3 are obtained. These values are 10% and 13% better than
the best results from Section 5.5. However, the number of departments violating
their aspect ratios increases to twelve and sixteen for n = 16 and for n = 17,
87
respectively. Examining Figures 5.18 and 5.19 verify that enforcing the aspect
ratio constraint is, in fact, important for practical shaped departments.
Figure 5.18. The best layout obtained by tabu search for Test Case 1, without penalty
function.
Figure 5.19. The best layout obtained by tabu search for Test Case 3, without penalty
function.
88
VI. VARIABLE DEPARTMENT AREAS
This chapter introduces the solution procedures for the retail space allocation
problem with variable department areas. Although the model introduced in Chapter III
includes constraints imposing lower and upper bounds on department areas, the solution
procedures investigated in Chapters IV and V dealt with constant department areas for
the sake of simplicity. Insights gained by the implementation of the MIP formulation of
the model, the constructive heuristic, and the tabu search have led to the solution
approaches devised herein.
This chapter starts with a discussion on alternative revenue formulations for the
departments. The discussion is based mainly on demand and revenue functions employed
in the shelf space allocation literature. Next, the modifications made on the tabu search
devised in Chapter V are explained in order to accommodate the variable department and
aisle areas. Finally, the chapter concludes with two example problems and analyses of the
results.
6.1. Choice of the revenue function
The relationship between the space allotted to a merchandise and the profit and/or
revenue has drawn the attention of researchers for almost fifty years. Brown and Tucker
(1961) articulate that the law of diminishing marginal returns applies to the space/revenue
89
relationship in retail settings. They identified three different product groupings based on
the effect of increasing shelf space in sales. Lee (1961) also asserted
that the effect of increasing shelf space must be of diminishing returns. However, neither
of these studies specified a functional form on the definition of the diminishing returns.
The assumption of diminishing marginal returns is validated by the field studies of Frank
and Massy (1970), Curhan (1973), and Dreze et al. (1994). Corstjens and Doyle (1981)
formulated the demand (q) for product i based on the space elasticity as follows:
?
?
=
=
K
ij
j
jiii
ij
i
ssrq
1
?
?
(6.1)
where
i
?
Space elasticity for product i
i
s
Shelf space allocated to product i
ij
?
Cross-elasticity between product i and product j
i
r
Demand multiplier for product i
Based on the definition above, Corstjens and Doyle also performed a field study
which suggested that the space elasticity for different products fluctuates between 0.06
and 0.25 and cross-elasticities between ?0.01 and ?0.05. Corstjens and Doyle?s
formulation has been used by various researchers such as Yang and Chen (1999), Irion et
al. (2004) and Mart?nez-de-Alb?niz and Roels (2007). Considering the cross-elasticities
of secondary importance, Irion et al. (2004) simplified the Corstjens and Doyle model by
90
removing the cross-elasticities from the formulation. They formulated the demand
function as:
i
iii
srq
?
= (6.2)
The simplified model by Irion et al. (2004) has also been widely accepted by
researchers. Using Brown and Tucker?s classification, Irion et al. (2004) suggested [0.06,
0.1], [0.16, 0.20], and [0.21, 0.25] as the closed intervals of space elasticity for
unresponsive, moderately responsive and responsive products respectively, to increase in
shelf space. Based on interviews made with a local retail store management, products
considered in Irion et al.?s study are assigned to one of the intervals above, and then the
space elasticities are estimated within their corresponding intervals.
Lee?s work (1961) defines the retail space in two dimensions: an area, not one
dimensional shelf space as with most of the studies. The only exception is the study of
Dreze et al. (1994) which investigated the effect of space allocated to the sales in actual
area, not as the length of shelf space. They empirically determined that the area allocated
to a product is significant in determining the sales using Gompertz model provided
below.
()
iii
s
ii
erq
?? exp
= (6.3)
Where
i
q is the demand for product i,
i
r ,
i
? and
i
? are the parameters of the
Gompertz model, and
i
s is the area occupied by product i. More specifically,
i
r is
referred to as the horizontal asymptote where
ii
rq ? , 0<
i
? and 0<
i
? together control
the increase in demand as a function of the increase in area.
91
The main motivation behind the use of the Gompertz model in Dreze et al.?s work
(1994) is the assumption of ?bounded unit sales? for a given product. The assumption
implies that there is a limit to the sales of a product, and once that limit (
i
r ) is reached,
increasing the allotted area,
i
s cannot increase the sales,
i
q . This assumption, however, is
not valid in our case. A department defines a set of different merchandise lines and
products that are grouped together, not a single item. For example, the shoe department
of a retail store might include men?s shoes and women?s shoes. When the space allotted
to the shoe department is increased, the additional space can be used for sports shoes,
children?s shoes or another brand of women?s shoes. Each of these alternatives can
increase the sales so that the asymptotic behavior of Gompertz function is unsuitable. In
essence, the choice of products for a single department in a retail store is so diverse that a
department can define a retail store by itself. To illustrate, sporting goods can be a
department in a retail store (e.g. JC Penney), or it can be a stand-alone retail store (e.g.
Dick?s Sporting Goods). Due to these reasons, the use of the power model (
i
iii
srq
?
= ) is
more suitable in our case than the Gompertz model to define the relationship between the
area and the revenue. Hence, we define the revenue of a department as:
i
iii
ArR
?
= (6.4)
and, the total expected revenue for the whole store as
a
n
i
i
RRR +=
?
=1
(6.5)
92
where
a
aaa
ArR
?
= , the contribution of aisle space on the revenue. Due to the non-linear
nature of the revenue function, a two stage optimization procedure is devised. In the first
stage, the area allotments are determined by solving the following model
a
n
i
i
RRR +=
?
=1
max (6.6)
s.t.
AAA
a
n
i
i
?+
?
=1
(6.7)
L
ii
AA ? ,i? (6.8)
Since the objective function of the model is not linear, a non-linear optimization
package such as LINGO can be used to solve the model. As stated in Chapter III, in the
revenue part of the model, there are also zone requirements for the departments. The
objective function is denoted by R since the model given by equations 6.6 ? 6.8
disregards the zone requirements of the departments. Depending on the level of
satisfaction of zone requirements, the actual revenue figure might be lower than the value
obtained by the solution of the model.
Next, by using the area allotments obtained from the model given by equations
6.6 ? 6.8, tabu search is performed to optimize the layout of the store. The details of the
tabu search implementation are presented in Section 6.2.
93
6.2. Tabu Search for Retail Spatial Design with Flexible Department Areas
Based on the results reported in Chapters IV and V, the choice of optimization tool
for the retail store design problem with flexible department and aisle areas is the tabu
search. The solution representation is very similar to the one used in Chapter V, however,
there are differences. The most important difference stems from the necessity of dealing
with the variable aisle width. In order to maintain the aisle width within acceptable limits,
the number of departments separated by the first baybreak, cp
1
, is effectively used in the
tabu search. In doing so, we eliminate those baybreak combinations that do not yield
acceptable values for the aisle width. The details of determining acceptable values of cp
1
are explained in subsequent sections. Because the area allotments are made prior to the
tabu search, the tabu search is mainly used to govern sequencing of the departments and
baybreaks in order to:
? optimize the location of departments in the layout,
? maximize the level of adjacency satisfaction, and,
? maintain the aspect ratio constraints of the departments.
In the following sections, the overall optimization scheme is discussed in detail,
starting with the solution representation.
1. Solution Representation and Decoding: The solution representation is depicted in
Figure 6.1. The encoding is composed of the sequence of departments, p, followed by
two baybreaks. The departments from the beginning of the permutation up to the first
baybreak point, cp
1
, are assigned to the outer bay. The departments starting from the
first baybreak point up to the second baybreak point are assigned to the upper bay,
94
while the remaining departments are assigned to the lower bay. Assignment of the
departments to the outer bay starts from the lower midpoint of the rectangular store
area and continues counterclockwise. The placements inside the racetrack are done
using boustrophedon ordering starting from the upper left corner. The initial
permutation and the corresponding baybreak combinations are generated randomly.
8 11A B C D E F G H I J K L M N
G H A B
F E D C
I J K
N M L
Figure 6.1. Solution representation and the corresponding layout.
2. Move operator: Two different move operators are used:
i. Swap: The swap operator exchanges the places of the two departments located in
the ith and jth positions in the permutation where i = 1, ?, n ? 1 and j = i + 1, ..., n.
ii. Re-partite: The re-partite operator is used to change the number of departments
allocated to each bay. After each swap operation, the newly obtained permutation
is coupled with every possible partition combination to obtain new solutions using
sets cp
1
and cp
2
. For instance, as illustrated in Figure 6.1, partitioning 8 ? 11
indicates that there are eight departments in the outer bay, three departments in the
upper bay, and the remaining departments in the lower bay. The definition of sets
cp
1
and cp
2
is provided in the candidate list strategies section.
95
3. Tabu List Entries: In the tabu list, the most recent department pairs swapped are kept.
To apply dynamic tabu tenure, a lower bound and an upper bound on the tabu tenure
are specified. Then, at each iteration, the size of the tabu list is determined according
to an integer uniform random number between these lower and the upper bounds. The
lower and the upper bounds on the tabu tenure are determined experimentally and set
to five and eight, respectively.
4. Neighborhood Definition: The neighborhood of a given solution is considered in two
different dimensions: permutation and partitioning. In the first stage, partitioning is
kept constant and from a given permutation, all other permutations that can be
reached by a single swap operation are considered. The number of solutions that can
be reached using the swap operator by assuming no change in the partitioning is
()21?nn
.
In the second stage, the permutation is kept constant, and the search is performed in the
partition neighborhood. The number of solutions that can be reached by changing the
partition is ()()221 ?? nn for a given permutation. Thus, the number of different
solutions that can be reached from any given solution is ( )( )421
2
?? nnn provided
that a complete neighborhood is searched for both swap and partitioning. For example,
if n = 20, then the size of the neighborhood is 32,490. The size of the neighborhood
will be reduced by candidate list strategies, as explained in the following sections.
96
ABCDE 2 4
(a)
BACDE 1 2
CBADE 1 3
DBCAE 1 4
EBCDA 2 3
ACBDE 2 4
ADCBE 3 4
AECDB
ABDCE
ABEDC
ABCED
(c)
(b)
(d)
Figure 6.2. The initial solution: permutation (a), partitioning (b), permutation
neighborhood (c) and partitioning neighborhood (d).
5. Fitness Function: Equations 6.9 through 6.11 present three different functions used.
These fitness functions are: the adjacency score only (F
a
), the revenue only (F
r
), and
the combination of adjacency score and the revenue (F
f
). The fitness functions F
a
and
F
r
are mainly used to determine to what extent revenue and the adjacency
components can be maximized without the involvement of the other. All the fitness
functions include a common term, the penalty function, which is to reduce the quality
of solutions that have departments violating the aspect ratio constraint. In equations
6.9 ? 6.11, the penalty term is
?
?
?
?
?
?
? ?
n
sn
, where n is the number of departments, s is
the number of departments violating their aspect ratio, and ? is the exponent
controlling the severity of the penalty function. The value of the exponent ? is
determined experimentally.
97
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
=
n
sn
REL
REL
F
P
a *
(6.9)
()[]
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
+
?
?
?
?
?
?
?
?
?
?
?
?
?+
=
?
?
=
=
n
sn
R
dzy
R
F
a
n
i
K
k
ikik
i
r
1
1
,0max1
(6.10)
()[]
?
?
?
?
?
?
? ?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
+
?
?
?
?
?
?
?
?
?
?
?
?
?+
=
?
?
=
=
n
sn
REL
REL
R
dzy
R
F
P
a
n
i
K
k
ikik
i
f *
1
1
,0max1
(6.11)
As noted under the solution representation, zone requirements of the departments
are not taken into consideration in determining the areas of the departments. Once the
layout is constructed, the revenue term of the fitness function,
?
?
?
?
?
?
?
=
n
i
i
R
1
, is calculated by
considering zone requirements of the departments as well. To do so, the revenue of a
department is calculated using the department area and the revenue function of the
department. Then, by considering the zone preference of the department and its location,
the actual revenue is obtained by equation (6.12) below.
()[]
?
=
?+
=
K
k
ikik
i
i
dzy
R
R
1
,0max1
(6.12)
The definitions y
ik
, z
k
and d
i
are given in Chapter III.
Calculation of the adjacency score is the same as presented in Chapter V. As
previously, two departments are considered to be adjacent to each other if they share a
common edge. For the departments that are separated by the aisle, two departments are
98
said to be adjacent to each other if those two departments are across from each other. For
instance, in Figure 6.1, Department L is adjacent to departments A, B, and C, in addition
to departments K and M.
With these settings, the pseudo code of the neighborhood generation is given as
follows:
Procedure tabuSearchNeighborhoodGeneration (Solution CURRENT ){
Initialize neighborhood array nArray;
for ( i = 0; i < n ? 1; i++){
for ( j = i + 1; j < n; j++){
Departments dP ? swap departments i, j of CURRENT;
Determine sets
1
cp and
2
cp using
I
A and
a
A ;
for (cp
1
1
cp? ){
for (cp
2
2
cp? ){
nArray.add(Solution(dP, cp
1
, cp
2
));
}end for
}end for
}end for
}end for
sort nArray;
return nArray;
}end procedure
6. Aspiration Criteria: If a solution within the neighborhood has a better fitness function
than the best solution encountered so far, a move to that solution is allowed even if
the move is tabu.
7. Candidate List Strategies: For this problem, ( ) ( ) 421
2
?? nnn distinct solutions can
be reached from any given solution. Of these solutions, ( ) 21?nn are due to distinct
permutations, and for each distinct combination there are ( )( ) 221 ?? nn baybreak
combinations. As mentioned in the solution representation, the location of the first
99
baybreak, cp
1
, determines the number of departments inside and outside the racetrack.
The location of cp
1
, thus, determines the width of the racetrack. As the value of cp
1
increases, the number of departments outside the racetrack increases, and the
racetrack runs closer towards the center, making the aisle wider. In contrast, as the
value of cp
1
decreases, the number of departments outside the racetrack decreases,
and the racetrack runs further from the center, making the aisle narrower. Hence,
there are natural limits over the values that cp
1
can assume that are imposed by the
lower and upper bounds on the aisle width. Given the total area of the departments
inside the racetrack, the width of the aisle can be calculated as:
()( )
fIf
a
I
a
AAAw ?? ?+=
2
1
(6.13)
where
?
=
=
n
cpi
i
I
AA
1
,
a
A is the aisle area and
f
? is the facility?s aspect ratio.
Then, the set of feasible first baybreaks for the sequence of departments, p, is defined
as:
{ }
U
aa
L
aa
wwwwk ??= ,|
1
cp (6.14)
Finally, for each
1
cp?k , the set of second baybreaks is defined as
{}
12
,,| cpcp ?<>= knmkmm (6.15)
where n is the number of the departments in the permutation. With the formulas
provided in equations 6.14 and 6.15, the number of baybreak combinations is reduced
substantially.
100
It is assumed that the decision makers have the ability to set the lower and upper
bounds on the width of the aisle. In choosing the values of
L
a
w and
U
a
w , the natural
lower and upper bounds on the aisle width imposed by the aisle area and the
department areas can be of help by using two extreme cases defined below:
a. Consider a department sequence where only the smallest department is
outside the racetrack. This is the case where the width of the aisle is the
smallest. Thus, a lower bound on the aisle width can be defined as:
() ()
?
?
?
?
?
?
?
?
?
?
?
?
+?
=
??
==
f
i
n
i
i
f
ai
n
i
i
a
AAAAA
w
??
minmin
2
1
11
(6.16)
b. By the same token, consider a department sequence where only the
smallest department is inside the racetrack, and the rest of the departments
are placed outside the racetrack. This is the case where the aisle width is at
its widest. Hence the upper bound on the aisle width is given by:
( ) ( )
?
?
?
?
?
?
?
?
?
+
=
f
i
f
ai
a
AAA
w
??
minmin
2
1
(6.17)
Any feasible layout has to satisfy the condition
aaa
www ?? , so the lower and
upper bounds of the aisle width,
L
a
w and
U
a
w also have to satisfy
a
U
a
L
aa
wwww ??? .
The values
a
w and
a
w might yield extreme values that are impractical (e.g. ft. 2=
a
w
and ft. 50=
a
w ). In such a case, tightening the interval ( )
U
a
L
a
ww , to reflect the decision
maker?s preferences would even further reduce the size of
1
cp , leading to a smaller
101
baybreak neighborhood. In addition, the values
a
w and
a
w would also help ascertain
whether the desired values of the aisle width can be achieved for a given value of the
total aisle area by comparing these values against the values of
L
a
w and
U
a
w .
8. Diversification Strategies: Diversification strategies are introduced to restart the search
from a different solution if there is no improvement for a certain number of moves in
the fitness of the best known solution. In such a case, the search restarts from a
randomly generated solution, and the tabu list is reset. The threshold value for the
diversification strategy to take effect is determined experimentally as 50 consecutive
non-improving moves. During trials, it is observed that increasing the threshold value
worsens the performance of the tabu search (i.e. less opportunity for restart) and
smaller values of the threshold do not provide enough opportunity for search
continuity.
9. Termination criteria: To terminate the search from a given initial solution, the number
of non-improving moves is recorded. If the best known solution (BEST) has not been
improved for a certain number of consecutive moves, the search terminates. Every
time BEST is updated, the non-improving solution counter starts from zero again.
Given the determination of the sets
1
cp and
2
cp and the definition of the
neighborhood generation procedure, the tabu search algorithm to solve the retail store
design problem is given as follows:
102
Procedure tabuSearch{
initialize CURRENT,Tenure, minTenure, maxTenure;
initialize iter = 0, iterDiversification, iterMax;
BEST ? CURRENT;
initialize tabuList, nArray;
do {
nArray ? tabuSearchNeighborhoodGeneration(CURRENT);
Tenure = minTenure + U(0, 1)(maxTenure ? minTenure)
for(i = 0; i < nArray.size(); i++){
if(nArray [i].fitness > BEST.fitness){ //Aspiration Criteria
CURRENT ? nArray [i];
BEST ? CURRENT;
tabuList.add(CURRENT);
update tabuList;
iter = 0;
break;
}end if
if(nArray [i] is not a tabu){
CURRENT ? nArray [i];
update tabuList;
break;
}end if
}end for
if (iter > iterDiversification){
generate a solution randomly, DIVER;
CURRENT ? DIVER;
reset tabuList;
}end if
iter++;
}while iter < iterMax
BEST.printSolution();
}end procedure
Given the area allotment model, neighborhood generation and the tabu search
algorithm, the overall optimization procedure can be depicted as follows:
103
Read
problem data
START
Optimize area
allotments
Eq.s 6.6 ? 6.8
Using LINGO
?Facility data
?Department data
?Adjacency matrix
Generate a random
solution
?Facility data
?Area allotments
?Adjacency matrix
?Solution representation
?Fitness function
?Tabu tenure
?Candidate list strategies
?Aspiration criterion
DiversificationTermination criteria
Generate neighborhood
Update the best solution
N
Y
N
Report the best solution
END
Y
Figure 6.3. Overall optimization procedure.
6.3. Experimentation
In this section, the results of the experimentation are reported. In order to test the
effectiveness of the optimization procedure, two example problems with n = 12 and n =
20 are generated. For both problems, the revenue data and area requirements are
104
generated randomly. The space elasticity data for the departments are determined by Irion
et al.?s approach. For each department, an assumption is made as to how responsive the
revenue of a department is to a change in the department area (e.g. unresponsive,
moderately responsive and responsive). Then a random number within the respective
boundaries for the space elasticity is generated. The revenue coefficients (r
i
) are also
generated randomly, along with the zone requirements, d
i
. The area requirements of the
departments for the 12 department problem are determined to create a test case in which
the aspect ratio constraint is difficult to satisfy. For the 20 department problem, however,
there is not too much discrepancy among the area requirements of the departments. To
illustrate, the ratio of the largest department to the smallest department for n = 12 is
around 4.5, whereas the same ratio for n = 20 is only 2.5.
For the 20 department problem, the same adjacency matrix from the 20
department problem presented in Chapter V is used. The adjacency matrix for the 12
department problem is the first twelve rows and columns of the adjacency matrix of the
20 department problem. Problem data for the n = 12 and n = 20 problems are provided in
Appendix III along with the optimal area allotments.
The dimensions of the facility are the same for both test problems: the facility has
a length of 25.5 units and a width of 17 units, yielding 433.5 sq. units of available space.
The minimal area requirements for the 12 department problem and 20 department
problems are 369 sq. units and 375 sq. units, respectively.
For the 12 department problem, the termination criterion of 5K non-improving
moves yielded the same (presumably optimal) solution in all trials with all different
105
fitness functions, as will be discussed in more detail. Since the execution times are
relatively small with the 12 department problem, trial and error was the method of choice
in determining the termination criterion. For the 20 department problem, however, a more
methodical approach is employed to determine the termination criteria. In order to
determine proper values of the termination criterion (number of consecutive non-
improving moves) with different fitness functions, an experiment is performed by using
the values 1K, 2K, 5K, 10K and 20K. It is found that termination criterion of 1K or
greater non-improving moves converge to the same fitness value for F
r
, whereas for F
a
and F
f
, it is observed that as the termination of the search is deferred, the average
performance increases. Figure 6.4 shows the increase in the average fitness value versus
various termination criteria. After analyzing the plot, the termination criteria for the
fitness function are set to 5K and 10K non-improving moves for F
a
and F
f
, respectively.
To verify whether there is a difference among the aforementioned values of the
termination criterion, an F-test was performed using the observations from ten trials at
each termination criterion for both F
a
and F
f
. The F-test revealed that the difference
among the average fitness obtained at different values of termination criterion is
significant (p-values are less than
4
10
?
for both F
a
and F
f
). Next, a t-test reveals that the
difference between the termination criteria of 5K and 10K is insignificant for F
a
(p =
0.14) so the termination criterion is set at 5K. Similarly, for F
f
, the difference between the
termination criteria of 10K and 20K is found insignificant (p = 0.25), so the termination
criteria is set at 10K.
106
0.790
0.795
0.800
0.805
0.810
0.815
0.820
0 5 10 15 20
T ermination Criteria ?10
3
Av
e
r
ag
e F
i
t
n
e
s
s
12200
12300
12400
12500
12600
12700
12800
0 5 10 15 20
T ermination Criteria ?10
3
A
v
er
ag
e F
i
t
n
es
s
(a) F
a
(b) F
f
Figure 6.4. Number of allowed non-improving moves vs. average fitness function.
In tables 6.1 and 6.2, the first column provides information regarding the
configurations of the experiment. The first letter indicates the fitness function used (F for
adjacency score and revenue combined, A for adjacency score only and R for revenue
only). The second letter indicates the revenue function used for area allotments, which is
exponential throughout the experiments. The last digit shows the exponent of the penalty
function (?). In the results which are provided in the second half of both tables 6.1 and
6.2, the penalty function is not used. For the 12 department example problem, the severity
of the penalty function is much greater than that of the 20 department problem, as less
severe penalties on aspect ratio violation do not yield feasible solutions. The best layouts
obtained for all configurations (six for n = 12 and another six for n = 20) are provided in
Appendix III.
107
Table 6.1. Best solutions found, n = 12.
*
Configuration Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
FE3 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 7803.565
AE3 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697
RE3 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143
FE0 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578
AE0 0 6 4 12 8 2 1 7 9 10 3 11 5 8, 9 11478.845 0.906 0.417 0.906
RE0 0 4 9 5 7 10 8 11 2 12 6 3 1 9, 10 13116.610 0.133 0.667 13116.610
Table 6.2. Best solutions found, n = 20
Configuration Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
FE1 0 3 18 13 19 17 10 12 9 5 8 15 16 6 20 14 11 7 2 4 1 14, 17 15888.820 0.805 1.000 12785.594
AE1 0 3 17 12 14 9 18 7 19 8 5 20 13 16 6 15 2 11 10 4 1 15, 18 14872.403 0.819 1.000 0.819
RE1 0 1 16 6 17 11 20 15 5 14 8 7 3 13 10 12 18 9 19 4 2 14, 17 16493.550 0.404 1.000 16493.550
FE0 0 16 20 5 8 19 11 14 9 12 7 18 3 6 10 15 1 2 17 13 4 14, 15 16150.165 0.822 0.500 13274.214
AE0 0 7 18 3 4 2 16 1 15 20 5 8 11 19 12 14 9 13 17 6 10 15, 20 13042.422 0.839 0.550 0.839
RE0 0 1 3 6 17 5 18 11 15 20 8 19 10 13 9 12 14 7 16 4 2 15, 16 16493.550 0.298 0.550 16493.550
In tables 6.1 and 6.2, the best solutions found for each configuration out of ten
trials are reported. As seen in tables 6.1 and 6.2, for all six different configurations, a
feasible solution can be found when the penalty function is used. Further, in all trials
across all configurations, feasible solutions are found by tabu search with the penalty
function. The summary of all trials are presented in Appendix III as well.
Tables A15 through A20 show that in all trials with n = 12, tabu search finds the
same fitness value, suggesting that the solutions reported in table 6.1 may be the optimal
solutions for the problem.
For the 20 department problem, reaching the same fitness value over the trials of
the configurations involving the adjacency score in the fitness function (configurations
starting with F and A, using the fitness functions F
a
and F
f
) could not be achieved. The
differences between average fitness functions for both configurations FE1 and FE0 and
*
ARP column shows the value of the penalty function; a value of 1.00 means all departments meet their
aspect ratio requirement.
108
configurations AE1 and AE0 are significant at a 1% level of confidence. For the
configurations involving the revenue function only, the same objective function is readily
achieved over all trials, but with different solutions. The summary of all trials for the six
configurations for n = 20 are provided in tables A21 ? A26.
The difficulty of attaining the same best solution within configurations is mainly
attributed to the fact that the search space is much larger with the 20 department problem.
In fact, the search space of the 20 department problem is five billion times larger than
that of the 12 department problem. In Table 6.3, the average execution times of the tabu
search in seconds for the twelve configurations are listed. For the 12 department problem,
average execution time was around 2 minutes, and the difference among the execution
times using different fitness functions was negligible. However, with the 20 department
problem, the differences among execution times for the different fitness functions
become more apparent, and overall, more than sixteen times longer than the 12
department problem on average. Even with these increases in average execution times,
the number of solutions evaluated is less than one trillionth of all possible solutions. An
interesting point is that when the penalty term is removed from the fitness function the
execution time decreases quite significantly for n = 20 with the fitness functions F
f
, and
F
a
. Removing the penalty term from the fitness function does not have a significant effect
on execution time for n = 12. This situation may be explained by the fact that enforcing
the penalty function for n = 20 makes the problem more difficult to solve, however since
the termination criterion of 5K provides ample opportunity for a thorough search for n =
12, the effect of removing the penalty function is undetectable.
109
Table 6.3. Average execution time in seconds.
n = 12 n = 20
Configuration Execution Time Configuration Execution Time
RE3 111.899 RE1 211.163
AE3 129.475 AE1 2204.549
FE3 139.259 FE1 4497.986
RE0 117.908 RE0 216.860
AE0 147.743 AE0 1769.080
FE0 127.122 FE0 3905.753
Table 6.4. Evaluation of the quality of the solutions, n = 12.
?
n = 12 Aspect ratio
w/o Aspect
Ratio
r
F
13116.610 13116.610
a
F
0.948 0.948
f
F
12,434.546 12,434.546
r
F
11,804.143 13,116.610
Deviation 10% 0%
a
F
0.697 0.906
Deviation 26% 4%
f
F
7803.565 11253.578
Deviation 37% 9%
In Table 6.4, the solution quality with respect to the theoretical upper bounds on
different fitness functions is provided for n = 12. The entry
r
F is simply the value of the
objective function obtained by solving the model given by equations 6.6 through 6.8. The
formulation for
a
F is provided earlier in Chapter V. Lastly,
f
F is simply
a
F
r
F . It
should be noted that since the upper bound on
f
F is calculated disregarding the possible
?
%Deviation calculated as: 100(UpperBound ? RealizedFitness)/(UpperBound)
110
interaction between the revenue and the adjacency score, it is rather a rough upper bound.
As presented in Table 6.4, with the 12 department problem, using the aspect ratio
constraint has a considerable impact on finding the optimal solution. When the penalty
function is in effect, the deviation from the upper bound can be as high as 37%, as
indicated in Table 6.4. When the penalty function is removed from the fitness function
formulation, the discrepancy between the upper bound and the best fitness function
reduces to zero from 10% in the case of
r
F , which means optimality is achieved.
Similarly, for
a
F and
f
F the deviation from upper bound reduces by 22% and 28%
respectively, suggesting that the 12 department problem is severely restricted by the
aspect ratio constraint.
As stated previously, for the fitness functions involving the adjacency score, tabu
search is unable to find solutions yielding the same fitness function for n = 20. For this
reason, the performance evaluation of the tabu search in comparison with the upper
bounds on the components of the fitness function is done in two different levels: the best
solution found and the average fitness value for each configuration for n = 20 (see Table
6.5). Whether the aspect ratio is enforced or not, for the trials where the fitness function
is
r
F , optimality is achieved in all trials. The deviations from the upper bound when
a
F
is used as the fitness function result from the underachievement of satisfying desirable
department adjacencies due to other considerations, such as avoiding aspect ratio
violations. This can be verified by the fact that when the penalty function is not used, the
deviation from the upper bound reduces to 11% from 13% for the best solution found and
15% from 18% on average.
111
Table 6.5. Evaluation of the quality of the solutions, n = 20.
?
n = 20 Aspect ratio
w/o Aspect
Ratio
r
F
16,493.550 16,493.550
a
F
0.935 0.935
f
F
15,421.469 15,421.469
r
F
16,493.550 16,493.550
Deviation 0% 0%
a
F
0.819 0.839
Deviation 12% 10%
f
F
12,785.594 13,274.214
Best
Deviation 17% 14%
r
F
16,493.550 16,493.550
Deviation 0% 0%
a
F
0.810 0.829
Deviation 13% 11%
f
F
12,630.505 13,184.637
Average
Deviation 18% 15%
When the choice of fitness function is
f
F , the deviations from the theoretical
upper bound are 17% when the penalty function is employed and 14% when the penalty
function is not used. For the best solution found, the value of the revenue part of the
fitness function is 15,889, and the adjacency score is 0.805, both of which are below the
values when there is no interaction effect (e.g. cases where the fitness function is either
r
F or
a
F ). These values are 3.7% and 13.9% below from
r
F and
a
F , respectively.
?
The first part of Table 6.5. (above the double line) lists the upper bounds on the revenue and the adjacency
satisfaction. The second part of the table (in between the double lines) lists the best solutions found for each
configuration and provides % deviations for each configuration. The last section of the table evaluates the
performance of the tabu search on average.
112
Actually, when the best solutions found in trials which revenue and adjacency score are
considered separately ( 493,16=
r
F and 819.0=
a
F ), one would expect a fitness value of
()507,13819.0493,16 ===
arf
FFF . Thus, 6% of the deviation from the upper bound can
be explained by the interaction of the revenue and the adjacency score components of the
fitness function, still leaving 11% unexplained. Considering the fact that the difference
between the average performances of configurations FE1 and FE0 is only 4%, for this
problem instance it is easy to find a feasible solution. However, the penalty function is
essential in directing the search to feasible solutions from the aspect ratio constraint point
of view as none of the trials result in a feasible solution for configuration FE0 (i.e. when
the penalty function is not used with the fitness function
f
F ).
Given the area allotments (see Appendix III), the theoretical lower and upper
bounds on the aisle width are calculated as 47.0=
a
w and 34.1=
a
w from equations 6.16
and 6.17. However, during experimentation, for both problems the actual bounds used on
the aisle width are 75.0=
L
a
w and 00.1=
U
a
w , in order to provide a practical store design.
Table 6.6 below shows the average aisle width obtained for the configurations across ten
trials. In all configurations except FE3, AE3, and RE3, similar aisle widths are observed.
The reason why aisle width in configurations FE3, AE3 and RE3 is significantly different
than the rest of the configurations is as follows: In order to maintain the aspect ratio
feasibility tabu search clusters the small departments inside the racetrack, and pushes the
larger departments outwards resulting in a smaller inner region, hence a wider aisle.
113
Table 6.6. Average aisle width.
n = 12 n = 20
Configuration Aisle Width Configuration Aisle Width
RE3 0.984 RE1 0.763
AE3 0.955 AE1 0.772
FE3 0.955 FE1 0.769
RE0 0.758 RE0 0.788
AE0 0.803 AE0 0.788
FE0 0.782 FE0 0.785
In figures 6.5 and 6.6 the progress of the fitness function and its components is
provided as a function of iteration counter, t. As expected, in both cases the frequency of
improvements in the fitness function is very high in the first few hundred steps, and as
the search progresses, the frequency of improvements reduces.
n = 12
0
0.2
0.4
0.6
0.8
1
1.2
1.4
0 200 400 600 800 1000 1200 1400 1600
t
Revenue 10e4
Adjacency Score
ARP
Fitness 10e4
Figure 6.5. Fitness, revenue, adjacency and ARP vs. number of iterations, n = 12.
114
n = 20
0
0.2
0.4
0.6
0.8
1
1.2
1.4
1.6
1.8
0 2000 4000 6000 8000 10000 12000 14000
t
Revenue 10e4
Adjacency Score
ARP
Fitness 10e4
Figure 6.6. Fitness, revenue, adjacency and ARP vs. number of iterations, n = 20.
Table 6.7 presents the effects of different initial solutions on the performance of
the tabu search. Configuration FE1 yields the most deviation from the configuration
average on the maximum side where the worst solution obtained is 1.67% worse than the
configuration average. Configuration AE0 yields the most deviation on the minimum
side, where the best solution obtained is 1.25% better than the configuration average.
Based on these values, it can be claimed that the variation due to the different initial
solutions is quite small, and the tabu search is robust to the changes in the initial solution.
Table 6.7. Performance evaluation with respect to average.
Configuration
Number of
Replications Minimum
%Deviation
from Average Maximum
%Deviation
from Average Average
FE1 10 12419.523 1.67% 12785.594 1.23% 12630.505
AE1 10 0.799 1.32% 0.819 1.13% 0.810
FE0 10 13065.476 0.90% 13274.214 0.68% 13184.637
AE0 10 0.819 1.21% 0.839 1.25% 0.829
An interesting point to note that the gap between the worst and the best solution
for configuration FE1 is about 3%, whereas the same gap for configuration FE0 is only
1.5%. The only difference between these two configurations is the use of the penalty
115
function. When this result is combined with the average execution times of
configurations FE1 (75 minutes) and FE0 (65 minutes), it seems that the penalty function
makes the problem more difficult to solve as it constricts the solution space. However,
the use of penalty function is of paramount importance to obtain practical department
shapes. A similar pattern can also be observed for configurations AE1 and AE0.
6.4. Varying the available store area
The results provided in Section 6.3 are obtained using total retail space of
17?25.5 = 433.5 sq. units. Another set of experiments is performed using a smaller and a
larger retail area by modifying the dimensions of the retail space to 16?24 = 384 sq. units
(12% smaller) and 18?27 = 486 sq. units (25% larger), respectively. The aspect ratio
( WL
f
=? ) for these cases is 1.5, the same as previously. As stated earlier, the total
minimum area requirements are 369 and 375 sq. units for n = 12 and n = 20, respectively.
The department data and the adjacency matrices used for n = 12 and n = 20 are the same
as in Section 6.3. The only difference is the change made to the right hand side of
constraint given by equation 6.7. Area allotments for these cases are provided in
Appendix III as well.
The additional area allotments are generally made in decreasing order of space
elasticities of departments,
i
? , though there are exceptions. The excess area allotments
are also affected by the revenue multiplier,
i
r . For instance, for the smallest total available
area (24?16 = 384 sq. units), the excess space is shared among departments E, G and K
for n = 12. Departments E and K have the highest space elasticities for this set of
116
departments, and department G?s unit revenue is the highest among all
i
r ?s for n = 12. By
the same token, departments C, K and P share the excess space for the available area of
384 sq. units when n = 20. In spite of higher space elasticities than that of department
C?s, departments E and Q do not receive additional area until the available space
increases to 433.5 sq. units. Comparing the minimal area requirements of departments E
and Q to department C?s minimal area requirement, the increased space would return a
smaller contribution for departments E and Q than department C due to their larger
minimal area requirements. That is the reason departments E and K receive no additional
space in spite of their higher space elasticities. As more excess space becomes available,
the departments with smaller space elasticities start receiving additional area, and those
departments already receiving additional area increase their amount of additional space.
However, no matter how much excess space becomes available, the departments with
space elasticity smaller than 0.1 do not receive additional space. As given in the model by
equations 6.6 through 6.8, the aisle also competes for additional space. For both problems
with n = 12 and n = 20, the aisle does not receive additional area allotment when the store
area is 24?16. Thereafter the aisle area increases consistently for both cases as more
excess space becomes available.
In Figure 6.7, excess area allotments for departments (the aisle is considered a
department) are provided for n = 12 and n = 20. In the charts, each color in each column
shows the percent increase in department area with respect to the department?s minimal
area requirement as more excess space becomes available with the increasing store area.
For instance, there is not a column corresponding to department B in Figure 6.7(a), which
117
means that department B did not receive any additional space no matter how much excess
space becomes available. Department G, on the other hand, starts receiving additional
space as soon as excess space becomes available, and continue to increase in size as the
total store area increases.
As can be verified by Figure 6.7, there are only three departments receiving
additional space for n = 12 and n = 20 when the total available area is 24?16 = 384 sq.
units. This number increases to seven for both problems for total available area of
25.5?17. When the total available area is increased to 27?18 = 486 sq. units, the number
of departments with excess area allotments becomes eight and ten for n = 12 and n = 20,
respectively.
118
0%
20%
40%
60%
80%
100%
120%
140%
AisleABCDEFGHI JKL
%
I
n
c
r
eas
e o
v
er
m
i
n
i
mu
m ar
e
a
r
e
q
u
i
r
em
en
t
24?16 25.5?17 27?18
(a) n = 12
0%
20%
40%
60%
80%
100%
120%
140%
160%
180%
Ai
s
l
e
A B C D
E F G
H
I J
K
L
M
N O
P
Q R
S T
%
I
n
cr
ea
s
e
o
v
er
m
i
n
i
m
u
m
ar
ea r
e
q
u
i
r
e
m
e
n
t
24?16 25.5?17 27?18
(b) n = 20
Figure 6.7. Increase in area allotments as a percentage of minimum required area.
The entire set of experiments is performed using the same lower and upper
bounds on the width of the aisle, 75.0=
L
a
w and 00.1=
U
a
w . In Tables 6.8 and 6.9, the
average aisle widths with different store areas under different fitness configurations are
provided for n = 12 and n = 20, respectively. When we examine the numbers, we can
verify that for the twelve department problem, aisle widths are scattered across
L
a
w and
119
U
a
w . In addition, for n = 12, the aisle width is significantly larger when the aspect ratio
penalty is enforced. As explained earlier, in order to maintain the aspect ratio
requirements, the tabu search clusters smaller departments inside the racetrack, leading to
a wider aisle. For the 20 department problem, on the other hand, the aisle width is
between the values of 0.76 and 0.82, independent of whether the aspect ratio is enforced.
When the aisle is narrower a larger number of departments are inside the racetrack.
Allowing more departments inside the racetrack increases the chances for those
departments to be adjacent to the other departments, leading to better adjacency scores.
Hence, in order to obtain better adjacency scores, the tabu search tries to assign as many
departments as possible inside the racetrack. This effort eventually results in the smaller
aisle width range near the lower bound on the aisle width.
Table 6.8. Comparison of average aisle widths n = 12.
n = 12 Store Area
Configuration 24?16 25.5?17 27?18
RE3 0.854 0.984 0.920
AE3 0.897 0.955 0.996
FE3 0.897 0.955 0.893
RE0 0.788 0.758 0.821
AE0 0.812 0.803 0.813
FE0 0.856 0.782 0.770
Table 6.9. Comparison of average aisle widths n = 20.
n = 20 Store Area
Configuration 24?16 25.5?17 27?18
RE1 0.759 0.763 0.805
AE1 0.762 0.772 0.775
FE1 0.759 0.769 0.794
RE0 0.816 0.788 0.802
AE0 0.817 0.788 0.802
FE0 0.783 0.785 0.792
120
Table 6.10. Comparison of results for n = 12.
n = 12 Store Area
Configuration 24?16 25.5?17 27?18
RE3 12056.070 11804.143 12691.285
AE3 0.756 0.697 0.720
FE3 8364.325 7803.565 8176.930
RE0 12782.020 13116.610 13403.970
AE0 0.905 0.906 0.906
FE0 10905.284 11253.578 11885.294
In order to be able to make a fair comparison of results under different retail area
constraints, the tabu search parameters are kept the same as in section 6.3. Table 6.10
provides the summary of experiments for n = 12. Given that the adjacency matrices in all
three area settings are the same, one would expect a steady increase in the value of fitness
function for
f
F due to the increase in revenue part (configuration FE3), but this is not the
case. Actually, the change in the size of the departments affects all fitness functions
similarly. When the aspect ratio constraint is in effect, the fitness values obtained for the
available store area of 25.5?17 are the worst with respect to the upper bounds for all
fitness functions used. The evaluation of the solution quality with respect to the upper
bounds on
r
F ,
a
F and
f
F are provided in Table 6.11. These results suggest that for n =
12, the store area of 25.5?17 is the most difficult case in terms of satisfying the aspect
ratio requirements. When we take a closer look at the fitness values obtained, we can
verify that the main cause of these deviations from the theoretical upper bound is the
number of misplaced departments with respect to their zone requirements. To illustrate,
the gap between the upper bound on adjacency score and the adjacency components of
121
the fitness functions of these three cases are 25%, 26% and 27%, for available areas of
24?16, 25.5?17 and 27?18, respectively. The same deviations for the revenue component
are 8%, 15% and 12%, respectively. These departments cannot be placed in their
preferred regions in order to prevent aspect ratio violations. The pictorial representation
of these misplacements of departments is provided in Figure 6.8. The same pattern can
also be observed when the adjacency satisfaction is the only consideration in determining
the quality of a layout. From the adjacency matrix, it can be verified that adjacency
between departments A and E is highly desirable, but tabu search is unable to find a
solution where these two departments are adjacent and there is no aspect ratio violation.
When the penalty function is not used (AE0 rows in Table 6.10), for all cases we obtain
similar adjacency scores in terms of deviation from the theoretical upper bounds. Finally,
for the fitness functions of
a
F and
f
F , the termination criteria were increased to 50K (ten
times larger than the actual termination criterion) non-improving moves to see whether a
better solution can be found for these configurations. This proved to be futile.
With the fitness function
r
F , the deviation from the upper bound is the highest for
the retail area of 25.5?17 when the aspect ratio constraint is enforced. This result is
consistent with the results found by using fitness functions
a
F and
f
F . As with the
a
F
and
f
F , the increase in the termination criterion does not yield a better solution for the
fitness function
r
F . However, when the aspect ratio is not enforced, the upper bound is
reached for all facility sizes examined.
122
(a) Available Area: 24?16 (b) Available Area: 25.5?17
(c) Available Area: 27?18
Figure 6.8. The best layouts obtained for n = 12, F
f
, aspect ratio enforced.
Table 6.11. Evaluation of the quality of the solutions, n = 12.
n = 12 Aspect ratio
w/o Aspect
Ratio Aspect ratio
w/o Aspect
Ratio
r
F
12,782.020 12,782.020 13,403.970 13,403.970
a
F
0.948 0.948 0.948 0.948
f
F
12,117.355 12,117.355 12,706.964 12,706.964
r
F
12,056.070 12,782.020 12,691.285 13,403.970
Deviation 6% 0% 5% 0%
a
F
0.756 0.905 0.720 0.906
Deviation 20% 5% 24% 4%
f
F
8,364.325 10,905.284 8,176.930 11,885.294
Deviation 31% 10% 36% 6%
As previously, for n = 12 in all trials the same fitness function value is obtained
for all different fitness function configurations. However, this is not the case for n = 20
123
and thus the comparisons are provided on the basis of both average and the best solutions
obtained. Tables 6.12 and 6.13 tabulate these results based on 10 trials for each
configuration.
Table 6.12. Comparison of average results for n = 20.
Store Area
Configuration 24?16 25.5?17 27?18
RE1 15989.050 16493.550 16914.630
AE1 0.799 0.810 0.810
FE1 11872.020 12630.505 13065.496
RE0 15989.050 16493.550 16914.630
AE0 0.826 0.829 0.836
FE0 12710.371 13184.637 13618.921
Table 6.13. Comparison of best results for n = 20.
Store Area
Configuration 24?16 25.5?17 27?18
RE1 15989.050 16493.550 16914.630
AE1 0.809 0.819 0.820
FE1 12061.070 12785.594 13262.997
RE0 15989.050 16493.550 16914.630
AE0 0.834 0.839 0.843
FE0 12769.943 13274.214 13794.568
Unlike the 12 department example, the average and the best fitness function
values increase as the available retail area increases for configurations FE1 and FE0
(fitness function
f
F ). This steady increase is mainly attributed to the increase in revenue
figure, as the differences among the values of fitness function
a
F (configurations AE1
and AE0 for retail areas of 16?24, 17?25.5 and 18?27) are quite small. The similarity
among the adjacency scores under different available area constraints can be attributed to
the larger number of adjacent department possibilities and easier to satisfy aspect ratio
124
constraints. The adjacent pairs of departments can be chosen in 3.1?10
15
and 1.3?10
45
different ways for n = 12 and n = 20, respectively. The very reason causing the 20
department problem to be more difficult to solve for adjacency maximization makes it
more robust from an adjacency satisfaction point of view to the changes in department
areas.
(a) Available Area: 24?16 (b) Available Area: 25.5?17
(c) Available Area: 27?18
Figure 6.9. The best layouts obtained for n = 20, F
f
, aspect ratio enforced.
In figure 6.9, the best layouts obtained for store areas of 16?24, 17?25.5, and
18?27 for n = 20 using the fitness function of F
f
are provided. According to equation
6.12, the misplaced departments with respect to their zone preferences in these solutions
are departments M and N in figures 6.9(a) and 6.9(b) and department G in 6.9(c). The
location of department N is dictated by the high adjacency preference of department N to
125
both departments I and K. Department M does not have strong adjacency relationships
with the remaining departments, and its contribution to the revenue is minimal. Hence, it
is used like a filler, for the sake of satisfying other adjacency opportunities and region
preferences of other departments. These misplacements are the root cause of the
deviations from the upper bound on revenue portion of the fitness function. The lowest
adjacency score in these layouts is 0.795, obtained for the available store area of 18?27.
When we take a closer look at the adjacent pair of departments in Figure 6.9(c), it
becomes evident that for only this solution, departments C and F cannot be placed
adjacent to each other, and, the closeness rating is ?absolutely necessary? for this pair of
departments. The layouts given in figures 6.9(a) and 6.9(b) satisfies all of the adjacency
requirements for department pairs where
ij
c = 125. Further, none of the layouts provided
in figure 6.9 contains an adjacent department pair for which 0<
ij
c . This suggests that in
spite of the small differences in overall adjacency scores, tabu search is able to satisfy the
most basic adjacency requirements even if the adjacency score is not the only
consideration in determining the quality of a layout.
For the 20 department problem, when revenue is the only criterion used in
evaluating the layouts, the upper bound on the fitness function is reached in both
configurations RE1 and RE0 for both retail areas 16?24 and 18?27 in all trials. However,
this is not the case for fitness functions
a
F and
f
F . The evaluation of the solution quality
with respect to the upper bounds on
r
F ,
a
F and
f
F is provided in Table 6.14. Due to
reasons explained previously, the deviations from the upper bounds for the retail areas of
126
16?24 and 18?27 are very similar to those reported in Section 6.3; variability in the retail
area and department allotments does not have a significant effect on the performance of
the tabu search for this problem instance.
Table 6.14. Evaluation of the quality of the solutions, n = 20.
Store Area 16?24 18?27
n = 20 Aspect ratio
w/o Aspect
Ratio Aspect ratio
w/o Aspect
Ratio
r
F
15,989.050 15,989.050 16,914.630 16,914.630
a
F
0.935 0.935 0.935 0.935
f
F
14,949.762 14,949.762 15,815.179 15,815.179
r
F
15,989.050 15,989.050 16,914.630 16,914.630
Deviation 0% 0% 0% 0%
a
F
0.809 0.834 0.820 0.843
Deviation 13% 11% 12% 10%
f
F
12,061.070 12,769.943 13,262.997 13,794.568
Best
Deviation 19% 15% 16% 13%
r
F
15,989.050 15,989.050 16,914.630 16,914.630
Deviation 0% 0% 0% 0%
a
F
0.799 0.826 0.810 0.836
Deviation 15% 12% 13% 11%
f
F
11,872.020 12,710.371 13,065.496 13,618.921
Average
Deviation 21% 15% 17% 14%
6.5. Conclusion
In this chapter, first, various possible revenue formulations are discussed based on
the literature in shelf space allocation and the exponential revenue function is selected to
be used with the variable area departments. Next, the solution representation and the tabu
search algorithm devised in Chapter V are modified to accommodate the variable aisle
width and non-zero aisle areas. The overall optimization procedure is then presented.
127
Two example problems are devised to investigate the effects of magnitude of the
problem, variability in department areas, and interaction of the components of the fitness
function. It is shown that for a problem with a small number of departments, tabu search
is able to consistently reach the same solution, in a relatively short time. However, it
takes much longer for a problem with a large number of departments to terminate the
search. The reason for that is twofold: first, the termination criterion is kept intentionally
long in order to accommodate a more thorough search, and the size of the neighborhood
for a problem involving more departments is larger, which makes the evaluation time of
the neighborhood longer.
The second outcome of the experimentation is that when the variability in size of
the departments is high, severity of the penalty function has to be increased in order to
obtain a feasible solution. Maintaining aspect ratios for the departments has an adverse
effect on the fitness function value achieved since the penalty function reduces the search
space.
In addition, when the facility size grows, the area allotments of departments
change. This alters the placement of departments within the store drastically. The change
in department sizes also affects the adjacencies realized and conformity of the
departments? actual locations with respect to their desired zone preferences.
Finally, an interaction is present between the adjacency score and the revenue
parts of the fitness function. When either revenue or adjacency score is used to evaluate
the candidate solutions as the sole criterion, the solutions provide better values for the
criterion used than that of the combination of both.
128
VII. CONCLUSIONS AND FUTURE RESEARCH
7.1. Conclusions
This research proposes a model and a solution approach for the retail facility
layout problem. In doing so, the racetrack layout is chosen as the generic layout
configuration. The quality of a layout is evaluated considering two criteria: the degree of
adjacency satisfaction among the departments and the revenue generated by the
departments. For the optimization of the proposed model, a mixed integer non-linear
programming (MINLP) model is devised first. Demonstrating the shortcomings of the
MINLP model, a constructive heuristic and an improvement heuristic based on tabu
search framework is developed assuming constant department areas and zero aisle area.
Next, variability on department and aisle areas are introduced and a revenue model is
proposed for the area allotment. Finally, the tabu search algorithm devised earlier is
modified to accommodate the requirements of the non-zero aisle area.
The MINLP model has several shortcomings. The non-convex departmental
shapes cannot be represented with the MINLP model, thus it was necessary to provide
excess space beyond the total area requirement. As the experimentation proved, the closer
the total available area to the actual area requirements, the more time is required to solve
the model to optimality. In addition, for larger problem instances, the model could not
129
find the optimal solution in a reasonable time. Moreover, areas of the departments deviate
from their required values as the area constraints can only be represented by
approximate constraints because of the linearity considerations in the constraint set.
Lastly, the objective function of the MINLP model is only composed of the revenue
portion of the objective function of the original model. As a result of increasing
computational time with the larger problem instances, the exact objective function used
elsewhere in this research is not employed in the MINLP formulation.
The constructive heuristic for the design of the retail store performed very
satisfactorily on the revenue side of the objective function however, it fails on adjacency
satisfaction and maintaining aspect ratio constraints. With the greedy nature of the
constructive heuristic, it was impossible to consider aspect ratio constraints, and myopic
rules in selecting adjacent department pairs did not provide satisfactory performance.
These results led to the design of the improvement heuristic.
In order to be used in conjunction with the improvement heuristic, a solution
representation is devised. The solution representation explicitly considers the
requirements of the generic layout and inspires from the FLEXBAY representation. The
flexibility of having non-convex department shapes such as L and U is an extension that
was not possible earlier in the context of continuous representation. In addition, with a
little effort (i.e. by estimating aspect ratios of the departments without fully constructing
the solution), the solution representation can identify those solutions that will lead to
aspect ratio violations. Thus, tabu search can eliminate those solutions from consideration
without completely evaluating them for the constant area case.
130
The improvement heuristic is designed using the tabu search framework.
Although tabu search does not guarantee optimality, its popularity in the combinatorial
optimization literature and the limitations of the MINLP model and the constructive
heuristic made the tabu search a viable alternative in solving the model designed in this
research. As proven by the comparison of results, the tabu search is actually proved to be
providing the optimal solutions in some cases. Features of tabu search such as candidate
list strategies and intensification/diversification cycles are effectively used to create a
tractable and efficient search algorithm.
The research is then extended by introducing variability to the area allotments of
the departments and the aisle network. For the area allotments, a widely accepted revenue
formulation from the shelf space allocation literature is used. It should be noted that the
solution approaches developed in this research do not entirely depend on the choice of the
revenue function, the solution approach can be used with any form of the revenue
function. Having non-zero aisle area required minor modifications on the solution
representation designed for the zero aisle area case, but it also provided a reduced size of
the neighborhood in the context of the tabu search.
As stated earlier, this research is one of the first studies considering the retail store
layout problem. Hence, the solution methodologies devised cannot be compared with the
existing literature in terms of computational experience. However, the tabu search based
solution approach yields good solutions in reasonable times for real size problems. In
order to provide a basis of comparison for future research, execution times for all test
problems and for all solution approaches are provided.
131
The classical facility layout point of view considers the area allocated to the aisles
as a waste to be minimized. Moreover, aisles are usually assumed to have zero area.
However, aisles in a retail setting serve two important purposes: to create an enjoyable
shopping atmosphere and to provide display space for promotional items. The effect of
aisle width on the shopping atmosphere is difficult to formulate, however, the aisle space
is thought of as another department for its use as a display area for promotional items,
and aisle area is treated as a variable competing for additional area allotment with the rest
of the departments. The width of the aisle is allowed to fluctuate within its upper and
lower bounds to accommodate alternative department configurations. This is a
completely new approach in facility layout literature as the aisles are either assumed non-
existent or treated as a hard constraint.
7.2. Future Research
This research is one of the very first attempts to propose a model and a solution
approach for the block layout of a retail store. It was necessary to make many
assumptions to devise the model and the solution approach. Future research can relax the
assumptions made here to better address the needs and specifications of retail store
reality. One apparent improvement opportunity to this end is the addition of another
entrance location to the retail store. The majority of major retail stores across the US are
located within shopping malls at the end points of the whole complex (as anchors) (Carter
and Vandell, 2005). Normally, retail stores have at least two entrances, one from the
132
outside, and the other from outside or inside the mall. The addition of a second entrance
location will enhance the ability of the model to capture the real world.
Another research opportunity for future research might be investigation of the
relationship between the department areas and the revenue. In this research it is assumed
that the relationship between the revenue and the area of the department is one with a
diminishing return, and, based on evidence from the literature, the mathematical
formulation of the relationship is chosen as the exponential model. Validity of this
assumption can be investigated using cross-sectional sales data of a brick and mortar
retail company. It might also be interesting to investigate whether similar departments of
different retail chains have similar responses to the variability of area in terms of sales
revenue. As interesting as this research would be, since the revenue formulation is only
used to determine the area allotments the remaining portion of the optimization procedure
would still be applicable with any given form of the revenue function.
As the results of the experiments proved, there is an interaction between the
adjacency satisfaction and the revenue maximization parts of the objective function. In all
example problems, the best solution found for the objective function of
arf
FFF = , both
r
F and
a
F settle to lesser values than when these objectives are used singly. This yields
room for future research to investigate the bi-objective version of the problem
formulation. The bi-objective version of the problem formulation provides the decision
maker with a set of alternative solutions that might better aid them in making a final
decision.
133
This research is totally dedicated to a single layout configuration, the racetrack
configuration, thanks to its popularity in retail settings. Since the solution representation
is customized to take advantage of the problem structure, it is not applicable to other
layout configurations. Extending the retail store design problem to other layout
configurations will be a natural extension of this research.
Retail facilities can expand to multistory buildings especially in densely populated
regions. A multistory facility version of the problem can address the layout problem of
such retail stores. Due to additional constraints imposed by the structure of multistory
buildings (such as elevator shafts, stairs, etc.), and partitioning of departments to the
stories, the multistory retail store design problem would be an interesting yet challenging
problem.
One of the main assumptions of this research is that the customer traffic density is
highest at near and around the entrance, and the customer traffic density decreases as one
travels away from the entrance. There are only a few studies addressing the traffic
patterns of the customers within retail settings, and those studies are limited to grocery
stores. The study of traffic patterns in other retail settings, to the best of our knowledge,
is not investigated yet. Such an investigation will yield very practical implications on
department placement, promotional product displays, and overall, the design of the retail
store as a whole.
134
REFERENCES
Alagoz, O., Norman, B.A. and Smith, A.E. (2008) Determining aisle structures for
facility designs using a hierarchy of algorithms. IIE Transactions, 40(11), 1019 ? 1031.
Arapoglu, R.A., Norman, B.A. and Smith, A.E. (2001) Locating input and output points
in facilities design ? a comparison of constructive, evolutionary and exact methods. IEEE
Transactions on Evolutionary Computation, 5, 192 ? 203.
Armour, G.C. and Buffa, E.S. (1963) A heuristic algorithm and simulation approach to
relative location of facilities. Management Science, 9, 294 ? 309.
Askin, R.G. and Standridge, C.R. (1993) Modeling and Analysis of Manufacturing
Systems, Wiley, New York, NY.
Barnes, J.W. and Chambers, J.B. (1995) Solving the job shop scheduling problem with
tabu search, IIE Transactions, 27, 257 - 263.
Batty, M. (2003) Agent Based Pedestrian Modeling, working paper, Centre for Advanced
Spatial Analysis, University College London.
Beamon, B.M. (1998) Performance, reliability, and performability of material handling
systems. International Journal of Production Research, 36, 377 ? 393.
Bellenger, D.N., Robertson, D.H. and Hirschman, E.C. (1978) Impulse Buying Varies by
Product, Journal of Advertising Research, 18, 15 ? 18.
Black, S. (2003) J.C. Penney might open first new local store since 1970s. Minneapolis/
St. Paul Business Journal, downloadable from http://www.bizjournals.com/twincities
/stories/2003/02/03/story8.html.
Bookbinder, J.H. and Feyrouz, H.Z. (2001) Direct product profitability and retail shelf-
space allocation models, Journal of Business Logistics 22 183 ? 208.
Bozer, Y.A., Meller, R.D. and Erlebacher, S.J. (1994) An improvement-type layout
algorithm for single and multiple-floor facilities. Management Science, 40, 918 ? 932.
Brown, W.M. and Tucker, W.T. (1961) Vanishing Shelf Space. Atlanta Economic
Review, 9 ? 13.
135
Burkard, R.E., Karisch, S.E. and Rendl, F. (1997) QAPLIB - A quadratic assignment
problem library. Journal of Global Optimization, 10, 391 ? 403.
Burkard, R.E., Cela, E., Karisch, S.E. and Rendl, F. (2002) QAPLIB - A quadratic
assignment problem library at: http://www.seas.upenn.edu/qaplib/.
Cachon, G. and Kok, A.G. (2007) Category management and coordination in retail
assortment planning in the presence of basket shopping consumers. Management Science,
53, 934 ? 951.
Carter, C.C. and Vandell, K.D. (2005) Store location in shopping centers: theory and
estimates. Journal of Real Estate Research, 27, 237 ? 266.
Chen, I.J. and Paulraj, A. (2004) Understanding supply chain management: critical
research and a theoretical framework. International Journal of Production Research, 42,
131 ? 163.
Chopra, S. and Meindl, P. (2006) Supply Chain Management, Third Ed., Prentice Hall,
Boston, MA.
Corstjens, M. and Doyle, P. (1981) A model for optimizing retail shelf space allocations,
Management Science, 27, 822 ? 833.
Cox, Keith K. (1970) the effect of shelf space upon sales of branded products. Journal of
Marketing Research (JMR), 7, 55 ? 58.
Curhan, R. C. (1973) Shelf space allocation and profit maximization in mass retailing.
Journal of Marketing, 37, 54 ? 60.
Davis, M., Kress, K., Lou, X. and Spalding, L. (2000) The future of retail, revitalizing
bricks-and-mortar stores, Institute for the Future Corporate Associates Program. 11(1).
Dreo, J., Petrowski, A., Siarry, P. and Taillard, ?.D. (2006) Metaheuristics for Hard
Optimization, Springer-Verlag, Berlin, pp 47 - 72.
Dreze, X., Hoch, S. J. and Purk, M. E. (1994) Shelf management and space elasticity,
Journal of Retailing, 70, 301 ? 326.
Drezner, T. (1994) Optimal continuous location of a retail facility, facility attractiveness,
and market share: an interactive model. Journal of Retailing, 70, 49 ? 64.
Drezner, Z. (ed) (1995) Facility Location: A Survey of Applications and Methods,
Springer, New York, NY.
136
Drezner, T. (1998) Location of multiple retail facilities with limited budget constraints ?
in continuous space. Journal of Retailing and Consumer Services, 5, 173 ? 184.
Dutta, K.N. and Sahu, S. (1982) A multigoal heuristic for facilities design problems:
MUGHAL. International Journal of Production Research, 20, 147 ? 154.
Eiselt, H.A., Laporte, G. and Thisse, J.-F. (1993) Competitive location models: a
framework and bibliography. Transportation Science, 27, 44 ? 54.
Farley, J.U. and Ring, W.L. (1966) A Stochastic model of supermarket traffic flow,
Operations Research, 14, 555 ? 567.
Frank, R. E. and Massy, W. F. (1970) Shelf position and space effects on sales. Journal
of Marketing Research (JMR), 7, 59 ? 66.
Gendreau, M. and Potvin, J.Y. (2005) Metaheuristics in combinatorial optimization,
Annals of Operations Research, 140, 189 ? 213.
Glover, F. (1986) Future paths for integer programming and links to artificial
intelligence, Computers and Operations Research, 13, 533 - 549.
Glover, F. (1989) Tabu Search Part I, ORSA Journal on Computing, 1, 190 ? 206.
Glover, F. (1990) Tabu Search Part II, ORSA Journal on Computing, 2, 4 ? 32.
Glover, F. (1995) Tabu Search Fundamentals and Uses, donwnloadable from http://leeds-
faculty.colorado.edu/glover/TS%20-%20Fundamentals&Uses.pdf.
Glover, F. and Laguna, M. (1997) Tabu Search, Kluwer Academic Publishers, Boston,
MA.
Glover, F. (1998) Tabu Search ? wellsprings and challenges, European Journal of
Operational Research, 106, 221 - 225.
Gu, J.X., Goetschalckx, M. and McGinnis, L.F. (2006) Research on warehouse operation:
A comprehensive review. European Journal of Operational Research, (in press).
Hajewski, D. (2005) Penney looking a lot like Kohl?s; new freestanding stores seek. The
Milwaukee Journal Sentinel, downloadable from http://www.findarticles.com/p/articles/
mi_qn4196/is_20051002/ai_n15644237/print.
137
Hwang, H., Choi, B. and 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, 97, 185 ? 195.
Irion, J., Al-Khayyal, F. and Lu, J-C. (2004) A piecewise linearization framework for
retail shelf space management models, downloadable from http://www.optimization-
online.org/DB_FILE/2004/10/967.pdf.
Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983) Optimization by simulated
annealing. Science, 220, 671 ? 680.
Kollat D.T. and Willet, R.P. (1967) Customer Impulse Purchase Behavior, Journal of
Marketing Research, 4, 21 ? 31.
Konak, A., Kulturel-Konak, S., Norman, B.A. and Smith, A.E. (2006) A new mixed
integer programming formulation for facility layout design using flexible bays.
Operations Research Letters 34, 660-672.
Koopmans, T.C. and Beckman, M. (1957) Assignment problems and the location of
economic activities. Econometrica, 25, 53 ? 76.
Kulturel-Konak, S. (2002) Facility layout and relayout under uncertainty. Doctoral
Dissertation, Auburn University, Auburn, AL.
Kulturel-Konak, S., Norman, B.A., Coit D.W. and Smith, A.E. (2004) Exploiting tabu
search memory in constrained problems. INFORMS Journal on Computing, 16, 241 ?
254.
Kulturel-Konak, S., Smith, A.E. and Norman, B.A. Bi-objective facility expansion and
relayout considering monuments. IIE Transactions, (in press).
Kulturel-Konak, S., Smith, A.E. and Coit, D.W. (2003) Efficiently solving the
redundancy allocation problem using tabu search, IIE Transactions, 35, 515-526.
Kulturel-Konak, S., Norman B.A., Smith, A.E. and Coit, D.W. (2004) Exploiting tabu
search memory in constrained problems, INFORMS Journal on Computing, 16 241 ?
254.
Kumar, V. and Karande, K. (2000) The effect of retail store environment on retailer
performance. Journal of Business Research, 49, 167 ? 181.
Kusiak, A. and Heragu, S.S. (1987) The facility layout problem. European Journal of
Operational Research, 29, 229 ? 251.
138
Larson, J.S., Bradlow, E.T. and Fader, P.S. (2005) An Exploratory Look at Supermarket
Shopping Paths, Technical Report, Wharton School of Business, University of
Pennsylvania.
Lee, R.C. and Moore, J.M. (1967) CORELAP ? Computerized relationship layout
planning. Journal of Industrial Engineering, 18, 194 ? 200.
Lee W. (1961) Space management in retail stores and implications to agriculture.
Marketing Keys to Profits in the 1960's, edited by Dolva W. K., American Marketing
Association, 523 ? 533.
Levy, M. and Weitz, B.A. (2001) Retailing Management, McGraw-Hill Irwin, Boston,
MA.
Logendran R. and Kriausakul T. (2006) A methodology for solving the unequal area
facility layout problem using distance and shape-based measures, International Journal
of Production Research, 44, 1243-1272.
Loiola, E.M., de Abreu, N.M.M., Boaventura-Netto, P.O., Hahn, P. and Querido, T.
(2007) A survey for the quadratic assignment problem, European Journal of Operational
Research, 176, 657 ? 690.
Mart?nez-de-Alb?niz, V. and Roels, G. (2007) Competing for shelf space. working paper,
Anderson Graduate School of Management, UCLA.
Mart?n-Herr?n, G. and Taboubi, S. (2005) Shelf-space allocation and advertising
decisions in the marketing channel: a differential game approach, International Game
Theory Review, 7, 313 ? 330.
Meller, R.D., and Bozer, Y.A. (1996) A new simulated annealing algorithm for the
facility layout problem. International Journal of Production Research, 34, 1675 ? 1692.
Meller, R.D. and Gau K.-Y. (1996a) The facility layout problem: Recent and emerging
trends and perspectives. Journal of Manufacturing Systems, 15, 351 ? 366.
Meller, R.D. and Gau K.-Y. (1996b) Facility layout objective functions and robust
layouts. International Journal of Production Research, 34, 2727 ? 2742.
Meller, R.D., Narayanan, V. and Vance, P. (1999) Optimal facility layout design.
Operations Research Letters, 23, 117 ? 127.
139
Montreuil, B. (1990) A modeling framework for integrating layout design and flow
network design. Proceedings of the Material Handling Research Colloquium, 43 ? 58,
Hebron, KY.
Misevicius, A. (2005) A tabu search algorithm for the quadratic assignment problem.
Computational Optimization and Applications, 30, 95 ? 111.
Muther, R. (1973) Systematic Layout Planning, Second Ed., Cahners Books, Boston,
MA.
Osman, I.H. (2006) A tabu search procedure based on a random Roulette diversification
for the weighted maximal planar graph problem, Computers & Operations Research, 33,
2526 ? 2546.
Owen, S.H. and Daskin, M.S. (1998) Strategic facility location: A review. European
Journal of Operational Research, 111, 423 ? 447.
Peters, B.A., Klutke, G.-A. and Botsali, A.R. (2004) Research Issues in Retail Facility
Layout Design, Proceedings of Eighth International Material Handling Research
Colloquium, Graz, Austria, 399 ? 414.
Reeves, C.R. (ed.) (1995) Modern Heuristic Techniques for Combinatorial Problems,
McGraw Hill, London, pp 104 ? 109.
ReVelle, C.S. and Eiselt H.A. (2005) Location analysis: A synthesis and survey.
European Journal of Operational Research, 165, 1 ? 19.
Rosenblatt, M.J. (1979) The facilities layout problem: a multi-goal approach.
International Journal of Production Research, 17, 323 ? 332.
Rouwenhorst, B., Reuter, B., Stockrahm,V., van Houtum, G.J., Mantel, R.J. and Zijm,
W.H.M. (2000) Warehouse design and control: Framework and literature review.
European Journal of Operational Research, 122, 515 ? 533.
Scardino, E. (2003) National brands and a national presence make for a killer
combination - Kohl's finest in apparel & accessories - Company Profile DSN retailing
today, downloadable from http://www.findarticles.com/p/articles/mi_m0FNP/is_17_42
/ai_107999722.
Seehof, J.M. and Evans, W.O. (1967) Automated layout design program. Journal of
Industrial Engineering, 18, 690 ? 695.
140
Sherali, H.D., Fraticelli, B.M.P. and Meller, R.D. (2003) Enhanced model formulations
for optimal facility layout. Operations Research, 51, 629 ? 644.
Skorin-Kapov, J. (1990) Tabu search applied to the quadratic assignment problem. ORSA
Journal on Computing, 2, 33 ? 45.
Snyder, L.V. (2006) Facility location under uncertainty: a review. IIE Transactions, 38,
537 ? 554.
Store Magazine Special Report: The Nation?s Retail Power Players 2005, downloadable
from http://www.stores.org/pdf/05JULYTOP100.pdf#search=%22100%20retailers%22.
Taillard, ?. D. (1991) Robust taboo search for the quadratic assignment problem, Parallel
Computing 17, 443 - 455.
Taillard, ?. D., Badeau P., Gendreau M., Guertin F. and Potvin J.Y., (1997) A tabu
search heuristic for the vehicle routing problem with soft time windows, Transportation
Science 31, 170-186.
Tam, K.Y. (1992) A simulated annealing algorithm for allocating space to manufacturing
cells. International Journal of Production Research, 30, 63 ? 87.
Tam, K.Y. and Chan, S.K. (1998) Solving facility layout problems with geometric
constraints using parallel genetic algorithms: experimentation and findings. International
Journal of Production Research, 36, 3253 ? 3272.
Tate, D.M. and Smith, A.E. (1995a) A genetic approach to the quadratic assignment
problem. Computers and Operations Research, 22, 73 ? 83.
Tate, D.M. and Smith, A.E. (1995b) Unequal area facility layout using genetic search. IIE
Transactions, 27, 465 ? 472.
Tatge, M. (2004) Kohl's Midlife Crisis, Forbes, downloadable from
http://www.forbes.com/business/2004/04/14/cz_mt_0414fastest.html.
Tompkins, J.A., White, J.A., Bozer, Y.A. and Tanchoco, J.M.A. (2003) Facilities
Planning, Third Ed., Wiley, New York, NY.
Tong, X. (1991) SECOT: A sequential construction technique for facility design.
Doctoral Dissertation, University of Pittsburgh, Pittsburgh, PA.
Urban, T. L. (1998) An inventory theoretic approach to product assortment and shelf
space allocation, Journal of Retailing, 74, 15 ? 35.
141
Wilkinson, J.B., Mason, J.B. and Paksoy, C.H. (1982) Assessing the Impact of Short-
Term Supermarket Strategy Variables, Journal of Marketing Research, 19, 72 ? 86.
Wu, Y. and Appleton, E. (2002) The optimization of block layout and aisle structure by a
genetic algorithm. Computers and Industrial Engineering, 41, 371 ? 387.
Xavier, D., Hoch, S. J. and Purk, M. E. (1994) Shelf management and space elasticity,
Journal of Retailing, 70, 301 ? 326.
Yang, M.-H. and Chen, W.-C., (1999) A study on shelf space allocation and
management, International Journal of Production Economics, 60?61, 309 ? 317.
Yang, M.-H. (2001) An efficient algorithm to allocate shelf space, European Journal of
Operational Research, 131, 107 ? 118.
142
APPENDIX I: Example Problem Data for the MIP Formulation
Problem 1:
n = 8 n = 8
B
x
= 10 B
x
= 9
B
y
= 7 B
y
= 7
2.3 ? R
x
' ? 2.7 2.05 ? R
x
' ? 2.45
1.55 ? R
y
' ? 1.95 1.55 ? R
y
' ? 1.95
7.3 ? R
x
" ? 7.7 6.55 ? R
x
" ? 6.95
5.05 ? R
y
" ? 5.45 5.05 ? R
y
" ? 5.45
Table A1. Department data, n = 8.
i
P
l
P
u
x
l
x
u
y
l
y
u
1 12.65 13.91 2.03 4.93 2.03 4.93
2 9.80 10.78 1.57 3.82 1.57 3.82
3 9.80 10.78 1.57 3.82 1.57 3.82
4 9.80 10.78 1.57 3.82 1.57 3.82
5 9.80 10.78 1.57 3.82 1.57 3.82
6 8.00 8.80 1.28 3.12 1.28 3.12
7 8.00 8.80 1.28 3.12 1.28 3.12
8 11.31 12.45 1.81 4.41 1.81 4.41
Table A2. Revenue data, n = 8.
i Area r
i
d
i
R
i 1
R
i 2
R
i 3
1 10 1 3 10.00 10.00 10.00
2 6 2 3 12.00 12.00 12.00
3 6 3 2 18.00 18.00 9.00
4 6 4 2 24.00 24.00 12.00
5 6 10 1 60.00 30.00 20.00
6 4 16 1 64.00 32.00 21.33
7 4 20 1 80.00 40.00 26.67
8 8 6 2 48.00 48.00 24.00
143
Problem 2:
n = 10 n = 10
B
x
= 11 B
x
= 11
B
y
= 8 B
y
= 7
2.55 ? R
x
' ? 2.95 2.55 ? R
x
' ? 2.95
1.8 ? R
y
' ? 2.2 1.55 ? R
y
' ? 1.95
8.05 ? R
x
" ? 8.45 8.05 ? R
x
" ? 8.45
5.8 ? R
y
" ? 6.2 5.05 ? R
y
" ? 5.45
Table A3. Department data, n = 10.
i
P
l
P
u
x
l
x
u
y
l
y
u
1 12.65 13.91 2.03 4.93 2.03 4.93
2 9.80 10.78 1.57 3.82 1.57 3.82
3 9.80 10.78 1.57 3.82 1.57 3.82
4 9.80 10.78 1.57 3.82 1.57 3.82
5 9.80 10.78 1.57 3.82 1.57 3.82
6 8.00 8.80 1.28 3.12 1.28 3.12
7 8.00 8.80 1.28 3.12 1.28 3.12
8 11.31 12.45 1.81 4.41 1.81 4.41
9 12.65 13.91 2.03 4.93 2.03 4.93
10 12.65 13.91 2.03 4.93 2.03 4.93
Table A4. Revenue data, n = 10.
i Area r
i
d
i
R
i 1
R
i 2
R
i 3
1 10 1 3 10.00 10.00 10.00
2 6 2 3 12.00 12.00 12.00
3 6 3 3 18.00 18.00 18.00
4 6 4 2 24.00 24.00 12.00
5 6 10 1 60.00 30.00 20.00
6 4 16 1 64.00 32.00 21.33
7 4 20 1 80.00 40.00 26.67
8 8 6 2 48.00 48.00 24.00
9 10 6 2 60.00 60.00 30.00
10 10 13 1 130.00 65.00 43.33
144
Problem 3:
n = 16
B
x
= 14
B
y
= 10
3.3 ? R
x
' ? 3.7
2.3 ? R
y
' ? 2.7
10.3 ? R
x
" ? 10.7
7.3 ? R
y
" ? 7.7
Table A5. Department data, n = 16.
i
P
l
P
u
x
l
x
u
y
l
y
u
1 12.65 13.91 2.03 4.93 2.03 4.93
2 9.80 10.78 1.57 3.82 1.57 3.82
3 9.80 10.78 1.57 3.82 1.57 3.82
4 9.80 10.78 1.57 3.82 1.57 3.82
5 9.80 10.78 1.57 3.82 1.57 3.82
6 8.00 8.80 1.28 3.12 1.28 3.12
7 8.00 8.80 1.28 3.12 1.28 3.12
8 11.31 12.45 1.81 4.41 1.81 4.41
9 9.80 10.78 1.57 3.82 1.57 3.82
10 11.31 12.45 1.81 4.41 1.81 4.41
11 6.93 7.62 1.11 2.70 1.11 2.70
12 12.00 13.20 1.93 4.67 1.93 4.67
13 6.93 7.62 1.11 2.70 1.11 2.70
14 12.00 13.20 1.93 4.67 1.93 4.67
15 8.00 8.80 1.28 3.12 1.28 3.12
16 8.00 8.80 1.28 3.12 1.28 3.12
145
Table A6. Revenue data, n = 16.
i Area r
i
d
i
R
i 1
R
i 2
R
i 3
1 10 1 3 10.00 10.00 10.00
2 6 2 3 12.00 12.00 12.00
3 6 3 2 18.00 18.00 9.00
4 6 4 2 24.00 24.00 12.00
5 6 10 1 60.00 30.00 20.00
6 4 16 1 64.00 32.00 21.33
7 4 20 1 80.00 40.00 26.67
8 8 6 1 48.00 24.00 16.00
9 6 5 2 30.00 30.00 15.00
10 8 5 2 40.00 40.00 20.00
11 3 5 3 15.00 15.00 15.00
12 9 6 1 54.00 27.00 18.00
13 3 13 2 39.00 39.00 19.50
14 9 9 1 81.00 40.50 27.00
15 4 3 3 12.00 12.00 12.00
16 4 2 3 8.00 8.00 8.00
146
APPENDIX II: Example Problem Data for Heuristics
Problem 1:
Number of departments, n = 16,
Total Store Area: 96 units sq.,
Store Length: 12 units,
Store Width: 8 units.
Table A7. Area, Revenue and Aspect Ratio Data for n = 16.
i Department A
i
r
i
d
i
0A1011. 1
1B 62 3
2C 31. 1
3D 64 2
4E 101. 1
5F 46
6G 201. 2
7H 86
8I 651. 3
9J 8 2
10 K 3 5 1.1 2
11 L 9 6 1.1 3
12 M 3 13 1.1 1
13 N 9 9 1.1 3
14 O 4 3 1.1 3
15 P 4 2 1.1 1
i
?
147
Problem 1 (continued):
Table A8. Adjacency Ratings and Scores for n = 16.
AB C D E F G H I J K L M N O P
A-25-125512555-255-2511-25125125
B -511115152555511
C -5551112555-2-255251
D --252555125-2551151
E 5255125155511251
F -51152551511
G - 1 1 -25 5 5 25 5 -25 25
H -51-251-125-2555
I - 125 25 5 -125 1 25 5
J -12 5115
K - -25 125 125 5 1
L 55125
M -51
N -55
O -125
P -
AB C D E F G H I J K L M N O P
A-EX IA I IX IXO, UO, UXO, UEA
B - I O, U O, U O, U O, U I O, U I E I X I O, U O, U
C -III, UO, UAIIX E,
D - X E I I O, U E X I O, U O, U I O, U
E - I E I A O, U E I I O, U A O, U
F - E O, U O, U I E I O, U I O, U O, U
G - O, U O, U X I I E I X E
H- U
I - A E I XX O, U E I
J - O, U E XX O, U O, U I
K -XAA IO, U
L -E IO, UE
M -I U
N -II
O -A
P -
148
Problem 2:
Number of departments, n = 17,
Total Store Area: 96 units sq.,
Store Length: 12 units,
Store Width: 8 units.
Table A9. Area, Revenue and Aspect Ratio Data for n = 17.
i Department A
i
r
i
d
i
0A 581. 1
1B 62 3
2C 831. 1
3D 4 2
4E 6101. 1
5F 16
6G 2201. 2
7H 86
8I 651. 3
9J 8 2
10 K 3 5 1.1 2
11 L 10 6 1.1 3
12 M 1 13 1.1 1
13 N 11 9 1.1 3
14 O 4 3 1.1 3
15 P 4 7 1.1 1
16 Q 5 12 1.1 2
i
?
149
Problem 2 (continued):
Table A10. Adjacency Ratings and Scores for n = 17.
AB C D E F G H I J K L M N O P Q
A-2512551525525151-25-25511
B -51125 - 2551525555525
C - 1 -25 5 5 25 -25 1 1 -25 125 25 1 -25 1
D -1 1 5251-251251-25
E -511115551-1 251
F -2551251255511125
G - 125 125 1 1 25 5 125 5 1 1
H - -25255152251
I - -25 25 1 -25 1 -25 25 1
J 511251125
K - -25 1 -125 -25 -25 25
L 551 1
M --25 1 1 5
N - -25 25 -25
O --125 5
P -5
Q -
AB C D E F G H I J K L M N O P Q
A - E A I O, U I E I E O, U I O, U X X I O, U O, U
B -EO, UA XEI, UIEIIIIA
C - O, U X I I E X O, U O, U X A E O, U X O, U
D - O, U I I O, U E I E O, U X O, U A O, U X
E - I O, U O, U O, U O, U E I I O, U XX E O, U
F - E IO, U E A I IO, UO, UO, U E
G - A A O, U O, U E I A I O, U O, U
H- U U
I - X E O, U X O, U X E O, U
J - I O, U O, U E O, U O, U E
K -X, UXXXX
L -IIO, UEA
M -X UO, U I
N -XEX
O -XX I
P -I
Q -
150
Problem 3:
Number of departments, n = 20,
Total Store Area: 121.5 units sq.,
Store Length: 13.5 units,
Store Width: 9 units.
Table A11. Area, Revenue and Aspect Ratio Data for n = 20.
i Department A
i
r
i
d
i
0 A 10 1 1.1 1
1 B 6 2 1.1 3
2 C 6 3 1.1 1
3 D 6 4 1.1 2
4 E 6 10 1.1 1
5 F 4 16 1.1 2
6 G 4 20 1.1 2
7 H 8 6 1.1 2
8 I 6 5 1.1 3
9 J 8 5 1.1 2
10 K 3 5 1.1 2
11 L 9 6 1.1 3
12 M 7.5 13 1.1 1
13 N 9 9 1.1 3
14 O 4 3 1.1 3
15 P 4 2 1.1 1
16 Q 7 12 1.1 1
17 R 5 14 1.1 1
18 S 5 18 1.1 2
19 T 4 7 1.1 3
i
?
151
Problem 3 (continued):
Table A12. Adjacency Ratings and Scores for n = 20.
AB C D E F G H I J K L M N O P Q R S T
A-1115515115-251112512525111
B -12551 51112515555-25
C - 5 5 125 5 1 1 25 -25 5 5 1 1 -125 5 5 -125 1
D - 25 125 5 1 5 25 5 25 1 5 1 -25 -25 5 1 1
E - 25 1 125 5 -25 25 5 1 5 25 5 5 5 5 125
F - 1 -25 5 5 25 -25 1 1 -25 125 25 1 -25 1
G - 1 5 5 1 25 5 25 1 -25 1 125 1 -25
H -511115551-125251
I -2551251255511125
J - 125 125 1 1 25 5 125 5 1 1
K - 5 -25 125 5 1 5 25 125 1
L - -25 25 1 -25 1 -25 25 1
M 511251125
N - -25 1 -125 -25 -25 25
O - 5 5 1 25 125
P --25115
Q - -25 25 -25
R - -125 5
S -5
T -
AB C D E F G H I J K L M N O P Q R S T
A - O, U O, U O, U I I O, U I O, U O, U I X O, U O, U A A E O, U O, U O, U
B - O, U E I O, U O, U I O, U I O, U O, U O, U E O, U I I I I XX
C - I I A I O, U O, U E X I I O, U O, U XX I I XX O, U
D - E A I O, U I E I E O, U I O, U X X I O, U O, U
E - E O, U A I X E I O, U I E I I I I A
F - O, U X I I E X O, U O, U X A E O, U X O, U
G - O, U I I O, U E I E O, U X O, U A O, U X
H - I O, U O, U O, U O, U E I I O, U XX E O, U
I - E I O, U E A I I O, U O, U O, U E
J - A A O, U O, U E I A I O, U O, U
K - I X A I O, U I E A O, U
L - X E O, U X O, U X E O, U
M - I O, U O, U E O, U O, U E
N -X, UXXXX
O -IIO, UEA
P - X O, U O, U I
Q -XEX
R -XX I
S -I
T -
152
APPENDIX III: Example Problem Data and Results from Chapter VI
Table A13. Revenue data for n = 12.
Department
L
i
A
i
?
i
r
i
?
i
d
- Aisle 40.00 N/A 896.761 0.168 N/A
A 1 45.00 1.10 713.926 0.227 1
B 2 42.00 1.10 851.911 0.081 1
C 3 20.00 1.10 370.836 0.091 1
D 4 35.00 1.10 504.733 0.199 1
E 5 10.00 1.10 279.706 0.246 2
F 6 15.00 1.10 136.194 0.219 2
G 7 15.00 1.10 775.968 0.191 2
H 8 50.00 1.10 831.138 0.089 2
I 9 12.00 1.10 547.104 0.086 3
J 10 10.00 1.10 333.647 0.197 3
K 11 30.00 1.10 263.850 0.244 3
L 12 45.00 1.10 759.471 0.194 3
153
Table A14. Revenue data for n = 20.
Department
L
i
A
i
?
i
r
i
?
i
d
- Aisle 40.00 N/A 955.78 0.168 N/A
A 1 15.00 1.10 570.52 0.072 1
B 2 17.00 1.10 442.53 0.188 1
C 3 13.00 1.10 467.64 0.215 1
D 4 15.50 1.10 408.80 0.168 1
E 5 20.50 1.10 564.99 0.228 2
F 6 16.00 1.10 383.83 0.217 2
G 7 16.50 1.10 403.03 0.061 2
H 8 12.00 1.10 456.78 0.062 2
I 9 21.00 1.10 448.18 0.069 3
J 10 12.50 1.10 394.11 0.163 3
K 11 14.50 1.10 506.71 0.235 3
L 12 13.50 1.10 317.83 0.077 3
M 13 18.50 1.10 304.66 0.185 1
N 14 14.00 1.10 445.50 0.164 2
O 15 19.50 1.10 455.99 0.086 3
P 16 17.50 1.10 560.62 0.227 1
Q 17 19.00 1.10 495.90 0.230 2
R 18 20.00 1.10 333.48 0.175 3
S 19 21.50 1.10 401.24 0.183 2
T 20 18.00 1.10 588.39 0.083 3
Figure A1. Best solution found, configuration: FE3, n = 12, store area: 25.5?17.
154
Figure A2. Best solution found, configuration: AE3, n = 12, store area: 25.5?17.
Figure A3. Best solution found, configuration: RE3, n = 12, store area: 25.5?17.
155
Figure A4. Best solution found, configuration: FE0, n = 12, store area: 25.5?17.
Figure A5. Best solution found, configuration: AE0, n = 12, store area: 25.5?17.
156
Figure A6. Best solution found, configuration: RE0, n = 12, store area: 25.5?17.
Figure A7. Best solution found, configuration: FE1, n = 20, store area: 25.5?17.
157
Figure A8. Best solution found, configuration: AE1, n = 20, store area: 25.5?17.
Figure A9. Best solution found, configuration: RE1, n = 20, store area: 25.5?17.
158
Figure A10. Best solution found, configuration: FE0, n = 20, store area: 25.5?17.
Figure A11. Best solution found, configuration: AE0, n = 20, store area: 25.5?17.
159
Figure A12. Best solution found, configuration: RE0, n = 20, store area: 25.5?17.
Table A15. Summary of runs for configuration: FE3, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 7803.565 152.290
2 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 289.136
3 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 204.639
4 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 7803.565 144.948
5 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 195.375
6 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 174.012
7 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 150.617
8 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 201.023
9 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 145.990
10 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 7803.565 139.259
Table A16. Summary of runs for configuration: AE3, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 133.010
2 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 170.407
3 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 176.697
4 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 0.697 188.063
5 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 122.785
6 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 155.335
7 0 3 8 5 12 7 1 2 4 6 11 9 10 10, 11 11195.220 0.697 1.000 0.697 179.009
8 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 0.697 224.579
9 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 0.697 133.351
10 0 6 4 2 1 7 12 5 8 3 11 10 9 10, 11 11195.220 0.697 1.000 0.697 129.475
160
Table A17. Summary of runs for configuration: RE3, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 232.541
2 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 209.276
3 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 198.168
4 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 164.878
5 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 136.045
6 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 113.121
7 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 117.958
8 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 110.166
9 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 114.102
10 0 7 12 11 4 8 1 2 9 5 10 6 3 9, 11 11804.143 0.225 1.000 11804.143 111.899
Table A18. Summary of runs for configuration: FE0, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 149.425
2 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 149.535
3 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 134.984
4 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 214.624
5 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 146.130
6 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 224.368
7 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 138.830
8 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 156.195
9 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 126.461
10 0 3 4 10 12 8 7 6 2 5 9 11 1 9, 10 13116.610 0.858 0.583 11253.578 127.122
Table A19. Summary of runs for configuration: AE0, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 6 4 12 8 2 1 7 9 10 3 11 5 8, 9 11478.845 0.906 0.417 0.906 136.356
2 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 123.977
3 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 148.874
4 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 163.306
5 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 205.059
6 0 6 4 12 8 2 1 7 9 10 3 11 5 8, 9 11478.845 0.906 0.417 0.906 125.599
7 0 5 1 2 8 4 12 9 6 7 11 3 10 8, 9 11352.835 0.906 0.583 0.906 149.376
8 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 205.209
9 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 176.827
10 0 7 1 2 8 12 4 6 9 5 11 3 10 8, 9 11478.845 0.906 0.417 0.906 147.743
Table A20. Summary of runs for configuration: RE0, n = 12, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 4 9 5 7 10 8 11 2 12 6 3 1 9, 10 13116.610 0.133 0.667 13116.610 108.904
2 0 4 7 5 8 10 9 11 1 3 12 6 2 10, 11 13116.610 0.308 0.750 13116.610 106.370
3 0 9 4 5 8 10 7 11 2 6 12 3 1 9, 10 13116.610 0.067 0.500 13116.610 111.959
4 0 4 9 7 8 10 5 11 2 12 6 3 1 9, 10 13116.610 0.131 0.667 13116.610 135.374
5 0 9 4 5 8 10 7 11 2 6 12 3 1 9, 10 13116.610 0.067 0.500 13116.610 104.849
6 0 9 4 5 8 10 7 11 2 12 6 3 1 9, 10 13116.610 0.117 0.583 13116.610 135.414
7 0 9 4 5 8 10 7 11 2 6 12 3 1 9, 10 13116.610 0.067 0.500 13116.610 120.531
8 0 4 9 5 8 10 7 11 2 12 6 3 1 9, 10 13116.610 0.162 0.583 13116.610 151.799
9 0 9 4 5 8 10 7 11 2 6 12 3 1 9, 10 13116.610 0.067 0.500 13116.610 127.282
10 0 9 4 5 7 10 8 11 2 6 12 3 1 9, 10 13116.610 0.041 0.583 13116.610 117.908
161
Table A21. Summary of runs for configuration: FE1, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 3 18 13 19 17 10 12 9 5 8 15 16 6 20 14 11 7 2 4 1 14, 17 15888.820 0.805 1.000 12785.594 3603.087
2 0 3 18 13 19 17 10 12 9 5 8 15 16 6 20 14 11 7 2 4 1 14, 17 15888.820 0.805 1.000 12785.594 7097.611
3 0 3 18 7 14 19 17 10 12 20 5 8 13 16 6 15 11 9 2 4 1 15, 17 16232.205 0.781 1.000 12673.397 5183.594
4 0 3 18 7 14 19 17 10 12 20 5 8 13 16 6 15 11 9 2 4 1 15, 17 16232.205 0.781 1.000 12673.397 4846.299
5 0 3 18 7 14 19 17 10 12 20 5 8 13 16 6 15 11 9 2 4 1 15, 17 16232.205 0.781 1.000 12673.397 6503.110
6 0 3 18 13 19 17 10 12 9 20 5 8 16 6 15 11 7 14 2 4 1 14, 16 16232.205 0.777 1.000 12615.120 4320.411
7 0 3 13 9 14 2 17 10 12 8 5 20 15 16 6 19 11 7 18 4 1 15, 17 15588.865 0.808 1.000 12600.191 3883.657
8 0 3 18 7 9 17 12 19 20 5 8 13 16 6 15 11 10 14 2 4 1 14, 17 15880.475 0.790 1.000 12539.418 3660.303
9 0 3 18 7 9 17 12 19 20 5 8 13 16 6 15 11 10 14 2 4 1 14, 17 15880.475 0.790 1.000 12539.418 2235.749
10 0 3 18 7 14 19 17 10 12 8 5 15 13 16 6 20 11 9 2 4 1 15, 17 15965.775 0.778 1.000 12419.523 3646.041
Table A22. Summary of runs for configuration: AE1, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 3 17 12 14 9 18 7 19 8 5 20 13 16 6 15 2 11 10 4 1 15, 18 14872.403 0.819 1.000 0.819 2549.709
2 0 19 17 10 12 7 18 20 15 1 16 6 3 13 9 2 8 5 11 14 4 15, 18 13450.942 0.819 1.000 0.819 3541.825
3 0 7 18 3 13 16 1 15 20 5 8 19 17 12 11 9 4 6 2 14 10 14, 18 13548.393 0.815 1.000 0.815 2984.941
4 0 9 18 7 12 10 17 19 8 4 3 2 16 13 15 6 5 11 14 20 1 15, 18 13390.877 0.814 1.000 0.814 1534.879
5 0 20 5 8 13 17 9 14 7 18 3 6 16 15 4 2 11 10 12 19 1 14, 18 14372.428 0.812 1.000 0.812 1794.277
6 0 8 5 13 15 16 6 3 17 12 19 7 18 2 10 9 4 1 20 14 11 14, 18 13775.032 0.809 1.000 0.809 1822.269
7 0 3 13 9 14 2 17 10 12 8 5 20 15 16 6 19 11 7 18 4 1 15, 17 15588.865 0.808 1.000 0.808 2748.687
8 0 3 13 17 12 14 9 18 7 8 5 20 15 16 6 19 11 10 2 4 1 15, 17 15726.680 0.803 1.000 0.803 2118.813
9 0 8 5 3 6 16 1 2 18 7 14 9 13 17 12 11 15 4 20 19 10 15, 18 13776.757 0.800 1.000 0.800 1417.143
10 0 18 2 11 19 17 12 8 20 15 1 16 13 3 5 9 10 14 7 4 6 14, 17 15011.160 0.799 1.000 0.799 1532.946
Table A23. Summary of runs for configuration: RE1, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 1 16 6 17 11 20 15 5 14 8 7 3 13 10 12 18 9 19 4 2 14, 17 16493.550 0.404 1.000 16493.550 225.558
2 0 3 17 6 19 11 20 18 5 8 9 16 1 14 12 15 10 7 4 13 2 13, 17 16493.550 0.484 1.000 16493.550 202.764
3 0 4 3 6 19 11 12 18 9 17 14 7 5 13 8 15 20 10 1 16 2 14, 17 16493.550 0.409 1.000 16493.550 191.397
4 0 6 3 11 14 17 20 15 18 5 8 12 16 13 19 10 9 7 4 1 2 14, 17 16493.550 0.387 1.000 16493.550 341.942
5 0 2 5 14 12 8 9 20 18 10 6 17 7 16 1 19 11 15 13 4 3 15, 17 16493.550 0.192 1.000 16493.550 188.683
6 0 4 5 6 17 18 10 20 12 9 7 19 16 13 8 15 11 14 3 1 2 14, 17 16493.550 0.390 1.000 16493.550 200.520
7 0 1 16 11 8 17 18 20 19 7 15 6 3 2 5 12 10 14 9 4 13 14, 17 16493.550 0.548 1.000 16493.550 183.815
8 0 3 20 17 14 5 18 10 15 11 19 6 16 4 8 12 9 7 2 1 13 14, 17 16493.550 0.332 1.000 16493.550 184.607
9 0 1 16 8 18 5 10 20 12 17 7 14 6 19 3 9 15 11 13 4 2 15, 17 16493.550 0.302 1.000 16493.550 201.281
10 0 2 19 7 6 14 5 10 12 20 17 8 9 16 1 11 18 15 13 4 3 15, 17 16493.550 0.292 1.000 16493.550 191.066
Table A24. Summary of runs for configuration: FE0, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 16 20 5 8 19 11 14 9 12 7 18 3 6 10 15 1 2 17 13 4 14, 15 16150.165 0.822 0.500 13274.214 3576.016
2 0 1 20 5 8 19 11 14 9 17 12 7 18 3 6 10 15 13 16 2 4 15, 16 16150.165 0.821 0.500 13258.752 2610.300
3 0 1 20 5 8 19 11 14 9 17 12 7 18 3 6 10 15 13 16 2 4 15, 16 16150.165 0.821 0.500 13258.752 5571.513
4 0 16 20 5 8 17 12 19 11 14 7 18 13 6 10 15 1 2 4 3 9 14, 15 16141.820 0.820 0.500 13236.447 4900.349
5 0 2 13 19 11 14 9 12 20 5 8 7 18 16 6 15 10 17 3 4 1 15, 17 16493.550 0.801 0.700 13209.052 5695.618
6 0 13 2 19 11 14 9 12 7 18 20 5 8 16 6 15 10 17 3 4 1 15, 17 16254.455 0.811 0.700 13184.861 3584.038
7 0 1 20 5 8 17 9 14 11 19 12 7 18 3 6 10 15 13 16 2 4 15, 16 16150.165 0.816 0.500 13181.442 4453.400
8 0 4 13 17 10 12 7 18 9 8 5 20 15 3 6 14 11 19 2 16 1 15, 17 16227.120 0.807 0.800 13100.545 2426.704
9 0 4 2 9 14 12 10 17 13 20 5 8 7 18 3 6 15 11 19 16 1 16, 17 16145.090 0.810 0.700 13076.827 2996.999
10 0 1 13 20 5 8 19 11 14 9 12 17 7 18 2 4 10 15 16 6 3 16, 17 16150.165 0.809 0.650 13065.476 3242.597
162
Table A25. Summary of runs for configuration: AE0, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 7 18 3 4 2 16 1 15 20 5 8 11 19 12 14 9 13 17 6 10 15, 20 13042.422 0.839 0.550 0.839 2468.740
2 0 10 12 3 6 16 1 15 20 13 7 18 2 19 17 9 14 8 5 4 11 15, 19 12696.507 0.839 0.650 0.839 2558.773
3 0 6 4 18 7 12 17 19 11 2 8 5 15 1 16 14 9 10 3 13 20 15, 18 14841.783 0.833 0.750 0.833 1324.494
4 0 6 16 1 15 5 8 2 18 7 19 17 13 3 11 14 20 9 4 12 10 14, 17 14773.168 0.830 0.950 0.830 1313.427
5 0 13 17 12 19 7 18 9 20 15 1 16 6 3 2 5 8 14 11 10 4 15, 19 14929.120 0.829 0.650 0.829 1153.898
6 0 16 8 5 20 13 17 12 19 11 14 7 18 6 10 15 1 2 4 3 9 14, 15 15353.640 0.827 0.400 0.827 2029.019
7 0 18 7 2 17 19 11 14 20 15 1 16 6 3 13 5 8 9 12 10 4 15, 20 14228.275 0.826 0.550 0.826 2161.538
8 0 14 9 13 2 18 7 3 6 16 1 15 19 17 10 12 20 5 4 8 11 16, 19 12694.098 0.824 0.750 0.824 1614.658
9 0 15 1 16 6 3 18 7 12 17 19 11 14 13 20 10 8 2 4 5 9 15, 19 13467.975 0.822 0.800 0.822 1914.778
10 0 6 4 18 7 9 14 11 19 8 5 20 13 16 17 10 12 3 2 1 15 14, 17 15163.230 0.819 0.700 0.819 1151.475
Table A26. Summary of runs for configuration: RE0, n = 20, store area: 25.5?17.
Trial Department Sequence Baybreaks Revenue
Adjacency
Score ARP Fitness
Time Elapsed
(sec)
1 0 1 3 6 17 5 18 11 15 20 8 19 10 13 9 12 14 7 16 4 2 15, 16 16493.550 0.298 0.550 16493.550 202.063
2 0 2 3 11 20 17 15 18 5 7 19 16 1 12 10 4 9 14 13 8 6 13, 14 16493.550 0.421 0.600 16493.550 266.900
3 0 6 3 5 20 17 18 11 10 19 8 7 12 4 1 14 15 9 16 13 2 15, 16 16493.550 0.473 0.600 16493.550 347.661
4 0 6 3 18 5 17 11 20 9 14 12 19 16 7 15 1 4 10 8 13 2 13, 14 16493.550 0.485 0.400 16493.550 207.321
5 0 1 3 10 6 18 14 5 11 9 17 19 7 15 4 13 8 12 16 20 2 16, 17 16493.550 0.331 0.600 16493.550 197.235
6 0 3 10 17 18 14 6 20 12 11 7 15 9 16 4 8 19 1 5 13 2 15, 16 16493.550 0.237 0.600 16493.550 181.022
7 0 6 3 5 17 18 20 11 15 7 10 19 1 4 12 9 16 13 8 14 2 14, 15 16493.550 0.390 0.500 16493.550 185.578
8 0 2 3 10 7 17 18 20 11 5 12 9 16 1 19 14 13 15 4 8 6 14, 15 16493.550 0.279 0.550 16493.550 188.332
9 0 6 2 11 14 20 5 18 15 9 17 19 10 16 7 12 1 4 13 8 3 14, 15 16493.550 0.346 0.450 16493.550 223.445
10 0 3 2 12 6 17 5 18 20 10 7 14 8 15 16 4 9 19 13 1 11 16, 17 16493.550 0.337 0.750 16493.550 169.044
Table A27. Area allotments for store areas 16?24, 17?25.5 and 18?27, n = 12.
Department 16?24 17?25.5 Increase 18?27 Increase
- Aisle 40.00 45.76 14.40% 53.46 33.65%
A 1 45.00 45.00 0.00% 45.00 0.00%
B 2 42.00 42.00 0.00% 42.00 0.00%
C 3 20.00 20.00 0.00% 20.00 0.00%
D 4 35.00 41.44 18.40% 50.56 44.46%
E 5 11.00 17.66 60.55% 22.46 104.18%
F 6 15.00 15.00 0.00% 16.27 8.47%
G 7 21.96 25.12 14.39% 30.22 37.61%
H 8 50.00 50.00 0.00% 50.00 0.00%
I 9 12.00 12.00 0.00% 12.00 0.00%
J 10 10.00 15.95 59.50% 19.68 96.80%
K 11 37.04 46.10 24.46% 58.62 58.26%
L 12 45.00 57.47 27.71% 65.73 46.07%
163
Table A28. Area allotments for store areas 16?24, 17?25.5 and 18?27, n = 20.
Department 16?24 17?25.5 Increase 18?27 Increase
- Aisle 40.00 44.86 12.15% 51.87 29.68%
A 1 15.00 15.00 0.00% 15.00 0.00%
B 2 17.00 17.00 0.00% 19.14 12.59%
C 3 14.35 21.19 47.67% 26.33 83.48%
D 4 15.50 15.50 0.00% 15.50 0.00%
E 5 20.68 30.75 48.69% 39.50 91.01%
F 6 16.00 16.80 5.00% 21.49 34.31%
G 7 16.50 16.50 0.00% 16.50 0.00%
H 8 12.00 12.00 0.00% 12.00 0.00%
I 9 21.00 21.00 0.00% 21.00 0.00%
J 10 12.50 12.50 0.00% 12.93 3.44%
K 11 19.19 28.63 49.19% 36.86 92.08%
L 12 13.50 13.50 0.00% 13.50 0.00%
M 13 18.50 18.50 0.00% 18.50 0.00%
N 14 14.00 14.00 0.00% 15.13 8.07%
O 15 19.50 19.50 0.00% 19.50 0.00%
P 16 20.28 30.28 49.31% 37.70 85.90%
Q 17 19.00 26.49 39.42% 34.05 79.21%
R 18 20.00 20.00 0.00% 20.00 0.00%
S 19 21.50 21.50 0.00% 21.50 0.00%
T 20 18.00 18.00 0.00% 18.00 0.00%