# An Improved Shuffled Frog Leaping Algorithm for Multiload AGV Dispatching in Automated Container Terminals

Authors: Xiaoyang Ma; Yongming Bian; Fei Gao
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

Multiload AGVs, which can carry more than one container at a time, are widely used in automated container terminals. The dispatching decisions for multiload AGVs serving in automated container terminals on the target of minimum travel distance are significant in the process of container transportation in terms of improving operating efficiency. Previous work usually focused on AGVs working in a single-carrier mode, which was not only inconsistent with actual circumstances but also a waste of resources. In this paper, we establish a new mathematical model to describe multiload AGVs operating in automated container terminals, which is closer to the actual situation in real terminals. Based on this improved model, we propose a priority rule-based algorithm, termed as shuffled frog leaping algorithm with a mutant process (SFLAMUT), which can increase the diversity of the population and improve the convergence rate. Experiments were carried out based on data generated randomly according to the working properties of container terminals, and it is observed that the proposed SFLAMUT presents an effective and efficient exploration process and yields promising results in solving the proposed mathematical model.


---

## Body

## 1. Introduction

Automatic guided vehicles (AGVs), driverless and battery-powered vehicles, are applied extensively for container handling operations in container terminals. The use of multiload AGVs, which can carry up to two 20 ft containers or one 40 ft container in container terminals, is not fully investigated. In this paper, we try to investigate multiload AGV dispatching at highly automated container terminals, which can be divided into three main areas, namely, the berthing area, transport area, and yard area. Figure1 illustrates the layout of automated container terminals. In the berthing area, containers are loaded or unloaded from a vessel by several quay cranes. The yard area is divided into several blocks, where containers are loaded and unloaded by stacking cranes. The sequence of the loading and unloading process is predetermined before a vessel arrives. The function of AGVs is to transport containers between the yard and the berth within the transport area according to the predetermined sequence.Figure 1
The layout of automated container terminals.In most container terminals, AGVs are used to carry a 20 ft or 40 ft container in a single-load carrier mode, which means an AGV cannot carry another container until it has completed the previous delivery task. In this way, there is no need to consider the capacity of AGVs and the size of containers, and thus the complexity of AGV dispatching is reduced. However, when delivering a 20 ft container, the half capacity of AGVs is not fully utilized, leading to a waste of resources and imposing a great burden on the traffic, especially when there are a large number of AGVs serving in the terminals. Given the high automation level of quay cranes and stacking cranes these days, the unloading and loading process of quay cranes and stacking cranes is of high efficiency. AGV dispatching in the transport area is becoming the bottleneck in automated container terminals.Specifically, the AGV dispatching problem is composed of three parts, respectively, assigning tasks, routing AGVs, and traffic control [1]. Since algorithms for routing and traffic control are already integrated into the electronic control systems provided by AGV manufacturers, we only focus on algorithms for assigning tasks in automated container terminals. In the case of single-load AGVs, which can only carry one container at a time, the task assignment problem can be seen as the classical m : n assignment problem without considering the sequence of the pickup and delivery operations. While referring to multiload AGVs, the task assignment problem is more complicated, as we may not only take the capacity of AGVs and the size of containers (20 ft or 40 ft) into consideration but also develop a pickup-delivery rule to determine the sequence of carrying out pickup tasks and delivery tasks, which dramatically increases the space complexity and time complexity of this problem.In order to improve the operation efficiency further, we establish a new mathematical model to describe the multiload AGV dispatching problem in automated container terminals. Based on the new model, we propose an improved shuffled frog leaping algorithm, which can increase the diversity of the population and exploit the potential to find the globally optimal solution to the dispatching problem.The rest of this article is presented as follows: in Section2, we provide a comprehensive view of existing works. In Section 3, we describe the multiload AGV dispatching problem we try to address in detail and establish a mathematical model based on the dispatching process we developed. The improved shuffled frog leaping algorithm used to solve the model is presented in Section 4. Finally, the computational experimental results of different algorithms are compared in Section 5, and conclusions are made in Section 6.


## 2. Related Works

### 2.1. Research on AGV Dispatching Problems

AGV dispatching has been studied extensively in the past decades. However, most of the studies focused on single-load AGV dispatching, assuming that there is only one type of container in the terminal, which is not the case in real practice. Bish et al. [2] divided the AGV problem into three subproblems, including assignment, scheduling, and routing. Based on the subproblems Bish et al. raised, the following researchers had made a further study. Zaghdoud et al. [3] proposed a hybrid approach that combined the Dijkstra algorithm, genetic algorithm, and a heuristic method to solve the assignment of containers to AGVs problem. Angeloudis and Bell [4] proposed a flexible dispatching algorithm along with a new AGV dispatching approach for job assignments problems in container terminal settings under various conditions of uncertainty. Rashidi and Tsang [5] addressed a scheduling problem for automated guided vehicles in container terminals by designing an extended network simplex algorithm (NSA+); however, it was proved to be time-consuming when solving problems with a large number of tasks. Miyamoto and Inoue [6] formulated the dispatch and conflict-free routing problem of capacitated AGV systems (DCFRPC) as an integer program and proposed local/random search methods. A two-stage ant colony algorithm (ACA) was proposed by Saidi-Mehrabad et al. [7] to address the combinatorial problem of job shop scheduling and conflict-free routing.


### 2.2. Research on Multiload AGV Dispatching Problems

Recently, as the latest trend in transfer equipment, the multiload AGVs show enormous potential in improving the operation efficiency of automated container terminals. Grunow et al. [1] developed a flexible priority rule-based approach for both single and dual-load vehicles and analyzed the MILP model in different scenarios concerning the total lateness of the AGVs. By combining different pickup-dispatching rules, Azimi et al. [8] generated several control strategies and determined the best control strategy in terms of different criteria such as system throughput (ST), mean flow time of parts (MFTP), mean tardiness of parts (MTP), and AGV idle time (AGVIT). Fazlollahtabar et al. [9] proposed a mathematical program and an optimization method in two stages, namely, searching the solution space and finding optimal solutions, by minimizing the penalized earliness and tardiness. Chawla et al. [10] presented the modified memetic particle swarm optimization algorithm (MMPSO), which is a combination of particle swarm optimization (PSO) for global search and memetic algorithm (MA) for local search, for scheduling of multiload AGVs in the flexible manufacturing systems. Ho and Liu [11] addressed the problem of load selection and pickup-dispatching of multiple-load AGVs by proposing various load-selection rules and pickup-dispatching rules, aiming at understanding not only the performance of load-selection rules and pickup-dispatching rules in two performance criteria (throughput and tardiness) but also the effects that pickup-dispatching rules and load-selection rules have on each other’s performance. Ho and Liu [12] also focused on the pickup-dispatching problem, for which nine pickup rules are proposed and studied in different performance measures, e.g., the system’s throughput, the mean flow time of parts, and the mean tardiness of parts. Huo and Hu [13] established a mixed-integer linear programming model for multiload AGV dispatching and solved it by applying the genetic algorithm. Huo et al. [14] proposed GUROBI and the genetic algorithm to solve the single-load and multiload AGV dispatching problem and tested and verified the superiority of multiload AGV.


### 2.3. Intelligent Optimization Algorithms

In order to address the multiload AGV dispatching problem efficiently and effectively, developing an appropriate algorithm is necessary. Previous work usually concentrated on the genetic algorithm, which can fall into a local optimum easily, especially when solving complicated problems. Some research shows that intelligent optimization algorithms can address many complicated computing problems efficiently. Among them, shuffled frog leaping algorithm (SFLA) is one of the most commonly used algorithms, which can improve the searching ability theoretically. However, the iterative times will increase as the problem becomes more complicated when SFLA converges to the global optimum solution [15]. Later, Niknam et al. [16] integrated a mutant process into SFLA to increase the diversity of the frog population, which can improve the searching ability of the global optimum solution. However, improving the convergence rate of the problem with large scale and high complexity is still needed. Quantum computation has many advantages, such as diversity and parallelism. Therefore, the intelligent optimization algorithm and quantum computation are combined to generate the quantum-inspired algorithm which attracts extensive attention in the field. The quantum-inspired algorithm is mainly based on the advantages of quantum diversity, which has a relatively large searching space in a small-scale range. The authors of References [17, 18] proposed a quantum-inspired shuffled frog leaping algorithm (QSFLA) to improve the diversity further. However, it increases the randomness of the solution which leads to the slowness of convergence speed. To solve the randomness of the solution, Sun et al. [19] once proposed quantum-behaved particle swarm optimization (QPSO) based on delta potential well, the solution space of which is transformed from quantum space into real space. Subsequently, Li et al. [20] further proposed QPSO for continuous space optimization. Quantum bit’s phase was used to describe the solution updated by the quantum rotation gate, which is used as a mutant process to avoid falling into the local optimum solution and improve the convergence speed.From the study of previous works, it is learned that multiload AGV dispatching in automated container terminals is not fully investigated. Considering the research gap, we establish an improved mathematical model to describe the multiload AGV dispatching problem and propose a new algorithm to find a better solution to this model.


## 2.1. Research on AGV Dispatching Problems

AGV dispatching has been studied extensively in the past decades. However, most of the studies focused on single-load AGV dispatching, assuming that there is only one type of container in the terminal, which is not the case in real practice. Bish et al. [2] divided the AGV problem into three subproblems, including assignment, scheduling, and routing. Based on the subproblems Bish et al. raised, the following researchers had made a further study. Zaghdoud et al. [3] proposed a hybrid approach that combined the Dijkstra algorithm, genetic algorithm, and a heuristic method to solve the assignment of containers to AGVs problem. Angeloudis and Bell [4] proposed a flexible dispatching algorithm along with a new AGV dispatching approach for job assignments problems in container terminal settings under various conditions of uncertainty. Rashidi and Tsang [5] addressed a scheduling problem for automated guided vehicles in container terminals by designing an extended network simplex algorithm (NSA+); however, it was proved to be time-consuming when solving problems with a large number of tasks. Miyamoto and Inoue [6] formulated the dispatch and conflict-free routing problem of capacitated AGV systems (DCFRPC) as an integer program and proposed local/random search methods. A two-stage ant colony algorithm (ACA) was proposed by Saidi-Mehrabad et al. [7] to address the combinatorial problem of job shop scheduling and conflict-free routing.


## 2.2. Research on Multiload AGV Dispatching Problems

Recently, as the latest trend in transfer equipment, the multiload AGVs show enormous potential in improving the operation efficiency of automated container terminals. Grunow et al. [1] developed a flexible priority rule-based approach for both single and dual-load vehicles and analyzed the MILP model in different scenarios concerning the total lateness of the AGVs. By combining different pickup-dispatching rules, Azimi et al. [8] generated several control strategies and determined the best control strategy in terms of different criteria such as system throughput (ST), mean flow time of parts (MFTP), mean tardiness of parts (MTP), and AGV idle time (AGVIT). Fazlollahtabar et al. [9] proposed a mathematical program and an optimization method in two stages, namely, searching the solution space and finding optimal solutions, by minimizing the penalized earliness and tardiness. Chawla et al. [10] presented the modified memetic particle swarm optimization algorithm (MMPSO), which is a combination of particle swarm optimization (PSO) for global search and memetic algorithm (MA) for local search, for scheduling of multiload AGVs in the flexible manufacturing systems. Ho and Liu [11] addressed the problem of load selection and pickup-dispatching of multiple-load AGVs by proposing various load-selection rules and pickup-dispatching rules, aiming at understanding not only the performance of load-selection rules and pickup-dispatching rules in two performance criteria (throughput and tardiness) but also the effects that pickup-dispatching rules and load-selection rules have on each other’s performance. Ho and Liu [12] also focused on the pickup-dispatching problem, for which nine pickup rules are proposed and studied in different performance measures, e.g., the system’s throughput, the mean flow time of parts, and the mean tardiness of parts. Huo and Hu [13] established a mixed-integer linear programming model for multiload AGV dispatching and solved it by applying the genetic algorithm. Huo et al. [14] proposed GUROBI and the genetic algorithm to solve the single-load and multiload AGV dispatching problem and tested and verified the superiority of multiload AGV.


## 2.3. Intelligent Optimization Algorithms

In order to address the multiload AGV dispatching problem efficiently and effectively, developing an appropriate algorithm is necessary. Previous work usually concentrated on the genetic algorithm, which can fall into a local optimum easily, especially when solving complicated problems. Some research shows that intelligent optimization algorithms can address many complicated computing problems efficiently. Among them, shuffled frog leaping algorithm (SFLA) is one of the most commonly used algorithms, which can improve the searching ability theoretically. However, the iterative times will increase as the problem becomes more complicated when SFLA converges to the global optimum solution [15]. Later, Niknam et al. [16] integrated a mutant process into SFLA to increase the diversity of the frog population, which can improve the searching ability of the global optimum solution. However, improving the convergence rate of the problem with large scale and high complexity is still needed. Quantum computation has many advantages, such as diversity and parallelism. Therefore, the intelligent optimization algorithm and quantum computation are combined to generate the quantum-inspired algorithm which attracts extensive attention in the field. The quantum-inspired algorithm is mainly based on the advantages of quantum diversity, which has a relatively large searching space in a small-scale range. The authors of References [17, 18] proposed a quantum-inspired shuffled frog leaping algorithm (QSFLA) to improve the diversity further. However, it increases the randomness of the solution which leads to the slowness of convergence speed. To solve the randomness of the solution, Sun et al. [19] once proposed quantum-behaved particle swarm optimization (QPSO) based on delta potential well, the solution space of which is transformed from quantum space into real space. Subsequently, Li et al. [20] further proposed QPSO for continuous space optimization. Quantum bit’s phase was used to describe the solution updated by the quantum rotation gate, which is used as a mutant process to avoid falling into the local optimum solution and improve the convergence speed.From the study of previous works, it is learned that multiload AGV dispatching in automated container terminals is not fully investigated. Considering the research gap, we establish an improved mathematical model to describe the multiload AGV dispatching problem and propose a new algorithm to find a better solution to this model.


## 3. Problem Statement

In the case we consider, the multiload AGVs serving in container terminals can carry one 40 ft container or two 20 ft containers at one time, so we mainly focus on the dispatching problem of multiload AGVs which can carry up to two containers at a time and describe this kind of problem in details in this section.A new assignment of tasks to available AGVs has to be determined, every moment a dispatching request is initiated. The definition of the multiload AGVs’ availability is sparklingly important in this case. The concept of the availability of multiload AGVs has been introduced by Grunow et al. [1]. An AGV is considered unavailable if its capacity is fully utilized by the tasks assigned to it, otherwise available if an AGV can provide capacity partially or fully.Based on the availability status of vehicles Grunow et al. proposed, we investigate the dispatching process and availability status of multiload AGVs further. An AGV is fully available after it unloads a 40 ft container or the second 20 ft container or two 20 ft containers simultaneously, and an AGV is partially available after loading the first 20 ft container. On the contrary, an AGV is unavailable after loading the second 20 ft container or a 40 ft container or two 20 ft containers simultaneously. As presented in Figure2, different kinds of lines represent different kinds of status. The solid line means that the AGV is not available both during the trip to the next stop and at the next stop, while the dotted line and dashed line represent that the AGV is fully available or partially available, respectively. For an AGV with a different status, tasks at the next stop vary. A fully available AGV can carry a 40 ft container or a 20 ft container or two 20 ft containers simultaneously, and a partially available AGV is allowed to load a second 20 ft container or unload the first 20 ft container it carries. However, an unavailable AGV can only carry out the delivery task to unload the container after finishing the previous pickup task. In order to determine which type of container should be carried and whether the next task is a pickup task or a delivery task, we develop a priority rule presented in the subsequent sections.Figure 2
The dispatching process of a multiload AGV and its availability status.Based on the multiload AGV dispatching process stated above, we formulate the mathematical model of the dispatching problem as follows, together with corresponding assumptions. The formulated dispatching problem is subjected to several constraints and optimized for minimum travel distance.


### 3.1. Basic Assumptions

The following assumptions are considered in the present study:(1)
At the initial stage, all of the AGVs are empty and are in the waiting place(2)
The distance between two points is known in advance, and AGVs travel from one point to another point through the predetermined guide path(3)
The location and number of delivery points and pickup points are fixed during the whole dispatching process(4)
The number of AGVs is also fixed(5)
Quay cranes, yard cranes, and multiload AGVs are reliable(6)
There is no task preemption(7)
There is no traffic congestion(8)
After completing all the tasks, the AGVs will travel to the waiting place


### 3.2. Model Formulation

Before introducing the newly proposed mathematical model, the following notation has to be defined.Parameters include the number of tasks, the number of AGVs, the node-set of all task points forAGVk, all available routes for AGVk, the maximum capacity of AGVk, and the traveling distance between different task points, which are known in advance according to the operation plan of automated container terminals. The detailed descriptions are shown below:


#### 3.2.1. Parameters

n: number of tasks
u: number of task points (including pickup points, delivery points, starting point, and termination point)
K: number of AGVs
P: node-set of pickup points
D: node-set of delivery points
T
=
P
∪
D: set of nodes for all task points
P
k: node-set of pickup points for AGVk
D
k: node-set of delivery points for AGVk
T
k
=
P
k
∪
D
k: node-set of pickup and delivery points for AGVk
s
k: starting point of AGVk
d
k: termination point of AGVk
V
k
=
T
k
∪
s
k
,
d
k: node-set of all task points for AGVk
A
k
=
V
k
×
V
k: all available routes for AGVk
C
k: the maximum capacity of AGVk
d
i
,
j
,
k: the traveling distance between points i and j
Nodesi and n+i: the pickup and delivery point of the ith task, respectively
n
i: the number of containers transported from point i to point n+iDecision variables include the routesAGVk visits, the number of containers AGVk carries, and the type of container loaded by AGVk, which are determined according to the shortest distance rule proposed in Section 4. The detailed descriptions are presented below:


#### 3.2.2. Decision Variables

x
i
,
j
,
k: the route AGVk visits. Initially, xi,j,k=0. If AGVk moves from point i to point j (i,j∈Ak), xi,j,k=xi,j,k+1.
l
i
,
k: the number of containers AGVk carries, after completing the task at point i. Initially, li,k=0.
s
i
,
k: the type of container loaded at point i by AGVk. If it is 40 ft, si,k=1. If it is 20 ft, si,k=0.Applying the above notation, multiload AGV dispatching problem in container terminals can be formulated as an integer programming model. The objective function and constraints of the problem are presented as follows:


#### 3.2.3. Objective Function

(1)
F
=
minimize
∑
k
∈
K
∑
i
,
j
∈
A
k
d
i
,
j
,
k
x
i
,
j
,
k
.


#### 3.2.4. Constraints

(2)
∑
j
∈
P
k
∪
d
k
x
s
k
,
j
,
k
=
1
,
∀
k
∈
K
,
(3)
∑
i
∈
D
k
∪
s
k
x
i
,
d
k
,
k
=
1
,
∀
k
∈
K
,
(4)
∑
k
∈
K
∑
j
∈
T
k
∪
d
k
x
i
,
j
,
k
=
1
,
∀
i
∈
P
k
,
(5)
∑
j
∈
T
k
x
i
,
j
,
k
−
∑
j
∈
T
k
x
j
,
n
+
i
,
k
=
0
,
∀
k
∈
K
,
i
∈
P
k
,
(6)
∑
i
∈
T
k
∪
s
k
x
i
,
j
,
k
−
∑
i
∈
T
k
∪
d
k
x
j
,
i
,
k
=
0
,
∀
k
∈
K
,
j
∈
T
k
,
(7)
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
,
i
∈
P
k
:
s
i
,
k
=
1
,
(8)
∑
j
∈
P
k
x
i
,
j
,
k
+
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
:
l
i
,
k
=
1
,
i
∈
P
k
:
s
i
,
k
=
0
,
(9)
x
i
,
j
,
k
l
i
,
k
−
n
i
−
l
j
,
k
=
0
,
∀
k
∈
K
,
i
,
j
∈
A
k
,
(10)
n
i
≤
l
i
,
k
≤
C
k
,
∀
k
∈
K
,
i
∈
P
k
,
(11)
0
≤
l
n
+
i
,
k
≤
C
k
−
n
i
,
∀
k
∈
K
,
n
+
i
∈
D
k
,
(12)
l
s
k
,
k
=
0
,
∀
k
∈
K
,
(13)
l
d
k
,
k
=
0
,
∀
k
∈
K
.Equation (1) is the objective function that minimizes total travel distances. Equations (2) and (3) are the constraints on the beginning and the end of the stage, which indicates that multiload AGVs must start traveling from the starting point before performing any tasks and move to the termination point to wait for the new pickup request after completing all tasks. Equation (4) illustrates that every task can only be executed once by one AGV. Equation (5) ensures that the pickup and delivery task of a container must be carried out by one AGV. Equation (6) means that if an AGV arrives at a task point, it will exit that point. Equations (7) and (8) are constraints on the sequence of delivery tasks and pickup tasks, which indicates that an AGV must go to the associated delivery point to unload the container if it has just loaded a 40 ft container, and an AGV can visit the associated delivery point or any pickup point where 20 ft containers are waiting to be loaded after loading a 20 ft container. Equations (9)∼(13) are constraints on the capacity of an AGV, which illustrate that the number of containers carried by the AGV will never exceed its capacity and the number of containers transported by the AGV from one point to another point will never exceed its load.


## 3.1. Basic Assumptions

The following assumptions are considered in the present study:(1)
At the initial stage, all of the AGVs are empty and are in the waiting place(2)
The distance between two points is known in advance, and AGVs travel from one point to another point through the predetermined guide path(3)
The location and number of delivery points and pickup points are fixed during the whole dispatching process(4)
The number of AGVs is also fixed(5)
Quay cranes, yard cranes, and multiload AGVs are reliable(6)
There is no task preemption(7)
There is no traffic congestion(8)
After completing all the tasks, the AGVs will travel to the waiting place


## 3.2. Model Formulation

Before introducing the newly proposed mathematical model, the following notation has to be defined.Parameters include the number of tasks, the number of AGVs, the node-set of all task points forAGVk, all available routes for AGVk, the maximum capacity of AGVk, and the traveling distance between different task points, which are known in advance according to the operation plan of automated container terminals. The detailed descriptions are shown below:


### 3.2.1. Parameters

n: number of tasks
u: number of task points (including pickup points, delivery points, starting point, and termination point)
K: number of AGVs
P: node-set of pickup points
D: node-set of delivery points
T
=
P
∪
D: set of nodes for all task points
P
k: node-set of pickup points for AGVk
D
k: node-set of delivery points for AGVk
T
k
=
P
k
∪
D
k: node-set of pickup and delivery points for AGVk
s
k: starting point of AGVk
d
k: termination point of AGVk
V
k
=
T
k
∪
s
k
,
d
k: node-set of all task points for AGVk
A
k
=
V
k
×
V
k: all available routes for AGVk
C
k: the maximum capacity of AGVk
d
i
,
j
,
k: the traveling distance between points i and j
Nodesi and n+i: the pickup and delivery point of the ith task, respectively
n
i: the number of containers transported from point i to point n+iDecision variables include the routesAGVk visits, the number of containers AGVk carries, and the type of container loaded by AGVk, which are determined according to the shortest distance rule proposed in Section 4. The detailed descriptions are presented below:


### 3.2.2. Decision Variables

x
i
,
j
,
k: the route AGVk visits. Initially, xi,j,k=0. If AGVk moves from point i to point j (i,j∈Ak), xi,j,k=xi,j,k+1.
l
i
,
k: the number of containers AGVk carries, after completing the task at point i. Initially, li,k=0.
s
i
,
k: the type of container loaded at point i by AGVk. If it is 40 ft, si,k=1. If it is 20 ft, si,k=0.Applying the above notation, multiload AGV dispatching problem in container terminals can be formulated as an integer programming model. The objective function and constraints of the problem are presented as follows:


### 3.2.3. Objective Function

(1)
F
=
minimize
∑
k
∈
K
∑
i
,
j
∈
A
k
d
i
,
j
,
k
x
i
,
j
,
k
.


### 3.2.4. Constraints

(2)
∑
j
∈
P
k
∪
d
k
x
s
k
,
j
,
k
=
1
,
∀
k
∈
K
,
(3)
∑
i
∈
D
k
∪
s
k
x
i
,
d
k
,
k
=
1
,
∀
k
∈
K
,
(4)
∑
k
∈
K
∑
j
∈
T
k
∪
d
k
x
i
,
j
,
k
=
1
,
∀
i
∈
P
k
,
(5)
∑
j
∈
T
k
x
i
,
j
,
k
−
∑
j
∈
T
k
x
j
,
n
+
i
,
k
=
0
,
∀
k
∈
K
,
i
∈
P
k
,
(6)
∑
i
∈
T
k
∪
s
k
x
i
,
j
,
k
−
∑
i
∈
T
k
∪
d
k
x
j
,
i
,
k
=
0
,
∀
k
∈
K
,
j
∈
T
k
,
(7)
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
,
i
∈
P
k
:
s
i
,
k
=
1
,
(8)
∑
j
∈
P
k
x
i
,
j
,
k
+
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
:
l
i
,
k
=
1
,
i
∈
P
k
:
s
i
,
k
=
0
,
(9)
x
i
,
j
,
k
l
i
,
k
−
n
i
−
l
j
,
k
=
0
,
∀
k
∈
K
,
i
,
j
∈
A
k
,
(10)
n
i
≤
l
i
,
k
≤
C
k
,
∀
k
∈
K
,
i
∈
P
k
,
(11)
0
≤
l
n
+
i
,
k
≤
C
k
−
n
i
,
∀
k
∈
K
,
n
+
i
∈
D
k
,
(12)
l
s
k
,
k
=
0
,
∀
k
∈
K
,
(13)
l
d
k
,
k
=
0
,
∀
k
∈
K
.Equation (1) is the objective function that minimizes total travel distances. Equations (2) and (3) are the constraints on the beginning and the end of the stage, which indicates that multiload AGVs must start traveling from the starting point before performing any tasks and move to the termination point to wait for the new pickup request after completing all tasks. Equation (4) illustrates that every task can only be executed once by one AGV. Equation (5) ensures that the pickup and delivery task of a container must be carried out by one AGV. Equation (6) means that if an AGV arrives at a task point, it will exit that point. Equations (7) and (8) are constraints on the sequence of delivery tasks and pickup tasks, which indicates that an AGV must go to the associated delivery point to unload the container if it has just loaded a 40 ft container, and an AGV can visit the associated delivery point or any pickup point where 20 ft containers are waiting to be loaded after loading a 20 ft container. Equations (9)∼(13) are constraints on the capacity of an AGV, which illustrate that the number of containers carried by the AGV will never exceed its capacity and the number of containers transported by the AGV from one point to another point will never exceed its load.


## 3.2.1. Parameters

n: number of tasks
u: number of task points (including pickup points, delivery points, starting point, and termination point)
K: number of AGVs
P: node-set of pickup points
D: node-set of delivery points
T
=
P
∪
D: set of nodes for all task points
P
k: node-set of pickup points for AGVk
D
k: node-set of delivery points for AGVk
T
k
=
P
k
∪
D
k: node-set of pickup and delivery points for AGVk
s
k: starting point of AGVk
d
k: termination point of AGVk
V
k
=
T
k
∪
s
k
,
d
k: node-set of all task points for AGVk
A
k
=
V
k
×
V
k: all available routes for AGVk
C
k: the maximum capacity of AGVk
d
i
,
j
,
k: the traveling distance between points i and j
Nodesi and n+i: the pickup and delivery point of the ith task, respectively
n
i: the number of containers transported from point i to point n+iDecision variables include the routesAGVk visits, the number of containers AGVk carries, and the type of container loaded by AGVk, which are determined according to the shortest distance rule proposed in Section 4. The detailed descriptions are presented below:


## 3.2.2. Decision Variables

x
i
,
j
,
k: the route AGVk visits. Initially, xi,j,k=0. If AGVk moves from point i to point j (i,j∈Ak), xi,j,k=xi,j,k+1.
l
i
,
k: the number of containers AGVk carries, after completing the task at point i. Initially, li,k=0.
s
i
,
k: the type of container loaded at point i by AGVk. If it is 40 ft, si,k=1. If it is 20 ft, si,k=0.Applying the above notation, multiload AGV dispatching problem in container terminals can be formulated as an integer programming model. The objective function and constraints of the problem are presented as follows:


## 3.2.3. Objective Function

(1)
F
=
minimize
∑
k
∈
K
∑
i
,
j
∈
A
k
d
i
,
j
,
k
x
i
,
j
,
k
.


## 3.2.4. Constraints

(2)
∑
j
∈
P
k
∪
d
k
x
s
k
,
j
,
k
=
1
,
∀
k
∈
K
,
(3)
∑
i
∈
D
k
∪
s
k
x
i
,
d
k
,
k
=
1
,
∀
k
∈
K
,
(4)
∑
k
∈
K
∑
j
∈
T
k
∪
d
k
x
i
,
j
,
k
=
1
,
∀
i
∈
P
k
,
(5)
∑
j
∈
T
k
x
i
,
j
,
k
−
∑
j
∈
T
k
x
j
,
n
+
i
,
k
=
0
,
∀
k
∈
K
,
i
∈
P
k
,
(6)
∑
i
∈
T
k
∪
s
k
x
i
,
j
,
k
−
∑
i
∈
T
k
∪
d
k
x
j
,
i
,
k
=
0
,
∀
k
∈
K
,
j
∈
T
k
,
(7)
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
,
i
∈
P
k
:
s
i
,
k
=
1
,
(8)
∑
j
∈
P
k
x
i
,
j
,
k
+
∑
j
=
n
+
i
x
i
,
j
,
k
=
1
,
∀
k
∈
K
:
l
i
,
k
=
1
,
i
∈
P
k
:
s
i
,
k
=
0
,
(9)
x
i
,
j
,
k
l
i
,
k
−
n
i
−
l
j
,
k
=
0
,
∀
k
∈
K
,
i
,
j
∈
A
k
,
(10)
n
i
≤
l
i
,
k
≤
C
k
,
∀
k
∈
K
,
i
∈
P
k
,
(11)
0
≤
l
n
+
i
,
k
≤
C
k
−
n
i
,
∀
k
∈
K
,
n
+
i
∈
D
k
,
(12)
l
s
k
,
k
=
0
,
∀
k
∈
K
,
(13)
l
d
k
,
k
=
0
,
∀
k
∈
K
.Equation (1) is the objective function that minimizes total travel distances. Equations (2) and (3) are the constraints on the beginning and the end of the stage, which indicates that multiload AGVs must start traveling from the starting point before performing any tasks and move to the termination point to wait for the new pickup request after completing all tasks. Equation (4) illustrates that every task can only be executed once by one AGV. Equation (5) ensures that the pickup and delivery task of a container must be carried out by one AGV. Equation (6) means that if an AGV arrives at a task point, it will exit that point. Equations (7) and (8) are constraints on the sequence of delivery tasks and pickup tasks, which indicates that an AGV must go to the associated delivery point to unload the container if it has just loaded a 40 ft container, and an AGV can visit the associated delivery point or any pickup point where 20 ft containers are waiting to be loaded after loading a 20 ft container. Equations (9)∼(13) are constraints on the capacity of an AGV, which illustrate that the number of containers carried by the AGV will never exceed its capacity and the number of containers transported by the AGV from one point to another point will never exceed its load.


## 4. Shuffled Frog Leaping Algorithm with a Mutant Process (SFLAMUT)

Multiload AGVs are assigned several tasks in the very beginning, and then each AGV carries out the tasks assigned according to a predetermined AGV control process, which works as a rule giving multiload AGV guidance about task determination (whether a delivery task or a pickup task is performed). To solve the model established above, we propose a priority rule-based algorithm, called shuffled frog leaping algorithm with a mutant process (SFLAMUT), which conforms to the shortest distance rule and an improved shuffled frog leaping scheme.The shortest distance rule, under which the multiload AGV will give priority to the containers in the nearest pickup point or delivery point, has been proved to have the best throughput performance in AGV dispatching problem [12]. Therefore, we adopt the shortest distance rule as our dispatching rule and design the multiload AGV control process based on this rule. When the operation begins, every AGV performs the pickup task or delivery task by following the control process illustrated in Figure 3.Figure 3
The multiload AGV control process.SFLAMUT, based on the shuffled frog leaping scheme, is designed to address the integer programming problem as Section3.2 stated, which has fast convergence speed and powerful searching ability to find the global optimum solution.


### 4.1. Population Initialization

Assuming that the number of tasks isl, the number of AGVs is k, the frog population size is F, and the number of subgroups is m. Set the state of the ith frog as Ni=ni1,ni2,…,nil, and the fitness value of its position as fitnessi=fNi. The state of every frog in the frog population is initialized randomly. All frogs are sorted in the ascending order according to the fitness value, before being divided into m subgroups containing s frogs, where m×s=F. The grouping process is stated as follows: the first frog is assigned to the first subgroup, the second frog is assigned to the second subgroup, … , the mth frog is assigned to the mthsubgroup, the m+1th frog is assigned to the first subpopulation, … , and so on, until every frog individual in the frog population is assigned to a subgroup. The whole frog population can be expressed as follows:(14)P=n11n12⋯n1j⋯n1ln21n22⋯n2j⋯n2l⋮⋮⋮⋮⋮⋮ni1ni2⋯nij⋯nil⋮⋮⋮⋮⋮⋮nF1nF2⋯nFj⋯nFl,where nij∈1,k is the serial number of an AGV, representing a specific AGV.


### 4.2. Fitness Function Calculation Based on the Shortest Distance Rule

The fitness function is mainly used to evaluate the frog position, which reflects the extent that the frog is near the best solution. The fitness value of a frog is derived from the objective function shown in equation (1), which is calculated by following the multiload AGV control process based on the short distance rule (illustrated in Figure 3). The relationship between the fitness function and objective function is shown below. FGA represents the best solution the genetic algorithm generates:(15)fitness=FFGA.The pseudocode of the shortest distance rule and the calculation process of the objective function is presented in Pseudocode1. Following parameters of this problem is predetermined: node-set of pickup points P=p1,p2,…,pj,…,pl; node-set of delivery points D=d1,d2,…,dj,…,dl; container size S=s1,s2,…,sj,…,sl; node-set of tasks T=t1,t2,…,tj,…,tl, where tj=pj,dj,sj, which means the jth task is to transport the container of size sj from pickup point pj to delivery point dj; the traveling distance between different task points distance=d11d12⋯d1j⋯d1ud21d22⋯d2j⋯d2u⋮⋮⋮⋮⋮⋮di1di2⋯dij⋯diu⋮⋮⋮⋮⋮⋮du1du2⋯duj⋯duu, where u represents the number of different task points and dij represents the distance between the ith task point and the jth task point.Pseudocode 1: The shortest distance rule and the calculation process of the objective function.
Initialize:/∗ initialize tasks and AGVs
T = InitializeTasks();/∗ initialize the pickup point, delivery point, and size of container of tasks
AGVs = InitializeAGVs();/∗ initialize the status of AGV and assign tasks to AGVs randomly
GetRoutes:/∗ AGV route planning according to tasks assigned
While there are tasks waiting or AGV is not in the waiting place:/∗ for every AGV in AGVs
IF AGV is in the waiting place or has just completed a pickup task or a delivery task:
IF AGV is empty:
IF the number of containers waiting to be loaded != 0:
AGV visits the nearest pickup point;
routep,d,k=routep,d,k+1;/∗ update the route of AGVs;AGVk travels from current point pto pickup point d
ELSE:
AGV travels to the waiting place;
routep,d,k=routep,d,k+1;/∗ AGVk travels from current point pto waiting point d
ELSE:
IF the size of the container the AGV is carrying == 40 ft:
AGV visits the delivery point;
routep,d,k=routep,d,k+1;/∗ AGVk travels from current point pto delivery point d
ELSE:
IF AGV is unavailable:
AGV visits the nearest delivery point;
routep,d,k=routep,d,k+1; /∗ AGVk travels from current point pto delivery point d
ELSE:
IF the number of containers waiting to be loaded != 0:
IF the distance travel to the nearest pickup point < the distance travel to the delivery point:
AGV visits the nearest pickup point;
routep,d,k=routep,d,k+1; /∗ AGVk travels from current point pto pickup point d
ELSE:
AGV visits the delivery point
routep,d,k=routep,d,k+1/∗ AGVk travels from current point pto the delivery point
ELSE:
AGV visits the delivery point
routep,d,k=routep,d,k+1/∗ AGVk travels from current point pto the delivery point d
RETURN route
Calculate the objective function:
F=∑∑routep,d,kdistancep,d,k/∗ distancep,d,k represents the distance between task point pand task point d


### 4.3. Updating with a Mutant Process

Assuming thatchu1≤u≤m is each subgroup, chulw=nu1lw,nu2lw,…,nujlw,…,nullw1≤j≤l represents the worst frog in the subgroup. chulb=nu1lb,nu2lb,…,nujlb,…,nullb represents the best frog in the subgroup, and G=n1gb,n2gb,…,njgb,…nlgb is the global best frog in the frog population. The specific update strategy is expressed as follows:(16)d=randint0,Δn,ifchulbt>chulwt,randintΔn,0,ifchulbt<chulwt,(17)chulwt+1=chulwt+d,where randint is a random integer ranging from 0 to Δn, or Δn to 0, where Δn=chulbt−chulwt, and t is the iterative time.In each subgroup,chulw is updated by equation (17). During the updating process, a temporary variable newchulw=nu1new,nu2new,…,nujnew,…,nulnew is used to store the updated solution. If newchulw is better than chulw, which means that the fitness value of newchulw is lower than the fitness value of chulw, newchulw will replace chulw. Otherwise, G will take the place of chulb in equation (16), and newchulw is recalculated. After completing the above process, if chulw is still not updated, a randomly generated newchulw will replace chulw. The previous process is repeated before reaching the local maximum iterative times. After the local search, all frogs are mixed and regrouped into m subgroups, and the above process of local search is repeated until reaching the boundary limits.The above update strategy may lead to convergence to the local optimal solution. To avoid falling into the local optimum and improve the diversity of the frog population, introducing a mutant process to this algorithm is necessary. The mutant process is developed according to the fitness value after all frogs being regrouped into subgroups, which can guarantee the convergence speed and avoid falling into the local optimum.The process is expressed as follows:(18)rj=randint1,k,j=1,2,…,k,(19)randchul=r1,r2,…,rj,…,rl,(20)d=randint0,chulbt−randchult,ifchulbt>chulwt,randintchulbt−randchult,0,ifchulbt<chulwt,(21)mutchul=randchul+d.If the fitness values ofrandchul is better than chulb,chulb will be substitute by randchul; Otherwise, if mutchul is better than chulb, chulb will be substitute by mutchul; otherwise, chulb will remain the same, and chulw will be substitute by randchul.


### 4.4. Algorithm Process

In summary, the algorithm process of SFLAMUT is stated as follows:(1)
Initialize populationP, and set iteration times t=0(2)
Calculate the fitness value of every frog by equation (15), keep the best frog(3)
Sort the frogs in population according to their fitness value in the ascending order and group the frogs into several subgroups(4)
Update the worst frog in every subgroup by equations (16) and (17)(5)
Divide the updated population into new subgroups(6)
Apply the mutant process by equations (18)∼(21)(7)
Judge whether the termination criteria is met; if so, the current best frog is the optimum result yielded; otherwise, sett=t+1 and turn to Step (2)


### 4.5. Convergence Analysis

#### 4.5.1. Local Convergence Analysis

To facilitate the convergence analysis, we assume that the number of subgroupm=1, indicating that the global best frog G equals the best frog chulb in the subgroup at the beginning. Describe equations (16) and (17) as follows.Thetth iteration:(22)chulwt=Roundrchulb−chulwt−1+chulwt−1,0<r<1,Thet+1th iteration:(23)chulwt+1=Roundrchulb−chulwt+chulwt,0<r<1,where Roundx is the integer number of x through rounding.Letei be equal to the difference between the integer number of rchulb−chulwi−1 through rounding and rchulb−chulwi−1, equations (24) and (25) can be derived as follows:(24)et=Roundrchulb−chulwt−1−rchulb−chulwt−1,(25)et+1=Roundrchulb−chulwt−rchulb−chulwt.Substitute equation (24) into equation (22) and equation (25) into equation (23), and let Δchult+1=chult+1−chult, then equation (26) can be derived from (equation (23) − equation (22)):(26)Δchulwt+1=1−rΔchulwt+et+1−et.Substitute equations (24) and (25) into equation (26):(27)Δchulwt+1−Δchulwt=ΔRound,where ΔRound=Roundrchulb−chulwt+Δchulwt−Roundrchulb−chulwt.Ifchulb−chulwt≥0, we can yield that Δchulwt+1≥0andΔchulwt≥0. In this case, −Δchulwt≤ΔRound≤0. If Δchulwt≠0, equation (28) can be derived:(28)Δchulwt+1Δchulwt=1+ΔRoundΔchulwt,−Δchulwt≤ΔRound<0.Letqt be equal to 1+ΔRound/Δchulwt. From equation (28), we can identify that 0<qt<1. In this case, limt⟶∞Δchulwt=0 and limt⟶∞chulwt=chulb, indicating that the result converges to the local optimal solution.Ifchulb−chulwt≤0, we can yield the same result according to the above derivation similarly.


#### 4.5.2. Global Convergence Analysis

As SFLAMUT is a kind of random search techniques, we determine whether SFLAMUT can get the global optimization solution through the convergence criteria of the stochastic algorithm proposed by Solis and Wets [21] as follows.For optimization problemA,f, we seek a point x in A which minimizes f on A. D is a random search algorithm, Xk is the solution of the kth iteration, and the solution of the next iteration is Xk+1=DXk,α, where A is the feasible solution space, f is the fitness function, α is a solution algorithm D once found.Condition H1:fDx,α≤fx, and if α∈A, fDx,α≤fα.Condition H2: for any subsetB of A with vB>0, we have that ∏k=0∞1−μkB=0, where vB is the Lebesgue measure on the set A, and μkB is the probability measure of solution at iteration k on the set B.Convergence Theory (Global Search) [21]: suppose that f is a measurable function, A is a measurable subset of Rn and Conditions H1 and H2 are satisfied. Let xkk=0∞ be a sequence generated by algorithm D. Then,(29)limk⟶∞Pxk∈Rε=1,where Rε is the set of global best solutions and Pxk∈Rε is the probability that the point xk generated by the algorithm is in Rε at step k.To verify whether SFLAMUT can get the global optimization solution or not, we just need to verify whether SFLAMUT satisfies Conditions H1 and H2. For SFLAMUT, algorithmD can be defined as follows:(30)DXbk,Xik=Xbk,fXbk≤fXik,Xik,fXbk>fXik.It is obvious that algorithmD satisfies Condition H1. If algorithm satisfies Condition H2, the union of all solutions algorithm D once found can consist of the feasible solution space, that is,(31)∪i=1FRi,k⊇A,where Ri,k is the solution algorithm D found at iteration times k and A is the feasible solution space. From equation (22), we have that(32)Ri,t=RoundrXb−Xit−1+Xit−1,0<r<1.From local convergence analysis, we have proved thatlimt⟶∞chulwt=chulb, so when t⟶∞, Ri,t⟶Xb. In this case, v∪i=1FRi,t∩A<vA, which means that the algorithm cannot ensure the global convergence if just updated through equations (16) and (17). Therefore, we introduce the mutant process (equations (18)∼(21)) to the updating process. Xit will be generated randomly through the mutant process after every iteration. In this case, if t⟶∞, we have that ∪i=1FRi,t=A, indicating that equation (31) is satisfied. In this case, for any subset B of A, we have that 0<μkB=∑i=0Fμi,kB≤1, ∏k=0∞1−μkB⟶limk⟶∞1−∑i=0Fμi,kBk=0, which means the probability that algorithm D cannot find the solution in B is zero, and therefore, Condition H2 is satisfied.In conclusion, the updating process of equations (16) and (17) can ensure that the algorithm converges to the current optimal position; however, it cannot guarantee the global convergence. When equations (16) and (17) cannot generate a better solution, equations (18)∼(21) randomly generate a solution to substitute a current solution, which can expand the sample space. In this case, as iteration times k⟶∞, the probability that SFLAMUT converges to the global optimum solution is 1, which indicates the global convergence of SFLAMUT.


## 4.1. Population Initialization

Assuming that the number of tasks isl, the number of AGVs is k, the frog population size is F, and the number of subgroups is m. Set the state of the ith frog as Ni=ni1,ni2,…,nil, and the fitness value of its position as fitnessi=fNi. The state of every frog in the frog population is initialized randomly. All frogs are sorted in the ascending order according to the fitness value, before being divided into m subgroups containing s frogs, where m×s=F. The grouping process is stated as follows: the first frog is assigned to the first subgroup, the second frog is assigned to the second subgroup, … , the mth frog is assigned to the mthsubgroup, the m+1th frog is assigned to the first subpopulation, … , and so on, until every frog individual in the frog population is assigned to a subgroup. The whole frog population can be expressed as follows:(14)P=n11n12⋯n1j⋯n1ln21n22⋯n2j⋯n2l⋮⋮⋮⋮⋮⋮ni1ni2⋯nij⋯nil⋮⋮⋮⋮⋮⋮nF1nF2⋯nFj⋯nFl,where nij∈1,k is the serial number of an AGV, representing a specific AGV.


## 4.2. Fitness Function Calculation Based on the Shortest Distance Rule

The fitness function is mainly used to evaluate the frog position, which reflects the extent that the frog is near the best solution. The fitness value of a frog is derived from the objective function shown in equation (1), which is calculated by following the multiload AGV control process based on the short distance rule (illustrated in Figure 3). The relationship between the fitness function and objective function is shown below. FGA represents the best solution the genetic algorithm generates:(15)fitness=FFGA.The pseudocode of the shortest distance rule and the calculation process of the objective function is presented in Pseudocode1. Following parameters of this problem is predetermined: node-set of pickup points P=p1,p2,…,pj,…,pl; node-set of delivery points D=d1,d2,…,dj,…,dl; container size S=s1,s2,…,sj,…,sl; node-set of tasks T=t1,t2,…,tj,…,tl, where tj=pj,dj,sj, which means the jth task is to transport the container of size sj from pickup point pj to delivery point dj; the traveling distance between different task points distance=d11d12⋯d1j⋯d1ud21d22⋯d2j⋯d2u⋮⋮⋮⋮⋮⋮di1di2⋯dij⋯diu⋮⋮⋮⋮⋮⋮du1du2⋯duj⋯duu, where u represents the number of different task points and dij represents the distance between the ith task point and the jth task point.Pseudocode 1: The shortest distance rule and the calculation process of the objective function.
Initialize:/∗ initialize tasks and AGVs
T = InitializeTasks();/∗ initialize the pickup point, delivery point, and size of container of tasks
AGVs = InitializeAGVs();/∗ initialize the status of AGV and assign tasks to AGVs randomly
GetRoutes:/∗ AGV route planning according to tasks assigned
While there are tasks waiting or AGV is not in the waiting place:/∗ for every AGV in AGVs
IF AGV is in the waiting place or has just completed a pickup task or a delivery task:
IF AGV is empty:
IF the number of containers waiting to be loaded != 0:
AGV visits the nearest pickup point;
routep,d,k=routep,d,k+1;/∗ update the route of AGVs;AGVk travels from current point pto pickup point d
ELSE:
AGV travels to the waiting place;
routep,d,k=routep,d,k+1;/∗ AGVk travels from current point pto waiting point d
ELSE:
IF the size of the container the AGV is carrying == 40 ft:
AGV visits the delivery point;
routep,d,k=routep,d,k+1;/∗ AGVk travels from current point pto delivery point d
ELSE:
IF AGV is unavailable:
AGV visits the nearest delivery point;
routep,d,k=routep,d,k+1; /∗ AGVk travels from current point pto delivery point d
ELSE:
IF the number of containers waiting to be loaded != 0:
IF the distance travel to the nearest pickup point < the distance travel to the delivery point:
AGV visits the nearest pickup point;
routep,d,k=routep,d,k+1; /∗ AGVk travels from current point pto pickup point d
ELSE:
AGV visits the delivery point
routep,d,k=routep,d,k+1/∗ AGVk travels from current point pto the delivery point
ELSE:
AGV visits the delivery point
routep,d,k=routep,d,k+1/∗ AGVk travels from current point pto the delivery point d
RETURN route
Calculate the objective function:
F=∑∑routep,d,kdistancep,d,k/∗ distancep,d,k represents the distance between task point pand task point d


## 4.3. Updating with a Mutant Process

Assuming thatchu1≤u≤m is each subgroup, chulw=nu1lw,nu2lw,…,nujlw,…,nullw1≤j≤l represents the worst frog in the subgroup. chulb=nu1lb,nu2lb,…,nujlb,…,nullb represents the best frog in the subgroup, and G=n1gb,n2gb,…,njgb,…nlgb is the global best frog in the frog population. The specific update strategy is expressed as follows:(16)d=randint0,Δn,ifchulbt>chulwt,randintΔn,0,ifchulbt<chulwt,(17)chulwt+1=chulwt+d,where randint is a random integer ranging from 0 to Δn, or Δn to 0, where Δn=chulbt−chulwt, and t is the iterative time.In each subgroup,chulw is updated by equation (17). During the updating process, a temporary variable newchulw=nu1new,nu2new,…,nujnew,…,nulnew is used to store the updated solution. If newchulw is better than chulw, which means that the fitness value of newchulw is lower than the fitness value of chulw, newchulw will replace chulw. Otherwise, G will take the place of chulb in equation (16), and newchulw is recalculated. After completing the above process, if chulw is still not updated, a randomly generated newchulw will replace chulw. The previous process is repeated before reaching the local maximum iterative times. After the local search, all frogs are mixed and regrouped into m subgroups, and the above process of local search is repeated until reaching the boundary limits.The above update strategy may lead to convergence to the local optimal solution. To avoid falling into the local optimum and improve the diversity of the frog population, introducing a mutant process to this algorithm is necessary. The mutant process is developed according to the fitness value after all frogs being regrouped into subgroups, which can guarantee the convergence speed and avoid falling into the local optimum.The process is expressed as follows:(18)rj=randint1,k,j=1,2,…,k,(19)randchul=r1,r2,…,rj,…,rl,(20)d=randint0,chulbt−randchult,ifchulbt>chulwt,randintchulbt−randchult,0,ifchulbt<chulwt,(21)mutchul=randchul+d.If the fitness values ofrandchul is better than chulb,chulb will be substitute by randchul; Otherwise, if mutchul is better than chulb, chulb will be substitute by mutchul; otherwise, chulb will remain the same, and chulw will be substitute by randchul.


## 4.4. Algorithm Process

In summary, the algorithm process of SFLAMUT is stated as follows:(1)
Initialize populationP, and set iteration times t=0(2)
Calculate the fitness value of every frog by equation (15), keep the best frog(3)
Sort the frogs in population according to their fitness value in the ascending order and group the frogs into several subgroups(4)
Update the worst frog in every subgroup by equations (16) and (17)(5)
Divide the updated population into new subgroups(6)
Apply the mutant process by equations (18)∼(21)(7)
Judge whether the termination criteria is met; if so, the current best frog is the optimum result yielded; otherwise, sett=t+1 and turn to Step (2)


## 4.5. Convergence Analysis

### 4.5.1. Local Convergence Analysis

To facilitate the convergence analysis, we assume that the number of subgroupm=1, indicating that the global best frog G equals the best frog chulb in the subgroup at the beginning. Describe equations (16) and (17) as follows.Thetth iteration:(22)chulwt=Roundrchulb−chulwt−1+chulwt−1,0<r<1,Thet+1th iteration:(23)chulwt+1=Roundrchulb−chulwt+chulwt,0<r<1,where Roundx is the integer number of x through rounding.Letei be equal to the difference between the integer number of rchulb−chulwi−1 through rounding and rchulb−chulwi−1, equations (24) and (25) can be derived as follows:(24)et=Roundrchulb−chulwt−1−rchulb−chulwt−1,(25)et+1=Roundrchulb−chulwt−rchulb−chulwt.Substitute equation (24) into equation (22) and equation (25) into equation (23), and let Δchult+1=chult+1−chult, then equation (26) can be derived from (equation (23) − equation (22)):(26)Δchulwt+1=1−rΔchulwt+et+1−et.Substitute equations (24) and (25) into equation (26):(27)Δchulwt+1−Δchulwt=ΔRound,where ΔRound=Roundrchulb−chulwt+Δchulwt−Roundrchulb−chulwt.Ifchulb−chulwt≥0, we can yield that Δchulwt+1≥0andΔchulwt≥0. In this case, −Δchulwt≤ΔRound≤0. If Δchulwt≠0, equation (28) can be derived:(28)Δchulwt+1Δchulwt=1+ΔRoundΔchulwt,−Δchulwt≤ΔRound<0.Letqt be equal to 1+ΔRound/Δchulwt. From equation (28), we can identify that 0<qt<1. In this case, limt⟶∞Δchulwt=0 and limt⟶∞chulwt=chulb, indicating that the result converges to the local optimal solution.Ifchulb−chulwt≤0, we can yield the same result according to the above derivation similarly.


### 4.5.2. Global Convergence Analysis

As SFLAMUT is a kind of random search techniques, we determine whether SFLAMUT can get the global optimization solution through the convergence criteria of the stochastic algorithm proposed by Solis and Wets [21] as follows.For optimization problemA,f, we seek a point x in A which minimizes f on A. D is a random search algorithm, Xk is the solution of the kth iteration, and the solution of the next iteration is Xk+1=DXk,α, where A is the feasible solution space, f is the fitness function, α is a solution algorithm D once found.Condition H1:fDx,α≤fx, and if α∈A, fDx,α≤fα.Condition H2: for any subsetB of A with vB>0, we have that ∏k=0∞1−μkB=0, where vB is the Lebesgue measure on the set A, and μkB is the probability measure of solution at iteration k on the set B.Convergence Theory (Global Search) [21]: suppose that f is a measurable function, A is a measurable subset of Rn and Conditions H1 and H2 are satisfied. Let xkk=0∞ be a sequence generated by algorithm D. Then,(29)limk⟶∞Pxk∈Rε=1,where Rε is the set of global best solutions and Pxk∈Rε is the probability that the point xk generated by the algorithm is in Rε at step k.To verify whether SFLAMUT can get the global optimization solution or not, we just need to verify whether SFLAMUT satisfies Conditions H1 and H2. For SFLAMUT, algorithmD can be defined as follows:(30)DXbk,Xik=Xbk,fXbk≤fXik,Xik,fXbk>fXik.It is obvious that algorithmD satisfies Condition H1. If algorithm satisfies Condition H2, the union of all solutions algorithm D once found can consist of the feasible solution space, that is,(31)∪i=1FRi,k⊇A,where Ri,k is the solution algorithm D found at iteration times k and A is the feasible solution space. From equation (22), we have that(32)Ri,t=RoundrXb−Xit−1+Xit−1,0<r<1.From local convergence analysis, we have proved thatlimt⟶∞chulwt=chulb, so when t⟶∞, Ri,t⟶Xb. In this case, v∪i=1FRi,t∩A<vA, which means that the algorithm cannot ensure the global convergence if just updated through equations (16) and (17). Therefore, we introduce the mutant process (equations (18)∼(21)) to the updating process. Xit will be generated randomly through the mutant process after every iteration. In this case, if t⟶∞, we have that ∪i=1FRi,t=A, indicating that equation (31) is satisfied. In this case, for any subset B of A, we have that 0<μkB=∑i=0Fμi,kB≤1, ∏k=0∞1−μkB⟶limk⟶∞1−∑i=0Fμi,kBk=0, which means the probability that algorithm D cannot find the solution in B is zero, and therefore, Condition H2 is satisfied.In conclusion, the updating process of equations (16) and (17) can ensure that the algorithm converges to the current optimal position; however, it cannot guarantee the global convergence. When equations (16) and (17) cannot generate a better solution, equations (18)∼(21) randomly generate a solution to substitute a current solution, which can expand the sample space. In this case, as iteration times k⟶∞, the probability that SFLAMUT converges to the global optimum solution is 1, which indicates the global convergence of SFLAMUT.


## 4.5.1. Local Convergence Analysis

To facilitate the convergence analysis, we assume that the number of subgroupm=1, indicating that the global best frog G equals the best frog chulb in the subgroup at the beginning. Describe equations (16) and (17) as follows.Thetth iteration:(22)chulwt=Roundrchulb−chulwt−1+chulwt−1,0<r<1,Thet+1th iteration:(23)chulwt+1=Roundrchulb−chulwt+chulwt,0<r<1,where Roundx is the integer number of x through rounding.Letei be equal to the difference between the integer number of rchulb−chulwi−1 through rounding and rchulb−chulwi−1, equations (24) and (25) can be derived as follows:(24)et=Roundrchulb−chulwt−1−rchulb−chulwt−1,(25)et+1=Roundrchulb−chulwt−rchulb−chulwt.Substitute equation (24) into equation (22) and equation (25) into equation (23), and let Δchult+1=chult+1−chult, then equation (26) can be derived from (equation (23) − equation (22)):(26)Δchulwt+1=1−rΔchulwt+et+1−et.Substitute equations (24) and (25) into equation (26):(27)Δchulwt+1−Δchulwt=ΔRound,where ΔRound=Roundrchulb−chulwt+Δchulwt−Roundrchulb−chulwt.Ifchulb−chulwt≥0, we can yield that Δchulwt+1≥0andΔchulwt≥0. In this case, −Δchulwt≤ΔRound≤0. If Δchulwt≠0, equation (28) can be derived:(28)Δchulwt+1Δchulwt=1+ΔRoundΔchulwt,−Δchulwt≤ΔRound<0.Letqt be equal to 1+ΔRound/Δchulwt. From equation (28), we can identify that 0<qt<1. In this case, limt⟶∞Δchulwt=0 and limt⟶∞chulwt=chulb, indicating that the result converges to the local optimal solution.Ifchulb−chulwt≤0, we can yield the same result according to the above derivation similarly.


## 4.5.2. Global Convergence Analysis

As SFLAMUT is a kind of random search techniques, we determine whether SFLAMUT can get the global optimization solution through the convergence criteria of the stochastic algorithm proposed by Solis and Wets [21] as follows.For optimization problemA,f, we seek a point x in A which minimizes f on A. D is a random search algorithm, Xk is the solution of the kth iteration, and the solution of the next iteration is Xk+1=DXk,α, where A is the feasible solution space, f is the fitness function, α is a solution algorithm D once found.Condition H1:fDx,α≤fx, and if α∈A, fDx,α≤fα.Condition H2: for any subsetB of A with vB>0, we have that ∏k=0∞1−μkB=0, where vB is the Lebesgue measure on the set A, and μkB is the probability measure of solution at iteration k on the set B.Convergence Theory (Global Search) [21]: suppose that f is a measurable function, A is a measurable subset of Rn and Conditions H1 and H2 are satisfied. Let xkk=0∞ be a sequence generated by algorithm D. Then,(29)limk⟶∞Pxk∈Rε=1,where Rε is the set of global best solutions and Pxk∈Rε is the probability that the point xk generated by the algorithm is in Rε at step k.To verify whether SFLAMUT can get the global optimization solution or not, we just need to verify whether SFLAMUT satisfies Conditions H1 and H2. For SFLAMUT, algorithmD can be defined as follows:(30)DXbk,Xik=Xbk,fXbk≤fXik,Xik,fXbk>fXik.It is obvious that algorithmD satisfies Condition H1. If algorithm satisfies Condition H2, the union of all solutions algorithm D once found can consist of the feasible solution space, that is,(31)∪i=1FRi,k⊇A,where Ri,k is the solution algorithm D found at iteration times k and A is the feasible solution space. From equation (22), we have that(32)Ri,t=RoundrXb−Xit−1+Xit−1,0<r<1.From local convergence analysis, we have proved thatlimt⟶∞chulwt=chulb, so when t⟶∞, Ri,t⟶Xb. In this case, v∪i=1FRi,t∩A<vA, which means that the algorithm cannot ensure the global convergence if just updated through equations (16) and (17). Therefore, we introduce the mutant process (equations (18)∼(21)) to the updating process. Xit will be generated randomly through the mutant process after every iteration. In this case, if t⟶∞, we have that ∪i=1FRi,t=A, indicating that equation (31) is satisfied. In this case, for any subset B of A, we have that 0<μkB=∑i=0Fμi,kB≤1, ∏k=0∞1−μkB⟶limk⟶∞1−∑i=0Fμi,kBk=0, which means the probability that algorithm D cannot find the solution in B is zero, and therefore, Condition H2 is satisfied.In conclusion, the updating process of equations (16) and (17) can ensure that the algorithm converges to the current optimal position; however, it cannot guarantee the global convergence. When equations (16) and (17) cannot generate a better solution, equations (18)∼(21) randomly generate a solution to substitute a current solution, which can expand the sample space. In this case, as iteration times k⟶∞, the probability that SFLAMUT converges to the global optimum solution is 1, which indicates the global convergence of SFLAMUT.


## 5. Experimental Results

### 5.1. Description of the Experiments

The proposed mathematical model and SFLAMUT were tested by computational experiments on hypothetical automated container terminals, in which multiload AGVs are employed. The computational experiment was performed by the Python program. We choose algorithms including genetic algorithm (GA), shuffled frog leaping algorithm (SFLA), and quantum-inspired shuffled frog leaping algorithm (QSFLA) as our benchmarks. The difference between the given algorithms is presented as follows:(1)
GA: traditional genetic algorithm with roulette wheel selection process, single-point crossover process, and a mutant process(2)
SFLA: traditional shuffled frog leaping algorithm with improved updating process suitable for solving integer programming problems(3)
QSFLA: shuffled frog leaping algorithm and quantum computation are combined to generate QSFLA, the solution space of which is transformed from quantum space into real space(4)
SFLAMUT: an improved shuffled frog leaping algorithm with a mutant process as stated in Section4


### 5.2. Parameter Settings

The parameters in the mathematical model we proposed were set as follows: The number of pickup points was set to 5, the number of delivery points to 5, and the number of multiload AGVs to 5. The parameters of different algorithms are presented in Table1. The sign “—” represents that the parameter of the algorithm does not exist.Table 1
Parameter settings of GA, SFLA, QSFLA, and SFLAMUT.
Number of tasks
Algorithm
Population size
Mutation rate
Number of subgroup
Number of internal interaction
10
GA
10
0.1
—
—
SFLA
10
—
5
2
QSFLA
10
—
5
2
SFLAMUT
10
—
5
2
20
GA
20
0.1
—
—
SFLA
20
—
10
2
QSFLA
20
—
10
2
SFLAMUT
20
—
10
2
30
GA
30
0.1
—
—
SFLA
30
—
10
3
QSFLA
30
—
10
3
SFLAMUT
30
—
10
3
40
GA
40
0.1
—
—
SFLA
40
—
20
2
QSFLA
40
—
20
2
SFLAMUT
40
—
20
2
50
GA
50
0.1
—
—
SFLA
50
—
25
2
QSFLA
50
—
25
2
SFLAMUT
50
—
25
2
60
GA
60
0.1
—
—
SFLA
60
—
30
2
QSFLA
60
—
30
2
SFLAMUT
60
—
30
2
70
GA
70
0.1
—
—
SFLA
70
—
35
2
QSFLA
70
—
35
2
SFLAMUT
70
—
35
2
80
GA
80
0.1
—
—
SFLA
80
—
40
2
QSFLA
80
—
40
2
SFLAMUT
80
—
40
2We used GA, QSFLA, SFLA, and SFLAMUT to solve the mathematical model, respectively, and evaluated the performance of the algorithms by comparing the convergence speed, optimal results, and stability at a fixed hybrid iteration number of 500.For tasks of different numbers ranging from 10 to 80, each algorithm was executed 50 times independently in order to reduce the impact of random factors. We calculated the best value, worst value, and mean value of the optimal results generated by 50 experimental runs of each algorithm. Details are shown in Table2.Table 2
The results of GA, SFLA, QSFLA, and SFLAMUT.
Number of task
Algorithm
Best value
Worst value
Mean value
Standard deviation
Running time (s)
10
GA
274
278
276
1.84
13.29
SFLA
274
274
274
0.00
48.66
QSFLA
274
274
274
0.00
65.31
SFLAMUT
274
274
274
0.00
50.85
20
GA
340
376
358
12.80
66.62
SFLA
328
348
336
6.85
256.19
QSFLA
336
352
344
5.33
352.88
SFLAMUT
328
340
332
5.03
273.24
30
GA
428
474
452
14.80
42.38
SFLA
416
440
426
7.23
179.25
QSFLA
428
452
439
6.88
248.90
SFLAMUT
406
434
425
8.85
187.57
40
GA
632
666
646
10.48
93.99
SFLA
608
636
625
9.80
352.66
QSFLA
612
658
636
14.42
493.33
SFLAMUT
608
628
620
5.85
381.65
50
GA
780
808
790
9.35
88.59
SFLA
772
786
778
5.32
335.90
QSFLA
772
794
783
7.19
471.73
SFLAMUT
760
784
774
7.15
358.49
60
GA
926
974
948
12.78
141.50
SFLA
914
950
932
11.37
542.50
QSFLA
928
960
948
9.23
758.42
SFLAMUT
910
946
927
12.62
582.16
70
GA
1138
1166
1150
10.46
153.68
SFLA
1108
1148
1126
9.91
592.01
QSFLA
1134
1164
1145
11.12
827.36
SFLAMUT
1106
1148
1126
12.54
639.29
80
GA
1192
1224
1214
9.32
205.87
SFLA
1176
1224
1197
15.70
800.00
QSFLA
1196
1228
1214
10.49
1090.99
SFLAMUT
1168
1218
1194
15.78
851.53


### 5.3. Results and Discussion

From Table2, we can figure out that when it comes to searching for a better optimum solution, intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT) perform better than the traditional heuristic algorithm (GA) in terms of the best value, worst value, and mean value in most cases. This is because GA with selection and crossover process will retain the genes of the best individuals to the next generation, leading to falling into the local optimum especially when the population size is small. However, SFLA, QSFLA, and SFLAMUT with the updating process of global information exchange can avoid falling into the local optimum to some extent. Although SFLA, QSFLA, and SFLAMUT perform better with respect to optimal solutions, they have longer running time than GA due to a more complex searching process. This limitation can be accepted in the case we consider because the task assignment process should be completed in advance, not in operation, which means there is plenty of time to execute each algorithm. Among intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT), SFLAMUT we proposed yielded the minimum best value, the minimum worst value, and the minimum mean value, indicating far better optimal results than the other three algorithms in all experiments we carried out. That means SFLAMUT has the potential to find the global optimum solution, despite a slightly longer running time. Besides, SFLAMUT has a relatively low value with respect to the standard deviation, which indicates better search accuracy and credibility.The optimization process of these four algorithms is compared in Figures4–11. As depicted in each figure, the vertical axis is the objective function, whose value is obtained from the mean value of 50 experimental runs of each algorithm, and the horizontal axis is the evolutionary generation (iteration times).Figure 4
The optimization process of 10 tasks.Figure 5
The optimization process of 20 tasks.Figure 6
The optimization process of 30 tasks.Figure 7
The optimization process of 40 tasks.Figure 8
The optimization process of 50 tasks.Figure 9
The optimization process of 60 tasks.Figure 10
The optimization process of 70 tasks.Figure 11
The optimization process of 80 tasks.As Figures4–11 show, intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT) have a faster convergence speed than the traditional heuristic algorithm (GA) in most cases. However, as the complexity of the problem increases, QSFLA and GA have almost similar performance concerning convergence speed and optimum results, which indicates QSFLA performs worse when solving complex problems. This is reasonable because QSFLA transforms the solution space from real space into quantum space, which improves the diversity but increases the randomness of the solution, leading to the slowness of convergence speed, especially when solving complicated problems. Therefore, when the iteration times are fixed, the results QSFLA yielded become worse and worse as problems become more and more complex (as shown in Figures 9–11). SFLA and SFLAMUT always perform better than QSFLA and GA because they have similar improved updating process as equations (16) and (17) show. Such an updating process maintains the advantages (avoiding falling into the local optimum and a faster convergence speed) of traditional SFLA and is suitable for solving the integer programming problem in the meantime. Compared with SFLA, SFLAMUT has the best performance among the four algorithms. We add the mutant process (equations (18)∼(21)) into the updating process of SFLAMUT, which enables SFLAMUT to randomly generate a solution compared with the local best solution, leading to more chances to find the global optimum solution when iteration times are fixed.Based on previous analysis, we can conclude that the SFLAMUT algorithm has a better global searching ability and a faster convergence speed.


## 5.1. Description of the Experiments

The proposed mathematical model and SFLAMUT were tested by computational experiments on hypothetical automated container terminals, in which multiload AGVs are employed. The computational experiment was performed by the Python program. We choose algorithms including genetic algorithm (GA), shuffled frog leaping algorithm (SFLA), and quantum-inspired shuffled frog leaping algorithm (QSFLA) as our benchmarks. The difference between the given algorithms is presented as follows:(1)
GA: traditional genetic algorithm with roulette wheel selection process, single-point crossover process, and a mutant process(2)
SFLA: traditional shuffled frog leaping algorithm with improved updating process suitable for solving integer programming problems(3)
QSFLA: shuffled frog leaping algorithm and quantum computation are combined to generate QSFLA, the solution space of which is transformed from quantum space into real space(4)
SFLAMUT: an improved shuffled frog leaping algorithm with a mutant process as stated in Section4


## 5.2. Parameter Settings

The parameters in the mathematical model we proposed were set as follows: The number of pickup points was set to 5, the number of delivery points to 5, and the number of multiload AGVs to 5. The parameters of different algorithms are presented in Table1. The sign “—” represents that the parameter of the algorithm does not exist.Table 1
Parameter settings of GA, SFLA, QSFLA, and SFLAMUT.
Number of tasks
Algorithm
Population size
Mutation rate
Number of subgroup
Number of internal interaction
10
GA
10
0.1
—
—
SFLA
10
—
5
2
QSFLA
10
—
5
2
SFLAMUT
10
—
5
2
20
GA
20
0.1
—
—
SFLA
20
—
10
2
QSFLA
20
—
10
2
SFLAMUT
20
—
10
2
30
GA
30
0.1
—
—
SFLA
30
—
10
3
QSFLA
30
—
10
3
SFLAMUT
30
—
10
3
40
GA
40
0.1
—
—
SFLA
40
—
20
2
QSFLA
40
—
20
2
SFLAMUT
40
—
20
2
50
GA
50
0.1
—
—
SFLA
50
—
25
2
QSFLA
50
—
25
2
SFLAMUT
50
—
25
2
60
GA
60
0.1
—
—
SFLA
60
—
30
2
QSFLA
60
—
30
2
SFLAMUT
60
—
30
2
70
GA
70
0.1
—
—
SFLA
70
—
35
2
QSFLA
70
—
35
2
SFLAMUT
70
—
35
2
80
GA
80
0.1
—
—
SFLA
80
—
40
2
QSFLA
80
—
40
2
SFLAMUT
80
—
40
2We used GA, QSFLA, SFLA, and SFLAMUT to solve the mathematical model, respectively, and evaluated the performance of the algorithms by comparing the convergence speed, optimal results, and stability at a fixed hybrid iteration number of 500.For tasks of different numbers ranging from 10 to 80, each algorithm was executed 50 times independently in order to reduce the impact of random factors. We calculated the best value, worst value, and mean value of the optimal results generated by 50 experimental runs of each algorithm. Details are shown in Table2.Table 2
The results of GA, SFLA, QSFLA, and SFLAMUT.
Number of task
Algorithm
Best value
Worst value
Mean value
Standard deviation
Running time (s)
10
GA
274
278
276
1.84
13.29
SFLA
274
274
274
0.00
48.66
QSFLA
274
274
274
0.00
65.31
SFLAMUT
274
274
274
0.00
50.85
20
GA
340
376
358
12.80
66.62
SFLA
328
348
336
6.85
256.19
QSFLA
336
352
344
5.33
352.88
SFLAMUT
328
340
332
5.03
273.24
30
GA
428
474
452
14.80
42.38
SFLA
416
440
426
7.23
179.25
QSFLA
428
452
439
6.88
248.90
SFLAMUT
406
434
425
8.85
187.57
40
GA
632
666
646
10.48
93.99
SFLA
608
636
625
9.80
352.66
QSFLA
612
658
636
14.42
493.33
SFLAMUT
608
628
620
5.85
381.65
50
GA
780
808
790
9.35
88.59
SFLA
772
786
778
5.32
335.90
QSFLA
772
794
783
7.19
471.73
SFLAMUT
760
784
774
7.15
358.49
60
GA
926
974
948
12.78
141.50
SFLA
914
950
932
11.37
542.50
QSFLA
928
960
948
9.23
758.42
SFLAMUT
910
946
927
12.62
582.16
70
GA
1138
1166
1150
10.46
153.68
SFLA
1108
1148
1126
9.91
592.01
QSFLA
1134
1164
1145
11.12
827.36
SFLAMUT
1106
1148
1126
12.54
639.29
80
GA
1192
1224
1214
9.32
205.87
SFLA
1176
1224
1197
15.70
800.00
QSFLA
1196
1228
1214
10.49
1090.99
SFLAMUT
1168
1218
1194
15.78
851.53


## 5.3. Results and Discussion

From Table2, we can figure out that when it comes to searching for a better optimum solution, intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT) perform better than the traditional heuristic algorithm (GA) in terms of the best value, worst value, and mean value in most cases. This is because GA with selection and crossover process will retain the genes of the best individuals to the next generation, leading to falling into the local optimum especially when the population size is small. However, SFLA, QSFLA, and SFLAMUT with the updating process of global information exchange can avoid falling into the local optimum to some extent. Although SFLA, QSFLA, and SFLAMUT perform better with respect to optimal solutions, they have longer running time than GA due to a more complex searching process. This limitation can be accepted in the case we consider because the task assignment process should be completed in advance, not in operation, which means there is plenty of time to execute each algorithm. Among intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT), SFLAMUT we proposed yielded the minimum best value, the minimum worst value, and the minimum mean value, indicating far better optimal results than the other three algorithms in all experiments we carried out. That means SFLAMUT has the potential to find the global optimum solution, despite a slightly longer running time. Besides, SFLAMUT has a relatively low value with respect to the standard deviation, which indicates better search accuracy and credibility.The optimization process of these four algorithms is compared in Figures4–11. As depicted in each figure, the vertical axis is the objective function, whose value is obtained from the mean value of 50 experimental runs of each algorithm, and the horizontal axis is the evolutionary generation (iteration times).Figure 4
The optimization process of 10 tasks.Figure 5
The optimization process of 20 tasks.Figure 6
The optimization process of 30 tasks.Figure 7
The optimization process of 40 tasks.Figure 8
The optimization process of 50 tasks.Figure 9
The optimization process of 60 tasks.Figure 10
The optimization process of 70 tasks.Figure 11
The optimization process of 80 tasks.As Figures4–11 show, intelligent optimization algorithms (SFLA, QSFLA, and SFLAMUT) have a faster convergence speed than the traditional heuristic algorithm (GA) in most cases. However, as the complexity of the problem increases, QSFLA and GA have almost similar performance concerning convergence speed and optimum results, which indicates QSFLA performs worse when solving complex problems. This is reasonable because QSFLA transforms the solution space from real space into quantum space, which improves the diversity but increases the randomness of the solution, leading to the slowness of convergence speed, especially when solving complicated problems. Therefore, when the iteration times are fixed, the results QSFLA yielded become worse and worse as problems become more and more complex (as shown in Figures 9–11). SFLA and SFLAMUT always perform better than QSFLA and GA because they have similar improved updating process as equations (16) and (17) show. Such an updating process maintains the advantages (avoiding falling into the local optimum and a faster convergence speed) of traditional SFLA and is suitable for solving the integer programming problem in the meantime. Compared with SFLA, SFLAMUT has the best performance among the four algorithms. We add the mutant process (equations (18)∼(21)) into the updating process of SFLAMUT, which enables SFLAMUT to randomly generate a solution compared with the local best solution, leading to more chances to find the global optimum solution when iteration times are fixed.Based on previous analysis, we can conclude that the SFLAMUT algorithm has a better global searching ability and a faster convergence speed.


## 6. Conclusions

In this paper, we establish an improved mathematical model for multiload AGV dispatching in automated container terminals, aiming at fully utilizing the capacity of multiload AGVs and improving its operation efficiency further. To find the global optimal solution to this model, we propose the shortest distance rule-based shuffled frog leaping algorithm with a mutant process (SFLAMUT). The experimental results of SFLAMUT outperform the other three algorithms (GA, SFLA, and QSFLA).Future research work can be extended to analyze the proposed model by considering other objective functions with respect to maximizing capacity utilization or minimizing total travel time. More in-depth research of other efficient algorithms to address the dispatching problem, such as machine learning algorithms, can be conducted based on the mathematical model proposed in this paper.



---

*Source: 1260196-2020-01-29.xml*