Method and System for Optimizing Store Space and Item Layout

Abstract

A method in a computer system for generating an efficient item assortment associated with a plurality of items includes obtaining choice set data specifying a multiplicity of choice sets associated with the plurality of items, where each of the multiplicity of choice sets includes several of the plurality of items, at least some of which are mutually substitutable, obtaining item interaction data descriptive of substitutions between pairs of items in each of the multiplicity of choice sets, obtaining a set of benefit metrics associated with the plurality of items, obtaining a constraint parameter associated with the item assortment, and generating an item selection based at least on the item interaction data, the set of benefit metrics, and the constraint parameter, where the item selection identifies at least one of the plurality of items selected for inclusion in the item assortment.

1 . A method in a computer system for generating an efficient item assortment associated with a plurality of items, the method comprising:
 obtaining choice set data specifying a multiplicity of choice sets associated with the plurality of items, wherein each of the multiplicity of choice sets includes several of the plurality of items, at least some of which are mutually substitutable;   obtaining item interaction data descriptive of substitutions between pairs of items in each of the multiplicity of choice sets;   obtaining a set of benefit metrics associated with the plurality of items;   obtaining a constraint parameter associated with the item assortment; and   generating an item selection based at least on the item interaction data, the set of benefit metrics, and the constraint parameter; wherein the item selection identifies at least one of the plurality of items selected for inclusion in the item assortment.   
     
     
         2 . The method of  claim 1 , wherein the item interaction data is indicative of a probability of transferring customer demand between items in each of the multiplicity of choice sets. 
     
     
         3 . The method of  claim 1 , wherein obtaining the constraint parameter includes obtaining a spatial metric indicative of a spatial limitation of a retail area in which the item assortment is to be physically disposed. 
     
     
         4 . The method of  claim 3 , wherein the retail area includes a plurality of merchandizing fixtures, each associated with a respective fixture width; and wherein the spatial limitation is a sum of the fixture widths. 
     
     
         5 . The method of  claim 3 , further comprising:
 obtaining a plurality of spatial metrics, each of the plurality of spatial metrics associated with a respective one of the plurality of items; and wherein   generating the item assortment includes comparing the plurality of spatial metrics to the constraint parameter.   
     
     
         6 . The method of  claim 1 , further comprising:
 obtaining a plurality of facing capacity parameters, wherein each of the plurality of facing capacity parameters specifies a respective number of units associated with a single facing of a respective one of the plurality of items; wherein   generating the item selection is further based on the plurality of facing capacity parameters.   
     
     
         7 . The method of  claim 1 , further comprising receiving a plurality of facing ranges, wherein each in the multiplicity of facing ranges specifies a minimum number of facings and a maximum number of facings for a respective one in the plurality of items; wherein generating the item selection further includes calculating a number of facings for each selected item in accordance with the plurality of facing ranges. 
     
     
         8 . The method of  claim 7 , further comprising generating a planogram associated with the item assortment, including generating a layout of the selected ones of the plurality of items in accordance with the respective numbers of facings and a set of layout rules. 
     
     
         9 . The method of  claim 1 , the method further comprising:
 generating a multiplicity of lists of facing combinations, wherein each of the multiplicity of lists corresponds to a respective one of the multiplicity of choice sets, and wherein each facing combination in each of the multiplicity of lists includes one or several facings of at least one of the items in the corresponding one of the multiplicity of choice sets; and wherein   the set of benefit metrics is a first set of benefit metrics, each in the first set of benefit metrics being associated with a respective one of the plurality of items; the method further comprising:
 generating a respective benefit metric for each facing combination in each of the multiplicity of lists of facing combinations based on the first set of benefit metrics and the item interaction data to define a second set of benefit metrics. 
   
     
     
         10 . The method of  claim 9 , wherein generating each benefit metric in the second set of benefit metrics includes applying a linear programming technique, comprising:
 projecting excess demand for each item in the corresponding one of the multiplicity of choice sets;   projecting excess supply for each item in the corresponding one of the multiplicity of choice sets;   sorting the corresponding one of the multiplicity of choice sets according o respective benefit metrics in the first set of benefit metrics to generate a sorted list; and   transferring the excess demand between items in the corresponding one of the multiplicity of choice sets according to at least the sorted list and the excess supply.   
     
     
         11 . The method of  claim 9 , wherein generating each benefit metric in the second set of benefit metrics includes generating a full replacement simulation model, comprising:
 obtaining historical sales data associated with the plurality of items;   simulating a sequential arrival of a plurality of customers, including associating each of the plurality of customers with a preferred item in the corresponding one of the multiplicity of choice sets based on the historical sales data; and   simulating a selection made by each customer, including:
 associating the selection with the corresponding preferred item if the preferred item is available; and 
 associating the selection with another item in the corresponding one of the multiplicity of choice sets if the preferred item is not available and if the other item is available, wherein a probability of choosing an item in the corresponding one of the multiplicity of choice sets is related to the item interaction data. 
   
     
     
         12 . The method of  claim 9 , wherein generating each benefit metric in the second set of benefit metrics includes generating a partial replacement simulation model, comprising:
 obtaining historical sales data associated with the plurality of items;   simulating a sequential arrival of a plurality of customers, including associating each of the plurality of customers with a preferred item in the corresponding one of the multiplicity of choice sets based on the historical sales data; and   simulating a selection made by each customer, including:
 associating the selection with the corresponding preferred item if the preferred item is available; and, if the preferred item is not available, further including one of: 
 associating the selection with another item in the corresponding one of the multiplicity of choice sets according to a probability derived from the item interaction data; or 
 not associating the selection with any of the items in the corresponding one of the multiplicity of choice sets according to the probability derived from the item interaction data. 
   
     
     
         13 . The method of  claim 9 , further comprising:
 obtaining a plurality of spatial metrics, wherein each of the plurality of spatial metrics corresponds to a respective one of the plurality of items; and wherein   generating the item selection includes selecting at most one facing combination from each one of the multiplicity of lists of facing combinations based on the second set of benefit metrics, the plurality of spatial metrics, and the constraint parameter associated with the item assortment.   
     
     
         14 . The method of  claim 13 , wherein selecting at most one facing combination from each one of the multiplicity of lists of facing combinations includes solving a multiple choice knapsack problem. 
     
     
         15 . The method of  claim 1 , further comprising receiving one or more business rules associated with the plurality of items, wherein
 generating the item selection includes applying the one or more business rules.   
     
     
         16 . The method of  claim 15 , wherein the one or more business rules includes an item-specific business rule specifying at least one of: mandatory inclusion of a specified one in the plurality of items in the item selection, a minimum number of facings of the specified one in the plurality of items in the item selection, or a maximum number of facings of the specified one in the plurality of items in the item selection. 
     
     
         17 . A system for generating an efficient item assortment associated with a plurality of items, comprising:
 a storage unit to store a plurality of profit metrics, wherein each of the plurality of profit metrics corresponds to a respective one of the plurality of items;   a choice set generator to generate choice set data specifying a multiplicity of choice sets associated with the plurality of items, wherein each of the multiplicity of choice sets includes several of the plurality of items, at least some of which are mutually substitutable;   a demand transfer matrix generator to receive item interaction data descriptive of substitutions between pairs of items in each of the multiplicity of choice sets, and to generate a respective demand transfer matrix for each of the multiplicity of choice sets to define a set of demand transfer matrices, wherein each demand transfer matrix includes a respective substitutability metric for each pair of items in the corresponding choice set; and   a combinatorial problem solver communicatively coupled to the storage unit, the choice set generator, and the demand transfer matrix generator to obtain a global constraint parameter and to generate an item selection based on at least one of the set of demand transfer matrices, the plurality of profit metrics, and the global constraint parameter.   
     
     
         18 . The system of  claim 17 , further comprising a choice set splitter to receive a selection of one of the multiplicity of choice sets and a split criterion, and to split the selected one of the multiplicity of choice sets into several choice sets according to the split criterion. 
     
     
         19 . The system of  claim 17 , wherein the storage unit further stores:
 a plurality of facing range parameters, wherein each of the plurality of facing range parameters corresponds to a respective one of the plurality of items; wherein each facing range parameter specifies a minimum number of facings and a maximum number of facings for a respective one in the plurality of items; the system further comprising:   a facing combination generator to generate a list of facing combinations for a respective one of the multiplicity of choice lists in accordance with the plurality of facing range parameters, wherein each facing combination includes one or several facings of at least one of the items in the corresponding one of the multiplicity of choice sets; and   a profit calculator to generate a respective profit metric for each facing combination in the list of facing combinations using the corresponding demand transfer matrix, the plurality of facing range parameters, and a subset of the plurality of profit metrics, to define a set of profit metrics.   
     
     
         20 . The system of  claim 19 , wherein the profit calculator includes a linear programming model solver to apply a linear programming technique. 
     
     
         21 . The system of  claim 19 , wherein the profit calculator includes a simulator with full replacement to simulate a plurality of sequential purchases by a respective plurality of customers. 
     
     
         22 . The system of  claim 19 , further comprising:
 a downscaling module to receive a number of facings limit, to compare a specified one of the plurality of facing range parameters to the number of facings limit, and to generate a reduced set of numbers of facings based on the specified one of the plurality of facing range parameters.   
     
     
         23 . The system of  claim 17 , wherein the storage unit is a first storage unit;
 wherein the global constraint parameter specifies a spatial constraint of a retail area in which the item assortment is to be disposed; and wherein the retail area is associated with a plurality of regions;   the system further comprising:   a second storage unit to store a plurality of spatial metrics, wherein each of the plurality of spatial metrics corresponds to a respective one of the plurality of regions.   
     
     
         24 . The system of  claim 23 , wherein the combinatorial problem solver includes:
 a multiple-choice knapsack problem solver to select at most one facing combination for each of the multiplicity of choice sets to define a global solution, and to generate a respective spatial metric for each selected facing combination;   a fixture splitter to split the global solution into a plurality of solutions, each of the plurality of solutions corresponding to a respective one of the plurality of regions; and   a multiple knapsack problem to optimize the plurality of solutions.   
     
     
         25 . A method in a computer system for generating an efficient item assortment associated with a plurality of items, to be disposed in a retail area having a plurality of regions, the method comprising:
 receiving item data that includes, for each of the plurality of items:
 a first metric associated with a physical parameter of the item; and 
 a second metric indicative of profitability of the item; 
   receiving retail region data that includes a plurality of metrics, wherein each of the plurality of metrics is associated with the physical parameter of a respective one of the plurality of regions;   receiving choice set data specifying a multiplicity of choice sets, wherein each of the multiplicity of choice sets includes several of the plurality of items, at least some of which are mutually substitutable;   receiving item interaction data that includes, for each of the multiplicity of choice sets, a metric of substitutability between items in the corresponding choice set;   generating a multiplicity of lists of facing combinations, wherein each of the multiplicity of lists corresponds to a respective one of the multiplicity of choice sets, and wherein each facing combination in each of the multiplicity of lists includes one or several facings of at least one of the items in the corresponding one of the multiplicity of choice sets;   calculating at least a profit metric and a physical parameter metric for each facing combination in each of the multiplicity of lists of facing combinations based on the first metric and the second metric of each item included in the facing combination and the interaction data associated with the corresponding choice set; and   selecting zero or more facing combinations from each of the multiplicity of lists of facing combinations to generate a selection so as to maximize a total profit associated with the selection in view of the retail region data and the first metric of each item included in the selection.   
     
     
         26 . The method of  claim 25 , wherein the item data further includes, for each of the plurality of items, a third metric indicative of a facing capacity of the item, wherein the facing capacity specifies a number of units associated with a single facing of the item; and wherein
 calculating the profit metric for each facing combination in each of the multiplicity of lists of facing combinations is further based on the third metric of each item included in the facing combination.   
     
     
         27 . The method of  claim 25 , wherein the physical parameter is a width, and wherein the plurality of regions corresponds to a plurality of merchandizing fixtures of the retail area. 
     
     
         28 . The method of  claim 25 , further comprising:
 splitting the selection into a plurality of selection portions, wherein each of the plurality of selection portions is to be disposed in a respective one of the plurality of regions.   
     
     
         29 . The method of  claim 25 , further comprising:
 identifying dominated facing combinations in each of the multiplicity of lists of facing combinations, wherein each dominated facing combination corresponds to a respective dominant facing combination so that the dominated facing combination and the respective dominant facing combination have the same physical parameter metric and different profit metrics;   removing dominated facing combinations prior to selecting zero or more facing combinations from each of the multiplicity of lists.   
     
     
         30 . A method in a computer system for generating an efficient item assortment for a plurality of items, the method comprising:
 obtaining a first plurality of parameters, wherein each of the first plurality of parameters includes a benefit metric of a respective one of the plurality of items;   obtaining a constraint parameter associated with the item assortment;   generating a plurality of facing combinations, each including one or more facings of one or more of the plurality of items;   generating a second plurality of parameters using the first plurality of parameters, wherein each of the second plurality of parameters includes a benefit metric of a respective one of the plurality of facing combinations;   maximizing a function of the second plurality of parameters, subject to a limitation associated with the constraint parameter, to generate an optimization result; and
 generating an item selection based on the optimization result. 
   
     
     
         31 . The method of  claim 30 , wherein each of the first plurality of parameters further includes a physical parameter metric of the respective one of the plurality of items; wherein
 each of the second plurality of parameters further includes a physical parameter metric of the respective one of the plurality of facing combinations.   
     
     
         32 . The method of  claim 30 , wherein the plurality of items define a multiplicity of choice sets, wherein at least some of the items in each of the multiplicity of choice sets are mutually substitutable; and wherein
 generating the plurality of facing combinations including generating a respective list of facing combinations for each of the multiplicity of choice sets.   
     
     
         33 . The method of  claim 32 , wherein maximizing the function of the second plurality of parameters includes selecting exactly one facing combination from each list of facing combinations. 
     
     
         34 . The method of  claim 32 , further comprising:
 obtaining item interaction data indicative of probabilities of substitutions between pairs of items in each of the multiplicity of choice sets; and wherein   generating the second plurality of parameters using the first plurality of parameters includes applying the item interaction data.   
     
     
         35 . The method of  claim 30 , wherein obtaining the constraint parameter includes:
 receiving a plurality of spatial metrics corresponding to a respective plurality of regions of a retail area; and   calculating a sum of the plurality of spatial metrics to generating a total spatial limitation; and wherein   maximizing the function of he second plurality of parameters includes maximizing the function subject to the total spatial limitation.   
     
     
         36 . The method of  claim 35 , wherein generating the item selection includes generating a plurality of sub-selections, each of the plurality of sub-selections corresponding to a respective one of the plurality of regions of the retail area, including:
 solving a multiple knapsack problem using the optimization result, the first plurality of parameters, and the plurality of spatial metrics.   
     
     
         37 . The method of  claim 30 , wherein generating the second plurality of parameters includes formatting the second plurality of parameters to comply with an input to a multiple-choice knapsack problem. 
     
     
         38 . The method of  claim 30 , wherein generating the second plurality of parameters includes applying at least one of a linear programming technique or a simulation technique. 
     
     
         39 . A method in a computer system for generating an efficient item assortment associated with a plurality of items, to be disposed in a retail area having a plurality of regions, the method comprising:
 obtaining a first plurality of parameters, wherein each of the first plurality of parameters is associated with a respective one of the plurality of items and includes:
 a benefit metric of the respective one of the plurality of items indicative of a financial benefit associated with a sale of one unit of the respective one of the plurality of items; and 
 a spatial metric of the respective one of the plurality of items specifying one of length, width, or height of the respective one of the plurality of items; 
   obtaining a plurality of spatial metrics, each of the plurality of spatial metrics corresponding to a respective one of the plurality of regions of the retail area;   obtaining choice set data specifying a multiplicity of choice sets associated with the plurality of items;   generating a plurality of facing combinations in accordance with the choice set data, wherein each of the plurality of facing combinations includes one or more facings of one or more items of a respective one of the multiplicity of choice sets;   generating a second plurality of parameters using the first plurality of parameters, wherein each of the second plurality of parameters corresponds to a respective one of the plurality of facing combinations and includes:
 a benefit metric of the respective one of the plurality of facing combinations indicative of an expected financial benefit associated with including the respective one of the plurality of facing combinations in the item assortment; and 
 a spatial metric of the respective one of the plurality of facing combinations specifying one of length, width, or height of the respective one of the plurality of facing combinations; 
   maximizing a function of the benefit metrics of the second plurality of parameters, subject to a limitation associated with the plurality of spatial metrics, to generate an optimization result; and
 generating an item selection based on the optimization result. 
   
     
     
         40 . A method in a computer system for generating an efficient item assortment associated with a plurality of items, to be disposed in a retail area having a plurality of regions, the method comprising:
 obtaining profitability data that includes a plurality of tuples, each of the plurality of tuples corresponding to a spatial metric of a particular combination of items and a profitability metric associated with the particular combination of items, wherein the profitability data is stored on a computer-readable medium;   using a first constraint parameter to automatically select a first tuple in the plurality of tuples to define an initial solution;   automatically applying at least one business rule to the initial solution; and   if the at least one business rule is not satisfied:
 obtaining a near-optimality parameter; 
 automatically selecting a subset of the plurality of tuples to define a region limited by the near-optimality parameter; and 
 automatically selecting a second tuple in the subset of the plurality of tuples to define a near-optimal solution. 
   
     
     
         41 . The method of  claim 40 , wherein the near-optimal solution is associated with the highest profitability metric in the selected subset. 
     
     
         42 . The method of  claim 40 , wherein the near-optimality parameter is associated with the profitability metric. 
     
     
         43 . The method of  claim 42 , wherein the near-optimality parameter is a first near-optimality parameter; the method further comprising:
 obtaining a second near-optimality parameter associated with the spatial metric; wherein   the region is limited by the first near-optimality parameter and the second near-optimality parameter.   
     
     
         44 . The method of  claim 40 , further comprising:
 applying the at least one business rule to the near-optimal solution; and   if the at least one business rule is not satisfied:
 reducing the subset of the plurality of tuples to define a smaller region; and 
 selecting a third tuple in the reduced subset of the plurality of tuples to define an updated near-optimal solution.