Computer-implemented systems and methods for pack optimization

• US 8,812,338 B2
• Filed: 04/29/2008
• Issued: 08/19/2014
• Est. Priority Date: 04/29/2008
• Status: Active Grant

• Current Assignee: SAS Institute Incorporated
• Original Assignee: SAS Institute Incorporated
• Inventors: Pratt, Robert William
• Primary Examiner(s): Boswell, Beth V
• Assistant Examiner(s): Swartz, Stephen S
• Application Number:
  US12/111,312
• Publication Number:
  US 20090271241A1
• Time in Patent Office: 2,303 Days
• Field of Search: 414/902, 705/7.25, 705/7.31, 705/28
• US Class Current: 705/7.25
• 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 distribution, comprising:

receiving, using one or more data processors, inner pack definition data identifying a number of items within an inner pack, wherein each item is available in one or more varieties, and wherein the inner pack definition data includes a number of each variety in the inner pack;

receiving, using the one or more data processors, outer pack definition data associating a number of inner packs with an outer pack;

receiving, using the one or more data processors, demand data identifying a predicted demand for each variety of an item at one or more stores;

receiving, using the one or more data processors, one or more constraint values, wherein each constraint value identifies one or more limitations on a planned distribution of packs;

generating, using the one or more data processors, a pack optimization problem using the inner pack definition data, the outer pack definition data, the demand data, and the one or more constraints;

generating, using the one or more data processors, a revised pack optimization problem using one or more heuristics, wherein a heuristic performs a linear programming relaxation upon the pack optimization problem, and wherein solving the revised pack optimization problem requires less computation time than solving the pack optimization problem; and

generating, using the one or more data processors, the planned distribution of packs by solving the revised pack optimization problem, wherein solving includes using a mixed-integer linear programming solver to determine the number of inner packs and the number of outer packs that best fulfill the predicted demand for each of the one or more stores, and wherein solving further includes subtracting an inner pack from a particular store and adding the subtracted inner pack to another store based on a particular constraint value.

2. The method of claim 1, further comprising:

verifying that the planned distribution of packs satisfies the one or more constraint values.

3. The method of claim 1, wherein the heuristic is a main rounding heuristic, and wherein the main rounding heuristic solves the linear programming relaxation and fixes one or more variables within the linear programming relaxation.

4. The method of claim 3, wherein the outer packs may be opened and separated as part of the planned distribution.

5. The method of claim 4, wherein the main rounding heuristic includes determining integer values of outer packs to be distributed to the plurality of stores, determining integer values of unopened outer packs to be distributed to each of the plurality of stores, determining integer values of inner packs from opened outer packs to be distributed to each of the plurality of stores, and updating the determined integer values based on the constraint values.

6. The method of claim 5, wherein determining an integer value for a number of outer packs to be distributed to the one or more stores further comprises:

solving the linear programming relaxation; and

rounding the number of outer packs to be distributed to the one or more stores.

7. The method of claim 5, wherein determining an integer value for a number of unopened outer packs to be distributed to each of the one or more stores further comprises:

rounding down the number of unopened outer packs distributed to each of the one or more stores.

8. The method of claim 5, wherein determining an integer value for a number of loose inner packs to be distributed to each of the one or more stores further comprises:

rounding down a number of inner packs assigned to a first store, the rounding down generating a remainder of inner packs; and

adding the remainder of inner packs to one or more second stores.

9. The method of claim 1, wherein one or more of the one or more stores are over supplied in the planned distribution of packs, and wherein one or more of the one or more stores are under supplied in the planned distribution of packs.

10. The method of claim 1, wherein pack optimization problems are solved iteratively at different levels of a hierarchy.

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

12. The method of claim 1, wherein the constraint values are associated with a minimum number of units to be distributed to a particular store, a maximum number of units to be distributed to a particular store, or a minimum number of units to be distributed to each store in the one or more stores.

13. The method of claim 1, wherein demand data associated with store to store demand is removed from the received demand data.

14. A computer-implemented system for optimizing a distribution, comprising:

one or more data processors;

one or more computer-readable storage mediums containing instructions configured to cause the one or more processors to perform operations including;

receiving inner pack definition data identifying a number of items within an inner pack, wherein each item is available in one or more varieties, and wherein the inner pack definition data includes a number of each variety in the inner pack;

receiving outer pack definition data associating a number of inner packs with an outer pack;

receiving demand data identifying a predicted demand for each variety of an item at one or more stores;

receiving one or more constraint values, wherein each constraint value identifies one or more limitations on a planned distribution of packs;

generating a pack optimization problem using the inner pack definition data, the outer pack definition data, the demand data, and the one or more constraints;

generating a revised pack optimization problem using one or more heuristics, wherein a heuristic performs a linear programming relaxation upon the pack optimization problem, and wherein solving the revised pack optimization problem requires less computation time than solving the pack optimization problem; and

generating the planned distribution of packs by solving the revised pack optimization problem, wherein solving includes using a mixed-integer linear programming solver to determine the number of inner packs and the number of outer packs that best fulfill the predicted demand for each of the one or more stores.

15. A computer-program product for optimizing a distribution, tangibly embodied in a machine-readable non-transitory storage medium, including instructions configured to cause a data processing apparatus to:

receive inner pack definition data identifying a number of items within an inner pack, wherein each item is available in one or more varieties, and wherein the inner pack definition data includes a number of each variety in the inner pack;

receive outer pack definition data associating a number of inner packs with an outer pack;

receive demand data identifying a predicted demand for each variety of an item at one or more stores;

receive one or more constraint values, wherein each constraint value identifies one or more limitations on a planned distribution of packs;

generate a pack optimization problem using the inner pack definition data, the outer pack definition data, the demand data, and the one or more constraints;

generate a revised pack optimization problem using one or more heuristics, wherein a heuristic performs a linear programming relaxation upon the pack optimization problem, and wherein solving the revised pack optimization problem requires less computation time than solving the pack optimization problem; and

generate the planned distribution of packs by solving the revised pack optimization problem, wherein solving includes using a mixed-integer linear programming solver to determine the number of inner packs and the number of outer packs that best fulfill the predicted demand for each of the one or more stores.

16. The computer-program product of claim 15, wherein the non-transitory storage medium is a RAM.