CN113869822A - Task scheduling method of trailer-mounted multi-AGV system based on multi-layer one-way graph - Google Patents

Abstract

The invention discloses a task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph, and belongs to the technical field of production scheduling. The invention combines the layout and geometric constraints of the physical space, considers the characteristics of the trailer-mounted multi-AGV system for material distribution, and constructs a multi-layer one-way diagram to ensure the conflict-free operation of the trailer-mounted multi-AGV system. The uncertainty of time is modeled, and a task scheduling model is established to minimize the advance lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and then obtain the task execution route assigned to each trailer-mounted AGV. The invention solves the task scheduling and decision-making problem of the trailer-mounted multi-AGV system, reduces the investment cost of enterprises in the process of intelligent transformation, ensures the coordinated and conflict-free operation of the trailer-mounted multi-AGV system, ensures the stability and timeliness of material distribution, and can effectively To reduce production costs, improve logistics efficiency and production efficiency.

Description

Task scheduling method of trailer-mounted multi-AGV system based on multi-layer one-way graph

technical field

The invention relates to a task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph, and belongs to the technical field of production scheduling.

Background technique

With the increasingly fierce market competition and the increasing personalized needs of customers, more and more manufacturing enterprises are gradually adopting the customized production mode. In order to improve the flexibility of the system and meet the needs of personalized customized production, the material distribution system of the enterprise gradually adopts the multi-AGV (Automated Guided Vehicle) system scheme. Using highly intelligent and flexible AGVs as transportation equipment, combined with corresponding intelligent scheduling models and optimization algorithms, the multi-AGV material distribution system built has the ability to automatically travel, actively avoid obstacles, and timely and accurately distribute materials, and can realize the entire process of material distribution. Highly automated and intelligent.

Although the multi-AGV system has developed rapidly and is technically sufficient to support the intelligent upgrading and transformation of the manufacturing material distribution system, traditional enterprises still use traditional manual transportation methods after considering the high input cost of purchasing multiple industrial AGVs, relying on traditional trailer-mounted vehicles for material transportation. In order to promote the upgrading and transformation of manufacturing enterprises, the enterprise combines intelligent AGVs with traditional trailer-mounted vehicles, and uses laser navigation AGVs as the head to tow a certain number of trailers to form multi-load trailer-mounted AGVs.

In the trailer-mounted multi-AGV system, it is necessary to pay attention to the constraints of the workshop environment on the physical properties of the trailer-mounted AGV. The longer the length of the trailer-mounted AGV, the larger the required turning radius, which is limited by the channel width of the production workshop. The maximum length of the trailer-mounted AGV allowed to pass through the turning port is also different, and the trailer-mounted AGV realizes loading and unloading by connecting or unloading the end trailer during the material distribution process, and its length is constantly changing. Therefore, a trailer-mounted AGV with a dynamically changing length, combined with environmental constraints, performs conflict-free path planning, which has become one of the problems that the trailer-mounted multi-AGV system needs to solve.

On the other hand, considering the waiting or lag time in the process of cooperating with each other and avoiding conflicts, the delivery time between two task points is uncertain, which affects the task scheduling results. Under the condition of multi-AGV collaboration and no conflict, considering the time uncertainty, delivering each known task to the corresponding demand point within a non-strictly constrained time window has also become an urgent problem to be solved in the task scheduling of the trailer-mounted multi-AGV system.

SUMMARY OF THE INVENTION

The purpose of the present invention is to provide a task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph. The invention combines the layout and geometric constraints of the physical space, considers the characteristics of the trailer-mounted multi-AGV system for material distribution, and constructs a multi-layer one-way diagram to ensure the conflict-free operation of the trailer-mounted multi-AGV system. The uncertainty of time is modeled, and a task scheduling model is established to minimize the advance lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and then obtain the task execution route assigned to each trailer-mounted AGV. The invention solves the task scheduling and decision-making problem of the trailer-mounted multi-AGV system, reduces the investment cost of enterprises in the process of intelligent transformation, ensures the coordinated and conflict-free operation of the trailer-mounted multi-AGV system, ensures the stability and timeliness of material distribution, and can effectively To reduce production costs, improve logistics efficiency and production efficiency.

The present invention is achieved through the following specific technical solutions:

Task scheduling method of trailer-mounted multi-AGV system based on multi-layer one-way map: First, according to the actual layout of the physical space, construct a topology one-way map, and determine the maximum length table of trailer-mounted AGVs that are allowed to turn through each node. Build a multi-layer one-way graph on the top to ensure the normal operation of the trailer-mounted AGV with variable length, and solve the conflict and deadlock of the trailer-mounted AGV through the waiting strategy, and build the distance matrix between nodes; On the basis of the direction graph and the distance matrix between nodes, the uncertainty of the delivery time is modeled by shifting the gamma distribution, and the uncertainty caused by the waiting strategy and other factors is solved, and a reasonable estimate of the delivery time of the trailer-mounted AGV is obtained. , determine the early lag penalty value of material distribution; finally, establish a task scheduling model to minimize the early lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and obtain the task execution route assigned to each trailer-mounted AGV.

A task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph of the present invention includes the following steps:

Step 1. According to the actual layout of the physical space, build a topological one-way map, determine the maximum length table of the trailer-mounted AGV that each node is allowed to turn through, and build a multi-layer one-way map on this basis to ensure variable-length trailer-mounted AGVs. The AGV can run normally in the system, and solve the conflict and deadlock of the trailer-mounted AGV through the waiting strategy, and build the distance matrix between the nodes;

Step 1.1: For the layout of the physical space, the important location points are abstracted into nodes, represented by v, where the set of all channel intersection nodes is V ^c , the set of all task demand nodes is V ^k , and the set of nodes where warehouse entrances and exits are located is V ^p , the set of all nodes V=V ^p ∪V ^k ∪V ^c , abstract the road into an edge, represented by z, the set is Z, build a topological map, and ensure that there is an accessible path between any two road nodes, each The edges can allow vehicles to enter and exit normally;

Step 1.2: According to the topology map constructed in Step 1.1, specify that the direction of each edge is one-way, that is, the edge zi _, j between any node v _i and the adjacent node v _j is a one-way edge, and the construction environment is one-way. graph G ₀ ;

Among them, each side allows multiple trailer-mounted AGVs to exist at the same time, but the interval between each trailer-mounted AGV must be greater than the specified safe driving distance. In the one-way diagram, the conflict problem of all trailer-mounted AGVs is solved through the waiting strategy ;

Step 1.3: According to the topology map constructed in step 1.1, combined with the geometric constraints of the actual physical space, determine the maximum length table of the trailer-mounted AGV that is allowed to turn and pass through each channel intersection node;

Step 1.4: Determine the maximum length of the trailer AGV as m according to the maximum length table of the trailer-mounted AGV that each node of the channel intersection is allowed to turn through created in step 1.3, and consider the trailer of length n (1≤n≤m) in turn. For the hanging AGV, the nodes whose maximum length of the trailer-mounted AGV is greater than or equal to n are selected from the set of nodes at the passage intersection V ^c to form a set.

中节点以外会使拖挂式AGV转弯的边，此时当且仅当集合

中节点作为单向边起点时，允许拖挂式AGV进行转弯；Combined with the initial one-way graph G ₀ constructed in step 1.2, delete the division set in G ₀

The edges other than the middle node that will turn the trailer-mounted AGV, if and only if the set

When the middle node is used as the starting point of the one-way edge, the trailer-mounted AGV is allowed to turn;

Construct the one-way graph G _n in turn to ensure that the trailer-mounted AGV with length n can operate normally in this one-way graph;

Step 1.5: Construct a multi-layer unidirectional graph G from the m unidirectional graphs obtained in step 1.4, G={G ₁ , G ₂ ,...G _m };

In order to avoid deadlock and the path constraints of the environment on the trailer-mounted AGV, the trailer-mounted AGV with a length of n (1≤n≤m) is only allowed to run on the one-way graph G _n ;

Step 1.6: According to the multi-layer one-way graph in step 1.5, use d _ij ⁿ to represent the length of n (1≤n≤m) trailer AGV from task node i to task node j (i, j∈V ^k ) The shortest distance of , constructs the distance matrix D _n between task nodes;

Step 2: According to the multi-layer one-way graph constructed in step 1 and the distance matrix between task nodes, the uncertainty of the delivery time is modeled by shifting the gamma distribution, and the uncertainty caused by factors such as the waiting strategy is solved. Reasonable estimation of the delivery time of the trailer-mounted AGV, determine the early lag penalty value of material delivery, and ensure that the material transportation task is completed within the non-strictly constrained time window of the demand point;

Step 2.1: Complete the time uncertainty modeling by introducing a distribution function describing the uncertain delivery time, and set the time u of the trailer-mounted AGV delivery unit distance to satisfy the translational gamma distribution of u~gamma (α, β, δ), where α is the shape parameter, β is the scale parameter, and δ is the translation;

The probability density function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (1):

The cumulative distribution function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (2):

Step 2.2: According to the translational gamma distribution of u constructed in step 2.1, combined with the additivity of the translational gamma distribution, the random delivery time T _ij of the trailer-mounted AGV from task node i to task node j satisfies T _ij ~ gamma ( d _ij α, β, d _ij δ);

Step 2.3: According to the translational gamma distribution of T _ij constructed in step 2.2, the time τ _k (X) required for the trailer-mounted AGV numbered to start from the warehouse to a certain task node k (k∈V ^k ) is as follows (3) shows:

Among them, R _ka is the set of all material demand points that the trailer-mounted AGV numbered a has passed before completing task k, including task node k and warehouse; x _ija is the decision variable, if the trailer-mounted AGV numbered a completes the task After the material of node i, the number of the next task node is j, then x _ija = 1, otherwise x _ija = 0; X is the set composed of all decision variables x _ija , representing the task scheduling scheme of the trailer-mounted multi-AGV system, X={x _ija |i,j∈V ^P ∪V ^k ,a∈A}, A is the set of trailer-mounted AGVs; _Lija (X) is the trailer-mounted AGV numbered a delivered from node i to node The length of the vehicle at j is related to the task scheduling scheme of the trailer-mounted multi-AGV system. _Lija (X) is shown in formula (4):

where |R _ka | represents the number of nodes in the set R _ka ;

Transform τ _k (X) into the form shown in formula (5):

Among them, θ _k represents the uncertain part of the delivery time, which satisfies θ _k ~gamma(α',β);

in,

Step 2.4: According to the time τ _k (X) required for the trailer-mounted AGV number a obtained in step 2.3 to arrive at the demand point k from the warehouse, combined with the time window demand [e _k ,l _k ] for the delivery of its materials , to determine the penalty value generated by the advance and lag of the trailer-mounted AGV;

Among them, _ek represents the start time of the time window, and _lk represents the end time of the time window;

Preferably, based on the quadratic loss function, determining the penalty value generated by the advance and lag of the trailer-mounted AGV includes the following steps:

When the trailer-mounted AGV numbered a undertakes the material transportation task k, the penalty E _ka (X) for physical delivery in advance of the time window is shown in formula (6):

表示配送时间不确定部分的下界，服从平移伽马分布，根据步骤2.1中公式(1)确定概率密度函数f，根据步骤2.1中公式(2)确定累积分布函数F；in,

Represents the lower bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1;

Among them, θ _k obeys the translational gamma distribution, the probability density function f is determined according to formula (1) in step 2.1, and the cumulative distribution function F is determined according to formula (2) in step 2.1;

Among them, a ₀ , a ₁ , and a ₂ are the coefficients of the quadratic loss function;

Similarly, the penalty D _ka (X) that will be physically delivered behind the time window is shown in Eq. (7):

表示配送时间不确定部分的上界，服从平移伽马分布，根据步骤2.1中公式(1)确定概率密度函数f，根据步骤2.1中公式(2)确定累积分布函数F；in,

Represents the upper bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1;

Among them, θ _k obeys the translational gamma distribution, the probability density function f is determined according to formula (1) in step 2.1, and the cumulative distribution function F is determined according to formula (2) in step 2.1;

Among them, a ₀ , a ₁ , and a ₂ are the coefficients of the quadratic loss function;

Step 3: According to the early lag penalty value obtained in step 2, establish a task scheduling model to minimize the early lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and determine the task execution route assigned to each trailer-mounted AGV;

Step 3.1: According to the early lag penalties E _ka (X) and D _ka (X) obtained in step 1.4, the optimization objective is that the trailer-mounted multi-AGV system completes all distribution tasks with the smallest early-delay penalty, and the constraint condition is the trailer-mounted AGV Transport constraints, establish a task scheduling model as follows:

The objective function is shown in formula (8):

The constraints are shown in equations (9) to (15) respectively:

x _ija ∈{0,1},i∈V ^p ∪V ^k ,j∈V ^p ∪V ^k ,a∈A (15)

的集合，|B|表示B中节点的数量；x_0ka、x_k0a由x_ija变化而来，为决策变量，如果编号为a的拖挂式AGV从仓库出发下一个任务节点编号为k，则x_0ka＝1，否则x_0ka＝0，如果x_0ka编号为a的拖挂式AGV运送完任务节点k的运输任务后返回仓库，则x_k0a＝1，否则x_k0a＝0；Among them, Q represents the maximum number of tasks that the trailer AGV can carry, and B represents any satisfaction

The set of , |B| represents the number of nodes in B; x _0ka , x _k0a are changed from x _ija and are decision variables. If the trailer AGV numbered a starts from the warehouse and the next task node number is k, then x _0ka =1, otherwise x _0ka =0, if x _0ka the trailer AGV with the number a of x 0ka returns to the warehouse after transporting the task of the task node k, then x _k0a =1, otherwise x _k0a =0;

Step 3.2: According to the task scheduling model constructed in Step 3.1, a simulated annealing algorithm is preferred to determine the task scheduling scheme of the trailer-mounted multi-AGV system, that is, the task execution route assigned to each trailer-mounted AGV.

Beneficial effects:

1. A task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph disclosed in the present invention constructs a multi-layer one-way graph according to the actual layout of the physical space, and applies the trailer-mounted AGV with variable length to manufacturing In the workshop, it can reduce the investment cost of the enterprise in the process of intelligent transformation, and solve the conflict and deadlock of the trailer-mounted AGV through the waiting strategy, so as to ensure the coordinated operation of the system without conflict;

2. A task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph disclosed in the present invention models the uncertainty of the delivery time by shifting the gamma distribution, which can effectively solve the problems caused by factors such as waiting strategies. Uncertainty affects the robustness of task scheduling methods;

3. A task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph disclosed in the present invention establishes a task scheduling model, so that the trailer-mounted multi-AGV system completes all delivery tasks with the smallest early lag penalty and is allocated to the multi-AGV system. The task execution route of each trailer AGV ensures the stability and timeliness of material distribution.

Description of drawings

1 is a schematic flowchart of a task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way graph of the present invention;

Figure 2 is the actual layout of the workshop;

Figure 3 is the key node diagram of the workshop;

Fig. 4 is a workshop one-way graph G ₁ ;

Fig. 5 is workshop one-way graph G ₂ ;

Fig. 6 is workshop one-way graph G ₃ ;

Fig. 7 is workshop one-way graph G ₄ ;

Figure 8 is a flowchart of the simulated annealing algorithm.

Detailed ways

In order to better illustrate the purpose and advantages of the present invention, the content of the invention will be further described below with reference to the accompanying drawings and examples.

Example 1:

As shown in FIG. 1 , the main process of a task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way map of the present invention is as follows: first, according to the actual layout of the physical space, a topology one-way map is constructed, and each node is determined. The maximum length table of the trailer-mounted AGV that allows turning through, and on this basis, a multi-layer one-way graph is constructed to ensure that the trailer-mounted AGV with variable length can operate normally, and the conflict and deadlock of the trailer-mounted AGV can be resolved through the waiting strategy. , to construct the distance matrix between nodes; then, on the basis of the multi-layer one-way graph and the distance matrix between nodes, the uncertainty of delivery time is modeled by shifting the gamma distribution to solve the inconsistency caused by factors such as waiting strategies. Deterministic impact, obtain a reasonable estimate of the delivery time of the trailer-mounted AGV, and determine the early-lag penalty value of material distribution; finally, establish a task scheduling model to minimize the early-lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and obtain The task execution route assigned to each trailer-mounted AGV.

This embodiment is the production layout and logistics requirements of the present invention applied to the assembly workshop of an agricultural machinery manufacturing enterprise. As shown in Figure 2, in the assembly workshop of this agricultural machinery manufacturing enterprise, there are general assembly lines and sub-assembly lines. Different components are assembled at different assembly stations, and finally the final assembly is carried out on the final assembly line. During the product assembly process, A large number of different kinds of materials need to be transported to the assembly station.

The concrete steps that the present invention is applied to the assembly workshop of the agricultural machinery manufacturing enterprise are as follows:

Step 1. According to the actual layout of the assembly workshop, build a topology one-way map, determine the maximum length table of the trailer-mounted AGV that each node is allowed to turn through, and build a multi-layer one-way map on this basis to ensure variable-length trailer-mounted AGVs. The AGV can run normally in the system, and solve the conflict and deadlock of the trailer-mounted AGV through the waiting strategy, and build the distance matrix between the nodes;

Step 1.1: For the layout of the assembly workshop, as shown in Figure 3, the important location points of the assembly workshop are abstracted into nodes, represented by v, where the set of all channel intersection nodes is V ^c , and the set of all task demand nodes is V ^k , the set of nodes where the warehouse entrance and exit are located is V ^p , the set of all nodes is V = V ^p ∪ V ^k ∪ V ^c , the road is abstracted into an edge, represented by z, the set is Z, and a topological map is constructed: the nodes numbered 1 to 30 represent The intersection nodes of the channel, numbered 31 to 57 represent the positions of the loading and unloading points in the layout, that is, the task demand nodes. Node 1 and node 24 correspond to the import and export of the material warehouse respectively. All materials of the production system enter the assembly workshop from node 1. The trailer AGV returns to the warehouse from node 24, and there is a situation in the system that the loading and unloading points overlap with the channel intersection, such as node 21 and node 49;

Step 1.2: According to the topology map constructed in Step 1.1, specify that the direction of each edge is one-way, and construct an environment one-way graph G ₀ ;

Step 1.3: According to the topology map constructed in step 1.1, combined with the geometric constraints of the assembly workshop, determine the maximum length table of the trailer-mounted AGV that is allowed to turn and pass through each channel intersection node, as shown in Table 1:

Table 1 The maximum length of the trailing AGV allowed to turn and pass through the intersection nodes of each channel

Step 1.4: According to the maximum length table of trailer-mounted AGVs that are allowed to turn through each channel intersection node created in step 1.3, determine the maximum length of trailer-mounted AGVs in the trailer-mounted multi-AGV system as 4, and consider the length as n(1 ≤n≤4) of the trailer-mounted AGV, select the nodes whose maximum length of the trailer-mounted AGV is greater than or equal to _n , which is allowed to turn through, to form ^a set Vnc from the node set ^Vc of the passage intersection;

Combined with the initial one-way graph G ₀ constructed in step 1.2, delete the edges in G ₀ other than the set V _n ^c nodes that will turn the trailer-mounted AGV, and construct one-way graphs G ₁ , G ₂ , G ₃ , G ₄ in turn, each The layer one-way diagram is shown in accompanying drawings 4 to 7;

Step 1.5: Construct a multi-layer unidirectional graph G from the 4 unidirectional graphs obtained in step 1.4, G={G ₁ , G ₂ , G ₃ , G ₄ }, a drag of length n (1≤n≤4) The hanging AGV is only allowed to run on the one-way graph G _n ;

Step 1.6: According to the multi-layer one-way graph in Step 1.5, build a distance matrix D _n between task nodes and a distance table between task nodes for drag-mounted AGVs with a length of n (1≤n≤4). As shown in table 2:

Table 2 Distance table between task nodes

Step 2: According to the multi-layer one-way graph constructed in step 1 and the distance matrix between task nodes, the uncertainty of the delivery time is modeled by shifting the gamma distribution, and the uncertainty caused by factors such as the waiting strategy is solved. Reasonable estimation of the delivery time of the trailer-mounted AGV, determine the early lag penalty value of material delivery, and ensure that the material transportation task is completed within the non-strictly constrained time window of the demand point;

Step 2.1: Set the time u of the trailer-mounted AGV delivery unit distance to satisfy the translational gamma distribution of u~gamma (α, β, δ), model the time uncertainty, and determine the shape parameters through parameter selection and optimization verification The value of α is 1, the value of scale parameter β is 0.25, and the value of translation δ is 0.75;

The probability density function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (1):

The cumulative distribution function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (2):

According to formula (1) and formula (2), the probability density function f(u)=16e ^3-4u of the time u～gamma(1,0.25,0.75) of the delivery unit distance is obtained, and the cumulative distribution function F(u)=1 -e ^3-4u ;

Step 2.2: According to the translational gamma distribution of u constructed in step 2.1, combined with the additivity of the translational gamma distribution, the random delivery time T _ij of the trailer-mounted AGV from node i to node j satisfies the translational gamma distribution T _ij ~ gamma(d _ij ,0.25,0.75d _ij );

Step 2.3: According to the translational gamma distribution of T _ij constructed in step 2.2, the time τ _k (X) required for the trailer-mounted AGV number a to arrive at a certain task node k (k∈V ^k ) from the warehouse is obtained As shown in formula (3):

Among them, R _ka is the set of all material demand points that the trailer-mounted AGV numbered a has passed before completing task k, including task node k and warehouse; x _ija is the decision variable, if the trailer-mounted AGV numbered a completes the task After the material of node i, the number of the next task node is j, then x _ija = 1, otherwise x _ija = 0; X is the set composed of all decision variables x _ija , representing the task scheduling scheme of the trailer-mounted multi-AGV system, X={x _ija |i,j∈V ^P ∪V ^k ,a∈A}, A is the set of trailer-mounted AGVs; _Lija (X) is the trailer-mounted AGV numbered a delivered from node i to node The length of the vehicle at j is related to the task scheduling scheme of the trailer-mounted multi-AGV system. _Lija (X) is shown in formula (4):

where |R _ka | represents the number of nodes in the set R _ka ;

Transform τ _k (X) into the form shown in formula (5):

Among them, θ _k represents the uncertain part of the delivery time, θ _k ～gamma(α',β);

in,

Step 2.4: This embodiment sets up a set of static task scheduling test cases according to the actual material transportation requirements of the assembly workshop. This case includes 20 tasks with non-strictly constrained time window requirements. The specific task nodes and time window constraints are shown in Table 3 As shown, the initial time of the system is set to 0, there are 7 trailer-mounted AGVs in the system, and the maximum length of each trailer-mounted AGV is 4;

Table 3 Static task scheduling test case table

According to the time τ _k (X) required for the trailer-mounted AGV number a obtained in step 2.3 to arrive at the demand point k from the warehouse, combined with the time window requirements [e _k ,l _k ] for its material delivery, as the preferred , based on the quadratic loss function, determine the penalty value of the trailer AGV in advance and lag;

Among them, _ek represents the start time of the time window, and _lk represents the end time of the time window;

When the trailer-mounted AGV numbered a undertakes the material transportation task k, the penalty E _ka (X) for physical delivery in advance of the time window is shown in formula (6):

表示配送时间不确定部分的下界，服从平移伽马分布，根据步骤2.1中公式(1)确定概率密度函数f，根据步骤2.1中公式(2)确定累积分布函数F；in,

Represents the lower bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1;

Among them, θ _k obeys the translational gamma distribution, the probability density function f is determined according to formula (1) in step 2.1, and the cumulative distribution function F is determined according to formula (2) in step 2.1;

Among them, a ₀ , a ₁ , and a ₂ are the coefficients of the quadratic loss function. After parameter selection and optimization verification, it is determined that the coefficient a ₀ of the quadratic loss function is 0, a ₁ is 1, and a ₂ is 0;

Similarly, the penalty D _ka (X) that will be physically delivered behind the time window is shown in Eq. (7):

表示配送时间不确定部分的上界，服从平移伽马分布，根据步骤2.1中公式(1)确定概率密度函数f，根据步骤2.1中公式(2)确定累积分布函数F；in,

Represents the upper bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1;

Step 3: According to the early lag penalty value obtained in step 2, establish a task scheduling model to minimize the early lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and determine the task execution route assigned to each trailer-mounted AGV;

Step 3.1: According to the early lag penalties E _ka (X) and D _ka (X) obtained in step 1.4, the optimization objective is that the trailer-mounted multi-AGV system completes all distribution tasks with the smallest early-delay penalty, and the constraint condition is the trailer-mounted AGV Transport constraints, establish a mathematical model of task scheduling as follows:

The objective function is shown in formula (8):

The constraints are shown in equations (9) to (15) respectively:

x _ija ∈{0,1},i∈V ^p ∪V ^k ,j∈V ^p ∪V ^k ,a∈A (15)

的集合，|B|表示B中节点的数量；Among them, Q represents the maximum number of tasks that the trailer AGV can carry, and B represents any satisfaction

The set of , |B| represents the number of nodes in B;

Step 3.2: According to the task scheduling model constructed in Step 3.1, a simulated annealing algorithm is preferred to determine the task scheduling scheme, that is, the task execution route assigned to each trailer-mounted AGV;

The flow chart of the simulated annealing algorithm is shown in Figure 8, and the specific implementation steps are as follows:

(1) Set the main control parameters of simulated annealing, including the initial temperature T ₀ , the end temperature T _end , the proportional temperature decrease rate κ (0<κ<1), and the maximum number of iterations Iter _max ; let the temperature T=T ₀ , the number of iterations iter = 1;

(2) Randomly generate the initial input value X ₀ , let X=X ₀ , determine the energy value of the initial value, that is, the objective function value f(X);

(3) Transform the current input value X to generate a new input value X', and the new input value X' corresponds to the new task allocation scheme of the trailer-mounted multi-AGV system;

(4) Calculate the new objective function value f(X′), the difference between the energy value of the new input value and the current input value Δf=f(X′)-f(X);

(5) If Δf<0, then X=X'; otherwise,

(6) Take a random number R=random(0,1) in the range (0,1), if P>R, then X=X′.

(7) If Iter<Iter _max , then Iter=Iter+1, and repeat (3) to (8), otherwise, go to (8);

(8) If T>T _end , then T=κT, and repeat (2) to (6), otherwise, go to (9);

(9) Output X and objective function value f(X);

The result obtained by the simulated annealing algorithm is the task scheduling scheme. Taking the task scheduling test case in step 2.4 as an example, the obtained results are:

X=[0 8 16 19 20 0 2 0 1 9 11 17 0 3 10 0 5 7 0 6 13 15 18 0 4 12 140];

The numbers in it represent the task numbers in the case of step 2.4, and the execution route for each trailer-mounted AGV task is shown in Table 4 below:

Table 4 Trailer AGV task execution route

The above-mentioned specific descriptions further describe the purpose, technical solutions and beneficial effects of the present invention in detail. It should be understood that the above-mentioned descriptions are only specific embodiments of the present invention, and are not intended to limit the protection of the present invention. Any modification, equivalent replacement, improvement, etc. made within the spirit and principle of the present invention shall be included within the protection scope of the present invention.

Claims (4)

1. A task scheduling method for a trailer-mounted multi-AGV system based on a multi-layer one-way map, characterized in that: firstly, according to the actual layout of the physical space, a topology one-way map is constructed, and each node is determined to allow turning through the trailer type. Based on the maximum length table of AGV, a multi-layer one-way graph is constructed to ensure the normal operation of trailer-mounted AGVs with variable lengths, and the conflict and deadlock of trailer-mounted AGVs are resolved through waiting strategies, and the distance between nodes is constructed. Then, based on the multi-layer one-way graph and the distance matrix between nodes, the uncertainty of the delivery time is modeled by shifting the gamma distribution to solve the uncertainty caused by the waiting strategy and other factors, and get the Reasonable estimation of the delivery time of the trailer-mounted AGV determines the early-lag penalty value of material distribution; finally, a task scheduling model is established to minimize the early-delay penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and obtain the allocation to each trailer-mounted AGV. task execution route. 2. as claimed in claim 1, it is characterized in that: comprise the steps: Step 1. According to the actual layout of the physical space, build a topological one-way map, determine the maximum length table of the trailer-mounted AGV that each node is allowed to turn through, and build a multi-layer one-way map on this basis to ensure variable-length trailer-mounted AGVs. The AGV can run normally in the system, and solve the conflict and deadlock of the trailer-mounted AGV through the waiting strategy, and build the distance matrix between the nodes; Step 1.1: For the layout of the physical space, the important location points are abstracted into nodes, represented by v, where the set of all channel intersection nodes is V ^c , the set of all task demand nodes is V ^k , and the set of nodes where warehouse entrances and exits are located is V ^p , the set of all nodes V=V ^p ∪V ^k ∪V ^c , abstract the road into an edge, represented by z, the set is Z, build a topological map, and ensure that there is an accessible path between any two road nodes, each The edges can allow vehicles to enter and exit normally; Step 1.2: According to the topology map constructed in Step 1.1, specify that the direction of each edge is one-way, that is, the edge zi _, j between any node v _i and the adjacent node v _j is a one-way edge, and the construction environment is one-way. graph G ₀ ; Among them, each side allows multiple trailer-mounted AGVs to exist at the same time, but the interval between each trailer-mounted AGV must be greater than the specified safe driving distance. In the one-way diagram, the conflict problem of all trailer-mounted AGVs is solved through the waiting strategy ; Step 1.3: According to the topology map constructed in step 1.1, combined with the geometric constraints of the actual physical space, determine the maximum length table of the trailer-mounted AGV that is allowed to turn and pass through each channel intersection node; Step 1.4: Determine the maximum length of the trailer AGV as m according to the maximum length table of the trailer-mounted AGV that each node of the channel intersection is allowed to turn through created in step 1.3, and consider the trailer of length n (1≤n≤m) in turn. For the hanging AGV, the nodes whose maximum length of the trailer-mounted AGV is greater than or equal to n are selected from the set of nodes at the passage intersection V ^c to form a set.

Combined with the initial one-way graph G ₀ constructed in step 1.2, delete the division set in G ₀

The edges other than the middle node that will turn the trailer-mounted AGV, if and only if the set

When the middle node is used as the starting point of the one-way edge, the trailer-mounted AGV is allowed to turn; Construct the one-way graph G _n in turn to ensure that the trailer-mounted AGV with length n can operate normally in this one-way graph; Step 1.5: Construct a multi-layer unidirectional graph G from the m unidirectional graphs obtained in step 1.4, G={G ₁ , G ₂ ,...G _m }; In order to avoid deadlock and the path constraints of the environment on the trailer-mounted AGV, the trailer-mounted AGV with a length of n (1≤n≤m) is only allowed to run on the one-way graph G _n ; Step 1.6: According to the multi-layer one-way graph in step 1.5, use d _ij ⁿ to represent the length of n (1≤n≤m) trailer AGV from task node i to task node j (i, j∈V ^k ) The shortest distance of , constructs the distance matrix D _n between task nodes; Step 2: According to the multi-layer one-way graph constructed in step 1 and the distance matrix between task nodes, the uncertainty of the delivery time is modeled by shifting the gamma distribution, and the uncertainty caused by factors such as the waiting strategy is solved. Reasonable estimation of the delivery time of the trailer-mounted AGV, determine the early lag penalty value of material delivery, and ensure that the material transportation task is completed within the non-strictly constrained time window of the demand point; Step 2.1: Complete the time uncertainty modeling by introducing a distribution function describing the uncertain delivery time, and set the time u of the trailer-mounted AGV delivery unit distance to satisfy the translational gamma distribution of u~gamma (α, β, δ), where α is the shape parameter, β is the scale parameter, and δ is the translation; The probability density function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (1):

The cumulative distribution function of the translational gamma distribution u～gamma(α,β,δ) is shown in formula (2):

Step 2.2: According to the translational gamma distribution of u constructed in step 2.1, combined with the additivity of the translational gamma distribution, the random delivery time T _ij of the trailer-mounted AGV from task node i to task node j satisfies T _ij ~ gamma ( d _ij α, β, d _ij δ); Step 2.3: According to the translational gamma distribution of T _ij constructed in step 2.2, the time τ _k (X) required for the trailer-mounted AGV numbered to start from the warehouse to a certain task node k (k∈V ^k ) is as follows (3) shows:

Among them, R _ka is the set of all material demand points that the trailer-mounted AGV numbered a has passed before completing task k, including task node k and warehouse; x _ija is the decision variable, if the trailer-mounted AGV numbered a completes the task After the material of node i, the number of the next task node is j, then x _ija = 1, otherwise x _ija = 0; X is the set composed of all decision variables x _ija , representing the task scheduling scheme of the trailer-mounted multi-AGV system, X={x _ija |i,j∈V ^P ∪V ^k ,a∈A}, A is the set of trailer-mounted AGVs; _Lija (X) is the trailer-mounted AGV numbered a delivered from node i to node The length of the vehicle at j is related to the task scheduling scheme of the trailer-mounted multi-AGV system. _Lija (X) is shown in formula (4):

where |R _ka | represents the number of nodes in the set R _ka ; Transform τ _k (X) into the form shown in formula (5):

Among them, θ _k represents the uncertain part of the delivery time, which satisfies θ _k ~gamma(α',β); in,

Step 2.4: According to the time τ _k (X) required for the trailer-mounted AGV number a obtained in step 2.3 to arrive at the demand point k from the warehouse, combined with the time window demand [e _k ,l _k ] for the delivery of its materials , to determine the penalty value generated by the advance and lag of the trailer-mounted AGV; Among them, _ek represents the start time of the time window, and _lk represents the end time of the time window; Step 3: According to the early lag penalty value obtained in step 2, establish a task scheduling model to minimize the early lag penalty for the trailer-mounted multi-AGV system to complete all distribution tasks, and obtain the task execution route assigned to each trailer-mounted AGV; Step 3.1: According to the early lag penalties E _ka (X) and D _ka (X) obtained in step 2.4, the optimization objective is that the trailer-mounted multi-AGV system completes all the delivery tasks with the smallest early-delay penalty, and the constraint condition is the trailer-mounted AGV Transport constraints, establish a task scheduling model as follows: The objective function is shown in formula (6):

Constraints are shown in equations (7) to (13) respectively:

x _ija ∈{0,1},i∈V ^p ∪V ^k ,j∈V ^p ∪V ^k ,a∈A (13) Among them, Q represents the maximum number of tasks that the trailer AGV can carry, and B represents any satisfaction

The set of , |B| represents the number of nodes in B; x _0ka , x _k0a are changed from x _ija and are decision variables. If the trailer AGV numbered a starts from the warehouse and the next task node number is k, then x _0ka =1, otherwise x _0ka =0, if x _0ka the trailer AGV with the number a of x 0ka returns to the warehouse after transporting the task of the task node k, then x _k0a =1, otherwise x _k0a =0; Step 3.2: According to the task scheduling model constructed in Step 3.1, determine the task scheduling scheme of the trailer-mounted multi-AGV system, that is, the task execution route assigned to each trailer-mounted AGV. 3. A kind of task scheduling method of trailer type multi-AGV system based on multi-layer one-way graph as claimed in claim 1 or 2, it is characterized in that: based on quadratic loss function, determine the penalty value that trailer type AGV produces in advance and lag , including the following steps: When the trailer-mounted AGV numbered a undertakes the material transportation task k, the penalty E _ka (X) for physical delivery in advance of the time window is shown in formula (14):

in,

Represents the lower bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1; Among them, θ _k obeys the translational gamma distribution, the probability density function f is determined according to formula (1) in step 2.1, and the cumulative distribution function F is determined according to formula (2) in step 2.1; Among them, a ₀ , a ₁ , and a ₂ are the coefficients of the quadratic loss function; Similarly, the penalty D _ka (X) for lagging the time window to be physically delivered is given by Eq. (15):

in,

Represents the upper bound of the uncertain part of the delivery time, which obeys the translational gamma distribution, determines the probability density function f according to formula (1) in step 2.1, and determines the cumulative distribution function F according to formula (2) in step 2.1; Among them, θ _k obeys the translational gamma distribution, the probability density function f is determined according to formula (1) in step 2.1, and the cumulative distribution function F is determined according to formula (2) in step 2.1; Among them, a ₀ , a ₁ , and a ₂ are the coefficients of the quadratic loss function. 4. A kind of task scheduling method of trailer type multi-AGV system based on multi-layer one-way graph as claimed in claim 1 or 2, it is characterized in that: in step 3.2, applying simulated annealing algorithm to determine the task of trailer type multi-AGV system Scheduling scheme, that is, the task execution route assigned to each trailer-mounted AGV.

Images