Method and apparatus for path planning and distance calculation

• US 7,920,961 B2
• Filed: 08/29/2007
• Issued: 04/05/2011
• Est. Priority Date: 08/29/2007
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Reinhardt, Christian, Kappallo, Jan, Puchta, Markus, Sabelfeld, Wassili, Mandel, Alexander
• Primary Examiner(s): Hellner; Mark
• Assistant Examiner(s): Diacou; Ari M
• Application Number:
  US11/847,166
• Publication Number:
  US 20090063035A1
• Time in Patent Office: 1,315 Days
• Field of Search: 700/214, 700/228, 700/99, 700/112, 700/302, 700/303, 701/200, 701/300
• US Class Current: 701/200
• CPC Class Codes: G06F 30/18 Network design, e.g. design based on topological or interconnect aspects of utility systems, piping, heating ventilation air conditioning [HVAC] or cabling circuit design at the physical level G06F30/39; network planning tools for wireless communication networks H04W16/18
• 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

Abstract

Methods and apparatuses enable generation of a managed space layout model defining permissible pathways for travel through the managed space. Each permissible pathway can be defined as a line segment or an edge bounded by coordinate pairs. Items and locations within the managed space are associated with permissible pathways, which association defines how the items/locations can be reached via travel through the managed space. The information can be saved as a network of nodes, which defines the intersection of the permissible pathways and includes information about the pathways. With the layout model, a path can be determined through the managed space to accomplish work in the managed space. The layout data allows a path distance to be calculated for a given work task that involves travel through the managed space.

Claims

1. A warehouse management system comprising:

a model generator to define a layout model of an area of a warehouse and save the model to a storage system, the model generator having

a layout analyzer to receive layout data for the area, the layout data including a grid representation of the area with structural features of the area indicated by coordinates on the grid;

a pathway definition module to define edges in the area, each edge representing a permissible pathway indicating where travel through the area is permissible, the edges being line segments bounded by a pair of coordinates; and

a node network generator to generate a network of nodes for the area where each node represents an end of each edge; and

a path generator to generate a path from the layout model for a task within the area, the path generator having

a layout analyzer to receive the layout model and identify a starting location and a task location within the area; and

a path calculator to generate a path from the starting location to the task location based on the edges defined within the layout model.

2. The method of claim 1, wherein to generate the path from the starting location to the target location comprises:

associating the task location with a particular permissible pathway of the model.

3. The system of claim 1, wherein the system performs

a functionality check to determine that complete congruity exists among the nodes of the network, prior to generating the path.

4. The system of claim 1, wherein the system

calculates the distance of the generated path, based on distance information for each permissible pathway traversed in the generated path.

5. The system of claim 1, wherein the path calculator further comprises:

a distance calculator to calculate a travel distance for the task.

6. The system of claim 1, further comprising:

a functionality check module coupled to the path calculator to determine whether the layout model includes a permissible path from the starting location to the task location for a resource specified to execute the task.

7. The system of claim 1, wherein to generate the path to the task location further comprises:

restricting the path based on the width and a size of a resource, where a path is defined that only traverses permissible pathways compatible in width with the size of the resource.

8. The system of claim 1, wherein to generate the path from the starting location to the task location comprises:

generating a shortest path.

9. The system of claim 8, wherein to generate the path from the starting location to the task location further comprises:

determining the shortest path for a given system resource, the system resource having one or more limitations on travel through the managed space based on size or movement capability.

10. The system of claim 8, wherein to generate the path from the starting location to the task location further comprises:

calculating the shortest path by applying one or more of a depth first search algorithm or a breadth first search algorithm to the network.

11. The system of claim 10, wherein applying one or more of the depth first search algorithm or the breadth first search algorithm comprises:

applying the depth first search algorithm up to a stopping criterion of a certain number of nodes of the network to generate a first feasible solution; and

then

applying the breadth first search algorithm to the network to refine the first feasible solution.

12. The system of claim 10, wherein applying one or more of the depth first search algorithm or the breadth first search algorithm comprises:

applying the depth first search algorithm to generate a first feasible solution; and

then

applying the breadth first search algorithm up to a stopping criterion of a certain number of nodes of the network to refine the first feasible solution.

13. An article of manufacture comprising a machine readable medium having content stored thereon to provide instructions to cause a machine to perform operations including:

obtaining layout data for a managed space, the layout data including a grid representation of the managed space and structural features of the managed space indicated by coordinates on the grid;

defining edges that represent permissible pathways for the managed space based on the layout data, the permissible pathways indicating areas of the managed space where travel through the managed space is permissible, the edges being line segments bounded by a pair of coordinates;

generating a network of nodes for the managed space where each node represents an end of each edge; and

saving the network of nodes to a storage system as a model for path planning for the managed space.

14. The article of manufacture of claim 13, wherein the content to provide instructions for defining the edges further comprises content to provide instructions for

defining each aisle of a warehouse as an edge, and each end of each aisle is represented by a node of the network of nodes.

15. The article of manufacture of claim 13, wherein the content further provides instructions to cause the machine to perform operations including:

perform a distance calculation on the network of nodes for a specified process that requires travel through the managed space; and

defining an engineered labor standard based at least in part on an expected time to perform the travel of the calculated distance through the managed space.

16. The article of manufacture of claim 13, further comprises content to provide instructions for:

generating a path for a specified resource, including performing a functionality test on the network of nodes to determine whether a path exists between a starting location and an identified location for the specified resource.

17. The article of manufacture of claim 16, wherein the content to provide instructions for generating the path for the specified resource from the starting location to the identified location further comprises content to provide instructions for

determining the starting location.

18. The article of manufacture of claim 16, wherein the content further provides instructions to cause the machine to perform operations including:

performing a distance calculation on the generated path.

19. The article of manufacture of claim 18, wherein the content to provide instructions for performing the distance calculation further comprises content to provide instructions for

applying a depth first search algorithm up to a stopping criterion of a certain number of nodes of the network to generate a feasible solution.

20. The article of manufacture of claim 18, wherein the content to provide instructions for performing the distance calculation further comprises content to provide instructions for

applying a user-selected distance calculation metric selected from the group consisting of a Manhattan distance calculation metric and a Euclidean distance calculation metric.

21. A computer-implemented method comprising:

obtaining layout data for a managed space, the layout data including a grid representation of the managed space and structural features of the managed space indicated by coordinates on the grid;

defining permissible pathways for the managed space based on the layout data, the permissible pathways indicating areas of the managed space where travel through the managed space is permissible, the permissible pathways represented as line segments bounded by a pair of coordinates;

identifying every intersection of permissible pathways with each other;

generating a network of nodes for the managed space based on identifying the intersections, each node representing an intersection of permissible pathways; and

saving the network of nodes to a storage system as a model for path planning for the managed space.

22. The method of claim 21, wherein defining the permissible pathways comprises:

defining permissible pathways as line segments bounded by a pair of grid coordinates, each permissible pathway having an individual associated size.

23. The method of claim 21, wherein defining the permissible pathways comprises:

defining a permissible pathway as a line segment bounded by a pair of grid coordinates and a direction of travel from one of the coordinates to the other, where travel in the reverse direction is impermissible.

24. The method of claim 21, wherein defining the permissible pathways comprises:

defining a permissible pathway as a line segment bounded by a pair of grid coordinates and a permissible resource-type, where traversal by a different resource type is impermissible.

25. The method of claim 21, further comprising:

generating a general network by coupling the network of nodes together with another network of nodes by at least one pathway not present within either network individually; and

saving the general network to the storage system as a model for concurrently testing the two networks.

26. The method of claim 21, further comprising:

performing a functionality check to determine that complete congruity exists among the nodes of the network, prior to saving the network of nodes.