Robot control system for minimizing a number of racks used for order picking

• US 10,329,090 B2
• Filed: 08/04/2017
• Issued: 06/25/2019
• Est. Priority Date: 08/04/2017
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Wang, Yonghui, Han, Yingjie, Zhao, Xutan, Zhang, Zhengxiang
• Primary Examiner(s): Logan, Kyle O
• Application Number:
  US15/669,150
• Publication Number:
  US 20190039830A1
• Time in Patent Office: 690 Days
• Field of Search: 700216
• CPC Class Codes: B65G 1/1378 the orders being assembled on fixed commissioning areas remote from the storage areas
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

Techniques are provided for controlling an order-picking, rack-transporting robot. More specifically, the robot is controlled to select a minimized number of movable racks storing ordered products identified in one or more orders for product deliveries, while still ensuring that all ordered products are included.

Claims

1. A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable storage medium and comprising instructions that, when executed, are configured to cause at least one computing device to:

identify an order set of ordered products from among a plurality of products stocked using a plurality of movable racks, the ordered products including a plurality of product types, wherein each movable rack is retrievable by a rack-transporting robot, and at least some of the ordered products, of the same product type, are stocked on different ones of the movable racks;

construct a robot control instruction directing the rack-transporting robot among the plurality of movable racks to thereby retrieve the order set for delivery, including

identifying a primary movable rack of the plurality of movable racks that includes a threshold number of ordered products of corresponding product types,

iteratively identifying subsequent movable racks of the plurality of movable racks, wherein each iteration identifies a subsequent movable rack that includes ordered products adding to a number of ordered products of remaining product types of the plurality of product types,

determining that a current iteration provides a rackset candidate when the identified movable racks include all of the ordered products of the plurality of product types,

identifying an updated primary movable rack of the plurality of movable racks that is different from the primary movable rack,

iteratively identifying subsequent, updated movable racks of the plurality of movable racks, wherein each iteration identifies a subsequent, updated movable rack that includes ordered products adding to an updated number of ordered products of remaining product types of the plurality of product types,

determining that an updated current iteration provides an updated rackset candidate when the identified updated movable racks include all of the ordered products of the plurality of product types,

constructing the robot control instruction using a selected rackset candidate from the rackset candidate and the updated rackset candidate, the selected rackset candidate having a minimized number of movable racks included therein; and

provide the robot control instruction to the rack-transporting robot for retrieval of the identified movable racks and transportation thereof to at least one location for the delivery of the ordered products.

2. The computer program product of claim 1, wherein the instructions, when executed, are further configured to:

identify the primary movable rack as a maximum matching rack in which the threshold number represents a maximum available number of the ordered products stored using any of the plurality of movable racks.

3. The computer program product of claim 1, wherein the instructions, when executed, are further configured to:

iteratively identify the subsequent movable racks of the plurality of movable racks by, at each iteration, and identifying the subsequent movable rack for the current iteration as having a maximum number of ordered products that have not yet been identified within at least one movable rack during at least one previous iteration.

4. The computer program product of claim 1, wherein the instructions, when executed, are further configured to:

identify the updated primary movable rack as a maximum matching rack including a maximum available number of the ordered products stored using any of the plurality of movable racks, other than the primary movable rack.

5. The computer program product of claim 1, wherein the instructions, when executed, are further configured to:

construct the robot control instruction including

constructing a bitmap model as a matrix including the plurality of moveable racks and the ordered products on perpendicular axes; and

representing ordered products stored using each rack of the plurality of moveable racks by constructing a bit representation including, for each rack, a bit value of one when a corresponding ordered product is included, and a bit value of zero when a corresponding ordered product is not included.

6. The computer program product of claim 5, wherein the instructions, when executed, are further configured to:

identify the primary movable rack as a maximum matching rack having a corresponding bit representation with a largest-available number of bits set equal to one.

7. The computer program product of claim 6, wherein the bitmap model includes a rack-specific count of ordered products for each rack, equal to a number of bit values set equal to one, and wherein the instructions, when executed, are further configured to:

iteratively identify subsequent movable racks of the plurality of movable racks, including

constructing, at each iteration, a bit representation of an offset value in which all ordered products included from at least one preceding iteration are represented using a bit value equal to one, and

updating the bitmap model including reducing the rack-specific count of ordered products for each rack that includes an ordered product included in the offset value.

8. The computer program product of claim 7, wherein the instructions, when executed, are further configured to:

iteratively identify subsequent movable racks of the plurality of movable racks, including performing rack selection based on a highest-available rack-specific count of ordered products, following the reducing of the rack-specific count of ordered products.

9. The computer program product of claim 7, wherein the instructions, when executed, are further configured to:

determine that the current iteration provides the rackset candidate when the identified movable racks include all of the ordered products of the plurality of product types, as represented by the offset value having all bits set equal to one.

10. A computer-implemented method, comprising:

identifying an order set of ordered products from among a plurality of products stocked using a plurality of movable racks, the ordered products including a plurality of product types, wherein each movable rack is retrievable by a rack-transporting robot, and at least some of the ordered products, of the same product type, are stocked on different ones of the movable racks;

constructing a robot control instruction directing the rack-transporting robot among the plurality of movable racks to thereby retrieve the order set for delivery, including

identifying a primary movable rack of the plurality of movable racks that includes a threshold number of ordered products of corresponding product types,

iteratively identifying subsequent movable racks of the plurality of movable racks, wherein each iteration identifies a subsequent movable rack that includes ordered products adding to a number of ordered products of remaining product types of the plurality of product types,

determining that a current iteration provides a rackset candidate when the identified movable racks include all of the ordered products of the plurality of product types,

identifying an updated primary movable rack of the plurality of movable racks that is different from the primary movable rack,

iteratively identifying subsequent, updated movable racks of the plurality of movable racks, wherein each iteration identifies a subsequent, updated movable rack that includes ordered products adding to an updated number of ordered products of remaining product types of the plurality of product types,

determining that an updated current iteration provides an updated rackset candidate when the identified updated movable racks include all of the ordered products of the plurality of product types,

constructing the robot control instruction using a selected rackset candidate from the rackset candidate and the updated rackset candidate, the selected rackset candidate having a minimized number of movable racks included therein; and

providing the robot control instruction to the rack-transporting robot for retrieval of the identified movable racks and transportation thereof to at least one location for the delivery of the ordered products.

11. The computer-implemented method of claim 10, wherein the identifying the primary movable rack comprises:

identifying a maximum matching rack in which the threshold number represents a maximum available number of the ordered products stored using any of the plurality of movable racks.

12. The computer-implemented method of claim 10, wherein the iteratively identifying the subsequent movable racks of the plurality of movable racks comprises, at each iteration:

identifying the subsequent movable rack for the current iteration as having a maximum number of ordered products that have not yet been identified within at least one movable rack during at least one previous iteration.

13. The computer-implemented method of claim 10, further comprising:

identifying the updated primary movable rack as a maximum matching rack including a maximum available number of the ordered products stored using any of the plurality of movable racks, other than the primary movable rack.

14. The computer-implemented method of claim 10, wherein constructing the robot control instruction includes:

constructing a bitmap model as a matrix including the plurality of moveable racks and the ordered products on perpendicular axes; and

representing ordered products stored using each rack of the plurality of moveable racks by constructing a bit representation including, for each rack, a bit value of one when a corresponding ordered product is included, and a bit value of zero when a corresponding ordered product is not included.

15. The computer-implemented method of claim 14, further comprising:

identifying the primary movable rack as a maximum matching rack having a corresponding bit representation with a largest-available number of bits set equal to one.

16. The computer-implemented method of claim 15, wherein the bitmap model includes a rack-specific count of ordered products for each rack, equal to a number of bit values set equal to one, and further comprising:

iteratively identifying subsequent movable racks of the plurality of movable racks, including

constructing, at each iteration, a bit representation of an offset value in which all ordered products included from at least one preceding iteration are represented using a bit value equal to one, and

updating the bitmap model including reducing the rack-specific count of ordered products for each rack that includes an ordered product included in the offset value.

17. The computer-implemented method of claim 16, wherein the iteratively identifying subsequent movable racks of the plurality of movable racks further comprises:

performing rack selection based on a highest-available rack-specific count of ordered products, following the reducing of the rack-specific count of ordered products.

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

determining that the current iteration provides the rackset candidate when the identified movable racks include all of the ordered products of the plurality of product types, as represented by the offset value having all bits set equal to one.

19. A computer program product, the computer program product being tangibly embodied on a non-transitory computer-readable storage medium and comprising instructions that, when executed, are configured to cause at least one computing device to:

receive at least one order for ordered products;

access an inventory database to determine storage locations of each of the ordered products on corresponding movable racks of a plurality of movable racks within a warehouse, wherein the corresponding movable racks store mixed product types and at least some of the ordered products are stored using multiple racks of the corresponding movable racks;

construct a bitmap model as a matrix including the corresponding movable racks and the ordered products on perpendicular axes;

represent ordered products stored using each rack of the corresponding movable racks by constructing a bit representation including, for each rack of the corresponding movable racks, a bit value of one when a corresponding ordered product is included, and a bit value of zero when a corresponding ordered product is not included;

storing product counts of ordered products in each corresponding movable rack, the product counts being set equal to a number of ones in the bit representations of the corresponding movable racks;

selecting a maximum matching rack of the corresponding movable racks, the maximum matching rack having a highest-available number of ones included in its corresponding bit representation;

reducing the product counts to reflect removal, for each corresponding movable rack, of each ordered product already included in the preceding maximum matching rack;

iteratively selecting a current maximum matching rack and reducing the product counts, until a rackset of all of the maximum matching racks includes all of the ordered products; and

providing a robot control instruction to a rack-transporting robot to retrieve the movable racks within the rackset, for packaging and delivery of the ordered products retrieved therefrom.

20. The computer program product of claim 19, wherein the instructions, when executed, are further configured to:

identify an updated rackset, including

resetting the bitmap model and product counts to an original state;

selecting an updated maximum matching rack that is different from the maximum matching rack;

reducing the re-set product counts to reflect removal, for each corresponding movable rack, of each ordered product already included in the preceding, updated maximum matching rack;

iteratively selecting a current, updated maximum matching rack and reducing the re-set product counts, until an updated rackset of all of the updated maximum matching racks includes all of the ordered products; and

selecting between the rackset and the updated rackset, based on which rackset includes fewer racks; and

providing a robot control instruction to a rack-transporting robot to retrieve the movable racks within the selected rackset.