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%