Determining distances in a warehouse

• US 20070156372A1
• Filed: 04/28/2004
• Published: 07/05/2007
• Est. Priority Date: 07/31/2003
• Status: Abandoned Application

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Christ, Thomas, Schrankler, Ralf
• Application Number:
  US10/562,378
• Publication Number:
  US 20070156372A1
• Time in Patent Office: Days
• US Class Current: 702/158
• CPC Class Codes: G01C 21/206 specially adapted for indoor navigation
• 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/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders

Abstract

The invention provides methods and apparatus, including computer program products, for warehouse management. In warehouse management it is often necessary to determine the shortest distance a resource has to travel through a warehouse when moving from a location A to a location B. To determine distances the locations are grouped together in zones. For every zone at least one entry and one exit point or node is defined. The function of an entry node and an exit node may be provided by a single node. Every node is defined by its coordinates. The routing is performed in three steps. In the first step a route from a source storage bin to an exit node of the zone is determined. This step may be referred to as “intra zone routing”. The intra zone routing can be done based on a metric. In the second step the distance from the source zone to the destination zone is determined. This step may be called “inter zone routing”. The inter zone routing may be done using a “line-of-sight method”. The third step consists of determining the distance from the entry node of the destination zone to a destination storage bin. This is again an “intra zone routing” as described in the first step.

Claims

1. Method of determining a path length in a warehouse between a first location, which is in a source zone of the warehouse, and a second location, which is in a destination zone of the warehouse, each zone having at least one entry node and/or exit node, the method comprising the following steps:

a first step of determining the distance within the source zone between the first location and an exit node of the source zone;

a second step of determining the distance between the exit node of the source zone and an entry node of the destination zone;

a third step of determining the distance within the destination zone between the entry node of the destination zone and the second location;

a fourth step of obtaining the path length by summing up the distances determined in the preceding steps.

2. The method of claim 1, wherein the distance within a zone is determined by applying a metric defined in the zone.

3. The method of claim 1, wherein the distance between two zones is determined by applying a line-of-sight principle.

4. The method of claim 1, wherein the location is defined by coordinates within the zone.

5. The method of claim 1, wherein the exit node and the entry node are defined by coordinates within the respective zone.

6. The method of claim 2, wherein the metric applied in a zone is one of Euclidean metric and Manhattan metric.

7. The method of claim 3, wherein the line-of-sight principle comprises determining the distance of the direct way between the two zones.

8. The method of claim 7, wherein the second step comprises, in case there is an obstacle blocking the direct way between the two zones, determining an additional distance for a path around the obstacle.

9. The method of claim 1, wherein the distances between nodes of two different zones are looked up in a table which comprises pre-calculated distances of each pair of nodes of different zones.

10. A method of determining a path in a warehouse for movement of a resource between a first location, which is in a source zone of the warehouse, and a second location, which is in a destination zone of the warehouse, wherein the path length is determined with the method of claim 1.

11. The method of claim 10, wherein the path is routed based on properties of at least one of a resource, a route, and a node.

12. The method of claim 11, wherein the one path is determined which is the shortest path between the first location and the second location.

29. A computer-readable storage medium comprising code for performing the method of claim 1, when executed in a computer system.

13. Method of calculating a path in a warehouse between a first location, which is in a source zone of the warehouse, and a second location, which is in a destination zone of the warehouse, each zone having at least one entry node and/or exit node, the method comprising the following steps:

determining a route from the first location to an exit node of the source zone;

determining the distance within the source zone between the first location and the exit node of the source zone;

determining a route from the exit node of the source zone to a pick and drop point associated with the source zone;

determining the distance between the exit node of the source zone and the pick and drop point associated with the source zone;

determining a route from the pick and drop point associated with the source zone to a pick and drop point associated with the destination zone;

determining the distance between the pick and drop point associated with the source zone and the pick and drop point associated with the destination zone;

determining a route from the pick and drop point associated with the destination zone to an entry node of the destination zone;

determining the distance between the pick and drop point associated with the destination zone and the entry node of the destination zone;

determining a route between the entry node of the destination zone and the second location;

determining the distance within the destination zone between the entry node of the destination zone and the second location;

obtaining the path length by summing up the distances determined in the preceding steps.

14. The method of claim 13, wherein for each route, a resource is determined which is able to move on the route.

15. The method of claim 13, wherein only such routes are determined on which selected resources are able to move.

16. The method of claim 13, wherein the shortest path between the first location and the second location is determined.

17. The method of claim 13, wherein the one path is determined which satisfies best a cost criterion, the cost criterion taking into account at least one of distances of the routes, travel time for the resource on the routes, and characteristics of the resources.

18. The method of claim 13, wherein each route determining step is followed by a step of calculating a cost criterion, whereby calculating the cost criterion takes into account at least one of distances of the respective determined route, travel time for the resource on the respective determined route, and an average value of characteristics of all the resources for the respective determined route.

30. A computer-readable storage medium comprising code for performing the method of claim 13, when executed in a computer system.

19. A method of modeling a warehouse with a computer system, the warehouse comprising a plurality of bins for storing goods, a plurality of work centers for processing goods, and a plurality of resources for moving the goods in the warehouse;

the method comprising the following steps;

a first step of defining a first plurality of zones, each zone representing a grouping of bins, or a work center, whereby with each zone, at least one node is associated, the node representing an entry and/or exit point for resources to/from the zone, and whereby with each bin and with each node in a zone, coordinates are associated which are representative of their location in the zone;

a second step of defining a first plurality or routes, each route representing a path for movement of a resource between nodes of a pair of zones, whereby with each of the routes, a path length is associated which is representative of the length of the route;

a third step of defining a second plurality of routes, each route representing a path for movement of a resource within a zone between a bin and a node of the zone;

whereby with each of the routes, a path length is associated which is representative of the length of the route.

20. The method of claim 19, further comprising defining a plurality of resource types, each resource type representing a kind of facility used for movement of a good within the warehouse.

21. The method of claim 20, further comprising defining a plurality of exceptions, each exception representing an obstacle for movement of a resource type on a route, whereby with each obstacle, a path length is associated which is representative of the length of the detour caused for the resource type to move around the obstacle.

22. The method of claim 21, further comprising defining a plurality of mandatory routes, each mandatory route representing a forced route for movement of a resource type, whereby with each mandatory route, a path length is associated which is representative of the length or the mandatory route.

23. The method of claim 22, further comprising

a step of defining a further plurality of nodes, each of the nodes representing a predefined location in the warehouse outside the zones;

a step or defining a third plurality or routes, each of the routes representing a path for movement of a resource between a node of the further plurality of nodes and a another node, whereby with each of the routes, a path length is associated which is representative of the length of the route.

24. The method of claim 23, further comprising associating with each resource type attributes which are descriptive of physical properties of the resource type.

25. The method of claim 24, further comprising associating with each node attributes which are descriptive of physical properties of the node.

26. The method of claim 25, further comprising associating with each route attributes which are descriptive of physical properties of the route.

27. The method of claim 26, wherein the second and third pluralities of routes are stored in a set of tables, each of the routes being referenceable by the two nodes between which the route is defined.

28. The method of claim 27, further comprising defining a second plurality of zones, each or the zones representing an entry and/or exit point to/from the warehouse, whereby with each zone, at least one node is associated, the node representing an entry and/or exit point for resources to/from the zone.

31. A computer-readable storage medium comprising code for performing the method of claim 19, when executed in a computer system.