Route Builder

• US 20150142168A1
• Filed: 11/21/2013
• Published: 05/21/2015
• Est. Priority Date: 11/21/2013
• Status: Active Grant

• Current Assignee: Intelligrated Incorporated (Honeywell International Inc.)
• Original Assignee: Intelligrated Incorporated (Honeywell International Inc.)
• Inventors: Holland, Mark C., Hays, Joshua P.
• Granted Patent: US 9,110,464 B2
• Time in Patent Office: Days
• US Class Current: 700/228
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202
• CPC Class Codes: G06Q 10/08 Logistics, e.g. warehousing, loading or distribution; Inventory or stock management

Abstract

Systems, methods, and devices of the various embodiments enable graph based routing of containers and adjustments of container routing based on one or more current material handling system state. The various embodiments enable examination and evaluation of the material handling systems using graphs to find an optimal route from a starting node in the material handling system to an ending node in the material handling system. In an embodiment, the graph may be a directed graph of edges and nodes of a material handling system. In an embodiment, the directed graph may include edge weights and the edge weights may be used to determine the optimal route for the container. In an embodiment, the edge weights may be updated as events occur in the material handling system which may result in dynamic routing of containers through the material handling system.

Claims

1. A method of optimizing container routes in a material handling system, comprising:

receiving, at a computing device, an indication of a starting node of a container in the material handling system;

receiving, at the computing device, an indication of an ending node of the container in the material handling system;

retrieving, at the computing device, a current graph of a material handling system;

identifying, at the computing device, any disabled nodes and edges in the current graph;

determining, at the computing device, the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges; and

sending the determined container route to a material handling system control module.

2. The method of claim 1, further comprising displaying the determined route on a display of the computing device.

3. The method of claim 1, wherein the material handling system includes a conveyor or a sorter.

4. The method of claim 1, wherein:

the current graph of the material handling system is a directional graph including edge weights; and

determining, at the computing device, the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges comprises determining, at the computing device, a route with a lowest total edge weight for the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges.

5. The method of claim 4, further comprising:

receiving an indication of an equipment status event; and

updating the current graph in response to receiving the indication of the equipment status event.

6. The method of claim 5, wherein:

the indication of the equipment status event is an indication of an enable or disable event for a node or edge; and

updating the current graph in response to receiving the indication of the equipment status event comprises updating the graph to change a status of a node or edge as enabled or disabled based on the indication of the enable or disable event.

7. The method of claim 5, wherein:

the indication of the equipment status event is an indication of a percentage utilization event; and

updating the current graph in response to receiving the indication of the equipment status event comprises changing an edge weight of the current graph based on the indication of the percentage utilization event.

8. The method of claim 5, further comprising:

determining, at the computing device, another container route with a new lowest total edge weight for another container through the material handling system from the starting node to the ending node based at least in part on the updated current graph avoiding any identified disabled nodes and edges; and

sending the determined another container route to the control module of the material handling system.

9. The method of claim 4, further comprising:

receiving an indication of a divert confirmation event; and

changing an edge weight of the current graph based on the indication of the divert confirmation event.

10. The method of claim 4, wherein the route with a lowest total edge weight for the container through the distribution center from the starting node to the ending node is determined at least in part using a minimum spanning tree algorithm.

11. A computing device, comprising:

a memory; and

a processor coupled to the memory, wherein the processor is configured with processor-executable instructions to perform operations comprising;

receiving, an indication of a starting node of a container in a material handling system;

receiving an indication of an ending node of the container in the material handling system;

retrieving, a current graph of a material handling system;

identifying, at the computing device, any disabled nodes and edges in the current graph;

determining the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges; and

sending the determined container route to a material handling system control module.

12. The computing device of claim 11, further comprising a display connected to the processor, wherein the processor is configured with processor-executable instructions to perform operations further comprising displaying the determined route on the display.

13. The computing device of claim 11, wherein the material handling system includes a conveyor or a sorter.

14. The computing device of claim 11, wherein the processor is configured with processor-executable instructions to perform operations such that:

the current graph of the material handling system is a directional graph including edge weights; and

determining the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges comprises determining a route with a lowest total edge weight for the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges.

15. The computing device of claim 14, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

receiving an indication of an equipment status event; and

updating the current graph in response to receiving the indication of the equipment status event.

16. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations such that:

the indication of the equipment status event is an indication of an enable or disable event for a node or edge; and

updating the current graph in response to receiving the indication of the equipment status event comprises updating the graph to change a status of a node or edge as enabled or disabled based on the indication of the enable or disable event.

17. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations such that:

the indication of the equipment status event is an indication of a percentage utilization event; and

updating the current graph in response to receiving the indication of the equipment status event comprises changing an edge weight of the current graph based on the indication of the percentage utilization event.

18. The computing device of claim 15, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

determining, at the computing device, another container route with a new lowest total edge weight for another container through the material handling system from the starting node to the ending node based at least in part on the updated current graph avoiding any identified disabled nodes and edges; and

sending the determined another container route to the control module of the material handling system.

19. The computing device of claim 14, wherein the processor is configured with processor-executable instructions to perform operations further comprising:

receiving an indication of a divert confirmation event; and

changing an edge weight of the current graph based on the indication of the divert confirmation event.

20. The computing device of claim 14, wherein the processor is configured with processor-executable instructions to perform operations such that the route with a lowest total edge weight for the container through the distribution center from the starting node to the ending node is determined at least in part using a minimum spanning tree algorithm.

21. A non-transitory processor readable storage medium having stored thereon processor-executable instructions configured to cause a processor to perform operations comprising:

receiving, an indication of a starting node of a container in a material handling system;

receiving an indication of an ending node of the container in the material handling system;

retrieving, a current graph of a material handling system;

identifying, at the computing device, any disabled nodes and edges in the current graph;

determining the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges; and

sending the determined container route to a material handling system control module.

22. The non-transitory processor readable storage medium of claim 21, wherein the stored processor-executable instructions are configured to cause a processor to perform operations further comprising displaying the determined route.

23. The non-transitory processor readable storage medium of claim 21, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that the material handling system includes a conveyor or a sorter.

24. The non-transitory processor readable storage medium of claim 21, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that:

the current graph of the material handling system is a directional graph including edge weights; and

determining the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges comprises determining a route with a lowest total edge weight for the container route through the material handling system from the starting node to the ending node based at least in part on the current graph avoiding any identified disabled nodes and edges.

25. The non-transitory processor readable storage medium of claim 24, wherein the stored processor-executable instructions are configured to cause a processor to perform operations further comprising:

receiving an indication of an equipment status event; and

updating the current graph in response to receiving the indication of the equipment status event.

26. The non-transitory processor readable storage medium of claim 25, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that:

the indication of the equipment status event is an indication of an enable or disable event for a node or edge; and

updating the current graph in response to receiving the indication of the equipment status event comprises updating the graph to change a status of a node or edge as enabled or disabled based on the indication of the enable or disable event.

27. The non-transitory processor readable storage medium of claim 25, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that:

the indication of the equipment status event is an indication of a percentage utilization event; and

updating the current graph in response to receiving the indication of the equipment status event comprises changing an edge weight of the current graph based on the indication of the percentage utilization event.

28. The non-transitory processor readable storage medium of claim 25, wherein the stored processor-executable instructions are configured to cause a processor to perform operations further comprising:

determining, at the computing device, another container route with a new lowest total edge weight for another container through the material handling system from the starting node to the ending node based at least in part on the updated current graph avoiding any identified disabled nodes and edges; and

sending the determined another container route to the control module of the material handling system.

29. The non-transitory processor readable storage medium of claim 24, wherein the stored processor-executable instructions are configured to cause a processor to perform operations further comprising:

receiving an indication of a divert confirmation event; and

changing an edge weight of the current graph based on the indication of the divert confirmation event.

30. The non-transitory processor readable storage medium of claim 24, wherein the stored processor-executable instructions are configured to cause a processor to perform operations such that the route with a lowest total edge weight for the container through the distribution center from the starting node to the ending node is determined at least in part using a minimum spanning tree algorithm.