# A CEGA-Based Optimization Approach for Integrated Designing of a Unidirectional Guide-Path Network and Scheduling of AGVs

Authors: Haining Xiao; Xing Wu; Yong Zeng; Jingjing Zhai
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

In the current industrial fields, automatic guided vehicles (AGVs) are widely employed to constitute the flexible manufacturing system (FMS), owing to their great advantages of routing flexibility and high efficiency. However, one main challenge lies in the coupling process of the design problem of the unidirectional guide-path network (UGN) and the task scheduling problem of AGVs. To reduce the complexity, most pertinent literatures only handle these problems one by one, based on the stepwise design methods, thereby neglecting the constraint conditions and the optimization objectives caused by the FMS environment. The motivation of the paper is to bring the coupling factors into the integrated design and solution process. Firstly, an integrated design model of designing UGN and scheduling AGVs simultaneously is proposed, with the objective of minimizing the makespan (i.e., the maximum completion time of all handling tasks), in the consideration of the practical constraints, e.g., the job handling and processing sequence constraints and the AGV number constraint. Secondly, a dual-population collaborative evolutionary genetic algorithm (CEGA) is developed to solve the problems of designing and scheduling in a parallel way. The solutions of the integrated model, i.e., the potential strongly connected UGN and the feasible processing and handling sequence, are, respectively, coded as two different subpopulations with independent and concurrent evolution processes. The neighbourhood search operation, the niche technique, and the elitism strategy are combined to improve the convergence speed and maintain the population diversity. The experimental results show that the integrated design model can formulate the problem more accurately, and the CEGA algorithm is computationally efficient with high solution quality.


---

## Body

## 1. Introduction

As a flexible and high-efficiency logistics system, an automatic-guided vehicle system (AGVS) has broad application prospects in fields such as port transportation, warehousing and distribution, and manufacturing [1]. The unidirectional guide-path network (UGN) design and the AGVS task scheduling [2–4] are the two main issues that should be addressed when the AGVS is adopted. Many design models and algorithms for these two problems have been proposed in the literature. For example, aiming at the UGN design problem, Kaspi et al. [5] proposed a branch and bound method to minimize the travel distance of loaded vehicles, which can obtain the optimal solution more stably. Since the time complexity of the algorithm increases exponentially with the scale of the network, the method is only suitable for small-scale design problems. To decrease the design time, some heuristic algorithms have been developed. For example, Ko and Egbelu [6] proposed a multistage design method that determines the direction of the path sequentially, according to the traffic flow, with the objective of minimizing the travel distance of loaded vehicles. However, this algorithm does not take into account the empty travel distance and the result may substantially differ from the actual situation. Seo et al. [7] solved the UGN design problem by using a tabu search (TS) algorithm but without the consideration of the empty travel distance. Besides, the algorithm has the comparatively strong dependence on the initial status, thereby being prone to fall into the local optimum. Guan et al. [8] proposed an improved electromagnetism-like mechanism algorithm to minimize both loaded and empty travel distance. Functionally similar approaches also include the genetic algorithm [9, 10] and the met heuristics algorithm [11].In recent years, many mathematical models and algorithms have been developed for the AGVs task scheduling problem in the manufacturing environment. For example, aiming at the logistics dynamic scheduling problem in an intelligent manufacturing workshop (IMW), Xu et al. [12] proposed an intelligent logistics scheduling model and response method with Automated-Guided Vehicles (AGVs) based on the mode of “request-scheduling-response.” Umar et al. [13] investigated the simultaneous scheduling of machines and AGVs in an FMS environment. A mixed-integer nonlinear programming model was formulated firstly, and a hybrid multiobjective genetic algorithm was then proposed to optimize the makespan, AGV travel time, and penalty cost. Kumar et al. [14] addressed simultaneous scheduling of both machines and material handling systems with alternative machines for the makespan minimizing objective. A machine selection heuristic and a vehicle assignment heuristic were incorporated in the differential evolution approach to assign tasks to appropriate machines and vehicles and to minimize cycle time. Similar research works can be found in Nouri et al. [15], Ahmadi-Javid and Hooshangi-Tabrizi [16], Lin et al. [17], Lacomme et al. [18], and Zhang and Li et al. [19]. Ahmadi-Javid and Hooshangi-Tabrizi [20] addressed a ternary integration scheduling problem, which incorporated employee timetabling into the schedules of machines and transportation systems in a job shop environment. A timed coloured Petri net (TCPN) approach with two performance objectives was devised in [21] for the simultaneous scheduling problem of machines and AGVs. Moreover, two heuristics (A∗ and ALS [22]) were developed to partially explore the graph. Lyu et al. [23] focused on the machine and AGV scheduling problem in a flexible manufacturing system by simultaneously considering the optimal number of AGVs, the shortest transportation time, a path planning problem, and a conflict-free routing problem (CFRP). To study these problems simultaneously, they proposed a genetic algorithm combined with the Dijkstra algorithm that is based on a time window. Li et al. [24] proposed a mathematical model and an improved harmony search algorithm for material transfer in a real-world manufacturing system.In fact, the design process of the UGN is potentially correlated with the task scheduling problem of AGVs in an FMS environment [25]. The mutual coupling relationship is mainly reflected in the following two aspects. On the one hand, the UGN determines the job transportation time among different workstations [26], while the transportation time is an important factor that must be considered in solving the AGVs task scheduling problem [27–29]. On the other hand, the AGVs task scheduling scheme influences the traffic flow [30] between each two workstations, which provides one main reference for the UGN design process. In this sense, these two problems are highly interacted with each other.However, the mutual coupling relationship is often neglected in the pertinent literature, in order to decrease the complexity of the problem. The stepwise design method, which separates the UGN design from the AGV task scheduling, is mostly employed in the current design process. Firstly, the loaded traffic flow matrix among all workstations is generated on the basis of the job technological route information. Secondly, an optimal UGN is designed by optimizing only one objective, i.e., the loaded and empty travel distance. Other objectives and constraints in the FMS environment, e.g., the job handling and processing sequence constraints introduced by the job technological route, are neglected in this design stage. Finally, the simultaneous scheduling of machines and AGVs is addressed by taking into account the practical constraints and other objectives in the industrial field, e.g., minimizing the makespan. It is obvious that the stepwise design method reduces the complexity of the problem significantly. However, the solution quality of UGN cannot be always guaranteed due to the model infidelity without the coupling relationship.The motivation behind this article lies in developing an integrated design model and a parallel optimization approach of the UGN design and AGV task scheduling, by considering the practical constraints imposed by the FMS environments. Our main contributions are twofold. On the one hand, an integrated design model of the UGN design and AGV scheduling in an FMS environment is constructed with the makespan minimization objective. The practical constraints in the industrial field, e.g., the job handling and processing sequence constraints, and the AGV number constraint, are considered in the model. On the other hand, a dual-population collaborative evolutionary genetic algorithm (CEGA) is proposed to solve the problems of designing and scheduling in a parallel way. Two kinds of chromosome are used, respectively, for coding the strongly connected UGN and the feasible processing and handling sequence as two different subpopulations. They evolve independently and concurrently, only having an information exchange when an individual need to be evaluated. Moreover, the neighbourhood search operation, the niche technique, and the elite retention strategy are combined to improve the convergence speed and maintain the population diversity.The rest of this paper is organised as follows. The problem statement is described in detail in Section2 and a new integrated model of simultaneously designing a UGN and scheduling AGVs in an FMS is formulated. In Section 3, a CEGA approach with specific evolutionary operators is proposed to solve the integrated model. In Section 4, computational experiments are carried out and experimental results are analysed and compared. Finally, conclusions and recommendations for future research are given in Section 5.


## 2. Problem Formulation

Figure1 shows a typical FMS layout and an undirected guided-path network of AGVS. In the figure, M0 and M9 represent the input workstation and output workstation, respectively. M1 to M8 are the processing workstations, and each workstation Mm is composed of an input buffer, a processing machine, and an output buffer. The input workstation only has an output buffer, and the output workstation has only an input buffer. There is an undirected guided-path network G=V,E in the middle, where V is the node set, which is composed of the loading points, unloading points, and other path intersection points. The edge (path segment) set is E, and the length of the edge ei,j is di,j. There are NJ kinds of jobs J=Jj1≤j≤NJ to be processed in this workshop. As shown in Figure 2, each job Jj is composed of nj processing tasks and nj+1 handling tasks. All handling tasks are performed by NG AGVs. The processing workstation and the time of each processing task are known. The questions needed to be settled are as follows: the direction of each guided-path section, the execution AGV of each handling task, and the execution sequence of all processing and handling tasks. First, some assumptions are given as follows:(1)
A processing machine can only perform one processing task at a time. Once a processing task is started, it cannot be interrupted. Each processing machine processes the jobs in the input buffer based on the first-come-first-served rule.(2)
When the FMS starts to run, each job is located at the output buffer of the input workstation and is waiting to be transported to the first processing workstation according to its technological route. The job will enter the input buffer, when it arrives at the unloading point of the workstation. After the job completes a processing task by the processing machine, it will enter the output buffer of the corresponding workstation and wait to be transported to the next workstation. After completing all processing tasks, the job will leave the system via the output workstation.(3)
When the FMS starts to run, all AGVs are located at the loading point of the input workstation. They will return to the loading point of the input workstation after completing all handling tasks.(4)
The capacity of all buffers in the system is sufficiently large, so deadlock problems triggered by the insufficient buffer capacity are not considered.(5)
An AGV can only carry one job at a time. The loading and unloading time are not taken into account.(6)
An idle AGV will stay at the unloading points of its last handling task but does not affect the operation of other AGVs.(7)
Routing deadlocks caused by path conflicts between AGVs are not considered.Figure 1
FMS layout and undirected guide-path network.Figure 2
Task sequence of each job.


### 2.1. Symbol Definitions

N
M is the number of processing workstations.
Ω
M
=
M
m
m
∈
N
and
0
≤
m
≤
N
M
+
1, the set of workstations. M1 to MNM are the processing workstations. M0 and MNM+1 represent the input workstation and output workstation, respectively.
N
J is the number of job types in the system.
Ω
J
=
J
j
j
∈
N
and
1
≤
j
≤
N
J, the set of jobs.
n
j is the total number of processing tasks for the job Jj.
Ω
O
j
=
O
i
,
j
i
∈
N
and
1
≤
i
≤
n
j, the set of all processing tasks for the job Jj.
Ω
G
=
A
G
V
k
k
∈
N
and
1
≤
k
≤
N
G, the set of AGVs, and NG represents the number of AGVs in the system.
b
i
,
j is the direction of the path segment ei,j. If the value is 1, the direction is from node vi to vj; the reverse direction occurs, if the value is 0.
N
P is the number of loading points.
N
D is the number of unloading points.
N
T is the number of handling tasks.
X
i
,
j
,
k
T is the assignment relationship between the handling tasks Tij and the vehicle AGVk. The value of 1 means task Tij will be executed by AGVk; otherwise, the value is 0.
X
i
,
j
,
k
T
N
T
×
N
G is the assignment matrix between all the AGVs and the handling tasks.
D
P
D
N
p
×
N
D is the matrix of the shortest distance among all loading and unloading points.
d
u
,
w
L is the element located at the u−th row and w−th column in DPDNp×ND, representing the shortest distance from the loading point Pu to the unloading point Dw.
D
D
P
N
D
×
N
P is the matrix of the shortest logistic distance among all unloading and loading points.
d
w
,
u
E is the element located at the w−th row and u−th column in DDPND×NP, representing the shortest logistic distance from the unloading point Dw to the loading point Pu.
C
k is the completion time for the AGVk as it returns to the loading point of the input workstation after finishing all handling tasks.
S
i
,
j
,
k
,
m
T is the starting time of handling task Ti,j, which is the m−th handling task of vehicle AGVk.
E
i
,
j
−
1
,
k
,
a
T is the completion time of handling task Ti,j−1, which is the a−th handling task of the vehicle AGVk.
S
i
,
j
,
w
,
n
O is the starting time of processing task Oi,j, which is the n−th processing task of workstation Mw.
E
i
,
j
,
w
,
n
O is the completion time of processing task Oi,j, which is the n−th processing task of workstation Mw.
v is the speed of the AGV.


### 2.2. Decision-Making Variables

(a)
b
i
,
j is the direction of all the path segments in the guide-path network. This variable is the decision variable of the traditional UGN design problem.
(b)
X
i
,
j
,
k
T
N
T
×
N
G is the assignment matrix between all the AGVs and the handling tasks. This variable is the first decision variable of the AGVs task scheduling problem.
(c)
The feasible execution sequence of all the processing and handling tasks. This variable is the second decision variable of the AGVs task scheduling problem.


### 2.3. Objective Function

The objective is to minimize the makespan, which is the maximum completion time of all AGVs return to the loading point of the input workstation after finishing all handling tasks. So, the objective function is(1)minMakespan==minmaxC1,C2,…,Ck,…,CNG,where Ck=Ec,NJ,k,aT+dw,0E/v.


### 2.4. Constraint Conditions

#### 2.4.1. Decision Variable Constraints

The decision variable is a 0-1 integer, that is,(2)∀ei,j∈Ehasbi,j∈0,1.The direction of each path segment is unique:(3)∀ei,j∈Ehasbi,j+bj,i=1.


#### 2.4.2. Auxiliary Decision Variable Constraints

The auxiliary decision variable is a 0-1 integer, that is,(4)∀Xi,j,kThasXi,j,kT∈0,1.Each handling task can only be assigned to one AGV:(5)∀Ti,jhas∑k=1NGXi,j,kT=1.


#### 2.4.3. The UGN Must Be Strongly Connected

Each node contains at least one outdegree (i.e., the number of edges starting from this node) and one indegree (i.e., the number of edges ending at this node), which is a necessary condition for a strongly connected UGN:(6)∀ei,j∈Ehas∑j=1NVbi,j≥1and∑j=1NVbj,i≥1.There is a route to link any pair of unloading point and loading point, so it can be written as follows:(7)∀dw,uE∈DDPND×NPhasdw,uE<∞.There is a route to link any pair of loading point and unloading point, which can be expressed as follows:(8)∀du,wL∈DPDNP×NDhasdu,wL<∞.


#### 2.4.4. Processing and Handling Sequence Constraints

Handling taskTi,j+1 can be executed only after the processing task Oi,j is completed:(9)Ei,j,u,nO≤Si,j+1,k,mT.Handling taskTi,j can be started only after the AGVk has completed the previous handling task Tc,d and arrived at the loading point Pu of the task Ti,j:(10)Ec,d,k,m−1T+dw,uEv≤Si,j,k,mT.Only after the job arrives at the current workstation, the current processing taskOi,j can start, which can be expressed by(11)Ei,j,k,mT=Si,j,k,mT+du,wLv≤Si,j,w,nO.Each processing machine can only perform one processing task at a time. So, only after the previous processing taskOg,h is finished, the next processing task Oi,j can start, which can be expressed by(12)Eg,h,w,n−1O≤Si,j,w,nO.As said before, the UGN design problem is potentially correlated with the AGVs task scheduling problem. The mutual coupling relationship is mainly reflected in the following two aspects. On the one hand, it can be seen from constraints (10) and (11) that the shortest distances among all loading or unloading points (dw,uE and du,wL) are the important factors to determine the beginning time of all processing and handling tasks, while the shortest distance between all loading points depends on the decision variable of the traditional UGN design problem. On the other hand, only when the decision variables of the AGVs scheduling problem are known, the completion time Ck can be determined by constraints (9) to (12), so as to evaluate the quality of the designed UGN.As both the UGN design and the AGVs scheduling problem in the FMS environment are nondeterministic polynomial time- (NP-) hard problems [31, 32], the integration of these two problems will become a more complex NP-hard problem. As a high-performance multipopulation heuristic intelligent search algorithm, the collaborative evolutionary genetic algorithm (CEGA) [33] divides the system decision variables into several variable subgroups. Each variable subgroup can select appropriate encoding scheme to obtain a subpopulation. Moreover, appropriate genetic operators can be designed for each subpopulation according to its encoding characteristics. The CEGA is very suitable for solving the problem of multivariable combinatorial optimization [34, 35]. Based on the characteristics of the abovementioned mathematical model, a dual-population CEGA involving the collaborative evolution of the UGN subpopulation and the task sequence subpopulation is proposed.


## 2.1. Symbol Definitions

N
M is the number of processing workstations.
Ω
M
=
M
m
m
∈
N
and
0
≤
m
≤
N
M
+
1, the set of workstations. M1 to MNM are the processing workstations. M0 and MNM+1 represent the input workstation and output workstation, respectively.
N
J is the number of job types in the system.
Ω
J
=
J
j
j
∈
N
and
1
≤
j
≤
N
J, the set of jobs.
n
j is the total number of processing tasks for the job Jj.
Ω
O
j
=
O
i
,
j
i
∈
N
and
1
≤
i
≤
n
j, the set of all processing tasks for the job Jj.
Ω
G
=
A
G
V
k
k
∈
N
and
1
≤
k
≤
N
G, the set of AGVs, and NG represents the number of AGVs in the system.
b
i
,
j is the direction of the path segment ei,j. If the value is 1, the direction is from node vi to vj; the reverse direction occurs, if the value is 0.
N
P is the number of loading points.
N
D is the number of unloading points.
N
T is the number of handling tasks.
X
i
,
j
,
k
T is the assignment relationship between the handling tasks Tij and the vehicle AGVk. The value of 1 means task Tij will be executed by AGVk; otherwise, the value is 0.
X
i
,
j
,
k
T
N
T
×
N
G is the assignment matrix between all the AGVs and the handling tasks.
D
P
D
N
p
×
N
D is the matrix of the shortest distance among all loading and unloading points.
d
u
,
w
L is the element located at the u−th row and w−th column in DPDNp×ND, representing the shortest distance from the loading point Pu to the unloading point Dw.
D
D
P
N
D
×
N
P is the matrix of the shortest logistic distance among all unloading and loading points.
d
w
,
u
E is the element located at the w−th row and u−th column in DDPND×NP, representing the shortest logistic distance from the unloading point Dw to the loading point Pu.
C
k is the completion time for the AGVk as it returns to the loading point of the input workstation after finishing all handling tasks.
S
i
,
j
,
k
,
m
T is the starting time of handling task Ti,j, which is the m−th handling task of vehicle AGVk.
E
i
,
j
−
1
,
k
,
a
T is the completion time of handling task Ti,j−1, which is the a−th handling task of the vehicle AGVk.
S
i
,
j
,
w
,
n
O is the starting time of processing task Oi,j, which is the n−th processing task of workstation Mw.
E
i
,
j
,
w
,
n
O is the completion time of processing task Oi,j, which is the n−th processing task of workstation Mw.
v is the speed of the AGV.


## 2.2. Decision-Making Variables

(a)
b
i
,
j is the direction of all the path segments in the guide-path network. This variable is the decision variable of the traditional UGN design problem.
(b)
X
i
,
j
,
k
T
N
T
×
N
G is the assignment matrix between all the AGVs and the handling tasks. This variable is the first decision variable of the AGVs task scheduling problem.
(c)
The feasible execution sequence of all the processing and handling tasks. This variable is the second decision variable of the AGVs task scheduling problem.


## 2.3. Objective Function

The objective is to minimize the makespan, which is the maximum completion time of all AGVs return to the loading point of the input workstation after finishing all handling tasks. So, the objective function is(1)minMakespan==minmaxC1,C2,…,Ck,…,CNG,where Ck=Ec,NJ,k,aT+dw,0E/v.


## 2.4. Constraint Conditions

### 2.4.1. Decision Variable Constraints

The decision variable is a 0-1 integer, that is,(2)∀ei,j∈Ehasbi,j∈0,1.The direction of each path segment is unique:(3)∀ei,j∈Ehasbi,j+bj,i=1.


### 2.4.2. Auxiliary Decision Variable Constraints

The auxiliary decision variable is a 0-1 integer, that is,(4)∀Xi,j,kThasXi,j,kT∈0,1.Each handling task can only be assigned to one AGV:(5)∀Ti,jhas∑k=1NGXi,j,kT=1.


### 2.4.3. The UGN Must Be Strongly Connected

Each node contains at least one outdegree (i.e., the number of edges starting from this node) and one indegree (i.e., the number of edges ending at this node), which is a necessary condition for a strongly connected UGN:(6)∀ei,j∈Ehas∑j=1NVbi,j≥1and∑j=1NVbj,i≥1.There is a route to link any pair of unloading point and loading point, so it can be written as follows:(7)∀dw,uE∈DDPND×NPhasdw,uE<∞.There is a route to link any pair of loading point and unloading point, which can be expressed as follows:(8)∀du,wL∈DPDNP×NDhasdu,wL<∞.


### 2.4.4. Processing and Handling Sequence Constraints

Handling taskTi,j+1 can be executed only after the processing task Oi,j is completed:(9)Ei,j,u,nO≤Si,j+1,k,mT.Handling taskTi,j can be started only after the AGVk has completed the previous handling task Tc,d and arrived at the loading point Pu of the task Ti,j:(10)Ec,d,k,m−1T+dw,uEv≤Si,j,k,mT.Only after the job arrives at the current workstation, the current processing taskOi,j can start, which can be expressed by(11)Ei,j,k,mT=Si,j,k,mT+du,wLv≤Si,j,w,nO.Each processing machine can only perform one processing task at a time. So, only after the previous processing taskOg,h is finished, the next processing task Oi,j can start, which can be expressed by(12)Eg,h,w,n−1O≤Si,j,w,nO.As said before, the UGN design problem is potentially correlated with the AGVs task scheduling problem. The mutual coupling relationship is mainly reflected in the following two aspects. On the one hand, it can be seen from constraints (10) and (11) that the shortest distances among all loading or unloading points (dw,uE and du,wL) are the important factors to determine the beginning time of all processing and handling tasks, while the shortest distance between all loading points depends on the decision variable of the traditional UGN design problem. On the other hand, only when the decision variables of the AGVs scheduling problem are known, the completion time Ck can be determined by constraints (9) to (12), so as to evaluate the quality of the designed UGN.As both the UGN design and the AGVs scheduling problem in the FMS environment are nondeterministic polynomial time- (NP-) hard problems [31, 32], the integration of these two problems will become a more complex NP-hard problem. As a high-performance multipopulation heuristic intelligent search algorithm, the collaborative evolutionary genetic algorithm (CEGA) [33] divides the system decision variables into several variable subgroups. Each variable subgroup can select appropriate encoding scheme to obtain a subpopulation. Moreover, appropriate genetic operators can be designed for each subpopulation according to its encoding characteristics. The CEGA is very suitable for solving the problem of multivariable combinatorial optimization [34, 35]. Based on the characteristics of the abovementioned mathematical model, a dual-population CEGA involving the collaborative evolution of the UGN subpopulation and the task sequence subpopulation is proposed.


## 2.4.1. Decision Variable Constraints

The decision variable is a 0-1 integer, that is,(2)∀ei,j∈Ehasbi,j∈0,1.The direction of each path segment is unique:(3)∀ei,j∈Ehasbi,j+bj,i=1.


## 2.4.2. Auxiliary Decision Variable Constraints

The auxiliary decision variable is a 0-1 integer, that is,(4)∀Xi,j,kThasXi,j,kT∈0,1.Each handling task can only be assigned to one AGV:(5)∀Ti,jhas∑k=1NGXi,j,kT=1.


## 2.4.3. The UGN Must Be Strongly Connected

Each node contains at least one outdegree (i.e., the number of edges starting from this node) and one indegree (i.e., the number of edges ending at this node), which is a necessary condition for a strongly connected UGN:(6)∀ei,j∈Ehas∑j=1NVbi,j≥1and∑j=1NVbj,i≥1.There is a route to link any pair of unloading point and loading point, so it can be written as follows:(7)∀dw,uE∈DDPND×NPhasdw,uE<∞.There is a route to link any pair of loading point and unloading point, which can be expressed as follows:(8)∀du,wL∈DPDNP×NDhasdu,wL<∞.


## 2.4.4. Processing and Handling Sequence Constraints

Handling taskTi,j+1 can be executed only after the processing task Oi,j is completed:(9)Ei,j,u,nO≤Si,j+1,k,mT.Handling taskTi,j can be started only after the AGVk has completed the previous handling task Tc,d and arrived at the loading point Pu of the task Ti,j:(10)Ec,d,k,m−1T+dw,uEv≤Si,j,k,mT.Only after the job arrives at the current workstation, the current processing taskOi,j can start, which can be expressed by(11)Ei,j,k,mT=Si,j,k,mT+du,wLv≤Si,j,w,nO.Each processing machine can only perform one processing task at a time. So, only after the previous processing taskOg,h is finished, the next processing task Oi,j can start, which can be expressed by(12)Eg,h,w,n−1O≤Si,j,w,nO.As said before, the UGN design problem is potentially correlated with the AGVs task scheduling problem. The mutual coupling relationship is mainly reflected in the following two aspects. On the one hand, it can be seen from constraints (10) and (11) that the shortest distances among all loading or unloading points (dw,uE and du,wL) are the important factors to determine the beginning time of all processing and handling tasks, while the shortest distance between all loading points depends on the decision variable of the traditional UGN design problem. On the other hand, only when the decision variables of the AGVs scheduling problem are known, the completion time Ck can be determined by constraints (9) to (12), so as to evaluate the quality of the designed UGN.As both the UGN design and the AGVs scheduling problem in the FMS environment are nondeterministic polynomial time- (NP-) hard problems [31, 32], the integration of these two problems will become a more complex NP-hard problem. As a high-performance multipopulation heuristic intelligent search algorithm, the collaborative evolutionary genetic algorithm (CEGA) [33] divides the system decision variables into several variable subgroups. Each variable subgroup can select appropriate encoding scheme to obtain a subpopulation. Moreover, appropriate genetic operators can be designed for each subpopulation according to its encoding characteristics. The CEGA is very suitable for solving the problem of multivariable combinatorial optimization [34, 35]. Based on the characteristics of the abovementioned mathematical model, a dual-population CEGA involving the collaborative evolution of the UGN subpopulation and the task sequence subpopulation is proposed.


## 3. Optimization Algorithm

Drawing upon the idea of collaborative evolution, two subpopulations are adopted to represent the UGN and the feasible task sequence, respectively. The UGN subpopulation is labelled as P1, in which each chromosome represents a strongly connected UGN. The task sequence subpopulation is labelled as P2, in which each chromosome corresponds to a feasible handling and processing task sequence. In the evolutionary process, the two subpopulations independently and concurrently evolve. Information exchange between the subpopulations occurs only during the process of fitness calculation. The algorithm mainly includes chromosome encoding, fitness calculation, subpopulations initialization, and the genetic evolutionary operations. The detailed methods are listed as follows.


### 3.1. Chromosome Representation and Encoding

#### 3.1.1. Encoding of the UGN

To reduce the complexity of the problem, the guide-path network is preprocessed before encoding. The node with only two path segments connected has special significance. Taking the path network shown in Figure1, for example, edge (1, 2) should have the same direction as edge (2, 3), in order to make node 2 satisfy the constraint shown in formula (6). Therefore, in the design process, edges (24, 1), (1, 2), (2, 3), (3, 4), (4, 5), and (5, 6) can be merged into one combined edge (24, 6). According to this preprocessing principle, the guide-path network shown in Figure 1 has nine combined edges. All combined edges and serial numbers are as shown in Table 1. The UGN is encoded with a binary chromosome code B=bNB…b2b1. Each bit in the code corresponds to the direction of a combined edge. The chromosome code length NB represents the number of combined edges after the preprocessing.Table 1
The combined edges after preprocessing.
Edge no.
Combined edge
Edge no.
Combined edge
Edge no.
Combined edge
1
(24, 6)
4
(12, 18)
7
(24, 6)
2
(6, 9)
5
(18, 21)
8
(9, 21)
3
(9, 12)
6
(21, 24)
9
(18, 12)


#### 3.1.2. Encoding of the Task Sequence

As shown in Figure2, a corresponding handling task occurs before each processing task. Therefore, the task sequence is coded based on the processing task sequence. Each gene in the task sequence chromosome denotes a processing task, which is expressed by the job type number. The length of code is equal to the total number of processing tasks of all jobs put together. For instance, when there are three jobs need to be processed and each job requires three processing tasks. If a feasible processing task sequence is O1,1O1,2O3,1O2,1O3,2O2,2O3,3O1,3O2,3, then the corresponding chromosome code is 113232312.


### 3.2. Fitness Calculation

Since the individual in each subpopulation represents only partial optimization problem, it cannot be evaluated independently. Therefore, if an individual in a subpopulation need to be evaluated, it has to combine with an individual in the other subpopulation to form a complete chromosome. The fitness calculation method for a complete chromosome is described as follows.A complete chromosome is composed of two parts. Take the complete chromosome of111111100413421322123414132431234 as an example. The first half is the UGN code. Referring to Table 1, the corresponding UGN is constructed, as shown in Figure 3. And the shortest logistic distance between all the loading and unloading points can be obtained by using the Floyd algorithm [36], as shown in Tables 2 and 3. If the AGV travelling speed is given, the logistics transportation times between all the loading and unloading points can be calculated. Therefore, the UGN determines the logistic time between workstations.Figure 3
The UGN determined by the UGN code111111100.Table 2
The shortest distances among all loading and unloading points.
From
To
D
1
D
2
D
3
D
4
D
5
D
6
D
7
D
8
D
9
P
0
30
60
90
120
210
180
150
190
160
P
1
240
20
50
80
170
140
110
150
120
P
2
210
170
20
50
140
110
80
120
90
P
3
180
140
110
20
110
80
50
90
60
P
4
220
180
150
180
150
120
90
60
30
P
5
60
90
120
150
240
210
180
220
190
P
6
90
50
80
110
20
170
140
180
150
P
7
120
80
50
80
50
20
110
150
120
P
8
150
110
80
110
80
50
20
180
150Table 3
The shortest distances among all unloading and loading points.
From
To
P
0
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
D
1
220
10
40
70
100
190
160
130
170
D
2
190
230
10
40
70
160
130
100
140
D
3
160
200
160
10
40
130
100
70
110
D
4
200
240
200
170
10
170
140
110
80
D
5
40
80
110
140
170
10
230
200
240
D
6
70
110
70
100
130
40
10
160
200
D
7
100
140
100
70
100
70
40
10
170
D
8
130
170
130
100
130
100
70
40
10
D
9
160
200
160
130
160
130
100
70
40The last half part of the complete chromosome is the task sequence code. First, the task sequence code is converted to a processing task sequence. Second, according to the fitness calculation flow shown in Figure4, the machine tool and the AGV are scheduled according to the task sequence to calculate the fitness. Assuming that the technological route information of the job set is provided, as shown in Table 4, the number of AGVs in the system is 4, the AGV speed is 1 m/s. The Gantt chart obtained by the fitness calculation flow is shown in Figure 5, and the makespan is 1,260 seconds.Figure 4
Flow chart for fitness calculation.Figure 5
Gantt chart of the example.


### 3.3. Subpopulation Initialization

The methods of the initial subpopulation generation for the two subpopulations are discussed as follows.


#### 3.3.1. UGN Subpopulation

The size of the UGN subpopulation isNP1. The procedure for generating the initial UGN subpopulation is as follows. First, generate a random UGN chromosome code and assign each bit of the code a random value of 0 or 1. Then, decode this code and check whether the corresponding UGN is strongly connected; if yes, keep the code; otherwise, generate a new code. Repeat the above steps until NP1 feasible codes are obtained. These feasible codes constitute the initial UGN subpopulation GP10.


#### 3.3.2. Task Sequence Subpopulation

The size of the task sequence subpopulation isNP2. NP2 distinct chromosome individuals are generated randomly, and these individuals constitute the initial task sequence subpopulation GP20.


### 3.4. Evolutionary Operations for the UGN Subpopulation

The evolutionary algorithm flow for the UGN subpopulation is shown in Figure6. The key steps include selection, crossover, mutation, individual evaluation, neighbourhood search, and niche elimination operations. The specific operations are described as follows.Figure 6
Collaborative evolutionary algorithm for the UGN subpopulation.


#### 3.4.1. UGN Selection

Firstly, all individuals in the parent subpopulationGP1i are sorted from large to small according to their fitness. Then, two different individuals are selected to enter the crossover operation by using the roulette selection method. The probability of an individual being selected is proportional to its fitness.


#### 3.4.2. UGN Crossover

This operator is implemented using the double-point crossover method. A crossover operation example is shown in Figure7. Firstly, two crossover positions are randomly generated. Then, the genes between the two positions of the parent individual 1 are replaced by the genes at the corresponding positions of the parent individual 2. The changed parent individual 1 becomes a new child individual.Figure 7
Example of UGN crossover operation.


#### 3.4.3. UGN Mutation Operation

The two-point mutation is employed, and a mutation operation example is shown in Figure8. Firstly, two mutation positions are randomly generated. Then, the genes at the two positions are reversed. Finally, the strongly connectivity of the UGN that corresponds to the code is verified. If the UGN is strongly connected, evaluate the individual; otherwise, repeat the steps of selection, crossover, and mutation operations again.Figure 8
Example of UGN mutation operation.


#### 3.4.4. UGN Individual Evaluation

Since the UGN individual represents only partial optimization problem, it cannot be evaluated directly. Therefore, in order to evaluate an UGN individual, several individuals are randomly selected from the task sequence subpopulation by using the roulette method. Multiple complete chromosomes are formed by combining these task sequence individuals with the UGN chromosome code. The fitness of each complete chromosome is separately calculated, and the greatest fitness is selected as the individual fitness for the UGN chromosome. To improve the convergence speed of the algorithm, the complete chromosome with the highest fitness will be used by the neighbourhood search operation.


#### 3.4.5. Neighborhood Search

As already mentioned, a complete chromosome is composed of the UGN code and the task sequence code. A neighbourhood solution will be obtained by reversing a certain bit of the UGN code, while other bits are unchanged. For an original complete chromosome with a UGN code length ofNB, there are NB neighbourhood solutions. First, the strong connectivity of the UGN that corresponds to each neighbourhood solution is verified. If the UGN is strongly connected, calculate its fitness value; otherwise, set the fitness value to 0. Then, find the neighbourhood solution with the highest fitness. If this neighbourhood solution is better than the original individual, use it to replace the original one.


#### 3.4.6. Niche Technique and Elitism Strategy

To measure the genetic differences between two individuals, the Hamming distance between two individual chromosomes is defined:(13)HBi,Bj=∑k=1NBbki−bkj.In the formula,bki is the value of the k−th position in the UGN individual code Bi.To avoid the early maturity in the evolution process of the subpopulation, it is necessary to maintain genetic diversity among the individuals in the subpopulation. Firstly, theNP1 offspring individuals are merged with all NP1 parent individuals to obtain 2NP1 individuals as the candidate subpopulation. Then, calculate the Hamming distance HBi,Bj between any two chromosomes. If the calculated HBi,Bj value is smaller than Hmin (which means they are similar chromosomes), multiply the fitness of the poor individual by an elimination factor η<1. Finally, these 2NP1 individuals in the candidate subpopulation are sorted according to the adjusted fitness, and the optimal NP1 individuals are selected to the next generation.


### 3.5. Evolutionary Operations for the Task Sequence Subpopulation

The flowchart of the evolutionary algorithm for the task sequence subpopulation is shown in Figure9. The key steps include the selection, crossover, mutation, and individual evaluation operations. The details are provided as follows.Figure 9
Collaborative evolutionary algorithm for the task sequence subpopulation.


#### 3.5.1. Task Sequence Selection

Using the roulette selection method, two different individuals fromGP2i are selected to enter the crossover operation step.


#### 3.5.2. Task Sequence Crossover

This operator is implemented by two-point crossover. An example of crossover operation is shown in Figure10. Assuming that the two parent individuals are Parent1 and Parent2, the crossover operation is described as follows:(i)
Step 1: randomly select two crossover positions Pos1 and Pos2(ii)
Step 2: translate the parent individual code into the processing task sequence(iii)
Step 3: rearrange the processing tasks of Parent1 between the two crossover positions according to their order in Parent2(iv)
Step 4: copy the rearranged Parent1 to the child individual(v)
Step 5: convert the child processing task sequence to the task sequence code.Figure 10
Example of task sequence crossover operation.


#### 3.5.3. Task Sequence Mutation

An example of the task sequence mutation operation is shown in Figure11. Randomly select two crossover positions Pos1 and Pos2. If the job types are different at these two positions, then the codes of the two positions are exchanged. Whether the mutated individuals have appeared in the parent subpopulation needs to be verified. If this individual has appeared in the parent population, then the selection, crossover, and mutation operations will be repeated until a different individual is generated.Figure 11
Example of task sequence mutation operation.


#### 3.5.4. Task Sequence Evaluation

Firstly, the roulette method is used to select multiple individuals from the UGN subpopulation. Secondly, the task sequence individual is merged with these UGN individuals to form multiple complete chromosomes. Finally, calculate the fitness of each complete chromosome and select the largest fitness as the evaluated individual fitness.


#### 3.5.5. Task Sequence Elitism Strategy

NewNP2 offspring individuals are merged with NP2 parent individuals. These 2NP2 individuals constitute the candidate population. NP2 optimal individuals of the candidate population are selected to constitute a new generation task sequence subpopulation.


## 3.1. Chromosome Representation and Encoding

### 3.1.1. Encoding of the UGN

To reduce the complexity of the problem, the guide-path network is preprocessed before encoding. The node with only two path segments connected has special significance. Taking the path network shown in Figure1, for example, edge (1, 2) should have the same direction as edge (2, 3), in order to make node 2 satisfy the constraint shown in formula (6). Therefore, in the design process, edges (24, 1), (1, 2), (2, 3), (3, 4), (4, 5), and (5, 6) can be merged into one combined edge (24, 6). According to this preprocessing principle, the guide-path network shown in Figure 1 has nine combined edges. All combined edges and serial numbers are as shown in Table 1. The UGN is encoded with a binary chromosome code B=bNB…b2b1. Each bit in the code corresponds to the direction of a combined edge. The chromosome code length NB represents the number of combined edges after the preprocessing.Table 1
The combined edges after preprocessing.
Edge no.
Combined edge
Edge no.
Combined edge
Edge no.
Combined edge
1
(24, 6)
4
(12, 18)
7
(24, 6)
2
(6, 9)
5
(18, 21)
8
(9, 21)
3
(9, 12)
6
(21, 24)
9
(18, 12)


### 3.1.2. Encoding of the Task Sequence

As shown in Figure2, a corresponding handling task occurs before each processing task. Therefore, the task sequence is coded based on the processing task sequence. Each gene in the task sequence chromosome denotes a processing task, which is expressed by the job type number. The length of code is equal to the total number of processing tasks of all jobs put together. For instance, when there are three jobs need to be processed and each job requires three processing tasks. If a feasible processing task sequence is O1,1O1,2O3,1O2,1O3,2O2,2O3,3O1,3O2,3, then the corresponding chromosome code is 113232312.


## 3.1.1. Encoding of the UGN

To reduce the complexity of the problem, the guide-path network is preprocessed before encoding. The node with only two path segments connected has special significance. Taking the path network shown in Figure1, for example, edge (1, 2) should have the same direction as edge (2, 3), in order to make node 2 satisfy the constraint shown in formula (6). Therefore, in the design process, edges (24, 1), (1, 2), (2, 3), (3, 4), (4, 5), and (5, 6) can be merged into one combined edge (24, 6). According to this preprocessing principle, the guide-path network shown in Figure 1 has nine combined edges. All combined edges and serial numbers are as shown in Table 1. The UGN is encoded with a binary chromosome code B=bNB…b2b1. Each bit in the code corresponds to the direction of a combined edge. The chromosome code length NB represents the number of combined edges after the preprocessing.Table 1
The combined edges after preprocessing.
Edge no.
Combined edge
Edge no.
Combined edge
Edge no.
Combined edge
1
(24, 6)
4
(12, 18)
7
(24, 6)
2
(6, 9)
5
(18, 21)
8
(9, 21)
3
(9, 12)
6
(21, 24)
9
(18, 12)


## 3.1.2. Encoding of the Task Sequence

As shown in Figure2, a corresponding handling task occurs before each processing task. Therefore, the task sequence is coded based on the processing task sequence. Each gene in the task sequence chromosome denotes a processing task, which is expressed by the job type number. The length of code is equal to the total number of processing tasks of all jobs put together. For instance, when there are three jobs need to be processed and each job requires three processing tasks. If a feasible processing task sequence is O1,1O1,2O3,1O2,1O3,2O2,2O3,3O1,3O2,3, then the corresponding chromosome code is 113232312.


## 3.2. Fitness Calculation

Since the individual in each subpopulation represents only partial optimization problem, it cannot be evaluated independently. Therefore, if an individual in a subpopulation need to be evaluated, it has to combine with an individual in the other subpopulation to form a complete chromosome. The fitness calculation method for a complete chromosome is described as follows.A complete chromosome is composed of two parts. Take the complete chromosome of111111100413421322123414132431234 as an example. The first half is the UGN code. Referring to Table 1, the corresponding UGN is constructed, as shown in Figure 3. And the shortest logistic distance between all the loading and unloading points can be obtained by using the Floyd algorithm [36], as shown in Tables 2 and 3. If the AGV travelling speed is given, the logistics transportation times between all the loading and unloading points can be calculated. Therefore, the UGN determines the logistic time between workstations.Figure 3
The UGN determined by the UGN code111111100.Table 2
The shortest distances among all loading and unloading points.
From
To
D
1
D
2
D
3
D
4
D
5
D
6
D
7
D
8
D
9
P
0
30
60
90
120
210
180
150
190
160
P
1
240
20
50
80
170
140
110
150
120
P
2
210
170
20
50
140
110
80
120
90
P
3
180
140
110
20
110
80
50
90
60
P
4
220
180
150
180
150
120
90
60
30
P
5
60
90
120
150
240
210
180
220
190
P
6
90
50
80
110
20
170
140
180
150
P
7
120
80
50
80
50
20
110
150
120
P
8
150
110
80
110
80
50
20
180
150Table 3
The shortest distances among all unloading and loading points.
From
To
P
0
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
D
1
220
10
40
70
100
190
160
130
170
D
2
190
230
10
40
70
160
130
100
140
D
3
160
200
160
10
40
130
100
70
110
D
4
200
240
200
170
10
170
140
110
80
D
5
40
80
110
140
170
10
230
200
240
D
6
70
110
70
100
130
40
10
160
200
D
7
100
140
100
70
100
70
40
10
170
D
8
130
170
130
100
130
100
70
40
10
D
9
160
200
160
130
160
130
100
70
40The last half part of the complete chromosome is the task sequence code. First, the task sequence code is converted to a processing task sequence. Second, according to the fitness calculation flow shown in Figure4, the machine tool and the AGV are scheduled according to the task sequence to calculate the fitness. Assuming that the technological route information of the job set is provided, as shown in Table 4, the number of AGVs in the system is 4, the AGV speed is 1 m/s. The Gantt chart obtained by the fitness calculation flow is shown in Figure 5, and the makespan is 1,260 seconds.Figure 4
Flow chart for fitness calculation.Figure 5
Gantt chart of the example.


## 3.3. Subpopulation Initialization

The methods of the initial subpopulation generation for the two subpopulations are discussed as follows.


### 3.3.1. UGN Subpopulation

The size of the UGN subpopulation isNP1. The procedure for generating the initial UGN subpopulation is as follows. First, generate a random UGN chromosome code and assign each bit of the code a random value of 0 or 1. Then, decode this code and check whether the corresponding UGN is strongly connected; if yes, keep the code; otherwise, generate a new code. Repeat the above steps until NP1 feasible codes are obtained. These feasible codes constitute the initial UGN subpopulation GP10.


### 3.3.2. Task Sequence Subpopulation

The size of the task sequence subpopulation isNP2. NP2 distinct chromosome individuals are generated randomly, and these individuals constitute the initial task sequence subpopulation GP20.


## 3.3.1. UGN Subpopulation

The size of the UGN subpopulation isNP1. The procedure for generating the initial UGN subpopulation is as follows. First, generate a random UGN chromosome code and assign each bit of the code a random value of 0 or 1. Then, decode this code and check whether the corresponding UGN is strongly connected; if yes, keep the code; otherwise, generate a new code. Repeat the above steps until NP1 feasible codes are obtained. These feasible codes constitute the initial UGN subpopulation GP10.


## 3.3.2. Task Sequence Subpopulation

The size of the task sequence subpopulation isNP2. NP2 distinct chromosome individuals are generated randomly, and these individuals constitute the initial task sequence subpopulation GP20.


## 3.4. Evolutionary Operations for the UGN Subpopulation

The evolutionary algorithm flow for the UGN subpopulation is shown in Figure6. The key steps include selection, crossover, mutation, individual evaluation, neighbourhood search, and niche elimination operations. The specific operations are described as follows.Figure 6
Collaborative evolutionary algorithm for the UGN subpopulation.


### 3.4.1. UGN Selection

Firstly, all individuals in the parent subpopulationGP1i are sorted from large to small according to their fitness. Then, two different individuals are selected to enter the crossover operation by using the roulette selection method. The probability of an individual being selected is proportional to its fitness.


### 3.4.2. UGN Crossover

This operator is implemented using the double-point crossover method. A crossover operation example is shown in Figure7. Firstly, two crossover positions are randomly generated. Then, the genes between the two positions of the parent individual 1 are replaced by the genes at the corresponding positions of the parent individual 2. The changed parent individual 1 becomes a new child individual.Figure 7
Example of UGN crossover operation.


### 3.4.3. UGN Mutation Operation

The two-point mutation is employed, and a mutation operation example is shown in Figure8. Firstly, two mutation positions are randomly generated. Then, the genes at the two positions are reversed. Finally, the strongly connectivity of the UGN that corresponds to the code is verified. If the UGN is strongly connected, evaluate the individual; otherwise, repeat the steps of selection, crossover, and mutation operations again.Figure 8
Example of UGN mutation operation.


### 3.4.4. UGN Individual Evaluation

Since the UGN individual represents only partial optimization problem, it cannot be evaluated directly. Therefore, in order to evaluate an UGN individual, several individuals are randomly selected from the task sequence subpopulation by using the roulette method. Multiple complete chromosomes are formed by combining these task sequence individuals with the UGN chromosome code. The fitness of each complete chromosome is separately calculated, and the greatest fitness is selected as the individual fitness for the UGN chromosome. To improve the convergence speed of the algorithm, the complete chromosome with the highest fitness will be used by the neighbourhood search operation.


### 3.4.5. Neighborhood Search

As already mentioned, a complete chromosome is composed of the UGN code and the task sequence code. A neighbourhood solution will be obtained by reversing a certain bit of the UGN code, while other bits are unchanged. For an original complete chromosome with a UGN code length ofNB, there are NB neighbourhood solutions. First, the strong connectivity of the UGN that corresponds to each neighbourhood solution is verified. If the UGN is strongly connected, calculate its fitness value; otherwise, set the fitness value to 0. Then, find the neighbourhood solution with the highest fitness. If this neighbourhood solution is better than the original individual, use it to replace the original one.


### 3.4.6. Niche Technique and Elitism Strategy

To measure the genetic differences between two individuals, the Hamming distance between two individual chromosomes is defined:(13)HBi,Bj=∑k=1NBbki−bkj.In the formula,bki is the value of the k−th position in the UGN individual code Bi.To avoid the early maturity in the evolution process of the subpopulation, it is necessary to maintain genetic diversity among the individuals in the subpopulation. Firstly, theNP1 offspring individuals are merged with all NP1 parent individuals to obtain 2NP1 individuals as the candidate subpopulation. Then, calculate the Hamming distance HBi,Bj between any two chromosomes. If the calculated HBi,Bj value is smaller than Hmin (which means they are similar chromosomes), multiply the fitness of the poor individual by an elimination factor η<1. Finally, these 2NP1 individuals in the candidate subpopulation are sorted according to the adjusted fitness, and the optimal NP1 individuals are selected to the next generation.


## 3.4.1. UGN Selection

Firstly, all individuals in the parent subpopulationGP1i are sorted from large to small according to their fitness. Then, two different individuals are selected to enter the crossover operation by using the roulette selection method. The probability of an individual being selected is proportional to its fitness.


## 3.4.2. UGN Crossover

This operator is implemented using the double-point crossover method. A crossover operation example is shown in Figure7. Firstly, two crossover positions are randomly generated. Then, the genes between the two positions of the parent individual 1 are replaced by the genes at the corresponding positions of the parent individual 2. The changed parent individual 1 becomes a new child individual.Figure 7
Example of UGN crossover operation.


## 3.4.3. UGN Mutation Operation

The two-point mutation is employed, and a mutation operation example is shown in Figure8. Firstly, two mutation positions are randomly generated. Then, the genes at the two positions are reversed. Finally, the strongly connectivity of the UGN that corresponds to the code is verified. If the UGN is strongly connected, evaluate the individual; otherwise, repeat the steps of selection, crossover, and mutation operations again.Figure 8
Example of UGN mutation operation.


## 3.4.4. UGN Individual Evaluation

Since the UGN individual represents only partial optimization problem, it cannot be evaluated directly. Therefore, in order to evaluate an UGN individual, several individuals are randomly selected from the task sequence subpopulation by using the roulette method. Multiple complete chromosomes are formed by combining these task sequence individuals with the UGN chromosome code. The fitness of each complete chromosome is separately calculated, and the greatest fitness is selected as the individual fitness for the UGN chromosome. To improve the convergence speed of the algorithm, the complete chromosome with the highest fitness will be used by the neighbourhood search operation.


## 3.4.5. Neighborhood Search

As already mentioned, a complete chromosome is composed of the UGN code and the task sequence code. A neighbourhood solution will be obtained by reversing a certain bit of the UGN code, while other bits are unchanged. For an original complete chromosome with a UGN code length ofNB, there are NB neighbourhood solutions. First, the strong connectivity of the UGN that corresponds to each neighbourhood solution is verified. If the UGN is strongly connected, calculate its fitness value; otherwise, set the fitness value to 0. Then, find the neighbourhood solution with the highest fitness. If this neighbourhood solution is better than the original individual, use it to replace the original one.


## 3.4.6. Niche Technique and Elitism Strategy

To measure the genetic differences between two individuals, the Hamming distance between two individual chromosomes is defined:(13)HBi,Bj=∑k=1NBbki−bkj.In the formula,bki is the value of the k−th position in the UGN individual code Bi.To avoid the early maturity in the evolution process of the subpopulation, it is necessary to maintain genetic diversity among the individuals in the subpopulation. Firstly, theNP1 offspring individuals are merged with all NP1 parent individuals to obtain 2NP1 individuals as the candidate subpopulation. Then, calculate the Hamming distance HBi,Bj between any two chromosomes. If the calculated HBi,Bj value is smaller than Hmin (which means they are similar chromosomes), multiply the fitness of the poor individual by an elimination factor η<1. Finally, these 2NP1 individuals in the candidate subpopulation are sorted according to the adjusted fitness, and the optimal NP1 individuals are selected to the next generation.


## 3.5. Evolutionary Operations for the Task Sequence Subpopulation

The flowchart of the evolutionary algorithm for the task sequence subpopulation is shown in Figure9. The key steps include the selection, crossover, mutation, and individual evaluation operations. The details are provided as follows.Figure 9
Collaborative evolutionary algorithm for the task sequence subpopulation.


### 3.5.1. Task Sequence Selection

Using the roulette selection method, two different individuals fromGP2i are selected to enter the crossover operation step.


### 3.5.2. Task Sequence Crossover

This operator is implemented by two-point crossover. An example of crossover operation is shown in Figure10. Assuming that the two parent individuals are Parent1 and Parent2, the crossover operation is described as follows:(i)
Step 1: randomly select two crossover positions Pos1 and Pos2(ii)
Step 2: translate the parent individual code into the processing task sequence(iii)
Step 3: rearrange the processing tasks of Parent1 between the two crossover positions according to their order in Parent2(iv)
Step 4: copy the rearranged Parent1 to the child individual(v)
Step 5: convert the child processing task sequence to the task sequence code.Figure 10
Example of task sequence crossover operation.


### 3.5.3. Task Sequence Mutation

An example of the task sequence mutation operation is shown in Figure11. Randomly select two crossover positions Pos1 and Pos2. If the job types are different at these two positions, then the codes of the two positions are exchanged. Whether the mutated individuals have appeared in the parent subpopulation needs to be verified. If this individual has appeared in the parent population, then the selection, crossover, and mutation operations will be repeated until a different individual is generated.Figure 11
Example of task sequence mutation operation.


### 3.5.4. Task Sequence Evaluation

Firstly, the roulette method is used to select multiple individuals from the UGN subpopulation. Secondly, the task sequence individual is merged with these UGN individuals to form multiple complete chromosomes. Finally, calculate the fitness of each complete chromosome and select the largest fitness as the evaluated individual fitness.


### 3.5.5. Task Sequence Elitism Strategy

NewNP2 offspring individuals are merged with NP2 parent individuals. These 2NP2 individuals constitute the candidate population. NP2 optimal individuals of the candidate population are selected to constitute a new generation task sequence subpopulation.


## 3.5.1. Task Sequence Selection

Using the roulette selection method, two different individuals fromGP2i are selected to enter the crossover operation step.


## 3.5.2. Task Sequence Crossover

This operator is implemented by two-point crossover. An example of crossover operation is shown in Figure10. Assuming that the two parent individuals are Parent1 and Parent2, the crossover operation is described as follows:(i)
Step 1: randomly select two crossover positions Pos1 and Pos2(ii)
Step 2: translate the parent individual code into the processing task sequence(iii)
Step 3: rearrange the processing tasks of Parent1 between the two crossover positions according to their order in Parent2(iv)
Step 4: copy the rearranged Parent1 to the child individual(v)
Step 5: convert the child processing task sequence to the task sequence code.Figure 10
Example of task sequence crossover operation.


## 3.5.3. Task Sequence Mutation

An example of the task sequence mutation operation is shown in Figure11. Randomly select two crossover positions Pos1 and Pos2. If the job types are different at these two positions, then the codes of the two positions are exchanged. Whether the mutated individuals have appeared in the parent subpopulation needs to be verified. If this individual has appeared in the parent population, then the selection, crossover, and mutation operations will be repeated until a different individual is generated.Figure 11
Example of task sequence mutation operation.


## 3.5.4. Task Sequence Evaluation

Firstly, the roulette method is used to select multiple individuals from the UGN subpopulation. Secondly, the task sequence individual is merged with these UGN individuals to form multiple complete chromosomes. Finally, calculate the fitness of each complete chromosome and select the largest fitness as the evaluated individual fitness.


## 3.5.5. Task Sequence Elitism Strategy

NewNP2 offspring individuals are merged with NP2 parent individuals. These 2NP2 individuals constitute the candidate population. NP2 optimal individuals of the candidate population are selected to constitute a new generation task sequence subpopulation.


## 4. Experiments and Analysis

### 4.1. UGN Design Experiment

The layout of an example FMS is shown in Figure1. The AGV speed is set at 1 m/s. The technological information of the job set is shown in Table 4. The integrated design method proposed in this paper is compared with the traditional stepwise design methods, which can be implemented as follows: firstly, the technological route information is converted into the loaded flow matrix among all loading and unloading points (Table 5). Secondly, with the objective of minimizing both loaded and empty travel distance, the method proposed by GUAN and DAI [8] is used to design the UGN. The results obtained by the method is the optimal UGN code [111111100], which corresponds to the UGN shown in Figure 3. The best empty flow matrix among all unloading and loading points is shown in Table 6. The total loaded and empty travel distance is J=JL+JE=1920+800=2720, which is calculated by formula (1) in reference [8]. Finally, with the makespan minimization objective, the simultaneous scheduling of machines and AGVs are addressed under this UGN by taking into account the constraints of the FMS application environment, e.g., the job handling and processing sequence constraint, as shown by formula (9)–(12), and the number of AGVs constraint, as shown in formula (5). The optimal results of the traditional methods and our approach for an AGVS with different numbers of AGVs and jobs are compared in Table 7.Table 4
Technological route information of job set 1.
Job
Mixing ratio (%)
Processing stationMm and processing time (s)
O
i,1
O
i,2
O
i,3
O
i,4
O
i,5
J1
25
M
1(150)
M
3(70)
M
7(100)
M
5(50)
M
9(0)
J2
25
M
4(100)
M
8(50)
M
6(75)
M
2(150)
M
9(0)
J3
25
M
2(150)
M
5(75)
M
8(125)
M
1(60)
M
9(0)
J4
25
M
3(150)
M
6(150)
M
4(50)
M
7(50)
M
9(0)Table 5
Loaded flow matrix among all loading and unloading points.
From
To
D
1
D
2
D
3
D
4
D
5
D
6
D
7
D
8
D
9
P
0
1
1
1
1
P
1
1
1
P
2
1
1
P
3
1
1
P
4
1
1
P
5
1
1
P
6
1
1
P
7
1
1
P
8
1
1Table 6
Optimal empty flow matrix among all unloading and loading points.
From
To
P
0
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
D
1
2
D
2
2
D
3
2
D
4
2
D
5
2
D
6
2
D
7
2
D
8
2
D
9
2
2Table 7
UGN design results.
Number of jobs
Number of AGVs
Traditional stepwise design method
Integrated design method
Makespan (s)
Actual travel distanceJ (m)
The optimal UGN
Makespan (s)
Actual travel distanceJ (m)
The optimal UGN
4
2
1730
3290
[111111100]
1705
3090
[111111110]
4
3
1265
2970
[111111100]
1265
3090
[111111110]
4
4
1260
2720
[111111100]
1200
3490
[111111111]
8
2
3120
6060
[111111100]
3060
5950
[111111110]
8
3
2120
6130
[111111100]
2090
5880
[111111110]
8
4
1660
5990
[111111100]
1650
6505
[111111110]
8
5
1475
5990
[111111100]
1430
5930
[111111110]
8
6
1410
6190
[111111100]
1395
6530
[111111111]As shown in Table7, the number of AGVs and the task sequence constraints introduced by the job technological route are all neglected by the traditional design methods based on the loaded flow matrix. Since the loaded flow matrix that corresponds to the technological routes is unchanged, the optimal UGN results obtained by the traditional method remain the same in all cases. However, when taking into account the constraints of the FMS application environment and the makespan minimization objective, the integrated design model proposed in this paper can adjust the optimal UGN according to the increase number of AGVs, and it can obtain a better solution than the traditional design model. In addition, as shown in Table 7, when both the number of jobs and AGVs is 4, the traditional stepwise design method gets a solution with the makespan of 1260 and the actual travel distance of 2720. The corresponding Gantt chart is shown in Figure 5. On the other hand, the integrated design method can get a better solution with the actual travel distance of 3490. This indicates that the total loaded and empty travel distance is not directly related to the makespan. However, the traditional UGN design model can only optimize the UGN by minimizing the total loaded and empty travel distance and reducing the UGN quality of the FMS application environment inevitably. This experiment proves the superiority of the integrated design model.


### 4.2. Optimization Algorithm Experiment

In order to test the performance of the proposed CEGA algorithm, a comparative experiment of four algorithms is carried out. The four algorithms are as follows:(i)
TS: A tabu search algorithm. The neighbour definition of an UGN solution is consistent with reference [7] defined by Seo and Lee. The tabu size of the UGN solution is set as 20. The neighbours of a task sequence solution are generated by exchanging the codes of the two positions where the job types are different. The tabu size of the task sequence solution is set at 100.(ii)
CEGA: The CEGA proposed in this paper. The parameters of the CEGA are set as follows. The population size of the UGN subpopulationNP1 is set to be 20. The population size of task sequence subpopulation NP2 is set at 100. Because the CEGA adopts elitist retention strategy to ensure the stability of the algorithm, so, we set the crossover rate Pc=1 and the mutation rate Pm=1.(iii)
TGA: among the CEGA, if without incorporating the niche technology and the neighbourhood search strategy, it becomes the traditional collaborative evolution genetic algorithm (TGA).(iv)
NGA: adding the niche strategy to the TGA will transform it into the niche collaborative evolution genetic algorithm (NGA). The parameters of the TGA and the NGA are consistent with that of the CEGA.All programs are written in Plant Simulation 15.0 from Siemens Ltd. The program interface is shown in Figure12. The running environment is Windows 10 with Intel Xeon E3-1535M V6 3.1 GHz, 32 GB RAM. Each algorithm is executed ten times using the same calculation example (both the number of jobs and AGVs is 4). The optimization process obtained by each algorithm is recorded every 0.4 minutes. The average makespan and the standard deviation performance of all the algorithms are shown in Figures 13 and 14.Figure 12
The program interface of all algorithms.Figure 13
The average makespan of the different algorithms.Figure 14
The standard deviation performance of the different algorithms.As shown in Figure13, the TS algorithm has a fast convergence speed in the early stage, when the search time is less than 0.8 minutes, it can get the local optimal solution as the best solution, but due to the lack of global search ability, the optimal result of the TS mainly depends on the initial random solution, which has greater randomness. As shown in Figure 14, the standard deviation of the TS is always greater than 180, which indicates that the stability of the algorithm is poor. Different from TS algorithm, the standard deviation of the three genetic algorithms decreases with the progress of the search process. In the later stage of the search, the standard deviation of the three genetic algorithms can be reduced to less than 75, which shows that the stability of genetic algorithm is much higher than the TS. Among the three genetic algorithms, the TGA has the good initial convergence effect. As the diversity among populations cannot be guaranteed, the TGA is easily trapped into the local optimum. Although the addition of niche technology causes a relatively poor initial convergence of the NGA, it can maintain the diversity of the populations. Hence, the later search performance of the NGA is better than that of the TGA. The CEGA combines both benefits of the niche technique and the neighbourhood search strategy, which is computationally efficient with the high solution quality. As shown in Table 7, when both the number of jobs and AGVs is four, the optimal makespan is 1,200. The proposed CEGA can stably obtain the global optimal solution after 3.6 minutes during each of ten runs, exhibiting the excellent overall performance.


## 4.1. UGN Design Experiment

The layout of an example FMS is shown in Figure1. The AGV speed is set at 1 m/s. The technological information of the job set is shown in Table 4. The integrated design method proposed in this paper is compared with the traditional stepwise design methods, which can be implemented as follows: firstly, the technological route information is converted into the loaded flow matrix among all loading and unloading points (Table 5). Secondly, with the objective of minimizing both loaded and empty travel distance, the method proposed by GUAN and DAI [8] is used to design the UGN. The results obtained by the method is the optimal UGN code [111111100], which corresponds to the UGN shown in Figure 3. The best empty flow matrix among all unloading and loading points is shown in Table 6. The total loaded and empty travel distance is J=JL+JE=1920+800=2720, which is calculated by formula (1) in reference [8]. Finally, with the makespan minimization objective, the simultaneous scheduling of machines and AGVs are addressed under this UGN by taking into account the constraints of the FMS application environment, e.g., the job handling and processing sequence constraint, as shown by formula (9)–(12), and the number of AGVs constraint, as shown in formula (5). The optimal results of the traditional methods and our approach for an AGVS with different numbers of AGVs and jobs are compared in Table 7.Table 4
Technological route information of job set 1.
Job
Mixing ratio (%)
Processing stationMm and processing time (s)
O
i,1
O
i,2
O
i,3
O
i,4
O
i,5
J1
25
M
1(150)
M
3(70)
M
7(100)
M
5(50)
M
9(0)
J2
25
M
4(100)
M
8(50)
M
6(75)
M
2(150)
M
9(0)
J3
25
M
2(150)
M
5(75)
M
8(125)
M
1(60)
M
9(0)
J4
25
M
3(150)
M
6(150)
M
4(50)
M
7(50)
M
9(0)Table 5
Loaded flow matrix among all loading and unloading points.
From
To
D
1
D
2
D
3
D
4
D
5
D
6
D
7
D
8
D
9
P
0
1
1
1
1
P
1
1
1
P
2
1
1
P
3
1
1
P
4
1
1
P
5
1
1
P
6
1
1
P
7
1
1
P
8
1
1Table 6
Optimal empty flow matrix among all unloading and loading points.
From
To
P
0
P
1
P
2
P
3
P
4
P
5
P
6
P
7
P
8
D
1
2
D
2
2
D
3
2
D
4
2
D
5
2
D
6
2
D
7
2
D
8
2
D
9
2
2Table 7
UGN design results.
Number of jobs
Number of AGVs
Traditional stepwise design method
Integrated design method
Makespan (s)
Actual travel distanceJ (m)
The optimal UGN
Makespan (s)
Actual travel distanceJ (m)
The optimal UGN
4
2
1730
3290
[111111100]
1705
3090
[111111110]
4
3
1265
2970
[111111100]
1265
3090
[111111110]
4
4
1260
2720
[111111100]
1200
3490
[111111111]
8
2
3120
6060
[111111100]
3060
5950
[111111110]
8
3
2120
6130
[111111100]
2090
5880
[111111110]
8
4
1660
5990
[111111100]
1650
6505
[111111110]
8
5
1475
5990
[111111100]
1430
5930
[111111110]
8
6
1410
6190
[111111100]
1395
6530
[111111111]As shown in Table7, the number of AGVs and the task sequence constraints introduced by the job technological route are all neglected by the traditional design methods based on the loaded flow matrix. Since the loaded flow matrix that corresponds to the technological routes is unchanged, the optimal UGN results obtained by the traditional method remain the same in all cases. However, when taking into account the constraints of the FMS application environment and the makespan minimization objective, the integrated design model proposed in this paper can adjust the optimal UGN according to the increase number of AGVs, and it can obtain a better solution than the traditional design model. In addition, as shown in Table 7, when both the number of jobs and AGVs is 4, the traditional stepwise design method gets a solution with the makespan of 1260 and the actual travel distance of 2720. The corresponding Gantt chart is shown in Figure 5. On the other hand, the integrated design method can get a better solution with the actual travel distance of 3490. This indicates that the total loaded and empty travel distance is not directly related to the makespan. However, the traditional UGN design model can only optimize the UGN by minimizing the total loaded and empty travel distance and reducing the UGN quality of the FMS application environment inevitably. This experiment proves the superiority of the integrated design model.


## 4.2. Optimization Algorithm Experiment

In order to test the performance of the proposed CEGA algorithm, a comparative experiment of four algorithms is carried out. The four algorithms are as follows:(i)
TS: A tabu search algorithm. The neighbour definition of an UGN solution is consistent with reference [7] defined by Seo and Lee. The tabu size of the UGN solution is set as 20. The neighbours of a task sequence solution are generated by exchanging the codes of the two positions where the job types are different. The tabu size of the task sequence solution is set at 100.(ii)
CEGA: The CEGA proposed in this paper. The parameters of the CEGA are set as follows. The population size of the UGN subpopulationNP1 is set to be 20. The population size of task sequence subpopulation NP2 is set at 100. Because the CEGA adopts elitist retention strategy to ensure the stability of the algorithm, so, we set the crossover rate Pc=1 and the mutation rate Pm=1.(iii)
TGA: among the CEGA, if without incorporating the niche technology and the neighbourhood search strategy, it becomes the traditional collaborative evolution genetic algorithm (TGA).(iv)
NGA: adding the niche strategy to the TGA will transform it into the niche collaborative evolution genetic algorithm (NGA). The parameters of the TGA and the NGA are consistent with that of the CEGA.All programs are written in Plant Simulation 15.0 from Siemens Ltd. The program interface is shown in Figure12. The running environment is Windows 10 with Intel Xeon E3-1535M V6 3.1 GHz, 32 GB RAM. Each algorithm is executed ten times using the same calculation example (both the number of jobs and AGVs is 4). The optimization process obtained by each algorithm is recorded every 0.4 minutes. The average makespan and the standard deviation performance of all the algorithms are shown in Figures 13 and 14.Figure 12
The program interface of all algorithms.Figure 13
The average makespan of the different algorithms.Figure 14
The standard deviation performance of the different algorithms.As shown in Figure13, the TS algorithm has a fast convergence speed in the early stage, when the search time is less than 0.8 minutes, it can get the local optimal solution as the best solution, but due to the lack of global search ability, the optimal result of the TS mainly depends on the initial random solution, which has greater randomness. As shown in Figure 14, the standard deviation of the TS is always greater than 180, which indicates that the stability of the algorithm is poor. Different from TS algorithm, the standard deviation of the three genetic algorithms decreases with the progress of the search process. In the later stage of the search, the standard deviation of the three genetic algorithms can be reduced to less than 75, which shows that the stability of genetic algorithm is much higher than the TS. Among the three genetic algorithms, the TGA has the good initial convergence effect. As the diversity among populations cannot be guaranteed, the TGA is easily trapped into the local optimum. Although the addition of niche technology causes a relatively poor initial convergence of the NGA, it can maintain the diversity of the populations. Hence, the later search performance of the NGA is better than that of the TGA. The CEGA combines both benefits of the niche technique and the neighbourhood search strategy, which is computationally efficient with the high solution quality. As shown in Table 7, when both the number of jobs and AGVs is four, the optimal makespan is 1,200. The proposed CEGA can stably obtain the global optimal solution after 3.6 minutes during each of ten runs, exhibiting the excellent overall performance.


## 5. Conclusions

A mutual coupling relationship exists between the UGN design process and the AGV task scheduling problem in the FMS environments. However, the coupling factors are often neglected by using the stepwise design method in the pertinent literature, in order to reduce the complexity of the problem at the cost of the solution quality of UGN. The motivation of the paper is to bring the coupling factors into the integrated design process. On the one hand, an integrated design model of designing a UGN and scheduling AGVs simultaneously is proposed, with the objective of minimizing the makespan, in the consideration of the practical constraints. On the other hand, a dual-population collaborative evolutionary genetic algorithm (CEGA) is developed to solve the problems of designing and scheduling in a parallel way. The experimental results show the satisfactory efficiency and performances of our model and approach. It is noteworthy that the AGVs in this research work still pertain to the ordinary single-load type. However, multiple-load AGVs are becoming increasingly popular in modern factories, owing to their less traffic congestion, smaller fleet size, and increased system throughput [37, 38]. Hence, the integrated design and solution process oriented to multiple-load AGVs will attract great interest in the future research work.



---

*Source: 3961409-2020-02-07.xml*