Computer-Implemented Systems And Methods For Pack Optimization

• US 20090271241A1
• Filed: 04/29/2008
• Published: 10/29/2009
• Est. Priority Date: 04/29/2008
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Pratt, Robert William
• Granted Patent: US 8,812,338 B2
• Time in Patent Office: Days
• US Class Current: 705/8
• CPC Class Codes: G05B 15/02 electric
• CPC Class Codes: G06Q 10/063 Operations research, analysis or management

Abstract

Computer-implemented systems and methods are provided for optimizing the distribution of packs of an item across an entity'"'"'s distribution network. Constraint values may be specified to limit the values that may be included in a planned distribution of packs. Also, heuristics may be used to reduce the computation time required to determine optimal values for a planned distribution of packs. Modeling of the planned distribution of packs and optimization of the number of packs to be distributed can be accomplished using a mixed-integer linear programming solver.

Claims

1. A computer-implemented method for optimizing a planned distribution of packs of an item among a plurality of retail stores, comprising:

specifying constraint values that limit what values may be included in the planned distribution of packs;

applying a heuristic to reduce the computation time required to determine optimal values for the planned distribution; and

using a mixed-integer linear programming solver to model the planned distribution of packs and determine optimized values for numbers of packs to be distributed to the plurality of retail stores.

2. The method of claim 1, further comprising processing the optimized values for numbers of packs to ensure that the optimized values for numbers of packs in the planned distribution satisfy the constraint values applicable to the planned distribution.

3. The method of claim 1, wherein the heuristic is a main rounding heuristic that forms a linear programming relaxation of a mixed-integer linear programming formulation and iterates between solving the linear programming relaxation and fixing one or more variables within the linear programming relaxation to an integer value.

4. The method of claim 3, wherein packs includes inner packs, each of which comprises a defined group of instances of the item that cannot be separated.

5. The method of claim 4, wherein packs includes outer packs, each of which comprises a defined group of inner packs that may be separated into its constituent inner packs as part of the planned distribution.

6. The method of claim 5, wherein the main rounding heuristic comprises a first stage, a second stage, a third stage, and a fourth stage;

the first stage comprising determining integer values for numbers of outer packs to be distributed to the plurality of stores;

the second stage comprising determining integer values for numbers of unopened outer packs to be distributed to each of the plurality of stores;

the third stage comprising determining integer values for numbers of loose inner packs to be distributed to each of the plurality of stores; and

the fourth stage comprising updating remaining decision variables using demand constraints, including numbers representing distributions of packs to one or more of the plurality of stores that differ from amounts requested by such stores.

7. The method of claim 6, wherein the linear programming solver operates in an iterative manner, setting one or more variables to integer values and re-solving the linear programming relaxation until each variable in a defined group of variables is set to an integer value.

8. The method of claim 6, wherein a limited quantity of packs is distributed across the plurality of stores by:

solving the linear programming relaxation related to distribution of the limited quantity of packs;

rounding down each variable representing a number of packs distributed to each of the plurality of stores in the solution of the linear programming relaxation to produce an integer pack distribution value for each of the plurality of stores;

determining a remainder R of packs by subtracting from the limited quantity of packs a sum of the integer pack distribution values for each of the plurality of stores;

finding among the plurality of stores those R stores for which the variables representing a pre-rounding number of packs in the solution to the linear programming relaxation include the greatest fractional portions; and

adding one pack from the limited quantity of packs to the integer pack distribution values for each of the R stores.

9. The method of claim 5, wherein a first stage of the main rounding heuristic comprises determining an integer value for a number of outer packs to be distributed to the plurality of stores by:

solving the linear programming relaxation;

rounding the number of outer packs that is closest to an integer value; and

iterating until the solution of the linear programming relaxation includes an integer-number distribution of outer packs to the plurality of stores.

10. The method of claim 9, wherein in a second stage of the main rounding heuristic comprises determining an integer value for a number of unopened outer packs to be distributed to each of the plurality of stores by:

solving the linear programming relaxation resulting from the first stage of the main rounding heuristic; and

rounding down the number of unopened outer packs distributed to each of the plurality of stores in the solution of the linear programming relaxation.

11. The method of claim 10, wherein in a third stage of the main rounding heuristic comprises determining an integer value for a number of loose inner packs to be distributed to each of the plurality of stores, wherein a total of the integer values for the numbers of loose inner packs to be distributed must agree with values for a number of opened outer packs determined by subtracting the number of unopened outer packs determined in the second stage from the total number of outer packs determined in the first stage and the defined group of inner packs of which each outer pack is comprised, by:

solving the linear programming relaxation resulting from the second stage of the main rounding heuristic;

rounding down each variable representing a number of loose inner packs distributed to each of the plurality of stores in the solution of the linear programming relaxation to produce an integer loose inner pack distribution value for each of the plurality of stores;

determining a remainder R according to the formula R=NumOpenedOuters*P−

sum(L₁ . . . L_n), where NumOpenedOuters is the number of opened outer packs, P is the number of inner packs in the defined group of inner packs of which each outer pack is comprised, and L₁ . . . L_n are the integer loose inner pack distribution values for each of the plurality of stores, which values are summed;

finding among the plurality of stores those R stores for which the variables representing a pre-rounding number of loose inner packs in the solution to the linear programming relaxation include the greatest fractional portions; and

adding one additional loose inner pack to the integer loose inner pack distribution values for each such store.

12. The method of claim 11, wherein in a fourth stage of the main rounding heuristic, values produced in the first, second, and third stages are used to update remaining decision variables using demand constraints, including numbers representing additional units distributed to one or more of the plurality of stores that are beyond amounts requested by such stores, for stores to which a greater number of units were distributed than were requested, and numbers representing units requested by one or more of the plurality of stores that were not distributed, for stores to which a lesser number of units were distributed than were requested.

13. The method of claim 1, wherein planned distributions that include multiple levels of distribution are modeled iteratively, with each level comprising a separate modeling problem, and combined to produce a single planned distribution incorporating the multiple levels of distribution.

14. The method of claim 1, wherein the constraint values are generated using the output of a demand modeling method.

15. The method of claim 1, wherein the constraint values limit one or more of the quantities chosen from the group:

a minimum number of units to be distributed to a particular store, a maximum number of units to be distributed to a particular store, and a minimum number of units to be distributed to each store in the plurality of stores.

16. A computer-implemented method for optimizing a planned distribution of packs of an item among a plurality of entities responsible for distributing or selling the item, comprising:

(a) determining whether one or more of the plurality of entities responsible for distributing or selling the item distributes or sells the item to another of the plurality of entities responsible for distributing or selling the item, and if so, removing from a model of the distribution problem those entities that distribute or sell to another of the plurality of entities;

(b) specifying constraint values that limit what values may be included in the planned distribution of packs;

(c) applying a heuristic in order to reduce the computation time required to determine optimal values for the planned distribution; and

(d) using a mixed-integer linear programming solver to model the planned distribution of packs and determine optimized values for numbers of packs to be distributed to each of the remaining plurality of entities responsible for distributing and/or selling the item.

17. The computer-implemented method of claim 16, further comprising:

(e) performing further processing on the optimized values for numbers of packs to ensure that the optimized values for numbers of packs satisfy the constraint values applicable to the planned distribution of packs.

18. The computer-implemented method of claim 17, further comprising:

(f) if any of the plurality of entities that are responsible for distributing and/or selling the item were removed in step (a), then repeating steps (a)-(e) only for the entities that were removed in step (a), wherein the planned distribution or distributions determined during the one or more previous iterations of steps (a)-(e) constitutes an input to the next iteration of steps (a)-(e).

19. A system for optimizing a planned distribution of packs of an item among a plurality of retail stores, comprising:

a data store for storing constraint values that limit what values may be included in the planned distribution of packs;

software instructions configured to apply a heuristic to reduce the computation time required to determine optimal values for the planned distribution; and

software instructions configured to solve mixed-integer linear programming problems or linear programming relaxations to model the planned distribution of packs and determine optimized values for numbers of packs to be distributed to each of the plurality of retail stores.

20. The system of claim 19, further comprising software instructions configured to process the optimized values for numbers of packs in the planned distribution to ensure that the optimized values for numbers of packs in the planned distribution satisfy the constraint values applicable to the planned distribution.