CN117764483A - Optimization method and system for picking path of warehouse logistics robot - Google Patents
Optimization method and system for picking path of warehouse logistics robot Download PDFInfo
- Publication number
- CN117764483A CN117764483A CN202311795729.8A CN202311795729A CN117764483A CN 117764483 A CN117764483 A CN 117764483A CN 202311795729 A CN202311795729 A CN 202311795729A CN 117764483 A CN117764483 A CN 117764483A
- Authority
- CN
- China
- Prior art keywords
- goods
- priority
- robot
- point
- cargo
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 64
- 238000005457 optimization Methods 0.000 title claims description 7
- 238000003860 storage Methods 0.000 claims abstract description 108
- 210000000349 chromosome Anatomy 0.000 claims abstract description 56
- 239000011159 matrix material Substances 0.000 claims abstract description 38
- 230000008569 process Effects 0.000 claims abstract description 13
- 230000005611 electricity Effects 0.000 claims description 16
- 238000010845 search algorithm Methods 0.000 claims description 15
- 238000003780 insertion Methods 0.000 claims description 11
- 230000037431 insertion Effects 0.000 claims description 11
- 230000008859 change Effects 0.000 claims description 8
- 239000013598 vector Substances 0.000 claims description 8
- 238000009826 distribution Methods 0.000 claims description 5
- 238000005070 sampling Methods 0.000 claims description 4
- 230000001174 ascending effect Effects 0.000 claims description 3
- 238000004364 calculation method Methods 0.000 claims description 3
- 238000012545 processing Methods 0.000 claims description 2
- 238000010586 diagram Methods 0.000 description 5
- 108090000623 proteins and genes Proteins 0.000 description 4
- 230000009466 transformation Effects 0.000 description 2
- 230000032258 transport Effects 0.000 description 2
- NAWXUBYGYWOOIX-SFHVURJKSA-N (2s)-2-[[4-[2-(2,4-diaminoquinazolin-6-yl)ethyl]benzoyl]amino]-4-methylidenepentanedioic acid Chemical compound C1=CC2=NC(N)=NC(N)=C2C=C1CCC1=CC=C(C(=O)N[C@@H](CC(=C)C(O)=O)C(O)=O)C=C1 NAWXUBYGYWOOIX-SFHVURJKSA-N 0.000 description 1
- 241000531116 Blitum bonus-henricus Species 0.000 description 1
- 235000008645 Chenopodium bonus henricus Nutrition 0.000 description 1
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 230000007547 defect Effects 0.000 description 1
- 238000011161 development Methods 0.000 description 1
- 238000012986 modification Methods 0.000 description 1
- 230000004048 modification Effects 0.000 description 1
- 238000006467 substitution reaction Methods 0.000 description 1
Abstract
The invention discloses a method and a system for optimizing a goods picking path of a storage logistics robot, which relate to the technical field of storage logistics robots and comprise the following steps: classifying the priority of the goods according to the order shipment sequence, and establishing the priority corresponding to the goods points; selecting different types of storage robots according to goods in different shapes, and establishing a pickability matrix corresponding to the storage robots and the goods; adopting three-section chromosome coding to respectively code cargo points, delivery priorities corresponding to the cargo points and a pickability matrix, and obtaining a three-section chromosome coding scheme; according to the three-section chromosome coding scheme, clustering the priority of the cargo shipment sequence and the distance between each cargo point and each priority center based on a mixed clustering algorithm; searching the path of the current cargo point after the clustering is completed by using a minimum cost method, and simultaneously changing the neighborhood structure of the three-section chromosome coding scheme by adopting a variable neighborhood searching algorithm in the searching process so as to obtain the optimal path.
Description
Technical Field
The invention relates to the technical field of storage logistics robots, in particular to a method and a system for optimizing a storage logistics robot picking path.
Background
The rapid development of electronic commerce pushes the quantity of express packages to be new, and the traditional warehouse center often uses a working mode of manually selecting goods, so that the mode has low shipment efficiency and high personnel cost due to the limited manual physical ability.
In order to improve the shipment efficiency of warehouse centers and reduce the cost, most warehouse centers currently use automatic guided vehicles (Automated Guided Vehicle, AGVs) to replace manual picking of the goods. The AGV determines goods shelves according to the order information to be picked, then moves to the bottoms of the goods shelves, jacks up the goods shelves and transports the goods shelves to a picking workbench, and goods delivery is completed. Such a mode of transportation fails to pick up cargo efficiently and accurately. Due to the height of the shelves, the AGVs not only need to travel slowly during transport, but also have a probability of collision. Aiming at the problems, the multifunctional storage robot is born. The transportation mode of the multifunctional storage robot is that the multifunctional storage robot firstly runs to a goods shelf where goods are located according to the demand of orders, the needed goods are grabbed by utilizing grabbing devices such as a vacuum chuck and a mechanical arm and then placed in a storage box carried by the multifunctional storage robot, and then the goods are transported to a picking workbench. With increasing importance of customer timeliness of goods arrival, the conventional transportation mode of the warehousing robot cannot meet the current customer demands. At present, an effective modeling and solving method is not seen in a shipment mode of the multifunctional warehousing robot aiming at order priority constraint.
In the prior art, a single gene chain coding and heuristic algorithm are adopted when the path problem of the traditional warehousing robot is solved. The single gene chain coding is that the order of picking goods points of the storage robot is represented by one gene chain. In addition, in solving the problem of the multifunctional warehousing robot with order priority, the capability of picking goods is different due to the difference in model of the multifunctional warehousing robot, so that the single-gene-chain code is not suitable for representing the picking sequence of the multifunctional warehousing robot and the pickability between the multifunctional warehousing robot and the goods. The traditional heuristic algorithm usually adopts a single gene chain coding mode, and the optimization of the sorting order of the multifunctional storage robot is realized through intelligent iterative evolution of the algorithm. However, because the multi-function warehousing robot has constraints of existence priority and model of the warehousing robot, the conventional heuristic algorithm is not suitable for representing such problems.
Disclosure of Invention
Aiming at the defect that the sorting path of the storage robot is difficult to optimize due to the constraint of the sorting priority and the model of the storage robot in the prior art, the invention provides the method and the system for optimizing the sorting path of the storage logistics robot, which establish three sections of chromosome coding schemes to respectively code the sorting performance of the cargo points, the priority and the correspondence of the multifunctional storage robot and the cargoes, and acquire the optimal path based on the mixed clustering operation and the variable neighborhood search algorithm of the minimum cost method, thereby solving the problem that the sorting order of the multifunctional storage robot cannot be optimized due to the constraint of the priority and the model of the storage robot in the prior art.
An optimization method of a warehouse logistics robot picking path comprises the following steps:
acquiring order information of the required goods;
according to order information of the goods, classifying the goods according to the order shipment sequence, and establishing a priority corresponding to the goods points;
selecting different types of storage robots according to goods in different shapes, and establishing a pickability matrix corresponding to the storage robots and the goods;
adopting a three-section chromosome coding method to respectively code the priority corresponding to the storage robot and the cargo point and the storage robot pickability matrix to obtain three-section chromosome codes;
according to the three-section chromosome coding, adopting a mixed clustering algorithm to cluster the priority of the cargo delivery sequence and the distance between each cargo point and each priority center;
searching paths of the clustered goods points by using a minimum cost method, and simultaneously changing a neighborhood structure of a three-section chromosome coding scheme by adopting a variable neighborhood searching algorithm in the searching process so as to obtain an optimal path; the method adopts a variable neighborhood search algorithm to change the neighborhood structure of the three-section chromosome coding scheme, and comprises the following specific processes: and under the double constraint that the priority of the goods points is the same and the model of the multifunctional warehousing robot is satisfied, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out.
Further, sorting the goods according to the order shipment sequence, and establishing the priority corresponding to the goods points, wherein the priority P corresponding to the goods points is established i ＝A，A＝{0，1，2}，P i =0 indicates that the cargo point priority is low; p (P) i =1 represents a cargo point priority medium; p (P) i =2 indicates that the cargo point has a high priority.
Further, selecting different types of storage robots according to goods in different shapes, and establishing a pickability matrix corresponding to the storage robots and the goods; wherein, the pickability of the goods corresponding to the warehousing robots is represented by an association matrix Mat, rows of the Mat represent the constraint vectors of the warehousing robots for providing picking for the goods i, and the collection of the constraint vectors is recorded as S i ，Mat represents a cargo point constraint vector which can be selected by the storage robot k, and a cargo point set served by the storage robot is marked as H k ，The matrix Mat is expressed as:
where K represents the set of storage robots k= {1,2,.. K denotes the stocker robot number, N denotes the goods set n= {1,2,3,4,..n },representing a decision variable, the item point 1 is 1 when the picking operation is provided by the warehousing robot k, and is otherwise 0.
Further, three-segment chromosome coding is adopted to respectively code cargo points, ex-warehouse priorities corresponding to the cargo points and pickability matrixes, and a three-segment chromosome coding scheme is obtained, and the method comprises the following steps:
generating a sequence of cargo points;
assigning the order priority to the appointed goods points according to the known order priority, and obtaining a chromosome coding scheme of the goods points corresponding to the order priority;
and carrying out coding operation on the corresponding relation between the storage robot and the goods according to the Mat matrix, and further obtaining a three-section chromosome coding scheme of the goods points, the priorities and the pickability matrix corresponding to the storage robot and the goods.
Further, according to the three-segment chromosome coding scheme, the priority of the cargo shipment sequence and the distance between each cargo point and each priority center are clustered by adopting a hybrid clustering algorithm, wherein the hybrid clustering algorithm comprises the steps of clustering the same priority together by using a DBSCAN to obtain clusters of each priority, calculating the position of a center by using a K-means algorithm, and clustering coordinate distances.
Further, the clustering of the same priorities together using DBSCAN results in clusters of each priority, comprising the steps of:
first for priority P i Cargo coordinate points=2 calculate a distance distribution matrix of cargo point coordinate set D, namely:
γ n×n ＝{D(i，j)|1≤i≤n，1≤j≤n}
the distance distribution matrix is subjected to ascending operation, and x elements are randomly selected in the ith rowElement composition gamma i
For gamma i The average number of the elements in the matrix is recorded asCalculating the value of i to obtain +.>
GeneratingRandomly selecting x objects in the cargo point coordinate set D, and sequentially calculating each +.>θ in list ps Neighborhood object number and sampling expectation of candidate values as MinP ts The parameters of (1) are as follows:
wherein N is i θ representing the ith object ps Neighborhood object number, minP ts Indicating the number of points at least contained in the adjacent area;
sequentially select and useAnd->Element θ ps And MinP ts Parameters are input into a DBSCAN algorithm to perform clustering operation on the goods coordinate set to respectively obtain corresponding clustering clusters under different input parameters, when the clustering clusters are continuously identical for 3 times, the output tends to be stable, the optimal clustering cluster number is recorded as M, and the clustering operation is repeatedly performed until aggregation is completedIf the cluster is not M, selecting the corresponding theta when the last cluster is selected ps And MinP ts As optimal parameters;
will give priority to P i ＝1，P i The above operations are performed sequentially=0.
Further, the method for obtaining the position of the center of mass by using the K-means algorithm and clustering the coordinate distances comprises the following steps:
calculating the coordinate center C of each priority level of the data processed by the DBSCAN algorithm;
calculating the distance between each goods point and the center of each priority;
on the condition that the cargo point priority constraint is satisfied, the cargo points with the same cargo point priority are allocated to the nearest coordinate center C K ；
Recalculating the center object position of each priority;
repeatedly calculating the distance between each cargo point and each priority center until the algorithm stops when the object classification in the cluster does not change, and outputting the set after the clustering processing
Further, the searching for the path of the current cargo point after the clustering is completed by using the least cost method comprises the following steps:
initializing the preprocessed data set, reading coordinate points of current data, and recording a current path as follows: current;
judging whether all the goods points are picked, if all the goods points are picked, finishing the algorithm, outputting the processed path and calculating the cost of the current path, and if the goods points are not picked, marking as C k The algorithm continues;
randomly selecting a certain non-picked cargo point C from the set of non-picked cargo points 1 C is carried out by 1 Current is added and marked C 1 Has been picked;
with the goods point C 1 Searching for a non-picked item set C as a base point k Point p of medium cargo 1 And cargo point p 2 And calculate its running cost as cost 1 、cost 2 ；
Comparing costs in case of meeting the storage robot load, priority and storage robot pickability 1 、cost 2 If cost is the cost 1 ＜cost 2 Then p is 1 Adding Current path Current, otherwise, adding p 2 The Current path Current is added.
Further, the method also comprises the step of establishing an objective function of the multifunctional warehousing robot shipment path problem with order priority constraint, and specifically comprises the following steps:
the total weight of the storage robot comprises the self weight of the multifunctional storage robotAnd load->Since the load and the electricity consumption rate of the storage robot are in a linear relationship, the function between the load and the electricity consumption rate is set as:
the storage robot is in no-load stateAnd fill->The power expression at that time is:
solving to obtain:
and carrying the solved formula into a power expression of the storage robot in no-load and full-load to obtain the following formula:
load m of storage robot when storage robot k reaches j point jk To the load when reaching the previous item point i, the weight q of the item picked at point i is added i It is expressed as:
due to the loading of the storage machineThe relation between the load and the electricity consumption rate of the storage robot is expressed as:
wherein x is ijk Representing a decision variable, wherein the storage robot k is 1 when driving from a goods point i to a goods point j, and is 0 otherwise;
according to the formula of power consumptionAnd speed formula->The power consumption of the warehouse robot k from i to j is obtained as follows:
wherein,represents the power consumption of the warehousing robot k from i to j, d ij The distance from the goods point i to the goods point j of the storage robot k is represented, t represents the running time of the storage robot, and v represents the running speed of the storage robot;
the relation between the load of the warehousing robot and the electricity consumption rate is brought into the formula to obtain the electricity consumption of the warehousing robot k from i to j as follows:
the objective function expression of the "multi-functional warehouse robot shipment path problem with order priority constraint" is obtained as follows:
wherein z represents a unit electricity price.
Further, an optimizing system of a warehouse logistics robot picking path comprises:
the acquisition module is used for acquiring order information of the required goods;
the priority classification module is used for classifying the goods according to the order information of the goods and the order shipment sequence, and establishing the priority corresponding to the goods points;
the pickability matrix building module is used for selecting different types of storage robots according to goods in different shapes and building pickability matrixes corresponding to the storage robots and the goods;
the three-section chromosome coding module is used for respectively coding the priority corresponding to the storage robot and the cargo point and the storage robot pickability matrix by adopting a three-section chromosome coding method to obtain three-section chromosome codes;
the clustering module is used for clustering the priority of the cargo shipment sequence and the distance between each cargo point and each priority center by adopting a mixed clustering algorithm according to the three-section chromosome codes;
the optimal path calculation module is used for searching paths of the clustered goods points by using a minimum cost method, and simultaneously changing the neighborhood structure of the three-section chromosome coding scheme by adopting a variable neighborhood search algorithm in the searching process so as to obtain an optimal path; the method adopts a variable neighborhood search algorithm to change the neighborhood structure of the three-section chromosome coding scheme, and comprises the following specific processes: and under the double constraint that the priority of the goods points is the same and the model of the multifunctional warehousing robot is satisfied, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out.
The invention provides a method and a system for optimizing a picking path of a warehouse logistics robot, which comprises the following steps of
The beneficial effects are that:
the invention provides a three-section chromosome coding scheme, which is used for respectively coding the delivery priorities corresponding to a multifunctional storage robot and goods points and the corresponding relation between the multifunctional storage robot and the goods to obtain a three-section chromosome coding scheme of a 'multifunctional storage robot delivery path problem with order priority constraint', and clustering the priorities of goods delivery sequences and the distances between each goods point and each priority center based on a mixed clustering algorithm according to the three-section chromosome coding scheme; searching paths of the current cargo points after clustering is completed by using a minimum cost method, so that the iteration speed of an algorithm is increased, and the risk of trapping in local optimum is reduced; meanwhile, in the searching process, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out under the double constraint that the priority of goods points is the same and the model of the multifunctional warehousing robot is met by adopting a variable neighborhood searching algorithm, so that an optimal path is obtained, and meanwhile, the constraint of a target problem is protected from being damaged.
Drawings
FIG. 1 is a schematic diagram of three-segment chromosome coding in an embodiment of the present invention;
FIG. 2 is a flowchart of a variable neighborhood search algorithm based on a hybrid clustering operation and a minimum cost method in an embodiment of the present invention;
FIG. 3 is a schematic diagram of clustering results in an embodiment of the present invention;
FIG. 4 is a schematic illustration of single point insertion with priority constraints in an embodiment of the present invention;
FIG. 5 is a schematic diagram of a two-point exchange with priority constraints in an embodiment of the present invention;
FIG. 6 is a schematic diagram of a two-stage exchange with priority constraints in an embodiment of the invention;
FIG. 7 is a schematic diagram of a 3-OPT operation with priority constraints in an embodiment of the invention.
Detailed Description
The following description of the embodiments of the present invention will be made clearly and completely with reference to the accompanying drawings, in which it is apparent that the embodiments described are only some embodiments of the present invention, but not all embodiments.
The invention discloses a planning method for solving a problem of a delivery path of a multifunctional warehousing robot with order priority constraints. First, a mixed integer model of the multi-functional warehouse robot shipment path problem with order priority constraints is established. Then, three sections of chromosome coding schemes are established to respectively code cargo points, priorities and pickability corresponding to the multifunctional warehousing robot and cargoes. Finally, a variable neighborhood search algorithm based on a mixed clustering operation and a minimum cost method is designed, and firstly, the mixed clustering algorithm is designed to perform clustering operation on cargo points. Then, a minimum cost method is designed to search the path of the multifunctional warehousing robot. Finally, redesigning a variable neighborhood search algorithm (Variable Neighborhood Search, VNS) under a three-segment chromosome coding scheme; the method specifically comprises the following steps:
step S1, a mixed integer rule of the problem of the shipment path of the multifunctional warehousing robot with order priority constraint is established.
TABLE 1 symbols and definitions
Step1: sorting the priority of the goods according to the order shipment sequence, and establishing the priority P corresponding to the goods points i ＝A，A＝{0，1，2}，P i =0 indicates that the cargo point priority is low; p (P) i =1 represents a cargo point priority medium; p (P) i =2 indicates that the cargo point has a high priority.
Step2: since there are differences in the shape of the goods, different types of warehousing robots are required to pick different shapes of goods. The invention designs an association matrix Mat for representing the correspondence relationship of the cargo corresponding to the pickability of the multifunctional warehousing robot. The row of Mat represents a collection of multi-function warehousing robot constraint vectors that can provide picking for good i, denoted S i ， Mat represents a cargo point constraint vector which can be selected by the multifunctional storage robot k, and a cargo point set which can be served by the multifunctional storage robot is marked as H k ，The concrete expression of the matrix Mat is shown in the formula (1):
step3: because the multifunctional warehousing robot uses the electric drive motor to move and select goods, the load and the power consumption rate of the multifunctional warehousing robot are closely related. The invention discloses a mixed integer model between the load and the electricity consumption rate of a multifunctional storage robot, which comprises the following specific steps:
the total weight of the multifunctional storage robot is the self weight of the multifunctional storage robotAnd load->Two parts. Since the load and the electricity consumption rate of the multifunctional warehousing robot are in a linear relationship, the function between the load and the electricity consumption rate is set as shown in a formula (2):
the power of the multifunctional warehousing robot in no-load and full-load is shown in a formula (3):
solving equation (3) may yield:
bringing equation (4) into (2) yields:
the load of the multifunctional warehousing robot k when reaching the point j is the load when reaching the previous goods point i plus the weight q of the goods selected at the point i i As shown in formula (6):
because of the multi-functional storage machine loadTherefore, the relation between the load and the power consumption rate of the warehousing robot can be obtained by bringing the formula (6) into the formula (5) as shown in the formula (7):
according to the formula of power consumptionAnd speed formula->The power consumption of the multifunctional warehousing robot k from i to j is shown in a formula (8):
the power consumption of the warehousing robot k from i to j, which is obtained by bringing the formula (7) into the formula (8), is shown as the formula (9):
step4: establishing an objective function of the multifunctional warehousing robot shipment path problem with order priority constraint, taking the minimum electricity consumption cost F as an optimization target, wherein the objective function is shown in a formula (10):
constraint 1: all the multifunctional warehousing robots must start from the sorting table and return to the sorting table after picking the goods:
constraint 2: all goods can be picked once only by one multifunctional warehousing robot
Constraint 3: the multifunctional warehousing robot must leave the goods point after picking the goods
Constraint 4: each multifunctional warehousing robot k must not exceed the rated load of the multifunctional warehousing robot when picking cargoes:
constraint 5: the priority of the multifunctional warehousing robot for picking cargoes is defined as P i When the picking priority of the goods point i is not less than the picking priority of the goods point j, the multifunctional warehousing robot needs to finish the picking of the goods with high priority first and then realize the picking with low priority.
Constraint 6: the cargo is constrained to be picked only by the designated multi-function warehousing robot according to the correlation matrix of the cargo and the multi-function warehousing robot pickability.
Constraint 7: the multi-functional warehousing robot cannot generate a sub-loop in the path during picking
U i -U j +Mx ijk ≤M-1，i，j∈V，U i 、U j ∈Z + (17)
M ε Z in constraint 7 + ，Z + And V is a cargo point set and is a positive integer set. Introducing decision variables U for each cargo point i (i.e.V) establishing Mi Le Talczem (Miller Tucker Zemlin, MTZ) constraint, setting decision variable U in MTZ constraint i ，U i And is more than or equal to 0. In addition, the value of M should be U i -U j The upper bound of +1 has been studied to show that M works better with the upper bound, so taking m=n, one can tighten constraint 7 to:
step S2: due to the constraints of priority among goods and pickability of the storage robot to the corresponding goods, the traditional single-gene chromosome coding method is not suitable for representing the problem. Therefore, the invention provides three-section chromosome coding to express the problem of the delivery path of the warehousing robot with order priority constraint, wherein the first section of the three-section chromosome coding is used for coding the multifunctional warehousing robot, the second section is used for coding the delivery priority corresponding to the multifunctional warehousing robot, and the third section is used for coding according to the pickability matrix corresponding to the multifunctional warehousing robot and the goods. The method comprises the following specific steps:
step1: firstly, generating a cargo point sequence, and then distributing the cargo point sequence to the appointed cargo point according to the known order priority, so as to obtain the chromosome coding scheme of the cargo point corresponding to the order priority. And then, carrying out coding operation on the corresponding relation between the multifunctional storage robot and the goods according to the Mat matrix, so as to obtain the three-section chromosome coding scheme of the multifunctional storage robot, the delivery priority corresponding to the multifunctional storage robot and the corresponding relation between the multifunctional storage robot and the goods. The scheme can obtain a feasible solution of the problem of the delivery path of the warehousing robot with order priority.
With 10 cargoesObject point, 3 multi-functional storage robots are examples. Firstly, assigning priorities corresponding to goods to each goods point according to order demands. P (P) i =2, i= {3,5,7} means that the priority of the cargo points 3,5,7 is 2, their priority is highest, and priority picking is performed; p (P) i =1, i= {2,4,6} indicates that the priority of the cargo points 2,4,6 is medium, suboptimal picking; p (P) i =0, i= {1,8,9, 10} means that the priority of the item points 1,8,9, 10 is low, and finally sorted. And then coding according to the cargo points and the pickability matrix Mat of the multifunctional warehousing robot. Firstly, the multifunctional storage robot 1 is allocated to the goods points 1,8,9 and 10, and the goods points 1,8,9 and 10 can be selected only by the multifunctional storage robot 1; then, the multifunctional storage robot 2 is allocated to the goods points 2,4 and 6, and the goods points 2,4 and 6 can be selected only by the multifunctional storage robot 2; finally, the allocation of the multi-function warehousing robots 3 to the goods points 3,5,7 means that the goods points 3,5,7 can only be picked up by the multi-function warehousing robots 3. A three-segment chromosome coding scheme for a multi-functional warehouse robot shipment path problem with order priority constraints is shown in fig. 1.
The sorting sequence of the multifunctional warehousing robot 1 shown in fig. 1 is 0-1-8-9-10-0; the sorting sequence of the multifunctional storage robot 2 is 0-2-4-6-0; the sorting sequence of the multifunctional warehousing robot 3 is 0-3-5-7-0.
Step S3: in order to solve the problem of the delivery path of the multifunctional warehousing robot with order priority constraint, the invention provides a variable neighborhood search algorithm based on mixed clustering operation and a minimum cost method, and the algorithm flow chart of the variable neighborhood search algorithm is shown in figure 2.
Step1: the K-means and DBSCAN algorithm is mostly adopted in solving the problem of cargo point clustering operation nowadays. The idea of K-means is to randomly input points in a feature space as initial cluster centers. Then, the distance from each cargo point to a centers is calculated, and the nearest cluster center point is selected as the mark category from the cargo points. And then, after the marked cluster centers are aligned, recalculating new center points of each cluster, and stopping the algorithm if the calculated new center points are identical to the original center points. Since the K value of the K-means algorithm is set manually, it is difficult to determine the value of the cluster center K and the number of clusters of cargo information, and if the K values are aggregated according to a fixed K value, the obtained centroid position may be far from the actual position. The density-based noise application spatial clustering (Density Based Spatial Clustering of Application with Noise, DBSCAN) algorithm is an unsupervised clustering algorithm. The basic idea of the DBSCAN algorithm is that the sample points in the radius circle domain with r as each sample point are calculated and obtained, and the corresponding core sample points are obtained; and traversing each sample in turn, and classifying the clusters of directly reachable sample points according to whether the samples are core samples or not. In addition, in order to solve the problem of long iteration time of the DBSCAN algorithm, the invention discloses a method for calculating the sampling expected value to replace the global expected value so as to accelerate the convergence rate of the algorithm.
The same priority is clustered together to obtain clusters of each priority first using DBSCAN. Table 2 is an algorithm symbol and definition table, and comprises the following specific steps:
TABLE 2 Algorithm notation and definition table
Step1: first for priority P i Cargo coordinate points=2 calculate a distance distribution matrix of cargo point coordinate set D, namely:
γ n×n ＝{D(i，j)|1≤i≤n，1≤j≤n}(19)
step2: performing row ascending operation on the matrix, and randomly selecting x elements to form gamma in the ith row i
Step3: for gamma i The average number of the elements in the matrix is recorded asCalculating the value of i to obtain +.>
Step4: generatingRandomly selecting x objects in the cargo point coordinate set D, and sequentially calculating each +.>θ in list ps Neighborhood object number and sampling expectation of candidate values as MinP ts The parameters of (1) are as follows:
in the above formula: n (N) i θ representing the ith object ps Number of neighborhood objects.
Step5: sequentially select and useAnd->Element θ ps And MinP ts And (3) inputting parameters into a DBSCAN algorithm to perform clustering operation on the cargo coordinate set, respectively obtaining corresponding clustering clusters under different input parameters, and when the clustering clusters are continuous for 3 times, outputting the clustering clusters to be stable, and recording the optimal clustering cluster number as M. Repeating until the cluster is not M, selecting corresponding theta when the last cluster is selected ps And MinP ts As the best parameters.
Step6: will give priority to P i ＝1，P i The above operations are performed sequentially=0.
Taking the coordinates of the goods points of each cluster as new input, then calculating the position of the mass center by using a K-means algorithm, and clustering the coordinate distances, wherein the specific steps are as follows:
step7: and calculating the coordinate center C of each priority level according to the data processed by the DBSCAN algorithm.
Step8: and calculating the distance between each cargo point and the center of each priority.
Step9: on the condition that the cargo point priority constraint is satisfied, the cargo points with the same cargo point priority are allocated to the nearest coordinate center C K 。
Step10: the center object position for each priority is recalculated.
Step11: repeating Step8 and Step9 until the object classification in the clustering scheme is stopped by the algorithm without change, and outputting the clustered setThe results obtained by the above clustering operation are shown in fig. 3. The red graphic priority is high; blue graphics are in priority; green graphics are low priority.
As customer orders increase, their algorithm iteration time continues to increase. In order to accelerate the algorithm solving speed, the invention adopts a minimum cost method to improve the algorithm searching efficiency, and comprises the following specific steps:
step12: initializing the preprocessed data set, reading coordinate points of current data, and recording a current path as follows: current.
Step13: judging whether all the goods points are picked, if so, ending the algorithm, outputting the processed path and calculating the cost of the current path. If the object point is not picked (denoted as C k ) And continuing.
Step14: randomly selecting a certain non-picked cargo point C from the set of non-picked cargo points 1 C is carried out by 1 Current is added and marked C 1 Has been picked.
Step15: with the goods point C 1 Searching for a non-picked item set C as a base point k Point p of medium cargo 1 And cargo point p 2 And calculate itThe running cost is recorded as cost 1 、cost 2 。
Step16: comparing costs under conditions of meeting the load, priority and pickability of the multifunctional warehousing robot 1 、cost 2 If cost is the cost 1 ＜cost 2 Then p is 1 The Current path Current is added. Otherwise, p is 2 The Current path Current is added. The current operation is performed and then jumps to Step13.
The basic idea of the variable neighborhood search algorithm is to expand the search range by systematically changing the neighborhood structure transformation during the search process to obtain a locally optimal solution. In order to improve the algorithm performance, the invention redesigns the neighborhood structure transformation under the three-section chromosome coding scheme, and proposes single-point insertion with priority constraint, two-point exchange with priority constraint, two-section exchange with priority constraint and 3-OPT with priority constraint. The specific algorithm comprises the following steps:
step17: the single-point insertion operation can be performed only when the multi-functional storage robot model is met while the delivery priority corresponding to the goods points is the same. The single point insertion operation is shown in fig. 4, where the insertion of the cargo point 5 into the cargo point 7 results in a new path.
Step18: and the two-point exchange operation can be performed under the condition of simultaneously meeting the double constraints of the same delivery priority corresponding to the goods points and the model of the multifunctional storage robot. Two-point exchange operation as shown in fig. 5, the cargo points 3 and 9 are exchanged to obtain a new path.
Step19: and the two-section exchange operation can be performed under the condition of simultaneously meeting the double constraints of the same delivery priority corresponding to the goods points and the model of the multifunctional storage robot. Two-stage exchange operation cargo points 3,5 and cargo points 1,8 are exchanged for two stages as described in fig. 6. Goods point 1 and goods point 3 are then exchanged between goods points 6 and 9, and goods point 8 and goods point 5 are then exchanged for a new path resulting from the positions of goods points 1 and 3.
The 3-OPT operation can be performed under the condition of simultaneously meeting the double constraints of the same priority of the goods points and the model of the multifunctional warehousing robot. The 3-OPT operation is as follows:
step20: the initial scheme obtained by the above operation is calculated as S, and the total distance from Start is calculated as L (S).
Step21: and taking out the goods points 8 and 10 with low priority and the goods points 2,4 and 6 with low priority, exchanging the goods points 8 and 10 with positions, then exchanging the new paths obtained by the positions 2,4 and 6 with the positions as shown in fig. 7, and finally calculating the exchanged distances.
Step22: if the distance after the 3-OPT operation with the priority constraint is smaller than L (S), adding the corresponding movement to S, that is, s+.3opt (S), and continuing the iteration of Step21, stopping the algorithm when the arc that can be operated is not satisfied, and stopping the algorithm until the selected cargo point has no new connection mode.
Step23: and judging whether the iteration times set by the algorithm are reached or whether stagnation occurs. If yes, the algorithm is ended, and a current optimal path planning scheme is output; otherwise, go to Step12 to continue the next iteration.
Step24: and outputting the optimal path planning scheme to a multifunctional warehouse robot dispatching platform.
Based on the same inventive concept, the invention provides an optimization system of a warehouse logistics robot picking path, which comprises:
and the acquisition module is used for acquiring order information of the required goods.
And the priority classification module is used for classifying the priorities of the goods according to the order information of the goods and the order shipment sequence, and establishing the priorities corresponding to the goods points.
The pickability matrix establishment module is used for selecting different types of storage robots according to goods in different shapes and establishing pickability matrices corresponding to the storage robots and the goods.
And the three-section chromosome coding module is used for respectively coding the priority corresponding to the storage robot and the cargo point and the storage robot pickability matrix by adopting a three-section chromosome coding method to obtain three-section chromosome codes.
And the clustering module is used for clustering the priority of the cargo shipment sequence and the distance between each cargo point and each priority center by adopting a mixed clustering algorithm according to the three-segment chromosome codes.
The optimal path calculation module is used for searching paths of the clustered goods points by using a minimum cost method, and simultaneously changing the neighborhood structure of the three-section chromosome coding scheme by adopting a variable neighborhood search algorithm in the searching process so as to obtain an optimal path; the method adopts a variable neighborhood search algorithm to change the neighborhood structure of the three-section chromosome coding scheme, and comprises the following specific processes: and under the double constraint that the priority of the goods points is the same and the model of the multifunctional warehousing robot is satisfied, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out.
The foregoing is only a preferred embodiment of the present invention, but the scope of the present invention is not limited thereto, and any person skilled in the art, who is within the scope of the present invention, should make equivalent substitutions or modifications according to the technical scheme of the present invention and the inventive concept thereof, and should be covered by the scope of the present invention.
Claims (10)
1. The optimizing method of the warehouse logistics robot picking path is characterized by comprising the following steps:
acquiring order information of the required goods;
according to order information of the goods, classifying the goods according to the order shipment sequence, and establishing a priority corresponding to the goods points;
selecting different types of storage robots according to goods in different shapes, and establishing a pickability matrix corresponding to the storage robots and the goods;
adopting a three-section chromosome coding method to respectively code the priority corresponding to the storage robot and the cargo point and the storage robot pickability matrix to obtain three-section chromosome codes;
according to the three-section chromosome coding, adopting a mixed clustering algorithm to cluster the priority of the cargo delivery sequence and the distance between each cargo point and each priority center;
searching paths of the clustered goods points by using a minimum cost method, and simultaneously changing a neighborhood structure of a three-section chromosome coding scheme by adopting a variable neighborhood searching algorithm in the searching process so as to obtain an optimal path; the method adopts a variable neighborhood search algorithm to change the neighborhood structure of the three-section chromosome coding scheme, and comprises the following specific processes: and under the double constraint that the priority of the goods points is the same and the model of the multifunctional warehousing robot is satisfied, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out.
2. The method for optimizing a picking path of a warehouse logistics robot according to claim 1, wherein the sorting of the priorities of the goods according to the order shipment sequence, and establishing the priorities corresponding to the goods points, wherein the priorities P corresponding to the goods points are established i ＝A，Indicating that the cargo point has low priority; p (P) i =1 represents a cargo point priority medium; p (P) i =2 indicates that the cargo point has a high priority.
3. The method for optimizing a picking path of a warehouse logistics robot according to claim 1, wherein different types of warehouse robots are selected according to different shapes of cargoes, and a pickability matrix corresponding to the warehouse robots and the cargoes is established; wherein, the pickability of the goods corresponding to the warehousing robots is represented by an association matrix Mat, rows of the Mat represent the constraint vectors of the warehousing robots for providing picking for the goods i, and the collection of the constraint vectors is recorded as S i ，Mat represents a cargo point constraint vector which can be selected by the storage robot k, and a cargo point set served by the storage robot is marked as H k ,/> The matrix Mat is expressed as:
where K represents the collection of storage robots, k= {1,2,., K, m }, K represents the storage robot number, N represents the collection of goods, n= {1,2,3,4, …, N },and (3) representing a decision variable, wherein the picking operation is provided by the storage robot k when the goods point is 1, otherwise, the picking operation is provided by the storage robot k, wherein m represents the number of the storage robots, and n represents the number of the goods.
4. The method for optimizing a picking path of a warehouse logistics robot according to claim 3, wherein three segments of chromosome codes are adopted to respectively code a cargo point, a delivery priority corresponding to the cargo point and a pickability matrix, and a three-segment chromosome coding scheme is obtained, and the method comprises the following steps:
generating a sequence of cargo points;
assigning the order priority to the appointed goods points according to the known order priority, and obtaining a chromosome coding scheme of the goods points corresponding to the order priority;
and carrying out coding operation on the corresponding relation between the storage robot and the goods according to the Mat matrix, and further obtaining a three-section chromosome coding scheme of the goods points, the priorities and the pickability matrix corresponding to the storage robot and the goods.
5. The method for optimizing the picking path of the warehouse logistics robot according to claim 2, wherein the mixed clustering algorithm is adopted to cluster the priority of the cargo delivery sequence and the distance between each cargo point and each priority center according to the three-section chromosome coding scheme, and comprises the steps of clustering the same priority together by using DBSCAN to obtain clusters of each priority and obtaining the position of the center by using a K-means algorithm to cluster the coordinate distance.
6. The method for optimizing a picking path of a warehouse logistics robot according to claim 5, wherein the clustering the same priorities together using DBSCAN to obtain clusters of each priority comprises the steps of:
first for priority P i Cargo coordinate points=2 calculate a distance distribution matrix of cargo point coordinate set D, namely:
γ n×n ＝{D(i,j)|1≤i≤n,1≤j≤n}
the distance distribution matrix is subjected to ascending operation, and x elements are randomly selected to form gamma in the ith row i
For gamma i The average number of the elements in the matrix is recorded asCalculating the value of i to obtain +.>
GeneratingRandomly selecting x objects in the cargo point coordinate set D, and sequentially calculating each +.>θ in list ps Neighborhood object number and sampling expectation of candidate values as MinP ts The parameters of (1) are as follows:
wherein N is i θ representing the ith object ps Neighborhood object number, minip ts Indicating the number of points at least contained in the adjacent area;
sequentially select and useAnd->Element θ ps And MinP ts Parameters are input into a DBSCAN algorithm to perform clustering operation on the goods coordinate set, corresponding clustering clusters under different input parameters are respectively obtained, when the clustering clusters are continuously identical for 3 times, the output tends to be stable, the optimal clustering cluster number is recorded as M, the operation is repeatedly performed until the clustering clusters are not M, and then corresponding theta is selected when the last clustering cluster is selected ps And Minp ts As optimal parameters;
will give priority to P i ＝1,P i The above operations are performed sequentially=0.
7. The method for optimizing a picking path of a warehouse logistics robot according to claim 5, wherein the calculating of the position of the center of mass by using the K-means algorithm and the clustering of the coordinate distance are performed, comprises the following steps:
calculating the coordinate center C of each priority level of the data processed by the DBSCAN algorithm;
calculating the distance between each goods point and the center of each priority;
on the condition that the cargo point priority constraint is satisfied, the cargo points with the same cargo point priority are allocated to the nearest coordinate center C K ；
Recalculating the center object position of each priority;
repeatedly calculating the distance between each cargo point and each priority center until the algorithm stops when the object classification in the cluster does not change, and outputting the set after the clustering processing
8. The method for optimizing a picking path of a warehouse logistics robot according to claim 1, wherein the searching for a path of a current cargo point after the clustering is completed by using a least cost method comprises the following steps:
initializing the preprocessed data set, reading coordinate points of current data, and recording a current path as follows: current;
judging whether all the goods points are picked, if all the goods points are picked, finishing the algorithm, outputting the processed path and calculating the cost of the current path, and if the goods points are not picked, marking as C k The algorithm continues;
randomly selecting a certain non-picked cargo point C from the set of non-picked cargo points 1 C is carried out by 1 Current is added and marked C 1 Has been picked;
with the goods point C 1 Searching for a non-picked item set C as a base point k Point p of medium cargo 1 And cargo point p 2 And calculate its running cost as cost 1 、cost 2 ；
Comparing costs in case of meeting the storage robot load, priority and storage robot pickability 1 、cost 2 If cost is the cost 1 <cost 2 Then p is 1 Adding Current path Current, otherwise, adding p 2 The Current path Current is added.
9. The method for optimizing a warehouse logistics robot picking path of claim 1, further comprising establishing an objective function of a multi-functional warehouse robot picking path problem with order priority constraints, comprising the steps of:
the total weight of the storage robot comprises the self weight of the multifunctional storage robotAnd load->Since the load and the electricity consumption rate of the storage robot are in a linear relationship, the function between the load and the electricity consumption rate is set as:
the storage robot is in no-load stateAnd fill->The power expression at that time is:
solving to obtain:
and carrying the solved formula into a power expression of the storage robot in no-load and full-load to obtain the following formula:
load m of storage robot when storage robot k reaches j point jk To the load when reaching the previous item point i, the weight q of the item picked at point i is added i It is expressed as:
due to the loading of the storage machineThe relation between the load and the electricity consumption rate of the storage robot is expressed as:
wherein x is ijk Representing a decision variable, wherein the storage robot k is 1 when driving from a goods point i to a goods point j, and is 0 otherwise;
according to the formula of power consumptionAnd speed formula->The power consumption of the warehouse robot k from i to j is obtained as follows:
wherein,represents the power consumption of the warehousing robot k from i to j, d ij The distance from the goods point i to the goods point j of the storage robot k is represented, t represents the running time of the storage robot, and v represents the running speed of the storage robot;
the relation between the load of the warehousing robot and the electricity consumption rate is brought into the formula to obtain the electricity consumption of the warehousing robot k from i to j as follows:
the objective function expression of the "multi-functional warehouse robot shipment path problem with order priority constraint" is obtained as follows:
wherein z represents a unit electricity price.
10. An optimization system for a warehouse logistics robot picking path, comprising:
the acquisition module is used for acquiring order information of the required goods;
the priority classification module is used for classifying the goods according to the order information of the goods and the order shipment sequence, and establishing the priority corresponding to the goods points;
the pickability matrix building module is used for selecting different types of storage robots according to goods in different shapes and building pickability matrixes corresponding to the storage robots and the goods;
the three-section chromosome coding module is used for respectively coding the priority corresponding to the storage robot and the cargo point and the storage robot pickability matrix by adopting a three-section chromosome coding method to obtain three-section chromosome codes;
the clustering module is used for clustering the priority of the cargo shipment sequence and the distance between each cargo point and each priority center by adopting a mixed clustering algorithm according to the three-section chromosome codes;
the optimal path calculation module is used for searching paths of the clustered goods points by using a minimum cost method, and simultaneously changing the neighborhood structure of the three-section chromosome coding scheme by adopting a variable neighborhood search algorithm in the searching process so as to obtain an optimal path; the method adopts a variable neighborhood search algorithm to change the neighborhood structure of the three-section chromosome coding scheme, and comprises the following specific processes: and under the double constraint that the priority of the goods points is the same and the model of the multifunctional warehousing robot is satisfied, single-point insertion operation, two-point exchange, two-section exchange and 3-OPT operation are sequentially and respectively carried out.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311795729.8A CN117764483A (en) | 2023-12-25 | 2023-12-25 | Optimization method and system for picking path of warehouse logistics robot |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN202311795729.8A CN117764483A (en) | 2023-12-25 | 2023-12-25 | Optimization method and system for picking path of warehouse logistics robot |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN117764483A true CN117764483A (en) | 2024-03-26 |
Family
ID=90323689
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN202311795729.8A Pending CN117764483A (en) | 2023-12-25 | 2023-12-25 | Optimization method and system for picking path of warehouse logistics robot |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN117764483A (en) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118246687A (en) * | 2024-04-12 | 2024-06-25 | 广州霖锋智能科技有限公司 | Robot handling scheduling method and system for warehouse logistics |
-
2023
- 2023-12-25 CN CN202311795729.8A patent/CN117764483A/en active Pending
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN118246687A (en) * | 2024-04-12 | 2024-06-25 | 广州霖锋智能科技有限公司 | Robot handling scheduling method and system for warehouse logistics |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Azadeh et al. | Robotized and automated warehouse systems: Review and recent developments | |
| EP3816886B1 (en) | Management method, apparatus, system applied to goods-to-person system, and server and computer storage medium | |
| WO2020238657A1 (en) | Goods sorting method and goods sorting system | |
| Zou et al. | Operating policies in robotic compact storage and retrieval systems | |
| CN108942946B (en) | Intelligent logistics environment robot loading method and device | |
| CN112132505B (en) | Robot picking method and system, robot, server and readable storage medium | |
| CN117764483A (en) | Optimization method and system for picking path of warehouse logistics robot | |
| Lee et al. | Simulation-based multiple automated guided vehicles considering charging and collision-free requirements in automatic warehouse | |
| CN113935452A (en) | Distribution center goods picking path planning method based on ant colony algorithm and genetic algorithm fusion | |
| CN116542365A (en) | Order allocation and AGV scheduling combined optimization method in mobile robot fulfillment system | |
| CN116797121A (en) | AGVs-based intelligent warehouse batch sorting optimization method | |
| CN113706081B (en) | Unmanned aerial vehicle picking and delivering system and method based on automatic express delivery device on city roof | |
| CN116203959A (en) | Robot path planning method and system based on HAC algorithm | |
| CN113867358A (en) | Intelligent path planning method for multi-unmanned vehicle collaborative traversal task | |
| CN115587679A (en) | AGV optimization scheduling method for intelligent warehouse | |
| CN114358233A (en) | Multi-AGV path planning problem optimization method and system based on double-hybrid particle swarm | |
| CN117371918A (en) | Goods space distribution two-stage optimization method and system based on improved order association rule | |
| CN114418707A (en) | Four-way shuttle vehicle path navigation method and system | |
| US20240336434A1 (en) | Robotic Fulfillment System Carton Release Logic | |
| CN117875189B (en) | Three-dimensional warehouse space layout method based on GA optimization GRO | |
| CN113095751A (en) | Multi-supplier carrying supply optimization method, device and system | |
| CN116796910B (en) | Order batch optimization method based on goods allocation strategy | |
| CN112508481A (en) | Intelligent storage multi-AGV scheduling method | |
| CN116523221A (en) | Optimal scheduling method and system for intelligent warehouse picking task | |
| Soyaslan et al. | A new truck based order picking model for automated storage and retrieval system (AS/RS) |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination |