CN111157000B - Method and apparatus for generating path information - Google Patents

Abstract

The embodiment of the application discloses a method and a device for generating path information. One embodiment of the method comprises: acquiring position information of at least one cargo to be picked; determining a channel for picking at least one goods to be picked in a predetermined channel set according to the position information; determining a picking path which takes a predetermined first position as a starting point and a predetermined second position as an end point and passes through the determined channel; determining the order picking path with the shortest length from the determined order picking paths; route information of the picking route with the shortest length is generated. The embodiment is beneficial to simplifying the solving process of the picking path with the shortest solving length on the premise of ensuring the accuracy of determining the shortest running path of the vehicle when picking the goods, improving the solving speed of the picking path with the shortest solving length and improving the picking efficiency of the goods.

Description

Method and device for generating route information

technical field

The embodiments of the present application relate to the field of computer technology, and in particular to a method and an apparatus for generating path information.

Background technique

At present, as a warehousing mode of human-machine collaboration, AGV (Automated Guided Vehicle, automatic guided transport vehicle) car can realize navigation based on SLAM (simultaneous localization and mapping, real-time positioning and map construction). Automatically drive to the picking point according to the planned route. Then the picker completes the picking task of the current picking point. The trolley continues to drive to the next picking point, and the picking personnel continue to pick. Until all picking tasks are completed. For all the picking points that the AGV trolley needs to reach, it is usually necessary to give a sequence to complete the picking of all the goods to be picked as quickly as possible.

In order to improve storage efficiency, the aisles in general warehouses are relatively narrow. In this scenario, there are usually two picking methods: one is to directly model and solve all the storage points to be picked; the other is not to consider The current task directly stipulates the order of all storage nodes (such as driving in S shape).

Contents of the invention

The embodiments of the present application propose a method and an apparatus for generating path information.

In the first aspect, the embodiment of the present application provides a method for generating route information, the method includes: obtaining the location information of at least one item to be picked; according to the location information, in a predetermined channel set, determine At least one channel for goods to be picked; determining a picking path starting from a predetermined first position and ending at a predetermined second position through the determined channel; from the determined picking path, determining the length Shortest Picking Path; Generates routing information for the shortest picking path.

In some embodiments, determining the picking path starting from the predetermined first position and ending at the predetermined second position through the determined channel includes: constructing a directed graph, wherein the directed graph includes : The node representing the starting point, the node representing the end point, and the node representing the end point of the determined channel. The pairwise nodes of the directed graph are connected, and the weight of the edge of the directed graph represents the distance between the corresponding positions of the two nodes connected by the edge. driving distance.

In some embodiments, from the determined picking paths, determining the picking path with the shortest length includes: from the directed graph, determining the node that represents the start point as the starting point, and the node that represents the end point as the end point, including representing The determined shortest path subgraph of nodes at the end points of the channel; determining the picking path corresponding to the shortest path subgraph as the picking path with the shortest length.

In some embodiments, from the directed graph, determine the shortest path subgraph with the node representing the starting point as the starting point, the node representing the end point as the end point, and the node representing the end point of the determined channel, including: from the directed In the figure, determine the path subgraph with the node representing the start point as the starting point, the node representing the end point as the end point, including the node representing the end point of the determined channel; the path subgraph that meets the preset conditions in the determined path subgraph The graph is determined as the target path subgraph; and the path subgraph with the shortest length is determined from the determined target path subgraph as the shortest path subgraph.

In some embodiments, the preset condition includes at least one of the following: among the nodes included in the path subgraph, the in-degree and the out-degree of nodes other than the characterizing start point and the characterizing end point are 1; the path subgraph does not include Ring; the edge connecting the two nodes corresponding to the two endpoints of the channel is the edge that the path subgraph passes through.

In some embodiments, the lanes are single row lanes.

In a second aspect, an embodiment of the present application provides a device for generating route information, the device comprising: an acquisition unit configured to acquire the location information of at least one item to be picked; a first determination unit configured to Information, in the predetermined channel set, determine the channel for picking at least one item to be picked; the second determination unit is configured to determine the predetermined first position as the starting point and the predetermined second position as the end point , the picking path passing through the determined channel; the third determining unit is configured to determine the picking path with the shortest length from the determined picking paths; the generating unit is configured to generate the picking path with the shortest length path information.

In some embodiments, the second determination unit includes: a construction module configured to construct a directed graph, wherein the directed graph includes: a node representing a start point, a node representing an end point, and a node representing an end point of the determined channel, Two nodes of the directed graph are connected, and the weight of the edge of the directed graph represents the driving distance between the positions corresponding to the two nodes connected by the edge.

In some embodiments, the third determination unit includes: a first determination module configured to determine from the directed graph that the node representing the starting point is the starting point and the node representing the ending point is the end point, including the node representing the determined path The shortest path subgraph of the node of the end point; the second determination module is configured to determine the picking path corresponding to the shortest path subgraph as the picking path with the shortest length.

In some embodiments, the first determination module includes: a first determination submodule configured to determine from the directed graph that the node representing the start point is the starting point and the node representing the end point is the end point, including the path that represents the determined path The path subgraph of the node of the endpoint; the second determination submodule is configured to determine the path subgraph that meets the preset conditions in the determined path subgraph as the target path subgraph; the third determination submodule is configured Determine the path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph.

In some embodiments, the preset condition includes at least one of the following: among the nodes included in the path subgraph, the in-degree and the out-degree of nodes other than the characterizing start point and the characterizing end point are 1; the path subgraph does not include Ring; the edge connecting the two nodes corresponding to the two endpoints of the channel is the edge that the path subgraph passes through.

In some embodiments, the lanes are single row lanes.

In the third aspect, the embodiment of the present application provides an electronic device for generating route information, including: one or more processors; a storage device, on which one or more programs are stored, when the above one or more programs Executed by the above-mentioned one or more processors, so that the one or more processors implement the method in any embodiment of the above-mentioned method for generating path information.

In a fourth aspect, the embodiment of the present application provides a computer-readable medium for generating path information, on which a computer program is stored, and when the program is executed by a processor, any one of the above-mentioned methods for generating path information is implemented. Example method.

In the method and device for generating route information provided in the embodiments of the present application, according to the position information of at least one item to be picked, the channel for picking at least one item to be picked is determined in a predetermined channel set, and then, the Taking the predetermined first position as the starting point and the predetermined second position as the end point, passing through the picking path of the determined channel, after that, determining the picking path with the shortest length from the determined picking paths, and finally , to generate the path information of the shortest picking path, so that by determining the shortest picking path, it helps to improve the picking efficiency of the goods, and helps to ensure the accuracy of the shortest path that the vehicle travels when picking the goods. Next, simplify the solution process of solving the picking path with the shortest length, increase the solving speed of picking the picking path with the shortest length, and increase the solving speed of picking the picking path with the shortest length.

Description of drawings

Other characteristics, objects and advantages of the present application will become more apparent by reading the detailed description of non-limiting embodiments made with reference to the following drawings:

FIG. 1 is an exemplary system architecture diagram to which an embodiment of the present application can be applied;

FIG. 2 is a flowchart of an embodiment of a method for generating path information according to the present application;

FIG. 3 is a schematic diagram of an application scenario of a method for generating path information according to the present application;

FIG. 4 is a flowchart of another embodiment of a method for generating path information according to the present application;

FIG. 5 is a schematic structural diagram of an embodiment of a device for generating route information according to the present application;

Fig. 6 is a schematic structural diagram of a computer system suitable for implementing the electronic device of the embodiment of the present application.

Detailed ways

The application will be further described in detail below in conjunction with the accompanying drawings and embodiments. It should be understood that the specific embodiments described here are only used to explain related inventions, rather than to limit the invention. It should also be noted that, for the convenience of description, only the parts related to the related invention are shown in the drawings.

It should be noted that, in the case of no conflict, the embodiments in the present application and the features in the embodiments can be combined with each other. The present application will be described in detail below with reference to the accompanying drawings and embodiments.

Fig. 1 shows an exemplary system architecture 100 to which the embodiment of the method for generating path information or the apparatus for generating path information of the embodiment of the present application can be applied.

As shown in FIG. 1 , the system architecture 100 may include terminal devices 101 , 102 , a server 103 , a network 104 and a vehicle 105 . The network 104 is used as a medium for providing communication links between the terminal devices 101 , 102 , the server 103 and the vehicle 105 . Network 104 may include various connection types, such as wires, wireless communication links, or fiber optic cables, among others.

The terminal devices 101 , 102 and the server 103 can interact with the vehicle 105 through the network 104 to receive or send messages (for example, receiving the location information of the vehicle 105 and sending instructions instructing the vehicle 105 to travel) and the like. Various communication client applications can be installed on the terminal devices 101 and 102, such as vehicle control applications, web browser applications, shopping applications, search applications, instant messaging tools, email clients, social platform software, and the like.

The terminal devices 101 and 102 may be hardware or software. When the terminal devices 101 and 102 are hardware, they may be various electronic devices with information transmission functions, including but not limited to smart phones, tablet computers, laptop computers, desktop computers and the like. When the terminal devices 101 and 102 are software, they can be installed in the electronic devices listed above. It can be implemented as multiple software or software modules (such as software or software modules for providing distributed services), or as a single software or software module. No specific limitation is made here.

The server 103 may be a server that provides various services, for example, a background server that provides support for calculations required by the terminal devices 101 , 102 or the vehicle 105 . The background server can analyze and process the received data such as the route planning request, and feed back the processing results (such as route information) to the terminal devices 101 , 102 or the vehicle 105 .

It should be noted that the method for generating path information provided by the embodiment of the present application can be executed by the terminal devices 101 and 102, and correspondingly, the means for generating path information can be set in the terminal devices 101 and 102; The method for generating path information provided in the embodiment can also be executed by the server 103, and correspondingly, the device for generating path information can also be set in the server 103; in addition, the method for generating path provided in the embodiment of the present application The information method can also be executed by the vehicle 105 (for example, the unit for generating route information in the vehicle 105 ), and correspondingly, the device for generating route information can also be set in the vehicle 105 .

It should be noted that the server may be hardware or software. When the server is hardware, it can be implemented as a distributed server cluster composed of multiple servers, or as a single server. When the server is software, it can be implemented as multiple software or software modules (such as software or software modules for providing distributed services), or as a single software or software module. No specific limitation is made here.

It should be understood that the numbers of terminal devices, networks and servers in Fig. 1 are only illustrative. According to the implementation needs, there can be any number of terminal devices, networks and servers. When the electronic device on which the information processing method runs does not need to perform data transmission with other electronic devices, the system architecture may not include other electronic devices except the electronic device on which the information processing method runs.

Continuing to refer to FIG. 2 , a flow 200 of an embodiment of the method for generating path information according to the present application is shown. The method for generating path information includes the following steps:

Step 201, acquire the location information of at least one item to be picked.

In this embodiment, the executing subject of the method for generating route information (for example, the server, terminal device or vehicle shown in FIG. 1 ) can acquire at least one waiting path from other electronic devices or locally through a wired connection or a wireless connection. The location information of the picked goods. Wherein, the above-mentioned goods to be picked may be goods to be picked. The above location information may represent the location of the goods to be picked.

Step 202, according to the position information, in the predetermined channel set, determine the channel for picking at least one item to be picked.

In this embodiment, according to the location information obtained in step 201, the execution subject may determine a channel for picking at least one item to be picked in the predetermined channel set.

In practice, generally, the goods to be picked can be stored in a warehouse, and the warehouse can be provided with equipment for placing goods (such as shelves, etc.). The above-mentioned equipment room for placing goods to be picked can form a channel for picking personnel to pick goods and for picking vehicles to drive in. The location information of the goods to be picked, the location information of the channel, and the like may be stored in the execution subject or other electronic devices communicatively connected with the execution subject. Thus, the above-mentioned executive body can send instructions to the above-mentioned vehicle to indicate the driving path of the vehicle, so that the picker can pick the goods to be picked. Here, the channel can be a one-way channel (a channel that cannot go backwards and can not turn around), or a two-way channel (a channel that can go backwards and can make a U-turn).

As an example, the execution subject may determine the channel closest to the position of the item to be selected from the channel set according to the location information of the item to be picked as the channel for picking the item to be picked.

Optionally, when the channel closest to the position of the cargo to be selected is occupied by other objects (such as other picking vehicles or obstacles, etc.), causing the nearest channel to be unable to drive in, the above-mentioned executive body can select from the above-mentioned channel set, Determining the channel second closest to the position of the item to be selected as the channel for picking the item to be selected.

In some optional implementation manners of this embodiment, the channel is a single-row channel. It can be understood that the narrower the aisle is set, the higher the storage capacity of the warehouse (the higher the utilization rate of the warehouse). Therefore, compared with the double-lane aisle, the single-lane aisle can improve the storage capacity of the warehouse; compared with the narrower aisle (such as the aisle that cannot be entered by vehicles), the single-lane aisle can save the physical strength of the pickers and improve the picking efficiency of the pickers. efficiency.

Step 203 , determining a picking path starting from the predetermined first position and ending at the predetermined second position and passing through the determined channel.

In this embodiment, the above-mentioned executive body may determine a picking path that starts from the predetermined first position and ends at the predetermined second position and passes through the determined channel. Wherein, the above-mentioned first position may be the position where the picking vehicle stops before picking, or it may be other positions in the warehouse where the picking vehicle can drive into, except for the above-mentioned position where the picking vehicle stops . The above-mentioned second position may be the position where the picking vehicle stops after picking, or it may be other positions in the warehouse where the picking vehicle can drive into, except for the above-mentioned position where the picking vehicle stops.

As an example, the above-mentioned execution subject may determine the starting point from the predetermined first position and the end point on the predetermined second position, and pass through all the picking routes of the determined channel, or may determine that the predetermined first position As the starting point, with the predetermined second position as the end point, passing through the determined channel and meeting the predetermined conditions (for example, the length of the determined picking path is less than other picking paths with the predetermined second position as the end point, passing through the determined channel) path) picking path.

In some optional implementation manners of this embodiment, the execution subject may perform step 203 as follows: construct a directed graph. Among them, the directed graph includes: the node representing the starting point, the node representing the end point and the node representing the end point of the determined channel, the two nodes of the directed graph are connected, and the weight of the edge of the directed graph represents the two nodes connected by the edge. The driving distance between the locations corresponding to nodes. Wherein, the end points of the channel may be the channel entry point and the exit point (for example, in FIG. 3 , the end points of the channel where the picking points 3028-3034 are located are the picking point 3028 and the picking point 3034). The travel distance may be the distance the pick vehicle is available to travel. It can be understood that when there is no obstacle between the line segment connecting the two positions, the length of the line segment can be the above-mentioned driving distance; The length of the path taken by avoiding obstacles from one location to another location is the above-mentioned driving distance.

Step 204, from the determined picking paths, determine the picking path with the shortest length.

In this embodiment, the execution subject may determine the shortest picking path from the determined picking paths.

As an example, when there is only one picking path determined by the execution subject through step 203, the execution subject may determine the selected picking path as the shortest picking path; When there is more than one path, the execution subject can determine the picking path with the shortest length by comparing the lengths of the determined picking paths.

In some optional implementations of this embodiment, when the above-mentioned step 203 is executed according to the above-mentioned way of constructing the directed graph, the above-mentioned execution subject may execute the step 204 according to the following steps:

The first step is to determine from the directed graph the shortest path subgraph starting from the node representing the start point and ending at the node representing the end point, including the node representing the end point of the determined channel.

The second step is to determine the picking path corresponding to the shortest path subgraph as the picking path with the shortest length.

It can be understood that the nodes included in the shortest path subgraph represent the starting point, the end point or the end point of the channel, and the edges of the shortest path subgraph represent the driving distance between the positions corresponding to the two nodes (including the starting point, the end point or the end point of the channel). Therefore, the above A shortest path subgraph may represent (ie correspond to) a picking path.

Step 205, generating path information of the shortest picking path.

In this embodiment, the execution subject may generate the path information of the shortest picking path. Wherein, the route information may indicate the order in which vehicles pass through various passages, as well as the entry point of each passage, and so on.

In some use cases, the above-mentioned execution subject may also send the above-mentioned path information to the vehicle (such as an AGV vehicle) to instruct the vehicle to travel.

Continue referring to FIG. 3 , which is a schematic diagram of an application scenario of the method for generating path information according to this embodiment. In the application scenario of FIG. 3 , the terminal device has acquired the location information of the goods 3101 , 3102 , 3103 and 3104 to be picked. Afterwards, according to the location information, the terminal device, in a predetermined channel set (including the channel where the picking points 3021-3027 for picking goods, the channel where the picking points 3028-3034 are located, and the channel where the picking points 3035-3041 are located, wherein, The endpoints of the channel where picking points 3021-3027 are located are picking points 3021 and 3027, the endpoints of the channel where picking points 3028-3034 are located are picking points 3028 and 3034, and the endpoints of the channel where picking points 3035-3041 are located are picking points In the point 3035 and the picking point 3041), the channel for picking the goods 3101-3104 to be picked is determined (that is, the channel where the picking points 3021-3027 are located and the channel where the picking points 3028-3034 are located). Subsequently, the above-mentioned terminal device determines the picking path starting from the predetermined first position 300 and ending at the predetermined second position 301, passing through the passages where the picking points 3021-3027 are located and the passages where the picking points 3028-3034 are located . Next, the terminal device determines the shortest picking path 310 (as shown by the dotted line in the figure) from the determined picking paths. Finally, the terminal device generates the path information of the picking path 310 with the shortest length. For example, the path information may be "300-3028-3029-3030-3031-3032-3033-3034-3027-3026-3025-3024-3023-3022-3021-301".

In the method provided by the above-mentioned embodiments of the present application, according to the acquired position information of at least one item to be picked, in the predetermined channel set, determine the channel for picking at least one item to be picked, and then determine the channel with the predetermined The first location is the starting point, the predetermined second location is the end point, and the picking path of the determined channel is passed through, and then the picking path with the shortest length is determined from the determined picking paths, and finally, the shortest length is generated Based on the path information of the picking path, based on determining the shortest picking path, it helps to improve the picking efficiency of the goods, and helps to simplify the solution under the premise of ensuring the accuracy of the shortest path of the vehicle when picking the goods. The process of solving the picking path with the shortest length, and improving the speed of solving the picking path with the shortest length.

Further referring to FIG. 4 , it shows a flow 400 of still another embodiment of the method for generating path information. The flow 400 of the method for generating path information includes the following steps:

Step 401, acquiring location information of at least one item to be picked.

In this embodiment, step 401 is basically the same as step 201 in the embodiment corresponding to FIG. 2 , and will not be repeated here.

Step 402, according to the position information, in the predetermined channel set, determine the channel for picking at least one item to be picked.

In this embodiment, step 402 is basically the same as step 202 in the embodiment corresponding to FIG. 2 , and will not be repeated here.

Step 403, building a directed graph.

In this embodiment, the executing subject of the method for generating route information (such as a server, a terminal device or a vehicle shown in FIG. 1 ) may construct a directed graph. Among them, the directed graph includes: the node representing the starting point, the node representing the end point and the node representing the end point of the determined channel, the two nodes of the directed graph are connected, and the weight of the edge of the directed graph represents the two nodes connected by the edge. The driving distance between the locations corresponding to nodes. Wherein, the end points of the channel may be the channel entry point and exit point. The travel distance may be the distance the pick vehicle is available to travel. It can be understood that when there is no obstacle between the line segment connecting the two positions, the length of the line segment can be the above-mentioned driving distance; The length of the path taken by avoiding obstacles from one location to another location is the above-mentioned driving distance.

As an example, the above execution subject may construct a directed graph G. Wherein, the directed graph G includes a node set V={v ₁ ,...,v _n }, wherein, n represents the number of nodes included in the directed graph G, node v ₁ represents the above-mentioned starting point, and node v _n represents the above-mentioned end point, Node v ₂ to node v _n-1 characterize the endpoints of the determined channel. Here, it is assumed that node v _i and node v _i+1 are two endpoints of a channel. Wherein, i is a positive even number smaller than n (thus, it can be ensured that the vehicle enters from one end point of the channel and drives out from the other end point of the channel, that is, passes through the channel). The set of edges is E, and (v _i , v _j ) represents an edge of the directed graph G from node v _i to node v _j . Any two nodes in a directed graph G are connected.

Step 404, from the directed graph, determine a path subgraph starting from the node representing the start point and ending at the node representing the end point, including the node representing the end point of the determined channel.

In this embodiment, the execution subject may determine from the directed graph the path subgraph starting from the node representing the start point and ending at the node representing the end point, including the node representing the end point of the determined channel.

As an example, the above execution subject can use 0 or 1 (or other identifiers) to indicate whether the edge (v _i , v _j ) is selected, for example:

Wherein, x _ij is used to identify whether the edge (v _i , v _j ) is selected.

Therefore, the above-mentioned execution subject can determine the above-mentioned path subgraph by determining the selected edges in the directed graph.

Step 405: Determine the path subgraph in the determined path subgraph that meets the preset condition as the target path subgraph.

In this embodiment, the execution subject may also determine a path subgraph that meets a preset condition in the determined path subgraph as the target path subgraph. Wherein, the aforementioned preset condition may be a pre-set condition for determining the target path subgraph, and the target path subgraph may be the path subgraph with the shortest length in the determined path subgraph, or may have certain characteristics (such as path subgraph excluding self-loops, etc.).

In some optional implementations of this embodiment, the preset conditions may include at least one of the following: among the nodes included in the path subgraph, the in-degree of nodes other than the characterizing start point and the characterizing end point is 1 and the out-degree is 1. The path subgraph does not include self-loops; the edge connecting the two nodes corresponding to the two endpoints of the channel is the edge passed by the path subgraph.

It can be understood that when the preset condition includes the above three items, the determined target path subgraph is usually the path subgraph with the shortest length among the determined path subgraphs.

Step 406: Determine the path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph.

In this embodiment, the execution subject may determine the path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph.

As an example, when there is only one sorting path determined by the above execution subject through step 405 (for example, the preset condition includes that among the nodes included in the path subgraph, the in-degree of nodes other than the representative start point and the representative end point is 1 and the out-degree is 1. When the path subgraph does not include the self-loop and the edge of the two nodes corresponding to the two endpoints of the connecting channel is the edge passed by the path subgraph), the above-mentioned executive body can determine a selected path as the shortest length of the selected path. The cargo path is used as the shortest path subgraph; when the execution subject determines more than one picking path through step 405, the execution subject can determine the picking path with the shortest length by comparing the lengths of the determined picking paths as The shortest path subgraph.

Step 407, determine the picking path corresponding to the shortest path subgraph as the picking path with the shortest length.

In this embodiment, the execution subject may determine the picking path corresponding to the shortest path subgraph as the picking path with the shortest length.

It can be understood that the nodes included in the shortest path subgraph represent the starting point, the end point or the end point of the channel, and the edges of the shortest path subgraph represent the distance between the corresponding positions (including the starting point, the end point or the end point of the channel) of the two nodes connected by the edge , therefore, the above-mentioned shortest path subgraph can represent (that is, correspond to) the picking path, and then, the above-mentioned execution subject can obtain the picking path with the shortest length.

Step 408, generating path information of the shortest picking path.

In this embodiment, step 408 is basically the same as step 205 in the embodiment corresponding to FIG. 2 , and will not be repeated here.

It can be seen from FIG. 4 that, compared with the embodiment corresponding to FIG. 2 , the process 400 of the method for generating path information in this embodiment highlights the step of using a directed graph to determine the picking path with the shortest length. Therefore, the scheme described in this embodiment can introduce constraint conditions to assist in determining the shortest picking path, thereby further simplifying the calculation of the shortest picking path on the premise of ensuring the accuracy of the shortest path that the vehicle travels when picking goods The solution process of the solution and the improvement of the solution speed of the picking path with the shortest length help to improve the picking efficiency of goods.

Further referring to FIG. 5 , as an implementation of the methods shown in the above figures, the present application provides an embodiment of a device for generating route information, which corresponds to the method embodiment shown in FIG. 2 , In addition to the features described below, this device embodiment may also include the same or corresponding features as those of the method embodiment shown in FIG. 2 . The device can be specifically applied to various electronic devices.

As shown in FIG. 5 , the apparatus 500 for generating path information in this embodiment includes: an acquiring unit 501 , a first determining unit 502 , a second determining unit 503 , a third determining unit 504 and a generating unit 505 . Wherein, the acquiring unit 501 is configured to acquire the location information of at least one item to be picked; the first determining unit 502 is configured to determine a channel for picking at least one item to be picked in a predetermined channel set according to the location information; The second determining unit 503 is configured to determine a picking path starting from a predetermined first position and ending at a predetermined second position through the determined channel; the third determining unit 504 is configured to start from the determined Among the picking paths, the picking path with the shortest length is determined; the generation unit 505 is configured to generate the path information of the picking path with the shortest length.

In this embodiment, the obtaining unit 501 of the apparatus 500 for generating route information may obtain the location information of at least one item to be picked from other electronic devices or locally through a wired or wireless connection. Wherein, the above-mentioned goods to be picked may be goods to be picked. The above location information may represent the location of the goods to be picked.

In this embodiment, based on the position information obtained by the acquiring unit 501, the first determining unit 502 may determine a channel for picking at least one item to be picked in the predetermined channel set.

In practice, generally, the goods to be picked can be stored in a warehouse, and the warehouse can be provided with equipment for placing goods (such as shelves, etc.). The above-mentioned equipment room for placing goods to be picked can form a channel for picking personnel to pick goods and for picking vehicles to drive in. The above-mentioned device 500 or other electronic devices communicatively connected with the above-mentioned device 500 may store the location information of the above-mentioned items to be picked, the location information of the channel, and the like. Thus, the above-mentioned device 500 can indicate the driving path of the vehicle by sending instructions to the above-mentioned vehicle, so that the picker can pick the goods to be picked. Here, the channel can be a one-way channel (a channel that cannot go backwards and can not turn around), or a two-way channel (a channel that can go backwards and can make a U-turn).

In this embodiment, the above-mentioned second determination unit 503 may determine a picking path starting from the predetermined first position and ending at the predetermined second position and passing through the determined channel. Wherein, the above-mentioned first position may be the position where the picking vehicle stops before picking, or it may be other positions in the warehouse where the picking vehicle can drive into, except for the above-mentioned position where the picking vehicle stops . The above-mentioned second position may be the position where the picking vehicle stops after picking, or it may be other positions in the warehouse where the picking vehicle can drive into, except for the above-mentioned position where the picking vehicle stops.

In this embodiment, the third determining unit 504 may determine the shortest picking path from the determined picking paths.

In this embodiment, the generating unit 505 may generate the path information of the shortest picking path. Wherein, the route information may indicate the order in which vehicles pass through various passages, as well as the entry point of each passage, and so on.

In some optional implementation manners of this embodiment, the second determining unit 503 may include: a construction module (not shown in the figure) configured to construct a directed graph. Among them, the directed graph includes: the node representing the starting point, the node representing the end point and the node representing the end point of the determined channel, the two nodes of the directed graph are connected, and the weight of the edge of the directed graph represents the two nodes connected by the edge. The driving distance between the locations corresponding to nodes. Wherein, the end points of the channel may be the channel entry point and exit point. The travel distance may be the distance the pick vehicle is available to travel. It can be understood that when there is no obstacle between the line segment connecting the two positions, the length of the line segment can be the above-mentioned driving distance; The length of the path taken by avoiding obstacles from one location to another location is the above-mentioned driving distance.

In some optional implementation manners of this embodiment, the third determining unit 504 may include: the first determining module (not shown in the figure) is configured to determine from the directed graph that the node representing the starting point is used as the starting point, With the node representing the end point as the end point, the shortest path subgraph including the node representing the end point of the determined channel; the second determination module (not shown in the figure) is configured to determine the picking path corresponding to the shortest path subgraph as the shortest path picking path.

It can be understood that the nodes included in the shortest path subgraph represent the starting point, the end point or the end point of the channel, and the edges of the shortest path subgraph represent the driving distance between the positions corresponding to the two nodes (including the starting point, the end point or the end point of the channel). Therefore, the above A shortest path subgraph may represent (ie correspond to) a picking path.

In some optional implementations of this embodiment, the first determining module (not shown in the figure) may include: the first determining submodule (not shown in the figure) is configured to determine from the directed graph The node representing the start point is the starting point, and the node representing the end point is the end point, including the path subgraph of the node representing the end point of the determined channel; the second determination submodule (not shown in the figure) is configured to convert the determined path The path subgraph that meets the preset conditions in the subgraph is determined as the target path subgraph; the third determination submodule (not shown in the figure) is configured to determine the path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph.

In some optional implementations of this embodiment, the preset conditions include at least one of the following: among the nodes included in the path subgraph, the in-degree of nodes other than the characterizing start point and the characterizing end point is 1 and the out-degree is 1 ; The path subgraph does not include self-loops; the edge connecting the two nodes corresponding to the two endpoints of the channel is the edge passed by the path subgraph.

It can be understood that when the preset condition includes the above three items, the determined target path subgraph is usually the path subgraph with the shortest length among the determined path subgraphs.

In some optional implementation manners of this embodiment, the channel is a single-row channel.

It can be understood that the narrower the aisle is set, the higher the storage capacity of the warehouse. Therefore, compared with the double-lane aisle, the single-lane aisle can improve the storage capacity of the warehouse; compared with the narrower aisle (such as the aisle that cannot be entered by vehicles), the single-lane aisle can save the physical strength of the pickers and improve the picking efficiency of the pickers. efficiency.

In the device provided by the above-mentioned embodiments of the present application, the acquisition unit 501 acquires the location information of at least one item to be picked, and then, the first determination unit 502 determines the location information for picking at least one item to be picked in a predetermined channel set according to the location information. The channel for picking goods, then, the second determining unit 503 determines the picking path starting from the predetermined first position and ending at the predetermined second position, passing through the determined channel, and then the third determining unit 504 From the determined picking paths, the picking path with the shortest length is determined, and finally, the generating unit 505 generates path information of the picking path with the shortest length, thereby helping to improve the picking of goods based on the picking path with the shortest length determined. Efficiency helps simplify the process of solving the picking path with the shortest length and improve the speed of solving the picking path with the shortest length while ensuring the accuracy of the shortest path that the vehicle travels when picking goods.

Referring now to FIG. 6 , it shows a schematic structural diagram of a computer system 600 suitable for implementing the electronic device of the embodiment of the present application. The electronic device shown in FIG. 6 is only an example, and should not limit the functions and scope of use of this embodiment of the present application.

As shown in FIG. 6 , a computer system 600 includes a central processing unit (CPU) 601 that can be programmed according to a program stored in a read-only memory (ROM) 602 or a program loaded from a storage section 608 into a random-access memory (RAM) 603 Instead, various appropriate actions and processes are performed. In the RAM 603, various programs and data required for the operation of the system 600 are also stored. The CPU 601, ROM 602, and RAM 603 are connected to each other through a bus 604. An input/output (I/O) interface 605 is also connected to the bus 604 .

The following components are connected to the I/O interface 605: an input section 606 including a keyboard, a mouse, etc.; an output section 607 including a cathode ray tube (CRT), a liquid crystal display (LCD), etc., and a speaker; a storage section 608 including a hard disk, etc. and a communication section 609 including a network interface card such as a LAN card, a modem, or the like. The communication section 609 performs communication processing via a network such as the Internet. A drive 610 is also connected to the I/O interface 605 as needed. A removable medium 611 such as a magnetic disk, optical disk, magneto-optical disk, semiconductor memory, etc. is mounted on the drive 610 as necessary so that a computer program read therefrom is installed into the storage section 608 as necessary.

In particular, according to an embodiment of the present disclosure, the processes described above with reference to the flowcharts can be implemented as computer software programs. For example, embodiments of the present disclosure include a computer program product, which includes a computer program carried on a computer-readable medium, where the computer program includes program codes for executing the methods shown in the flowcharts. In such an embodiment, the computer program may be downloaded and installed from a network via communication portion 609 and/or installed from removable media 611 . When the computer program is executed by the central processing unit (CPU) 601, the above-mentioned functions defined in the method of the present application are performed.

It should be noted that the computer-readable medium described in this application may be a computer-readable signal medium or a computer-readable storage medium or any combination of the two. A computer readable storage medium may be, for example, but not limited to, an electrical, magnetic, optical, electromagnetic, infrared, or semiconductor system, apparatus, or device, or any combination thereof. More specific examples of computer-readable storage media may include, but are not limited to, electrical connections with one or more wires, portable computer diskettes, hard disks, random access memory (RAM), read-only memory (ROM), erasable Programmable read-only memory (EPROM or flash memory), optical fiber, portable compact disk read-only memory (CD-ROM), optical storage device, magnetic storage device, or any suitable combination of the above. In the present application, a computer-readable storage medium may be any tangible medium that contains or stores a program that can be used by or in conjunction with an instruction execution system, apparatus, or device. In this application, however, a computer-readable signal medium may include a data signal propagated in baseband or as part of a carrier wave, in which computer-readable program codes are carried. Such propagated data signals may take many forms, including but not limited to electromagnetic signals, optical signals, or any suitable combination of the foregoing. A computer-readable signal medium may also be any computer-readable medium other than a computer-readable storage medium, which can send, propagate, or transmit a program for use by or in conjunction with an instruction execution system, apparatus, or device. . Program code embodied on a computer readable medium may be transmitted using any appropriate medium, including but not limited to wireless, wireline, optical fiber cable, RF, etc., or any suitable combination of the foregoing.

Computer program code for carrying out the operations of this application can be written in one or more programming languages, or combinations thereof, including object-oriented programming languages—such as Java, Smalltalk, C++, and conventional A procedural programming language—such as "C" or a similar programming language. The program code may execute entirely on the user's computer, partly on the user's computer, as a stand-alone software package, partly on the user's computer and partly on a remote computer or entirely on the remote computer or server. In cases involving a remote computer, the remote computer can be connected to the user computer through any kind of network, including a local area network (LAN) or a wide area network (WAN), or it can be connected to an external computer (such as through an Internet service provider). Internet connection).

The flowchart and block diagrams in the Figures illustrate the architecture, functionality, and operation of possible implementations of systems, methods and computer program products according to various embodiments of the present application. In this regard, each block in a flowchart or block diagram may represent a module, program segment, or portion of code that contains one or more logical functions for implementing specified executable instructions. It should also be noted that, in some alternative implementations, the functions noted in the block may occur out of the order noted in the figures. For example, two blocks shown in succession may, in fact, be executed substantially concurrently, or they may sometimes be executed in the reverse order, depending upon the functionality involved. It should also be noted that each block of the block diagrams and/or flowchart illustrations, and combinations of blocks in the block diagrams and/or flowchart illustrations, can be implemented by a dedicated hardware-based system that performs the specified functions or operations , or may be implemented by a combination of dedicated hardware and computer instructions.

The units involved in the embodiments described in the present application may be implemented by means of software or by means of hardware. The described units may also be set in a processor. For example, it may be described as: a processor includes an acquiring unit, a first determining unit, a second determining unit, a third determining unit, and a generating unit. Wherein, the names of these units do not constitute a limitation of the unit itself under certain circumstances, for example, the acquisition unit may also be described as "a unit for acquiring position information of at least one item to be picked".

As another aspect, the present application also provides a computer-readable medium. The computer-readable medium may be included in the electronic device described in the above-mentioned embodiments; or it may exist independently without being assembled into the electronic device. middle. The above-mentioned computer-readable medium carries one or more programs, and when the above-mentioned one or more programs are executed by the electronic device, the electronic device: acquires the location information of at least one item to be picked; according to the location information, at a predetermined In the channel set, determine the channel for picking at least one item to be picked; determine the picking path starting from the predetermined first position and ending at the predetermined second position through the determined channel; from the determined Among the picking paths, determine the picking path with the shortest length; generate the path information of the picking path with the shortest length.

The above description is only a preferred embodiment of the present application and an illustration of the applied technical principles. Those skilled in the art should understand that the scope of the invention involved in this application is not limited to the technical solution formed by the specific combination of the above-mentioned technical features, and should also cover the technical solutions formed by the above-mentioned technical features or without departing from the above-mentioned inventive concept. Other technical solutions formed by any combination of equivalent features. For example, a technical solution formed by replacing the above-mentioned features with technical features with similar functions disclosed in (but not limited to) this application.

Claims (12)

1. A method for generating path information, comprising: Obtaining location information of at least one item to be picked; According to the position information, in a predetermined set of passages, determine a passage for picking the at least one item to be picked, wherein the passage is a one-way passage; Constructing a directed graph, wherein the directed graph includes: a node representing a predetermined first position, a node representing a predetermined second position, and a node representing an end point of the determined channel, the first position comprising a location where the picking vehicle stopped before picking, the second location including a location where the picking vehicle stopped after picking, and the determined endpoints of the lane include entry points and exit points for the lane; Using the directed graph, determine a picking path starting from the first location and ending at the second location, passing through the determined aisle, wherein the determined picking path includes characterizing the determined aisle the endpoint of the node; Using the directed graph, from the determined picking paths, determine the picking path with the shortest length; generating path information of the picking path with the shortest length, where the path information is used to indicate the picking order of the at least one item to be picked; Wherein, according to the position information, in the predetermined channel set, determining the channel for picking the at least one item to be picked includes: For each item to be picked, in the channel set, determine the channel that is closest to the position indicated by the position information of the item to be picked and is not occupied as the channel for picking the item to be picked, and the channel in the channel set Impassable while occupied. 2. The method according to claim 1, wherein two nodes of the directed graph are connected, and the weight of the edges of the directed graph represents the travel distance between the positions corresponding to the two nodes connected by the edges. 3. The method according to claim 2, wherein, from the determined picking paths, determining the picking path with the shortest length comprises: From said directed graph, determining a shortest path subgraph starting from said node representing said starting point and ending at said node representing said end point, including nodes representing the end points of the determined path; Determining the picking path corresponding to the shortest path subgraph as the picking path with the shortest length. 4. The method according to claim 3, wherein, from the directed graph, determining the node that characterizes the starting point as a starting point and the node that characterizes the end point as an end point includes characterizing The determined shortest path subgraph of nodes at the endpoints of the channel, comprising: From said directed graph, determining a path subgraph starting from said node representing said starting point and ending at said node representing said end point, including nodes representing the end points of the determined channel; Determining a path subgraph that meets a preset condition in the determined path subgraph as a target path subgraph; Determine the path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph. 5. The method according to claim 4, wherein the preset conditions include at least one of the following: Among the nodes included in the path subgraph, the in-degree of nodes other than those representing the starting point and the end point is 1 and the out-degree is 1; Path subgraphs do not include self-loops; The edge connecting the two nodes corresponding to the two endpoints of the channel is the edge that the path subgraph passes through. 6. An apparatus for generating route information, comprising: An acquisition unit configured to acquire location information of at least one item to be picked; The first determining unit is configured to determine a channel for picking the at least one item to be picked in a predetermined channel set according to the position information, wherein the channel is a one-way channel; a building module configured to build a directed graph, wherein the directed graph includes: a node representing a predetermined first location, a node representing a predetermined second location, and a node representing an endpoint of a determined path, The first location includes a location where a picking vehicle stops prior to picking, and the second location includes a location where a picking vehicle stops after picking; The second determining unit is configured to use the directed graph to determine a picking path starting from the first position and ending at the second position and passing through the determined channel, wherein the first The location includes a location where the picking vehicle stopped before picking, the second location includes a location where the picking vehicle stopped after picking, and the determined endpoints of the lane include entry and exit points for the lane, wherein the determined the pick path includes nodes representing endpoints of the determined lanes; The third determination unit is configured to determine the shortest picking path from the determined picking paths by using the directed graph; a generating unit configured to generate path information of the picking path with the shortest length, the path information being used to indicate the picking order of the at least one item to be picked; Wherein, the first determining unit is further configured to: for each item to be picked, determine in the set of channels the closest unoccupied channel to the position indicated by the position information of the item to be picked as the channel for picking the item. The aisles of the goods to be picked, the aisles in the set of aisles are impassable when occupied. 7 . The device according to claim 6 , wherein two nodes of the directed graph are connected, and the weight of the edges of the directed graph represents the travel distance between the positions corresponding to the two nodes connected by the edges. 8. The device according to claim 7, wherein the third determining unit comprises: The first determining module is configured to determine, from the directed graph, the node that characterizes the starting point as the starting point and the node that characterizes the end point as the end point, including the node that characterizes the end point of the determined channel The shortest path subgraph of nodes; The second determining module is configured to determine the picking path corresponding to the shortest path subgraph as the picking path with the shortest length. 9. The apparatus according to claim 8, wherein the first determining module comprises: The first determination submodule is configured to determine from the directed graph that the node representing the start point is the starting point and the node representing the end point is the end point, including the end point representing the determined channel The path subgraph of the nodes of ; The second determination submodule is configured to determine a path subgraph in the determined path subgraph that meets preset conditions as a target path subgraph; The third determination submodule is configured to determine a path subgraph with the shortest length from the determined target path subgraph as the shortest path subgraph. 10. The device according to claim 9, wherein the preset condition comprises at least one of the following: Among the nodes included in the path subgraph, the in-degree of nodes other than those representing the starting point and the end point is 1 and the out-degree is 1; Path subgraphs do not include self-loops; The edge connecting the two nodes corresponding to the two endpoints of the channel is the edge that the path subgraph passes through. 11. An electronic device comprising: one or more processors; a storage device on which one or more programs are stored, When the one or more programs are executed by the one or more processors, the one or more processors are made to implement the method according to any one of claims 1-5. 12. A computer-readable medium, on which a computer program is stored, wherein, when the program is executed by a processor, the method according to any one of claims 1-5 is implemented.

Images