# A Novel Scheduling Algorithm for Common Rail Dual Automatic Guided Vehicles Particle Filtering Algorithm for Industrial Process Control

Authors: Yanghua Gao; Weidong Lou; Hailiang Lu
Journal: Mathematical Problems in Engineering
 (2021)

---

## Abstract

This paper explores deep into the collaborative scheduling of common rail dual automatic guided vehicles (AGVs). Firstly, a dual AGV scheduling model was constructed to minimize the overall time of material distribution. Then, a novel scheduling algorithm was developed to dynamically plan the orders based on time windows. To effectively minimize the distribution time, heuristic algorithms were adopted to initialize the distribution order of materials. On this basis, the collaboration between the two AGVs was innovatively designed based on dynamic planning and time windows, making up for the defects of traditional methods in AGV cooperation. This greatly shortens the running time of the entire system in material distribution. The computing results fully demonstrate the efficiency and rationality of our algorithm. Finally, our algorithm was proved to be superior to the benchmark method through experiments on actual industrial instances.


---

## Body

## 1. Introduction

With economic growth and industrial development, there is a rising demand for automation and intelligent transport. This gives birth to a series of automated logistics equipment, such as automatic identification system, automatic guided vehicle (AGV) system, and cargo tracking system. The AGV system boasts greater application potential than the other systems, owing to its advantages in automation and efficiency.The operations in many factories are faced with a nondeterministic polynomial-time (NP) hard problem: two AGVs at the opposite ends of a rail need to deliver materials to tanks along the rail, and the material distribution should be planned reasonably to minimize the distribution time. This problem was defined by Erdoğan in 2013 as the twin robots scheduling problem (TRSP) [1].The TRSP applies widely in the robotic industry, where gantry robots are employed by job-shops for packaging, assembly, palletizing, and depalletizing [2]. Similar scheduling problems have arisen in the context of automated parking garages [3] and automated libraries [4]. In addition, the TRSP can be extended to multidimensional problems, namely, robots working on shelves, and multirobot problems like multirobot cooperation system [5, 6].The dispatching of common rail dual AGVs is a typical TRSP in factories to quickly dispatch materials between tanks or automatically schedule express delivery in warehouses. Traditionally, this novel and specific problem is solved by simple heuristic algorithms, such as genetic algorithms (GA) and [7–10] particle swarm optimization (PSO) [11–13]. Due to the sheer scale of the problem, it is difficult for these algorithms to converge to the global optimal solution. Thus, it is urgent an efficient and feasible scheduling algorithm for common rail dual AGVs.This paper establishes a model of the common rail dual AGVs and presents an efficient solution to the model. The remainder of this paper is organized as follows: Section2 sets up a dual AGV scheduling model to minimize the running time of the AGV system; Section 3 presents a novel heuristic scheduling algorithm that dynamically plans material distribution tasks based on time windows; Section 4 compares our method with the benchmark method through experiments on a set of benchmark instances; Section 5 wraps up this work.


## 2. Model Construction

To model the common rail dual AGV system, the actual factory scheduling problem was abstracted and redefined as follows (Table1).Table 1
The symbol description.
SymbolMeaningl1The length of tank intervall2The length of each tankLThe slot lengthWiMaterial, wherei is the material numberCTiTank, wherei is the tank numberMThe total number of tankszAiThe current loading states of each AGVOAiThe current directions of each AGVmAiThe motion states of each AGVCiThe current states of each tankCTkFSerial number of the target tankTtempMaterialWi is temporarily stored in the left neighbor of the target tankTclrThe time it takes to empty the target tankφAiWhether AGVAi carries compatible materialsdk1k2The distance between the two AGVstThe time to pass through a tankTThe time of picking up and putting down materialsTtotalThe running time of the entire AGV systemDThe length of each AGV journeyThe common rail dual AGV system has two AGVs, one rail, and two independent hangars. During the operation, the two AGVs automatically drive in opposite directions along the same rail. Each end of the rail leads to a hangar. The tanks are evenly arranged along one or both sides of the rail for material stacking. Multiple materials can be stacked in the same tank but can only be picked up from top to bottom.Each AGV is preallocated by the system. The operation of each AGV includes three steps: picking, transporting, and placing along the rail. The AGV can only handle one material at a time. After completing all tasks, the AGV must return to its hangar to be reset for the next operation.To avoid collisions, a safe distance must be maintained between the two AGVs. Suppose that the two AGVs operate at the same speed on the rail, which can be calculated at timet when passing by a tank. Then, the two AGVs take the same amount of time (on average), T, to pick up and put down the material (Figure 1).Figure 1
The abstract diagram of the dual AGV system.After abstracting the actual problem, the objective is to design a dual AGV scheduling strategy that minimizes the times for the two AGVs to complete the assigned material tasks and return to their respective hangars.


### 2.1. Dual AGV Scheduling Model with Minimized Time

#### 2.1.1. Motion States and Directions of AGVs

To clearly illustrate the coordinate change of AGVs, the rail was abstracted into a numerical axis with the leftmost end as the origin. It is assumed that the tanks are arranged at equal intervals. The length of each interval and the length of each tank are denoted asl1 and l2, respectively. Then, the total length of each slot, that is, each tank and its left interval, can be calculated by(1)L=l1+l2.The current loading states of the two AGVs can be described by the state variablezAi (i = 1, 2):(2)zAi=0,AGVAiis unloaded,1,AGVAiis loaded,2,AGVAiis picking up materials,3,AGVAiis putting down materials.The current directions of the two AGVs can be represented by a 0–1 decision variableOAi (i = 1, 2):(3)OAi=0,AGVAimoves to the left,1,AGVAimoves to the right.Taking the picking and placing processes as static state (through which the two AGVs avoid collision), the current motion states of the two AGVs can be illustrated by another 0–1 decision variablemAi (i = 1, 2):(4)mAi=0,AGVAiis at rest,1,AGVAiis in motion.


#### 2.1.2. States of Tanks

If a material is placed in its target tank, the material is compatible with the tank. Otherwise, the material is not compatible with the tank. LetCi be the current state of the tank. If the tank belongs to the state Ci = −1, all materials have been delivered to the target tank and the two AGVs have returned to the hangars:(5)Ci=0,the tank is empty,1,there are incompatible materials in the tank,−1,the tank is full of compatible materials.


#### 2.1.3. Tank Constraints

The materials are handled by the last-in, first-out principle. That is, each material is transported to the current tank to the target tankCTkF, where k is the serial number of the target tank. The destination slot must be empty or only compatible before the material is placed:(6)CTkF=0or−1.IfCTkF=1, there are incompatible materials. The number of noncompatible materials is denoted as j. Then, it is necessary to judge the direction OAi of the AGV. If OAi=0, the AGV temporarily places the target material Winow in the right neighbor of the target tank CTk+1F. If OAi=1, the material Winow is temporarily stored in the left neighbor of the target tank CTk−1F, which can be recorded as Ttemp=T.Next, the AGV drives toCTkF and transports j incompatible materials to the left neighbor CTk−1F or the right neighbor CTk+1F without temporary storage of Winow until CTkF=0or−1. The time it takes to empty the target tank is denoted as Tclr=2T+2tj. Figure 2 illustrates the rules for material delivery.Figure 2
The rules for material delivery.


#### 2.1.4. Distribution Constraint

When being delivered to its destination tank, each material must be distributed by the specified AGV. Hence, an indexφAi was introduced to judge whether AGV Ai carries materials that are compatible with the target tank:(7)φAi=0,AGVAicarries compatible materials,1,AGVAicarries incompatible materials,and, then, at any moment, make bothφAi values of the two AGVs zero:(8)∑φAi=0,and this constraint ensures that each AGV is delivering the materials allocated to it at any time.


#### 2.1.5. Safe Distance Constraint

The positions of AGV1 and AGV2 on the rail, denoted asXk1A1 and Xk2A2, can be, respectively, derived as(9)Xk1A1=k1L,Xk2A2=k2L,where k1 and k2 are tank numbers of AGV1 and AGV2, respectively.Then, the distance betweenA1 and A2 can be represented by dk1k2. There is a phased conflict between the schedules of the two AGVs. To avoid directional conflict between A1 and A2, at least one slot length L must be maintained between them as the safe distance [14]:(10)dk1k2=Xk1A1−Xk2A2=bL,b∈Z+,b≥2.Thus, the relationship between the locations of the two AGVs can be described as(11)k2=k1+b,b∈Z+,b≥2.


### 2.2. Dual AGV Scheduling Model with Minimal Time

Under the above constraints, a dual AGV scheduling model can be established to minimize the time of material distribution. The paths of the AGVs can be described by an undirected graphG=CT,E, where CT  =  CT1,CT2,…,CTm is the set of tanks, and E = E1,E2,…,Ei is the set of intervals between tanks CTi and CTj. Then, the length of the journey of each AGV can be described as an integer multiple of slot length L:(12)Eij=i−jL.Suppose that an AGV changes direction forb times on the way to deliver materials. Let CTi and CTj be the start and end points of the AGV at the second change of direction B (0 ≤ BB ≤ bb), respectively. Then, the route of the AGV is denoted as EijB. The travel length of the AGV can be expressed as(13)D=∑b=0BEijB.Obviously, each AGV picks up the same amount of materials as those it delivers. Letn be the times of pick-ups (and also the times of placements) of the AGV, let t be the time to pass through a tank, and let T be the time of picking up and putting down materials. Then, the time for each AGV to complete its tasks and return to its hangar can be determined. The total time for AGV1 to complete its tasks and return to its hangar can be calculated by(14)Ttotal1=D1t+n1T,where D1 is the length of the journey of AGV1 and n1 is the number of pick-ups or placements of AGV1.The total time for AGV2 to complete its tasks and return to its hangar can be calculated by(15)Ttotal2=D2t+n2T,where D2 is the length of the journey of AGV2 and n2 is the number of pick-ups or placements of AGV2.Then, the total running time of the entire AGV system equals the longer running time between the two AGVs:(16)Ttotal=maxTtotal1,Ttotal2.In this way, a dual AGV scheduling model can be established aiming to let the two AGVs complete their tasks and return to their respective hangar as early as possible, that is, to minimize the running time of the entire AGV system:(17)minTtotals.t.CTkF=0or−1,∑φAi=0,Ttemp=T,Tclr=2T+2tj,dk1k2=Xk1A1−Xk2A2=bL,b∈Z+,b≥2,k2=k1+b,b∈Z+,b≥2,Eij=i−jL,D=∑b=0BEijB,Ttotal1=D1t+n1T,Ttotal2=D2t+n2T,Ttotal=maxTtotal1,Ttotal2.


## 2.1. Dual AGV Scheduling Model with Minimized Time

### 2.1.1. Motion States and Directions of AGVs

To clearly illustrate the coordinate change of AGVs, the rail was abstracted into a numerical axis with the leftmost end as the origin. It is assumed that the tanks are arranged at equal intervals. The length of each interval and the length of each tank are denoted asl1 and l2, respectively. Then, the total length of each slot, that is, each tank and its left interval, can be calculated by(1)L=l1+l2.The current loading states of the two AGVs can be described by the state variablezAi (i = 1, 2):(2)zAi=0,AGVAiis unloaded,1,AGVAiis loaded,2,AGVAiis picking up materials,3,AGVAiis putting down materials.The current directions of the two AGVs can be represented by a 0–1 decision variableOAi (i = 1, 2):(3)OAi=0,AGVAimoves to the left,1,AGVAimoves to the right.Taking the picking and placing processes as static state (through which the two AGVs avoid collision), the current motion states of the two AGVs can be illustrated by another 0–1 decision variablemAi (i = 1, 2):(4)mAi=0,AGVAiis at rest,1,AGVAiis in motion.


### 2.1.2. States of Tanks

If a material is placed in its target tank, the material is compatible with the tank. Otherwise, the material is not compatible with the tank. LetCi be the current state of the tank. If the tank belongs to the state Ci = −1, all materials have been delivered to the target tank and the two AGVs have returned to the hangars:(5)Ci=0,the tank is empty,1,there are incompatible materials in the tank,−1,the tank is full of compatible materials.


### 2.1.3. Tank Constraints

The materials are handled by the last-in, first-out principle. That is, each material is transported to the current tank to the target tankCTkF, where k is the serial number of the target tank. The destination slot must be empty or only compatible before the material is placed:(6)CTkF=0or−1.IfCTkF=1, there are incompatible materials. The number of noncompatible materials is denoted as j. Then, it is necessary to judge the direction OAi of the AGV. If OAi=0, the AGV temporarily places the target material Winow in the right neighbor of the target tank CTk+1F. If OAi=1, the material Winow is temporarily stored in the left neighbor of the target tank CTk−1F, which can be recorded as Ttemp=T.Next, the AGV drives toCTkF and transports j incompatible materials to the left neighbor CTk−1F or the right neighbor CTk+1F without temporary storage of Winow until CTkF=0or−1. The time it takes to empty the target tank is denoted as Tclr=2T+2tj. Figure 2 illustrates the rules for material delivery.Figure 2
The rules for material delivery.


### 2.1.4. Distribution Constraint

When being delivered to its destination tank, each material must be distributed by the specified AGV. Hence, an indexφAi was introduced to judge whether AGV Ai carries materials that are compatible with the target tank:(7)φAi=0,AGVAicarries compatible materials,1,AGVAicarries incompatible materials,and, then, at any moment, make bothφAi values of the two AGVs zero:(8)∑φAi=0,and this constraint ensures that each AGV is delivering the materials allocated to it at any time.


### 2.1.5. Safe Distance Constraint

The positions of AGV1 and AGV2 on the rail, denoted asXk1A1 and Xk2A2, can be, respectively, derived as(9)Xk1A1=k1L,Xk2A2=k2L,where k1 and k2 are tank numbers of AGV1 and AGV2, respectively.Then, the distance betweenA1 and A2 can be represented by dk1k2. There is a phased conflict between the schedules of the two AGVs. To avoid directional conflict between A1 and A2, at least one slot length L must be maintained between them as the safe distance [14]:(10)dk1k2=Xk1A1−Xk2A2=bL,b∈Z+,b≥2.Thus, the relationship between the locations of the two AGVs can be described as(11)k2=k1+b,b∈Z+,b≥2.


## 2.1.1. Motion States and Directions of AGVs

To clearly illustrate the coordinate change of AGVs, the rail was abstracted into a numerical axis with the leftmost end as the origin. It is assumed that the tanks are arranged at equal intervals. The length of each interval and the length of each tank are denoted asl1 and l2, respectively. Then, the total length of each slot, that is, each tank and its left interval, can be calculated by(1)L=l1+l2.The current loading states of the two AGVs can be described by the state variablezAi (i = 1, 2):(2)zAi=0,AGVAiis unloaded,1,AGVAiis loaded,2,AGVAiis picking up materials,3,AGVAiis putting down materials.The current directions of the two AGVs can be represented by a 0–1 decision variableOAi (i = 1, 2):(3)OAi=0,AGVAimoves to the left,1,AGVAimoves to the right.Taking the picking and placing processes as static state (through which the two AGVs avoid collision), the current motion states of the two AGVs can be illustrated by another 0–1 decision variablemAi (i = 1, 2):(4)mAi=0,AGVAiis at rest,1,AGVAiis in motion.


## 2.1.2. States of Tanks

If a material is placed in its target tank, the material is compatible with the tank. Otherwise, the material is not compatible with the tank. LetCi be the current state of the tank. If the tank belongs to the state Ci = −1, all materials have been delivered to the target tank and the two AGVs have returned to the hangars:(5)Ci=0,the tank is empty,1,there are incompatible materials in the tank,−1,the tank is full of compatible materials.


## 2.1.3. Tank Constraints

The materials are handled by the last-in, first-out principle. That is, each material is transported to the current tank to the target tankCTkF, where k is the serial number of the target tank. The destination slot must be empty or only compatible before the material is placed:(6)CTkF=0or−1.IfCTkF=1, there are incompatible materials. The number of noncompatible materials is denoted as j. Then, it is necessary to judge the direction OAi of the AGV. If OAi=0, the AGV temporarily places the target material Winow in the right neighbor of the target tank CTk+1F. If OAi=1, the material Winow is temporarily stored in the left neighbor of the target tank CTk−1F, which can be recorded as Ttemp=T.Next, the AGV drives toCTkF and transports j incompatible materials to the left neighbor CTk−1F or the right neighbor CTk+1F without temporary storage of Winow until CTkF=0or−1. The time it takes to empty the target tank is denoted as Tclr=2T+2tj. Figure 2 illustrates the rules for material delivery.Figure 2
The rules for material delivery.


## 2.1.4. Distribution Constraint

When being delivered to its destination tank, each material must be distributed by the specified AGV. Hence, an indexφAi was introduced to judge whether AGV Ai carries materials that are compatible with the target tank:(7)φAi=0,AGVAicarries compatible materials,1,AGVAicarries incompatible materials,and, then, at any moment, make bothφAi values of the two AGVs zero:(8)∑φAi=0,and this constraint ensures that each AGV is delivering the materials allocated to it at any time.


## 2.1.5. Safe Distance Constraint

The positions of AGV1 and AGV2 on the rail, denoted asXk1A1 and Xk2A2, can be, respectively, derived as(9)Xk1A1=k1L,Xk2A2=k2L,where k1 and k2 are tank numbers of AGV1 and AGV2, respectively.Then, the distance betweenA1 and A2 can be represented by dk1k2. There is a phased conflict between the schedules of the two AGVs. To avoid directional conflict between A1 and A2, at least one slot length L must be maintained between them as the safe distance [14]:(10)dk1k2=Xk1A1−Xk2A2=bL,b∈Z+,b≥2.Thus, the relationship between the locations of the two AGVs can be described as(11)k2=k1+b,b∈Z+,b≥2.


## 2.2. Dual AGV Scheduling Model with Minimal Time

Under the above constraints, a dual AGV scheduling model can be established to minimize the time of material distribution. The paths of the AGVs can be described by an undirected graphG=CT,E, where CT  =  CT1,CT2,…,CTm is the set of tanks, and E = E1,E2,…,Ei is the set of intervals between tanks CTi and CTj. Then, the length of the journey of each AGV can be described as an integer multiple of slot length L:(12)Eij=i−jL.Suppose that an AGV changes direction forb times on the way to deliver materials. Let CTi and CTj be the start and end points of the AGV at the second change of direction B (0 ≤ BB ≤ bb), respectively. Then, the route of the AGV is denoted as EijB. The travel length of the AGV can be expressed as(13)D=∑b=0BEijB.Obviously, each AGV picks up the same amount of materials as those it delivers. Letn be the times of pick-ups (and also the times of placements) of the AGV, let t be the time to pass through a tank, and let T be the time of picking up and putting down materials. Then, the time for each AGV to complete its tasks and return to its hangar can be determined. The total time for AGV1 to complete its tasks and return to its hangar can be calculated by(14)Ttotal1=D1t+n1T,where D1 is the length of the journey of AGV1 and n1 is the number of pick-ups or placements of AGV1.The total time for AGV2 to complete its tasks and return to its hangar can be calculated by(15)Ttotal2=D2t+n2T,where D2 is the length of the journey of AGV2 and n2 is the number of pick-ups or placements of AGV2.Then, the total running time of the entire AGV system equals the longer running time between the two AGVs:(16)Ttotal=maxTtotal1,Ttotal2.In this way, a dual AGV scheduling model can be established aiming to let the two AGVs complete their tasks and return to their respective hangar as early as possible, that is, to minimize the running time of the entire AGV system:(17)minTtotals.t.CTkF=0or−1,∑φAi=0,Ttemp=T,Tclr=2T+2tj,dk1k2=Xk1A1−Xk2A2=bL,b∈Z+,b≥2,k2=k1+b,b∈Z+,b≥2,Eij=i−jL,D=∑b=0BEijB,Ttotal1=D1t+n1T,Ttotal2=D2t+n2T,Ttotal=maxTtotal1,Ttotal2.


## 3. Scheduling Algorithm

### 3.1. Time Windows Model

Letrij be the j-th occupied time window on the i-th tank, and let fmn be the n-th idle time window on the m-th tank. At each moment t, AGV1 and AGV2 occupy the time window where a tank is located. Then, the time Tarrfk0p,fkFq to move from the current tank k0 of the material to the target tank kF can be calculated by(18)Tarrfk0p,fkFq=Lfk0p+tk0kF+tΔ,where Lfk0p is the time to reach the starting tank K0 in a free time; tk0kF is the time to move from the starting tank K0 to the end tank KF without considering safe distance; tΔ is the additional time to move from K0 to KF incurred by the location and motion states of the other AGV [15].


### 3.2. Adding Safe Distance

Under the safe distance, the tankrij where AGV is located and its left neighbor ri−1j and right neighbor ri+1j are occupied simultaneously; moreover, the other AGV cannot appear in this section with this AGV at the same time. Then, the current state vi of the current slot can be depicted as [16](19)vi=0,the tank is occupied and the AGV is in theithori±1thtank,1,the tank is free and the AGV is not in theithori±1thtank.For every timet, the state of each slot needs to be changed with the location of the AGV. Figure 3 explains the occupation state of the time window.Figure 3
The occupation state of the time window.


### 3.3. Heuristic Scheduling Algorithm for Dynamic Planning of Material Distribution Tasks Based on Time Windows (DPTW)

#### 3.3.1. Workflow

Step 1. Find the shortest time delivery sequence for the independent delivery state of each AGV by the genetic algorithm (GA)(1)
Parameter initializationInitialize the selection, crossover, and mutation probabilities according to the performance of the AGVs.(2)
EncodingSet up a coding string of the lengthnAi and values between 1 and nAi, where nAi is the total number of materials assigned to Ai.(3)
Generating the initial solutionRandomly generate a coded string of lengthnAi; that is, randomly arrange the order of material delivery, as the initial solution.(4)
Fitness calculationTake the penultimate time required to complete the local materials in the current order (1/Ttotal) as the fitness function. The reciprocal value of the fitness is negatively correlated with the time cost and positively with the fitness of each individual.(5)
Population selectionUse the Tournament Selection Method (TSM) [17, 18] to remove some individuals from the population, and select one of the best fit individuals to enter the next population. Repeat this process until the new population equals the original population in size.(6)
Crossover and mutationImplement the reverse mutation operator [19] and exchange the order of material distribution.(7)
EvolutionObtain the new population and repeat Step (4) until the 10,000-th iteration to get the best fit individuals.(8)
DecodingDecode the genetic sequence of the order of local material distribution for each AGV. Store the results of AGV1 and AGV2 in one-dimensional (1D) arraysp01 and p02, respectively, which reflect the minimum running time in the case of independent interaction.Step 2. Order distribution based on the initial minimum running timeAs shown in Figure4, distribute the first task to AGV1 and AGV2 according to the initial scheduling plan p01, obtain the time window of the first task of each AGV, and judge whether there is an overlapping section RPS between the routes of the two AGVs.If yes, let the AGV closer to the destination tank continue with its delivery, and halt the other AGV until the overlapping section is cleared.If not, repeat Step 2 after the delivery to assign the second task as per the initial plan until an overlapping section arises. Once an overlapping section occurs, go to Step 3 for dynamic planning of the next task.Step 3. Dynamic planning of the next task based on time windowsAssign the next taskRWi+1K0,KF,ti+1 to an AGV after it has placed the current task material and entered the unloaded state zAi=0.(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.IfA1 terminates the current task but A2 continues with the current task, dynamically plan the next task of A1 in combination with the time window of A2; conversely, dynamically plan the next task of A2 in combination with the time window of A1.Firstly, search for the nearest tanks on the left and right of the current slot ofA1, and denote them as optional task points RW1 and RW2, following the greedy strategy. Take the number of the next materials in the original plan p01 as alternative task point RW3.Next, obtain the time window of the alternative tank separately, and plan the route and time to reach the starting and target tanks.Finally, compareA2 with the time windows of the current target tank, measure the set of overlapping sections RP1SS, RP2SS, and RP3SS, and take the RW corresponding to min{RP1SS,RP2SS,RP3SS} as the next task.(2)
Case 2: the two AGVs end the current task in a synchronized manner.IfA1 and A2 terminate the current task at the same time and if the distribution of the next task to one of them affects that of the other, then A1 and A2 search for the nearest tanks on the left and right of their current slots and denote them as optional task points RW1A1,RW2A1 and RW1A2,RW2A2 following the greedy strategy and also take the number of the next materials in the original plan p01 as alternative task points RW3A1 and RW3A2.Next, obtain the time windows of the three alternative task points ofA1 and A2, respectively, and plan the route and time for each AGV to reach the starting and target tanks.Finally, establish the set of overlapping sections, and take the least overlapping combinations as the next task of the two AGVs.Step 4. Determine the motion state for the next task(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.Let an AGV receive the next task as a collaborator, compare the time windows for transporting the current materials, and choose to stop or stay away for cooperation with the AGV still engaged in material delivery at the end of the overlapping section, according to its locationki and whether ki−2/ki+2 is busy at the next moment:(20)vki=1,vki−2vki+2=1,move left/right,vki=1,vki+2=0,move to the/end tank,vki=0,vki−2vki+2=1,Stop.(2)
Case 2: the two AGVs end the current task in a synchronized manner.Since there is an overlapping section between the two AGVs, choose the collaborator based on their distances from the starting tank to the target tank. Make the AGV farther away from its target tank as the collaborator, and choose to stop or stay away. The determination of the motion state for the next task is illustrated in Figure5.Step 5. Repeating Steps 3 and 4 until the end of material distributionRepeat Steps 3 and 4 until all material tasks are completed, return to the hangar, count the transport time of each task, and obtain the shortest timeminTtotal.(2)
Running time optimizationTo minimize the overall time cost of placing the target materials, the two AGVs can cooperate with each other to empty their target tank under the following conditions.Figure 4
The handling of overlapping section.Figure 5
The determination of the motion state for the next task.One AGV can issue an emptying request to the other AGV if their distancedk1k2 satisfies(21)dk1k2≥2Tt+2L.Suppose that AGV1 is the one issuing the request. Letk2 and kA2 be the current position and starting tank of AGV2, respectively; let kA1 be the target tank of AGV1 (k2<kA1<kA2). If AGV2 is unloaded currently and moves in the same direction (right) as AGV1, then AGV2 will accept the request under the following conditions:(22)OA1=OA2=1,zA2=0,k2<kA1<kA2.Suppose that AGV2 is the one issuing the request. Letk1 and kA1 be the current position and starting tank of AGV1, respectively; let kA2 be the target tank of AGV2 (k1<kA2<kA1). If AGV1 is unloaded currently and moves in the same direction (right) as AGV2, then AGV1 will accept the request under the following conditions:(23)OA1=OA2=1,zA1=0,k1<kA2<kA1.Figure6 explains the process of dual AGVs collaborating with each other.Figure 6
The collaboration between the two AGVs.


#### 3.3.2. Algorithm Flow

Figure7 presents the workflow of the proposed algorithm.Figure 7
The workflow of the proposed algorithm.


## 3.1. Time Windows Model

Letrij be the j-th occupied time window on the i-th tank, and let fmn be the n-th idle time window on the m-th tank. At each moment t, AGV1 and AGV2 occupy the time window where a tank is located. Then, the time Tarrfk0p,fkFq to move from the current tank k0 of the material to the target tank kF can be calculated by(18)Tarrfk0p,fkFq=Lfk0p+tk0kF+tΔ,where Lfk0p is the time to reach the starting tank K0 in a free time; tk0kF is the time to move from the starting tank K0 to the end tank KF without considering safe distance; tΔ is the additional time to move from K0 to KF incurred by the location and motion states of the other AGV [15].


## 3.2. Adding Safe Distance

Under the safe distance, the tankrij where AGV is located and its left neighbor ri−1j and right neighbor ri+1j are occupied simultaneously; moreover, the other AGV cannot appear in this section with this AGV at the same time. Then, the current state vi of the current slot can be depicted as [16](19)vi=0,the tank is occupied and the AGV is in theithori±1thtank,1,the tank is free and the AGV is not in theithori±1thtank.For every timet, the state of each slot needs to be changed with the location of the AGV. Figure 3 explains the occupation state of the time window.Figure 3
The occupation state of the time window.


## 3.3. Heuristic Scheduling Algorithm for Dynamic Planning of Material Distribution Tasks Based on Time Windows (DPTW)

### 3.3.1. Workflow

Step 1. Find the shortest time delivery sequence for the independent delivery state of each AGV by the genetic algorithm (GA)(1)
Parameter initializationInitialize the selection, crossover, and mutation probabilities according to the performance of the AGVs.(2)
EncodingSet up a coding string of the lengthnAi and values between 1 and nAi, where nAi is the total number of materials assigned to Ai.(3)
Generating the initial solutionRandomly generate a coded string of lengthnAi; that is, randomly arrange the order of material delivery, as the initial solution.(4)
Fitness calculationTake the penultimate time required to complete the local materials in the current order (1/Ttotal) as the fitness function. The reciprocal value of the fitness is negatively correlated with the time cost and positively with the fitness of each individual.(5)
Population selectionUse the Tournament Selection Method (TSM) [17, 18] to remove some individuals from the population, and select one of the best fit individuals to enter the next population. Repeat this process until the new population equals the original population in size.(6)
Crossover and mutationImplement the reverse mutation operator [19] and exchange the order of material distribution.(7)
EvolutionObtain the new population and repeat Step (4) until the 10,000-th iteration to get the best fit individuals.(8)
DecodingDecode the genetic sequence of the order of local material distribution for each AGV. Store the results of AGV1 and AGV2 in one-dimensional (1D) arraysp01 and p02, respectively, which reflect the minimum running time in the case of independent interaction.Step 2. Order distribution based on the initial minimum running timeAs shown in Figure4, distribute the first task to AGV1 and AGV2 according to the initial scheduling plan p01, obtain the time window of the first task of each AGV, and judge whether there is an overlapping section RPS between the routes of the two AGVs.If yes, let the AGV closer to the destination tank continue with its delivery, and halt the other AGV until the overlapping section is cleared.If not, repeat Step 2 after the delivery to assign the second task as per the initial plan until an overlapping section arises. Once an overlapping section occurs, go to Step 3 for dynamic planning of the next task.Step 3. Dynamic planning of the next task based on time windowsAssign the next taskRWi+1K0,KF,ti+1 to an AGV after it has placed the current task material and entered the unloaded state zAi=0.(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.IfA1 terminates the current task but A2 continues with the current task, dynamically plan the next task of A1 in combination with the time window of A2; conversely, dynamically plan the next task of A2 in combination with the time window of A1.Firstly, search for the nearest tanks on the left and right of the current slot ofA1, and denote them as optional task points RW1 and RW2, following the greedy strategy. Take the number of the next materials in the original plan p01 as alternative task point RW3.Next, obtain the time window of the alternative tank separately, and plan the route and time to reach the starting and target tanks.Finally, compareA2 with the time windows of the current target tank, measure the set of overlapping sections RP1SS, RP2SS, and RP3SS, and take the RW corresponding to min{RP1SS,RP2SS,RP3SS} as the next task.(2)
Case 2: the two AGVs end the current task in a synchronized manner.IfA1 and A2 terminate the current task at the same time and if the distribution of the next task to one of them affects that of the other, then A1 and A2 search for the nearest tanks on the left and right of their current slots and denote them as optional task points RW1A1,RW2A1 and RW1A2,RW2A2 following the greedy strategy and also take the number of the next materials in the original plan p01 as alternative task points RW3A1 and RW3A2.Next, obtain the time windows of the three alternative task points ofA1 and A2, respectively, and plan the route and time for each AGV to reach the starting and target tanks.Finally, establish the set of overlapping sections, and take the least overlapping combinations as the next task of the two AGVs.Step 4. Determine the motion state for the next task(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.Let an AGV receive the next task as a collaborator, compare the time windows for transporting the current materials, and choose to stop or stay away for cooperation with the AGV still engaged in material delivery at the end of the overlapping section, according to its locationki and whether ki−2/ki+2 is busy at the next moment:(20)vki=1,vki−2vki+2=1,move left/right,vki=1,vki+2=0,move to the/end tank,vki=0,vki−2vki+2=1,Stop.(2)
Case 2: the two AGVs end the current task in a synchronized manner.Since there is an overlapping section between the two AGVs, choose the collaborator based on their distances from the starting tank to the target tank. Make the AGV farther away from its target tank as the collaborator, and choose to stop or stay away. The determination of the motion state for the next task is illustrated in Figure5.Step 5. Repeating Steps 3 and 4 until the end of material distributionRepeat Steps 3 and 4 until all material tasks are completed, return to the hangar, count the transport time of each task, and obtain the shortest timeminTtotal.(2)
Running time optimizationTo minimize the overall time cost of placing the target materials, the two AGVs can cooperate with each other to empty their target tank under the following conditions.Figure 4
The handling of overlapping section.Figure 5
The determination of the motion state for the next task.One AGV can issue an emptying request to the other AGV if their distancedk1k2 satisfies(21)dk1k2≥2Tt+2L.Suppose that AGV1 is the one issuing the request. Letk2 and kA2 be the current position and starting tank of AGV2, respectively; let kA1 be the target tank of AGV1 (k2<kA1<kA2). If AGV2 is unloaded currently and moves in the same direction (right) as AGV1, then AGV2 will accept the request under the following conditions:(22)OA1=OA2=1,zA2=0,k2<kA1<kA2.Suppose that AGV2 is the one issuing the request. Letk1 and kA1 be the current position and starting tank of AGV1, respectively; let kA2 be the target tank of AGV2 (k1<kA2<kA1). If AGV1 is unloaded currently and moves in the same direction (right) as AGV2, then AGV1 will accept the request under the following conditions:(23)OA1=OA2=1,zA1=0,k1<kA2<kA1.Figure6 explains the process of dual AGVs collaborating with each other.Figure 6
The collaboration between the two AGVs.


### 3.3.2. Algorithm Flow

Figure7 presents the workflow of the proposed algorithm.Figure 7
The workflow of the proposed algorithm.


## 3.3.1. Workflow

Step 1. Find the shortest time delivery sequence for the independent delivery state of each AGV by the genetic algorithm (GA)(1)
Parameter initializationInitialize the selection, crossover, and mutation probabilities according to the performance of the AGVs.(2)
EncodingSet up a coding string of the lengthnAi and values between 1 and nAi, where nAi is the total number of materials assigned to Ai.(3)
Generating the initial solutionRandomly generate a coded string of lengthnAi; that is, randomly arrange the order of material delivery, as the initial solution.(4)
Fitness calculationTake the penultimate time required to complete the local materials in the current order (1/Ttotal) as the fitness function. The reciprocal value of the fitness is negatively correlated with the time cost and positively with the fitness of each individual.(5)
Population selectionUse the Tournament Selection Method (TSM) [17, 18] to remove some individuals from the population, and select one of the best fit individuals to enter the next population. Repeat this process until the new population equals the original population in size.(6)
Crossover and mutationImplement the reverse mutation operator [19] and exchange the order of material distribution.(7)
EvolutionObtain the new population and repeat Step (4) until the 10,000-th iteration to get the best fit individuals.(8)
DecodingDecode the genetic sequence of the order of local material distribution for each AGV. Store the results of AGV1 and AGV2 in one-dimensional (1D) arraysp01 and p02, respectively, which reflect the minimum running time in the case of independent interaction.Step 2. Order distribution based on the initial minimum running timeAs shown in Figure4, distribute the first task to AGV1 and AGV2 according to the initial scheduling plan p01, obtain the time window of the first task of each AGV, and judge whether there is an overlapping section RPS between the routes of the two AGVs.If yes, let the AGV closer to the destination tank continue with its delivery, and halt the other AGV until the overlapping section is cleared.If not, repeat Step 2 after the delivery to assign the second task as per the initial plan until an overlapping section arises. Once an overlapping section occurs, go to Step 3 for dynamic planning of the next task.Step 3. Dynamic planning of the next task based on time windowsAssign the next taskRWi+1K0,KF,ti+1 to an AGV after it has placed the current task material and entered the unloaded state zAi=0.(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.IfA1 terminates the current task but A2 continues with the current task, dynamically plan the next task of A1 in combination with the time window of A2; conversely, dynamically plan the next task of A2 in combination with the time window of A1.Firstly, search for the nearest tanks on the left and right of the current slot ofA1, and denote them as optional task points RW1 and RW2, following the greedy strategy. Take the number of the next materials in the original plan p01 as alternative task point RW3.Next, obtain the time window of the alternative tank separately, and plan the route and time to reach the starting and target tanks.Finally, compareA2 with the time windows of the current target tank, measure the set of overlapping sections RP1SS, RP2SS, and RP3SS, and take the RW corresponding to min{RP1SS,RP2SS,RP3SS} as the next task.(2)
Case 2: the two AGVs end the current task in a synchronized manner.IfA1 and A2 terminate the current task at the same time and if the distribution of the next task to one of them affects that of the other, then A1 and A2 search for the nearest tanks on the left and right of their current slots and denote them as optional task points RW1A1,RW2A1 and RW1A2,RW2A2 following the greedy strategy and also take the number of the next materials in the original plan p01 as alternative task points RW3A1 and RW3A2.Next, obtain the time windows of the three alternative task points ofA1 and A2, respectively, and plan the route and time for each AGV to reach the starting and target tanks.Finally, establish the set of overlapping sections, and take the least overlapping combinations as the next task of the two AGVs.Step 4. Determine the motion state for the next task(1)
Case 1: the two AGVs do not end the current task in a synchronized manner.Let an AGV receive the next task as a collaborator, compare the time windows for transporting the current materials, and choose to stop or stay away for cooperation with the AGV still engaged in material delivery at the end of the overlapping section, according to its locationki and whether ki−2/ki+2 is busy at the next moment:(20)vki=1,vki−2vki+2=1,move left/right,vki=1,vki+2=0,move to the/end tank,vki=0,vki−2vki+2=1,Stop.(2)
Case 2: the two AGVs end the current task in a synchronized manner.Since there is an overlapping section between the two AGVs, choose the collaborator based on their distances from the starting tank to the target tank. Make the AGV farther away from its target tank as the collaborator, and choose to stop or stay away. The determination of the motion state for the next task is illustrated in Figure5.Step 5. Repeating Steps 3 and 4 until the end of material distributionRepeat Steps 3 and 4 until all material tasks are completed, return to the hangar, count the transport time of each task, and obtain the shortest timeminTtotal.(2)
Running time optimizationTo minimize the overall time cost of placing the target materials, the two AGVs can cooperate with each other to empty their target tank under the following conditions.Figure 4
The handling of overlapping section.Figure 5
The determination of the motion state for the next task.One AGV can issue an emptying request to the other AGV if their distancedk1k2 satisfies(21)dk1k2≥2Tt+2L.Suppose that AGV1 is the one issuing the request. Letk2 and kA2 be the current position and starting tank of AGV2, respectively; let kA1 be the target tank of AGV1 (k2<kA1<kA2). If AGV2 is unloaded currently and moves in the same direction (right) as AGV1, then AGV2 will accept the request under the following conditions:(22)OA1=OA2=1,zA2=0,k2<kA1<kA2.Suppose that AGV2 is the one issuing the request. Letk1 and kA1 be the current position and starting tank of AGV1, respectively; let kA2 be the target tank of AGV2 (k1<kA2<kA1). If AGV1 is unloaded currently and moves in the same direction (right) as AGV2, then AGV1 will accept the request under the following conditions:(23)OA1=OA2=1,zA1=0,k1<kA2<kA1.Figure6 explains the process of dual AGVs collaborating with each other.Figure 6
The collaboration between the two AGVs.


## 3.3.2. Algorithm Flow

Figure7 presents the workflow of the proposed algorithm.Figure 7
The workflow of the proposed algorithm.


## 4. Computational Results in Industrial Implementation

To verify its performance, the proposed algorithm was applied to minimize the overall time of the common rail dual AGVs in handling 16 actual orders from a factory. For comparison, the classical GA was also tested to test whether our algorithm can outshine the common baseline search algorithm. Tables2 to 17 provide the details of the 16 orders.Table 2
Instance 1 (number of tanks: 20).
Material serial numberAllocated AGVCurrent tankTarget tank121202123324114178519761109721112811479216510217811118112219121312013Table 3
Instance 2 (number of tanks: 20).
Material serial numberAllocated AGVCurrent tankTarget tank1211022393144425151686272721018811116911251011317112151512216141311781421818151198162208Table 4
Instance 3 (number of tanks: 20).
Material serial numberAllocated AGVCurrent tankTarget tank111822214313641318515156271729118291992102102104111105122122013113101421812151197Table 5
Instance 4 (number of tanks: 20).
Material serial numberAllocated AGVCurrent tankTarget tank12113223632513417251946210571111282114921141011216112125121161113116171411717152171616118101711919Table 6
Instance 5 (number of tanks: 20).
Material serial numberAllocated AGVCurrent tankTarget tank11118222231214413175242062787281382816918910191211210912210513211121411311151131161131217215201811812191207Table 7
Instance 6 (number of tanks: 25).
Material serial numberAllocated AGVCurrent tankTarget tank1112222113231042710519561101671112082121491131710214211111524122161413217161421821151191616220617222191822361912513Table 8
Instance 7 (number of tanks: 25).
Material serial numberAllocated AGVCurrent tankTarget tank11118223431434141051766271072716818139291510210211111101221221311217141131715214151611514172181818218319121242022220Table 9
Instance 8 (number of tanks: 25).
Material serial numberAllocated AGVCurrent tankTarget tank121321233232414751519627177281282949110310112201121324121154132164142172151181116119117220718221151922223201232321124162212525Table 10
Instance 9 (number of tanks: 25).
Material serial numberAllocated AGVCurrent tankTarget tank1231921543262342755197611020711128214229114910215411115181221771322020142207151212116222251712216181245Table 11
Instance 10 (number of tanks: 25).
Material serial numberAllocated AGVCurrent tankTarget tank12314225143181041101851111462127721219821424921551021641111624122171413117181411911151191416119217219121812017191207201211621221322222172312425Table 12
Instance 11 (number of tanks: 30).
Material serial numberAllocated AGVCurrent tankTarget tank121121227312142513516286263071810829299110191011191121171211312131132514213241511526162167172172318217271921810202184212241422227523128232412912Table 13
Instance 12 (number of tanks: 30).
Material serial numberAllocated AGVCurrent tankTarget tank12152222323124172851813619217292682101691112010111911114112216113218614224251522413162252017126318127151922721202291121130282223025Table 14
Instance 13 (number of tanks: 30).
Material serial numberAllocated AGVCurrent tankTarget tank121142226323254142852515616247173827179289101121111112712112513114201411515151151162161517217918218281921812202196211197221212623224724225142522632622632712729Table 15
Instance 14 (number of tanks: 30).
Material serial numberAllocated AGVCurrent tankTarget tank111272118311284131152320614187142082699281610282711192512110221321013142111815111101611111711316182132019114920214121116222211620231161024217142511928261196272198281202329224113022425312263032227193322927Table 16
Instance 15 (number of tanks: 30).
Material serial numberAllocated AGVCurrent tankTarget tank1232221429324141429526216271671758185918251021111111111221224131133014214415114191621524171169181162191172420120232112012221222123222824223252522692612652722916Table 17
Instance 16 (number of tanks: 40).
Material serial numberAllocated AGVCurrent tankTarget tank11415224183171941718521128621127721228212329212241021526111152412219261312128142222815123416123251722416182242819125292022515211262522226322322636241281625128162612916271302828130372913123302321531236832137133313820342382835139203623922As shown in Table18, our algorithm greatly shortened the overall distribution time of the GA, an evidence to its rationality and high performance. Take order 7 as an example to illustrate the rationality and effectiveness of our algorithm. Figure 8 explains the next routes of the two AGVs in the event of a conflict [20].Table 18
The computing results (unit: s).
InstanceDPTWGAInstance 1550755Instance 2620805Instance 3595780Instance 4650855Instance 59201365Instance 6665915Instance 77851190Instance 89951375Instance 99101120Instance 109751235Instance 1113551860Instance 1210751665Instance 1314851910Instance 1418752350Instance 1515952130Instance 1622953345Figure 8
The illustration of conflict avoidance in order 7.By our algorithm, the final results of AGV operations and order of material distribution were obtained. Then, the distribution order was randomly changed to obtain new solutions to AGV running time. After the changes, the running time of the AGVs and the relevant solutions were observed to see if our algorithm could lead to the best solution.Figure9 presents the randomly changed order and the new running time of the 30 orders in Tables 2 to 17. It can be seen that all the new solutions were greater than the original running time, indicating that the scheduling plan of our algorithm is the best possible solution.Figure 9
The running time after random changes of material distribution order.The next step is to verify whether any solution in the 16 solutions is the optimal solution. Taking order 7 as the object, the order of material distributions was changed randomly twice, three times, and four times, respectively. The running time of each change is shown in Figure10.Figure 10
The running time after three types of changes in material distribution order.It can be seen that, after the changes in material distribution order, the final new solutions were greater than the benchmark value of 785. Hence, the proposed algorithm can always obtain the optimal solution.


## 5. Conclusions

This paper models and solves the problem of common rail dual AGVs scheduling in a novel way. The proposed solving algorithm for the problem consists of five steps, each of which is described in detail, and provides the scheduling plans considering the various situations of AGV motions. The performance of our algorithm was fully verified through experiments. The results show that our algorithm can solve the problem more efficiently and is more effective than the GA in all cases. Even if the solution structure was partly changed by random, our algorithm could still find the optimal solution very quickly. The future research will extend proposed method to multi-AGV cooperative scheduling or develop even more efficient online dynamic programming algorithms for this problem.



---

*Source: 6651615-2021-01-06.xml*