Granted Patent B2

US 11,049,065 · App. 16/024,744 · Granted Jun 29, 2021

Inventors: Sandeep Sikka (Natick, MA); Nitin Verma (Natick, MA); Michael Bhaskaran (Sherborn, MA)

Assignee: Staples, Inc.

G06Q10/087

Abstract

Claims (124)

1. A method comprising:

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster, wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining an order volume of the first SKU; and

determining that the order volume of the first SKU satisfies a threshold of SKU order volume;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

2. The method of claim 1 , wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining an order volume of a first SKU pair, the first SKU pair including the first SKU of the first cluster and the second SKU of the second cluster; and

determining that the order volume of the first SKU pair satisfies a threshold of SKU pair order volume.

3. The method of claim 1 , wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining the order volume of the first SKU;

determining a SKU replica threshold of the first SKU based on the order volume of the first SKU;

determining an order volume of a first SKU pair, the first SKU pair including the first SKU of the first cluster and the second SKU of the second cluster; and

determining a pair replica target of the first SKU pair based on the order volume of the first SKU pair.

4. The method of claim 1 , wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining a SKU replica count of the first SKU, the SKU replica count of the first SKU indicating a number of clusters that contain the first SKU;

determining that the SKU replica count of the first SKU satisfies a SKU replica threshold of the first SKU;

determining a pair replica count of a first SKU pair, the first SKU pair including the first SKU of the first cluster and the second SKU of the second cluster, the pair replica count of the first SKU pair indicating a number of clusters that contain the first SKU and the second SKU of the first SKU pair;

determining that the pair replica count of the first SKU pair is less than a pair replica target of the first SKU pair; and

responsive to determining that the SKU replica count of the first SKU satisfies the SKU replica threshold of the first SKU and determining that the pair replica count of the first SKU pair is less than the pair replica target of the first SKU pair, determining to replicate the first SKU of the first cluster to the second cluster.

5. The method of claim 1 , further comprising:

determining, from SKUs associated with a storage facility, to-be-clustered SKUs based on order volumes of the to-be-clustered SKUs;

generating an initial cluster including the to-be-clustered SKUs;

initializing a cluster queue, the cluster queue including the initial cluster; and wherein

determining the processing cluster includes determining the processing cluster to be a cluster that occupies a start position of the cluster queue.

6. The method of claim 1 , wherein determining the processing cluster includes:

determining the processing cluster to be a cluster that occupies a start position of a cluster queue; and the method comprises:

responsive to determining that the first cluster violates the defined constraint, appending the first cluster to an end position of the cluster queue.

7. The method of claim 1 , wherein determining whether the first cluster and the second cluster satisfy the defined constraint includes:

determining that the first cluster satisfies a defined threshold cluster size; and

determining that the second cluster satisfies the defined threshold cluster size.

8. The method of claim 1 , wherein dividing the processing cluster into the first cluster and the second cluster includes:

determining an isolated SKU in the processing cluster based on one or more first SKU affinities of the isolated SKU;

filtering the isolated SKU from the processing cluster; and

dividing the filtered processing cluster into the first cluster and the second cluster based on the SKU affinities between the one or more SKUs in the filtered processing cluster; and the method includes:

responsive to replicating the first SKU of the first cluster to the second cluster, computing a first attachment score between the isolated SKU and the first cluster and a second attachment score between the isolated SKU and the second cluster; and

assigning the isolated SKU to one of the first cluster and the second cluster based on the first attachment score between the isolated SKU and the first cluster and the second attachment score between the isolated SKU and the second cluster.

9. The method of claim 8 , wherein determining the isolated SKU in the processing cluster includes:

determining the one or more first SKU affinities between the isolated SKU in the processing cluster and one or more other SKUs in the processing cluster; and

determining that the one or more first SKU affinities between the isolated SKU and the one or more other SKUs satisfy a defined threshold SKU affinity.

10. The method of claim 8 , wherein computing the first attachment score between the isolated SKU and the first cluster includes:

determining order volumes of one or more SKU pairs, each SKU pair including the isolated SKU and a SKU in the first cluster; and

computing the first attachment score between the isolated SKU and the first cluster based on the order volumes of the one or more SKU pairs.

11. The method of claim 1 , wherein the processing cluster excludes a non-clustering SKU, and the method includes:

determining, from SKUs associated with a storage facility, the non-clustering SKU based on an order volume of the non-clustering SKU;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, computing a first attachment score between the non-clustering SKU and the first cluster and a second attachment score between the non-clustering SKU and the second cluster; and

assigning the non-clustering SKU to one of the first cluster and the second cluster based on the first attachment score between the non-clustering SKU and the first cluster and the second attachment score between the non-clustering SKU and the second cluster.

12. A method comprising:

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster, wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining an order volume of the first SKU;

determining a SKU replica threshold of the first SKU based on the order volume of the first SKU;

determining an order volume of a first SKU pair, the first SKU pair including the first SKU of the first cluster and the second SKU of the second cluster; and

determining a pair replica target of the first SKU pair based on the order volume of the first SKU pair;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

13. A method comprising:

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster, wherein determining the first SKU of the first cluster to be replicated to the second cluster includes:

determining a SKU replica count of the first SKU, the SKU replica count of the first SKU indicating a number of clusters that contain the first SKU;

determining that the SKU replica count of the first SKU satisfies a SKU replica threshold of the first SKU;

determining a pair replica count of a first SKU pair, the first SKU pair including the first SKU of the first cluster and the second SKU of the second cluster, the pair replica count of the first SKU pair indicating a number of clusters that contain the first SKU and the second SKU of the first SKU pair;

determining that the pair replica count of the first SKU pair is less than a pair replica target of the first SKU pair; and

responsive to determining that the SKU replica count of the first SKU satisfies the SKU replica threshold of the first SKU and determining that the pair replica count of the first SKU pair is less than the pair replica target of the first SKU pair, determining to replicate the first SKU of the first cluster to the second cluster;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

14. A method comprising:

determining, from SKUs associated with a storage facility, to-be-clustered SKUs based on order volumes of the to-be-clustered SKUs;

generating an initial cluster including the to-be-clustered SKUs;

initializing a cluster queue, the cluster queue including the initial cluster;

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item, wherein determining the processing cluster includes determining the processing cluster to be a cluster that occupies a start position of the cluster queue;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

15. A method comprising:

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item, wherein determining the processing cluster includes determining the processing cluster to be a cluster that occupies a start position of a cluster queue;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster violates the defined constraint, appending the first cluster to an end position of the cluster queue;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

16. A method comprising:

determining, by a processor, a processing cluster including one or more stock keeping units (SKUs), each of the one or more SKUs including an item identifier corresponding to an item;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster, wherein dividing the processing cluster into the first cluster and the second cluster includes:

determining an isolated SKU in the processing cluster based on one or more first SKU affinities of the isolated SKU;

filtering the isolated SKU from the processing cluster; and

dividing the filtered processing cluster into the first cluster and the second cluster based on the SKU affinities between the one or more SKUs in the filtered processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint, and computing a first attachment score between the isolated SKU and the first cluster and a second attachment score between the isolated SKU and the second cluster;

assigning the isolated SKU to one of the first cluster and the second cluster based on the first attachment score between the isolated SKU and the first cluster and the second attachment score between the isolated SKU and the second cluster;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

17. The method of claim 16 , wherein determining the isolated SKU in the processing cluster includes:

determining the one or more first SKU affinities between the isolated SKU in the processing cluster and one or more other SKUs in the processing cluster; and

determining that the one or more first SKU affinities between the isolated SKU and the one or more other SKUs satisfy a defined threshold SKU affinity.

18. The method of claim 16 , wherein computing the first attachment score between the isolated SKU and the first cluster includes:

determining order volumes of one or more SKU pairs, each SKU pair including the isolated SKU and a SKU in the first cluster; and

computing the first attachment score between the isolated SKU and the first cluster based on the order volumes of the one or more SKU pairs.

19. A method comprising:

determining, from one or more stock keeping units (SKUs) associated with a storage facility, a non-clustering SKU based on an order volume of the non-clustering SKU;

determining, by a processor, a processing cluster including one or more SKUs, each of the one or more SKUs including an item identifier corresponding to an item, wherein the processing cluster excludes the non-clustering SKU;

dividing, by the processor, the processing cluster into a first cluster and a second cluster based on SKU affinities between the one or more SKUs in the processing cluster;

determining, by the processor, a first SKU of the first cluster to be replicated to the second cluster based on a demand correlation between the first SKU of the first cluster and a second SKU of the second cluster;

replicating, by the processor, the first SKU of the first cluster to the second cluster;

responsive to replicating the first SKU of the first cluster to the second cluster, determining, by the processor, whether the first cluster and the second cluster satisfy a defined constraint;

responsive to determining that the first cluster and the second cluster satisfy the defined constraint, assigning, by the processor, the first cluster to a first physical location and assigning the second cluster to a second physical location, and computing a first attachment score between the non-clustering SKU and the first cluster and a second attachment score between the non-clustering SKU and the second cluster;

assigning the non-clustering SKU to one of the first cluster and the second cluster based on the first attachment score between the non-clustering SKU and the first cluster and the second attachment score between the non-clustering SKU and the second cluster; and

autonomously navigating, by the processor, an automated guided vehicle to the first physical location and to the second physical location based on the assignment of the first cluster and the second cluster.

Assignments (10)