# An Improved Discrete PSO for Tugboat Assignment Problem under a Hybrid Scheduling Rule in Container Terminal

Authors: Su Wang; Min Zhu; Ikou Kaku; Guoyue Chen; Mingya Wang
Journal: Mathematical Problems in Engineering
 (2014)

---

## Abstract

In container terminal, tugboat plays vital role in safety of ship docking. Tugboat assignment problem under a hybrid scheduling rule (TAP-HSR) is to determine the assignment between multiple tugboats and ships and the scheduling sequence of ships to minimize the turnaround time of ships. A mixed-integer programming model and the scheduling method are described for TAP-HSR problem. Then an improved discrete PSO (IDPSO) algorithm for TAP-HSR problem is proposed to minimize the turnaround time of ships. In particular, some new redefined PSO operators and the discrete updating rules of position and velocity are developed. The experimental results show that the proposed IDPSO can get better solutions than GA and basic discrete PSO.


---

## Body

## 1. Introduction

Nowadays, more and more people have recognized the importance of world trade via container terminals. Ship docking is one important operation having an influence on the productivity of container terminal which includes two types of operations. One is the berth allocation often described as the problem in which the berthing time and the berthing position are specified to each ship [1]. The other is the tugboat assignment described as a decision problem to find the best assignment of tugboats and scheduling sequence of ships which minimizes the turnaround time of ships subject to the assignment rules. Tugboat is one kind of small ships with large engine used to move ships in and out of berth [2]. With the steadily growing size and rapidly increasing number of entry ships, safe and efficient docking operation of ships is one of the most important issues in container terminals [3]. Because container terminal has finite tugboats with different service abilities, it is very important to develop effective tugboat assignment method to reduce turnaround time of ships and maintain high productivity of container terminal.When a ship arrives at the container terminal, the ship should be assigned an available berth for unloading and loading containers. However ships cannot dock by themselves to the berths because the port lane is narrow and the port water is shallow. The specified equipment called tugboat is used to help ships dock safely. Due to the strong structure and large power, tugboat can pull large-sized ships. If a ship is so large that one tugboat cannot tug, two or more tugboats can be used together to tow the ship. It is considered that, only with an available berth and proper tugboats, a ship can dock safely and prepare for unloading or loading operation. Otherwise, it has to wait at the anchorage outside the container terminal.Several studies have been conducted for equipment assignment or scheduling problem in container terminals, such as berth assignment [4, 5], quay crane scheduling [6–8], yard crane scheduling [9, 10], truck scheduling [11], and storage space assignment [12]. However, little research work on tugboat assignment problem can be found. Mori [3] outlined tugboat development situation and tugboat business in Asian countries, especially in Japan. Liu and Wang introduced tugboat allocation simulation [13] and then Liu studied the tugboat scheduling problem and employed a hybrid evolutionary algorithm to solve this problem [14]. However, it only focused on the tugboat scheduling rules without mathematical model. Furthermore, the study did not cover the optimization of the assignment plan between tugboats and ships.Tugboat assignment is a typical kind of assignment optimization problem. The existing approaches for solving the assignment problems can be divided into two categories. The traditional methods are mathematical programming approaches using Branch and Bound [15] and Lagrangian Relaxation [16] to get the best solution efficiently, but only for small-sized problem. Besides, metaheuristic algorithms involving genetic algorithms (GA) [17–19], ant colony optimization [20, 21], simulated annealing (SA) [22], Tabu search (TS) [23, 24], and variable neighborhood search (VNS) [25] are fast and efficient algorithms to get approximate solutions with reasonable computational time for solving large scale and more difficult combination optimization problem.Recently, particle swarm optimization (PSO) is a novel evolutionary algorithm presented by Kennedy and Eberhart [26]. Due to easy implementation and fast convergence, PSO has proved to be an effective and competitive algorithm for a wide variety of optimization problems. However, most of the published studies have concentrated on the continuous optimization problems. Recently, some work has been done to the discrete optimization problem. In order to extend the application to discrete space, Kennedy and Eberhart [27] proposed a discrete binary version of PSO where a particle moved in a state space restricted to zero and one on each dimension. Yin et al. [28] embedded a hill-climbing heuristic in PSO to assign application tasks to processors such that the resource demand of each task was satisfied and the system throughput was increased. Lin et al. [29] implemented a hybrid PSO (HPSO) to solve the biobjective personnel assignment problem. The HPSO algorithm was combined with the random-key (RK) encoding scheme and individual enhancement (IE) scheme. Similar hybrid PSO algorithms are proposed by introducing operations of GAs into PSO systems by Robinson et al. [30]. Lian et al. [31] proposed some new valid PSO operators for permutation job-shop scheduling to minimize makespan. Prescilla and Immanuel Selvakumar [32] applied the modified binary particle swarm optimization algorithm to solve the real-time task assignment in heterogeneous multiprocessor.To the best of our knowledge, there is no published work for dealing with tugboat assignment using PSO. In this paper, we introduce the tugboat assignment problem under a hybrid scheduling rule (TAP-HSR) and give the mathematical model. Then, an improved discrete PSO algorithm for TAP-HSR problem is proposed to minimize the turnaround time of ships. In particular, a new method for redefining PSO operators is developed. The experimental results show that the proposed method is effective and efficient compared to GA.The rest of this paper is organized as follows. In the next section, tugboat assignment problem under a hybrid scheduling rule (TAP-HSR) and the mathematical model are described. Section3 proposes the improved discrete PSO (IDPSO) for TAP-HSR problem. Section 4 discusses the experimental results. Finally, Section 5 provides some conclusions and the future work.


## 2. Problem Formulation and Scheduling Rules

### 2.1. Problem Description

The tugboat assignment problem under a hybrid scheduling rule is an essential decision-making problem in container terminal. The tugboat assignment operation has two procedures. One is to find the assignment plan under the assignment rules. The other is to generate the scheduling sequence of ships based on the assignment plan and some scheduling rules.Container terminal assigns tugboats to ships based on some assignment rules. Firstly, each tugboat can serve at most one ship and each ship can be assigned one or more ships at any time. Secondly, the assigned number of tugboats is determined by ship length. The ship with length equal to or less than 100 meters needs one tugboat at least. Otherwise, the ship with the length more than 100 meters needs two tugboats at least. Finally, it is required to assign tugboat with proper horsepower (ps). Horsepower is a common unit to measure tugboat power. The tugboat with higher horsepower has more service capacity to tug longer ship. The assignment rules between ships and tugboats are shown in Table1.Table 1
Assignment rules between ships and tugboats.
Length of ship (m)
Required horsepower (ps) of tugboats
Required number of tugboats
Docking operation time (min)
0–100
⩾2600
⩾1
40
100–200
⩾5200
⩾2
48
200–250
⩾6400
⩾2
60
250–300
⩾6800
⩾2
75
⩾300
⩾8000
⩾2
85Assignment plan only describes the matching relationship of multiple tugboats and multiple ships. It is required to use some scheduling rules to determine a scheduling sequence of ships according to the assignment plan. This paper applies a hybrid scheduling rule combined with first-come-first-served (FCFS) rule and first-fit rule. Based on the hybrid scheduling rule, the ship with earlier arriving time and the available assigned tugboats has the higher priority of docking.The goal of TAP-HSR is to minimize the turnaround time of ships under the premise that all ships finish docking. With more and more ships arriving, it is impossible to make sure that ships can have available tugboats for docking immediately at arrival. Some ships will wait outside the terminal at the anchorage until available tugboats can work for them. Good assignment can decrease the waiting time of ships so that the container terminal can serve more ships and get more profits.


### 2.2. Model Formulation

In this paper, TAP-HSR is based on the following assumptions.(1)
The expected arriving time and the length of all ships are known.
(2)
The docking operation time of ship depends on the length of ship and is independent of tugboat.
(3)
Each ship has an available berth for unloading and loading containers.
(4)
Tugboat can work for only one ship at the same time.
(5)
The preparation time of tugboat is zero which means one tugboat can start to serve the next ship immediately after it finishes the previous ship.
(6)
All tugboats are available when the first ship starts to berth.
(7)
The operation of tugboat requires an uninterrupted period of time.This paper describes TAP-HSR problem with the following notations.m: the number of tugboats
n: the number of ships
J
j: the ship j, j
∈
{
1,2
,
3
,
…
,
n
}
h
i: the horsepower of tugboat i
p
j: the state of tugboat i (p
j
=
0 denotes tugboat i is available. Otherwise, p
j
=
1)
q
j: the state of ship j (q
j
=
1 denotes ship j finished docking. Otherwise, q
j
=
0)
o
j: the scheduling order of ship j
l
j: the length of ship j
h
i: the horsepower of tugboat i. i
∈
{
1,2
,
3
,
…
,
m
}
t
j: the operation time of ship j
I
j: the arriving time of ship j
S
j: the start docking time of ship j
T
j: the completion of docking time of ship j
H
j: the least required horsepower of ship j
R
j: the least required tugboat number of ship j
x
i
j: decision variable denotes tugboat i assigned to ship j.This paper gives the following definitions.Definition 1 (assignment matrix).
X
m
n is the decision matrix which describes the assignment between ships and tugboats. The decision variable x
i
j
∈
{
0,1
} denotes whether or not tugboat i is assigned to ship j:
(1)
X
m
n
=
x
11
x
12
⋯
x
1
n
x
21
x
22
⋯
x
2
n
⋮
⋮
⋯
⋮
x
m
1
x
m
2
⋯
x
m
n
,
x
i
j
=
1
Tugboat
i
is
assigned
to
ship
j
0
Otherwise
.Definition 2 (conflict ship).
If tugboati is assigned to both ship j and ship k and ship j is scheduled for docking before ship k, ship j is called the conflict ship of ship k. Let C
k denote the conflict ship set of ship k:
(2)
C
k
=
{
J
j
∣
x
i
j
·
x
i
k
=
1
,
o
j
<
o
k
}
.
C
k
=
⌀ represents that all of the assigned tugboats to ship k are available when ship k arrives. In that condition, the ship can dock immediately at arriving time. Otherwise, if the assigned tugboats are working for the conflict ships of ship k, ship k has to wait until all the conflict ships finish docking.LetT
S denote the start docking time of the first ship and let T
F denote the completion docking time of the last ship. The objective function of TAP-HSR problem is to minimize the turnaround time of ships described as
(3)
min
⁡
T
F
-
T
S
,
where T
S
=
0 according to assumption (
6
) and T
F is the maximum completion docking time of ships defined as
(4)
T
F
=
max
⁡
j
=
1
n
T
j
.The objective function ismin
⁡
T
F represented by the following formula:
(5)
min
⁡
max
⁡
j
=
1
n
T
j
.To find the maximum completion docking time of ships, it is required to calculate the completion docking time of each shipT
j (j
=
1,2
,
3
,
…
,
n) represented as the start docking time of ship S
j plus the operation time of ship t
j:
(6)
T
j
=
S
j
+
t
j
.In TAP-HSR problem, letJ
j denote ship j. According to Definition 2, the maximum completion time of the conflict ships of J
j is max
⁡
J
k
∈
C
j
⁡
T
k. The start docking time S
j is calculated by
(7)
S
j
=
max
⁡
⁡
{
I
j
,
max
⁡
J
k
∈
C
j
⁡
T
k
}
⁡
.Equation (7) states that if ship arrives after the time when all the conflict ships have done the docking operation, the start docking time is the arriving time. Otherwise, the start docking time of this ship is the maximum completion docking time of the conflict ships.The constraints in TAP-HSR problem are as follows:(8)
∑
i
=
1
m
x
i
j
≥
R
j
,
∑
i
=
1
m
x
i
j
h
i
≥
H
j
.Constraints in (8) ensure that the total number and horsepower of tugboats assigned to each ship should meet the assignment rules to make sure that the tugboats have enough horsepower to tug the ship.


### 2.3. The Scheduling Method

The assignment matrix only describes the assignment plan between ships and tugboats. It is required to generate the scheduling sequence of ships based on the assignment matrix and scheduling rules. The scheduling sequence is generated as in the following steps.Step 1.
Order the ships by the arriving time. Initializep
i
=
0, q
j
=
0, the number of finished ships k
=
0, and the initial scheduling order o_flag = 1.Step 2.
Check the assignment matrix whether it is a feasible solution which satisfies constraints in (8). If it is a feasible solution, go to Step 3.Step 3.
Find the conflict ships of each ship and generate the scheduling sequence based on first-fit rule. The pseudocode of generating scheduling sequence is described in Pseudocode1.Pseudocode 1
While (k < n)
Set the state of each tugboatp
i = 0
Forj = 1 to n
If (q
j = 0 and the state of each assigned tugboat p
i = 0)
o
j
=
o
_
flag
Set the state of each assigned tugboatp
i = 1
Calculate the conflict ship setc
j
Calculate the start docking times
j according to (7)
Calculate the completion docking timeT
j according to (6)
Set the state of shipj  q
j
=
1
k = k + 1
End if
Nextj
o_flag = o_flag + 1
End
Calculate the turnaround time of ships according to (4).Step 4.
Output the scheduling sequence, the start docking time and completion docking time of each ship, and the turnaround time of ships.We give one example of scheduling ships based on assignment plan. Table2 shows the tugboat allocation. Table 3 shows the arriving ships.Table 2
One example of tugboat allocation.
Tugboat number
Horsepower (ps)
Number
1
2600
1
2
3200
1
3
3400
1
4
4000
1Table 3
One example of arriving ships.
Ship number
Length (m)
Arriving time (min)
Operation time (min)
1
87
0
40
2
245
5
60
3
286
10
75
4
93
15
40
5
202
20
60One assignment matrix between tugboats and ships is as follows:(9)
X
i
=
0
1
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
0
0
1
J
1
J
2
J
3
J
4
J
5
.X
i satisfies constraints in (8) so that it is a feasible assignment. According to the scheduling method, the scheduling sequence O
=
(
J
1
,
J
3
,
J
4
,
J
2
,
J
5
) and turnaround time of ships is 135 minutes. The scheduling Gant graph is as in Figure 1.Figure 1
The scheduling Gant graph.


## 2.1. Problem Description

The tugboat assignment problem under a hybrid scheduling rule is an essential decision-making problem in container terminal. The tugboat assignment operation has two procedures. One is to find the assignment plan under the assignment rules. The other is to generate the scheduling sequence of ships based on the assignment plan and some scheduling rules.Container terminal assigns tugboats to ships based on some assignment rules. Firstly, each tugboat can serve at most one ship and each ship can be assigned one or more ships at any time. Secondly, the assigned number of tugboats is determined by ship length. The ship with length equal to or less than 100 meters needs one tugboat at least. Otherwise, the ship with the length more than 100 meters needs two tugboats at least. Finally, it is required to assign tugboat with proper horsepower (ps). Horsepower is a common unit to measure tugboat power. The tugboat with higher horsepower has more service capacity to tug longer ship. The assignment rules between ships and tugboats are shown in Table1.Table 1
Assignment rules between ships and tugboats.
Length of ship (m)
Required horsepower (ps) of tugboats
Required number of tugboats
Docking operation time (min)
0–100
⩾2600
⩾1
40
100–200
⩾5200
⩾2
48
200–250
⩾6400
⩾2
60
250–300
⩾6800
⩾2
75
⩾300
⩾8000
⩾2
85Assignment plan only describes the matching relationship of multiple tugboats and multiple ships. It is required to use some scheduling rules to determine a scheduling sequence of ships according to the assignment plan. This paper applies a hybrid scheduling rule combined with first-come-first-served (FCFS) rule and first-fit rule. Based on the hybrid scheduling rule, the ship with earlier arriving time and the available assigned tugboats has the higher priority of docking.The goal of TAP-HSR is to minimize the turnaround time of ships under the premise that all ships finish docking. With more and more ships arriving, it is impossible to make sure that ships can have available tugboats for docking immediately at arrival. Some ships will wait outside the terminal at the anchorage until available tugboats can work for them. Good assignment can decrease the waiting time of ships so that the container terminal can serve more ships and get more profits.


## 2.2. Model Formulation

In this paper, TAP-HSR is based on the following assumptions.(1)
The expected arriving time and the length of all ships are known.
(2)
The docking operation time of ship depends on the length of ship and is independent of tugboat.
(3)
Each ship has an available berth for unloading and loading containers.
(4)
Tugboat can work for only one ship at the same time.
(5)
The preparation time of tugboat is zero which means one tugboat can start to serve the next ship immediately after it finishes the previous ship.
(6)
All tugboats are available when the first ship starts to berth.
(7)
The operation of tugboat requires an uninterrupted period of time.This paper describes TAP-HSR problem with the following notations.m: the number of tugboats
n: the number of ships
J
j: the ship j, j
∈
{
1,2
,
3
,
…
,
n
}
h
i: the horsepower of tugboat i
p
j: the state of tugboat i (p
j
=
0 denotes tugboat i is available. Otherwise, p
j
=
1)
q
j: the state of ship j (q
j
=
1 denotes ship j finished docking. Otherwise, q
j
=
0)
o
j: the scheduling order of ship j
l
j: the length of ship j
h
i: the horsepower of tugboat i. i
∈
{
1,2
,
3
,
…
,
m
}
t
j: the operation time of ship j
I
j: the arriving time of ship j
S
j: the start docking time of ship j
T
j: the completion of docking time of ship j
H
j: the least required horsepower of ship j
R
j: the least required tugboat number of ship j
x
i
j: decision variable denotes tugboat i assigned to ship j.This paper gives the following definitions.Definition 1 (assignment matrix).
X
m
n is the decision matrix which describes the assignment between ships and tugboats. The decision variable x
i
j
∈
{
0,1
} denotes whether or not tugboat i is assigned to ship j:
(1)
X
m
n
=
x
11
x
12
⋯
x
1
n
x
21
x
22
⋯
x
2
n
⋮
⋮
⋯
⋮
x
m
1
x
m
2
⋯
x
m
n
,
x
i
j
=
1
Tugboat
i
is
assigned
to
ship
j
0
Otherwise
.Definition 2 (conflict ship).
If tugboati is assigned to both ship j and ship k and ship j is scheduled for docking before ship k, ship j is called the conflict ship of ship k. Let C
k denote the conflict ship set of ship k:
(2)
C
k
=
{
J
j
∣
x
i
j
·
x
i
k
=
1
,
o
j
<
o
k
}
.
C
k
=
⌀ represents that all of the assigned tugboats to ship k are available when ship k arrives. In that condition, the ship can dock immediately at arriving time. Otherwise, if the assigned tugboats are working for the conflict ships of ship k, ship k has to wait until all the conflict ships finish docking.LetT
S denote the start docking time of the first ship and let T
F denote the completion docking time of the last ship. The objective function of TAP-HSR problem is to minimize the turnaround time of ships described as
(3)
min
⁡
T
F
-
T
S
,
where T
S
=
0 according to assumption (
6
) and T
F is the maximum completion docking time of ships defined as
(4)
T
F
=
max
⁡
j
=
1
n
T
j
.The objective function ismin
⁡
T
F represented by the following formula:
(5)
min
⁡
max
⁡
j
=
1
n
T
j
.To find the maximum completion docking time of ships, it is required to calculate the completion docking time of each shipT
j (j
=
1,2
,
3
,
…
,
n) represented as the start docking time of ship S
j plus the operation time of ship t
j:
(6)
T
j
=
S
j
+
t
j
.In TAP-HSR problem, letJ
j denote ship j. According to Definition 2, the maximum completion time of the conflict ships of J
j is max
⁡
J
k
∈
C
j
⁡
T
k. The start docking time S
j is calculated by
(7)
S
j
=
max
⁡
⁡
{
I
j
,
max
⁡
J
k
∈
C
j
⁡
T
k
}
⁡
.Equation (7) states that if ship arrives after the time when all the conflict ships have done the docking operation, the start docking time is the arriving time. Otherwise, the start docking time of this ship is the maximum completion docking time of the conflict ships.The constraints in TAP-HSR problem are as follows:(8)
∑
i
=
1
m
x
i
j
≥
R
j
,
∑
i
=
1
m
x
i
j
h
i
≥
H
j
.Constraints in (8) ensure that the total number and horsepower of tugboats assigned to each ship should meet the assignment rules to make sure that the tugboats have enough horsepower to tug the ship.


## 2.3. The Scheduling Method

The assignment matrix only describes the assignment plan between ships and tugboats. It is required to generate the scheduling sequence of ships based on the assignment matrix and scheduling rules. The scheduling sequence is generated as in the following steps.Step 1.
Order the ships by the arriving time. Initializep
i
=
0, q
j
=
0, the number of finished ships k
=
0, and the initial scheduling order o_flag = 1.Step 2.
Check the assignment matrix whether it is a feasible solution which satisfies constraints in (8). If it is a feasible solution, go to Step 3.Step 3.
Find the conflict ships of each ship and generate the scheduling sequence based on first-fit rule. The pseudocode of generating scheduling sequence is described in Pseudocode1.Pseudocode 1
While (k < n)
Set the state of each tugboatp
i = 0
Forj = 1 to n
If (q
j = 0 and the state of each assigned tugboat p
i = 0)
o
j
=
o
_
flag
Set the state of each assigned tugboatp
i = 1
Calculate the conflict ship setc
j
Calculate the start docking times
j according to (7)
Calculate the completion docking timeT
j according to (6)
Set the state of shipj  q
j
=
1
k = k + 1
End if
Nextj
o_flag = o_flag + 1
End
Calculate the turnaround time of ships according to (4).Step 4.
Output the scheduling sequence, the start docking time and completion docking time of each ship, and the turnaround time of ships.We give one example of scheduling ships based on assignment plan. Table2 shows the tugboat allocation. Table 3 shows the arriving ships.Table 2
One example of tugboat allocation.
Tugboat number
Horsepower (ps)
Number
1
2600
1
2
3200
1
3
3400
1
4
4000
1Table 3
One example of arriving ships.
Ship number
Length (m)
Arriving time (min)
Operation time (min)
1
87
0
40
2
245
5
60
3
286
10
75
4
93
15
40
5
202
20
60One assignment matrix between tugboats and ships is as follows:(9)
X
i
=
0
1
0
0
0
1
1
0
0
0
1
1
1
0
0
0
1
0
0
1
J
1
J
2
J
3
J
4
J
5
.X
i satisfies constraints in (8) so that it is a feasible assignment. According to the scheduling method, the scheduling sequence O
=
(
J
1
,
J
3
,
J
4
,
J
2
,
J
5
) and turnaround time of ships is 135 minutes. The scheduling Gant graph is as in Figure 1.Figure 1
The scheduling Gant graph.


## 3. Discrete PSO Algorithm for TAP-HSR Problem

TAP-HSR is in one kind of NP-hard problem and difficult for human schedulers. The goal of our research is to achieve as good as possible results in reasonable computational time.


### 3.1. Standard PSO Algorithm

Swarm optimization algorithm is a swarm intelligence algorithm proposed by Kennedy and Eberhart [26] as a simulation of the social behavior of bird flocking. PSO is composed of a number of individuals called particles. Particles are initialized with random locations and velocities. Each particle tries to improve the location by following the best location of itself and the best particle of the whole swarm. The position of ith particle is represented by M-dimensional vector denoted by X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
M
) (i
=
1,2
,
…
,
k). The velocity for the ith particle can be described as V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
M
) (i
=
1,2
,
…
,
k).A particle’s movement is based on (10):
(10)
v
i
t
+
1
=
ω
×
v
i
t
+
c
1
×
rand
1
(
)
×
p
i
t
-
x
i
t
+
c
2
×
rand
2
(
)
×
p
g
t
-
x
i
t
,
(11)
x
i
t
+
1
=
x
i
t
+
v
i
t
+
1
,
where ω is called inertia weight [33], c
1 and c
2 are two constant numbers which are often called social or cognitive confidence coefficients, the functions rand
1
(
) and rand
2
(
) can generate a random number in [
0,1
], x
i
t is the position of ith particle at the iteration t, v
i
t is the velocity of ith particle at the iteration t, p
i
t is the local best position that ith particle has reached at the iteration t, and p
g
t is the global best position that all the particles have reached at the iteration t.


### 3.2. The Improved Discrete PSO

Because of the continuous position space of particles, standard encoding method of PSO cannot be directly adopted for discrete optimization problems. It is a challenge to employ the algorithm in combinatorial optimization problems, especially for assignment problem. In this paper, we exploit a new redefining PSO operator method and discrete updating rules of position and velocity to get the solutions for TAP-HSR problem.


#### 3.2.1. Discrete Particle Representation

The most important problem in applying PSO to TAP-HSR problem is to find a suitable particle representation method. In assignment problem, each particle represents a candidate assignment matrix withm
×
n elements [34]. Each element is an integer value in {
0,1
}. For example, in (12)   X
i denotes one assignment that assigns four tugboats to five ships. Tugboat 1 is assigned to ship 1. Tugboats 2 and 3 are assigned to ship 2. Tugboats 1 and 2 are assigned to ship 3. Tugboat 4 is assigned to ship 4. Tugboats 3 and 4 are assigned to ship 5.One example of particle represented by assignment matrix is as follows:(12)
X
i
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
.


#### 3.2.2. Operators Redefinition

Definition 3.
The position subtraction operatorX
i
⊟
X
j
: the subtraction of two positions can be defined as XOR (exclusive OR) operation of binary matrix:
(13)
X
i
⊟
X
j
=
¬
X
i
∧
X
j
∨
X
i
∧
¬
X
j
.
Equation (14) gives one example of the subtraction of positions X
i
t and X
i
t
+
1. 											(14)
X
i
t
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
,
X
i
t
+
1
=
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
,
X
i
t
+
1
⊟
X
i
t
=
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
.
It can be seen that the subtraction of positions is to find the different elements between two positions [34]. According to (11), the velocity is the subtraction of positions that can be represented by a set of the numerical pairs. (
v
j
)
length denotes the element number of v
j:
(15)
v
j
=
{
x
,
y
∣
x
∈
1,2
,
…
,
M
,
y
∈
1,2
,
…
,
N
}
.
In (12),    v
i
t
+
1
=
X
i
t
+
1
⊟
X
i
t
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. (
v
i
t
+
1
)
length
=
4.Definition 4.
The velocity addition operatorv
i
⊞
v
j: the addition of velocities is considered as a union of the elements in v
i or in v
j:
(16)
v
i
⊞
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
or
x
,
y
∈
v
j
}
.Definition 5.
The velocity subtraction operatorv
i
⊟
v
j: the subtraction of velocities is considered as the relative complement elements of v
j with respect to v
i. v
i
⊟
v
j is denoted by the set of elements in v
i but not in v
j:
(17)
v
i
⊟
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
,
x
,
y
∉
v
j
}
.One example of the addition and subtraction of two velocities is as follows:(18)
v
i
=
2,3
,
3,2
,
3,3
,
4,2
,
v
j
=
1,5
,
3,2
,
v
i
⊞
v
j
=
2,3
,
3,2
,
3,3
,
4,2
,
1,5
,
v
i
⊟
v
j
=
2,3
,
3,3
,
4,2
.Definition 6.
The multiply operator of coefficient and velocityc
⊠
v: let c be coefficient and let v be velocity. c is a random real number in (
0,1
):
(19)
c
⊠
v
=
v
2
a
b
c
=
v
a
b
c
∈
(
0,0.5
]
⊟
v
a
b
c
∈
0.5,1
,
where a and b are random integers and a
,
b
∈
[
1
,
(
v
)
length
]. v
a
b represents a subelement string of v
2 from the ath element to the bth element in (20). If a
=
1, b
=
(
v
)
length, v
1
(
v
)
length
=
v.Examples ofv
a
b are as follows:
(20)
v
2,3
,
3,2
,
3,3
,
4,2
v
1
3
∣
1
2,3
,
3,2
,
3,3
,
∣
3
4,2
hhhhhlh
2,3
,
3,2
,
3,3
v
2
3
2,3
,
∣
2
3,2
,
3,3
∣
3
(
4,2
)
hhhhlhh
3,2
,
3,3
v
1
4
∣
1
2,3
,
3,2
,
3,3
,
(
4,2
)
∣
4
h
h
h
h
h
h
h
2,3
,
3,2
,
3,3
,
4,2
.Based on (19), v
1
⊞
(
c
⊠
v
2
) can be represented by
(21)
v
1
⊞
(
c
⊠
v
2
)
=
v
1
⊞
v
2
a
b
c
∈
(
0,0.5
]
v
1
⊟
v
2
a
b
c
∈
0.5,1
.For illustration,v
1
=
{
1,5
,
3,2
,
(
2,3
)
} and v
2
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. Table 4 shows some examples of c
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).Table 4
Examples ofc
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).
c
a
b
c
⊠
v
2
v
1
⊞
(
c
⊠
v
2
)
c
∈
(
0,0.5
]
1
3
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
1
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
2
3
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
4
4
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊞
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
,
(
4,2
)
}
c
∈
(
0.5,1
)
1
3
⊟
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
1
3
=
{
(
1,5
)
}
2
3
⊟
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
}
4
4
⊟
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊟
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
}From Table4, it is known that if c
∈
0,0.5, v
1
⊞
(
c
⊠
v
2
) can be added to some new elements. If c
∈
(
0.5,1
), some elements might be deleted from v
2. This method can keep the diversity of the swarm and exploit the global search ability of PSO thoroughly.Definition 7.
The multiply operator of inertia weight and velocityω
⊠
v: let ω
=
1 and let ω
⊠
v
=
v.
Based on Definitions3–7, the new discrete movements of particles are followed by the following equations:
(22)
v
i
t
+
1
=
v
i
t
⊞
p
i
t
⊟
x
i
t
a
1
b
1
c
1
⊞
p
g
t
⊟
x
i
t
a
2
b
2
c
2
(23)
x
i
t
+
1
=
x
i
t
⊞
v
i
t
+
1
.


#### 3.2.3. The Procedure of IDPSO for TAP-HSR

The pseudocode of the improved discrete PSO is listed in Pseudocode2.Pseudocode 2
Step  1. (Initializing)
Initialize the parameters: the max iterationN
C
max
⁡, the no-improvement iteration G
C
max
⁡, swarm size K,
each particle’s location and velocity, the local best locationp
i and the global best location p
g.
Step  2. (Updating and Fitness Calculation)
Set the iteration numbert = 1
Repeat
For each particle, generate random parameter:c
1, c
2, a
1, a
2, b
1, b
2
Update the velocity of each particle according to (22)
Update the position of each particle according to (23)
Check the new positionX
i
t
+
1 is a feasible assignment according to (8)
If (X
i
t
+
1 is not a feasible assignment) then
MutationX
i
t
+
1 to a feasible assignment
End if
Generate the scheduling sequence
Calculate the turnaround time as fitness ofX
i
t
+
1
Updatep
i, p
g
Check the improvement ofp
g
Ifp
g is improved then
c_flag = 0
Else
c_flag = c_flag + 1
End if
t = t + 1
Untillt > N
C
max
⁡ or c_flag = G
C
max
⁡
Step  3. (Final stage)
Output the best tugboat assignment, the ship scheduling sequence, the start docking time and the
completion docking time of eachship, the turnaround time of the best assignment.


## 3.1. Standard PSO Algorithm

Swarm optimization algorithm is a swarm intelligence algorithm proposed by Kennedy and Eberhart [26] as a simulation of the social behavior of bird flocking. PSO is composed of a number of individuals called particles. Particles are initialized with random locations and velocities. Each particle tries to improve the location by following the best location of itself and the best particle of the whole swarm. The position of ith particle is represented by M-dimensional vector denoted by X
i
=
(
x
i
1
,
x
i
2
,
…
,
x
i
M
) (i
=
1,2
,
…
,
k). The velocity for the ith particle can be described as V
i
=
(
v
i
1
,
v
i
2
,
…
,
v
i
M
) (i
=
1,2
,
…
,
k).A particle’s movement is based on (10):
(10)
v
i
t
+
1
=
ω
×
v
i
t
+
c
1
×
rand
1
(
)
×
p
i
t
-
x
i
t
+
c
2
×
rand
2
(
)
×
p
g
t
-
x
i
t
,
(11)
x
i
t
+
1
=
x
i
t
+
v
i
t
+
1
,
where ω is called inertia weight [33], c
1 and c
2 are two constant numbers which are often called social or cognitive confidence coefficients, the functions rand
1
(
) and rand
2
(
) can generate a random number in [
0,1
], x
i
t is the position of ith particle at the iteration t, v
i
t is the velocity of ith particle at the iteration t, p
i
t is the local best position that ith particle has reached at the iteration t, and p
g
t is the global best position that all the particles have reached at the iteration t.


## 3.2. The Improved Discrete PSO

Because of the continuous position space of particles, standard encoding method of PSO cannot be directly adopted for discrete optimization problems. It is a challenge to employ the algorithm in combinatorial optimization problems, especially for assignment problem. In this paper, we exploit a new redefining PSO operator method and discrete updating rules of position and velocity to get the solutions for TAP-HSR problem.


### 3.2.1. Discrete Particle Representation

The most important problem in applying PSO to TAP-HSR problem is to find a suitable particle representation method. In assignment problem, each particle represents a candidate assignment matrix withm
×
n elements [34]. Each element is an integer value in {
0,1
}. For example, in (12)   X
i denotes one assignment that assigns four tugboats to five ships. Tugboat 1 is assigned to ship 1. Tugboats 2 and 3 are assigned to ship 2. Tugboats 1 and 2 are assigned to ship 3. Tugboat 4 is assigned to ship 4. Tugboats 3 and 4 are assigned to ship 5.One example of particle represented by assignment matrix is as follows:(12)
X
i
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
.


### 3.2.2. Operators Redefinition

Definition 3.
The position subtraction operatorX
i
⊟
X
j
: the subtraction of two positions can be defined as XOR (exclusive OR) operation of binary matrix:
(13)
X
i
⊟
X
j
=
¬
X
i
∧
X
j
∨
X
i
∧
¬
X
j
.
Equation (14) gives one example of the subtraction of positions X
i
t and X
i
t
+
1. 											(14)
X
i
t
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
,
X
i
t
+
1
=
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
,
X
i
t
+
1
⊟
X
i
t
=
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
.
It can be seen that the subtraction of positions is to find the different elements between two positions [34]. According to (11), the velocity is the subtraction of positions that can be represented by a set of the numerical pairs. (
v
j
)
length denotes the element number of v
j:
(15)
v
j
=
{
x
,
y
∣
x
∈
1,2
,
…
,
M
,
y
∈
1,2
,
…
,
N
}
.
In (12),    v
i
t
+
1
=
X
i
t
+
1
⊟
X
i
t
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. (
v
i
t
+
1
)
length
=
4.Definition 4.
The velocity addition operatorv
i
⊞
v
j: the addition of velocities is considered as a union of the elements in v
i or in v
j:
(16)
v
i
⊞
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
or
x
,
y
∈
v
j
}
.Definition 5.
The velocity subtraction operatorv
i
⊟
v
j: the subtraction of velocities is considered as the relative complement elements of v
j with respect to v
i. v
i
⊟
v
j is denoted by the set of elements in v
i but not in v
j:
(17)
v
i
⊟
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
,
x
,
y
∉
v
j
}
.One example of the addition and subtraction of two velocities is as follows:(18)
v
i
=
2,3
,
3,2
,
3,3
,
4,2
,
v
j
=
1,5
,
3,2
,
v
i
⊞
v
j
=
2,3
,
3,2
,
3,3
,
4,2
,
1,5
,
v
i
⊟
v
j
=
2,3
,
3,3
,
4,2
.Definition 6.
The multiply operator of coefficient and velocityc
⊠
v: let c be coefficient and let v be velocity. c is a random real number in (
0,1
):
(19)
c
⊠
v
=
v
2
a
b
c
=
v
a
b
c
∈
(
0,0.5
]
⊟
v
a
b
c
∈
0.5,1
,
where a and b are random integers and a
,
b
∈
[
1
,
(
v
)
length
]. v
a
b represents a subelement string of v
2 from the ath element to the bth element in (20). If a
=
1, b
=
(
v
)
length, v
1
(
v
)
length
=
v.Examples ofv
a
b are as follows:
(20)
v
2,3
,
3,2
,
3,3
,
4,2
v
1
3
∣
1
2,3
,
3,2
,
3,3
,
∣
3
4,2
hhhhhlh
2,3
,
3,2
,
3,3
v
2
3
2,3
,
∣
2
3,2
,
3,3
∣
3
(
4,2
)
hhhhlhh
3,2
,
3,3
v
1
4
∣
1
2,3
,
3,2
,
3,3
,
(
4,2
)
∣
4
h
h
h
h
h
h
h
2,3
,
3,2
,
3,3
,
4,2
.Based on (19), v
1
⊞
(
c
⊠
v
2
) can be represented by
(21)
v
1
⊞
(
c
⊠
v
2
)
=
v
1
⊞
v
2
a
b
c
∈
(
0,0.5
]
v
1
⊟
v
2
a
b
c
∈
0.5,1
.For illustration,v
1
=
{
1,5
,
3,2
,
(
2,3
)
} and v
2
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. Table 4 shows some examples of c
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).Table 4
Examples ofc
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).
c
a
b
c
⊠
v
2
v
1
⊞
(
c
⊠
v
2
)
c
∈
(
0,0.5
]
1
3
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
1
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
2
3
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
4
4
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊞
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
,
(
4,2
)
}
c
∈
(
0.5,1
)
1
3
⊟
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
1
3
=
{
(
1,5
)
}
2
3
⊟
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
}
4
4
⊟
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊟
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
}From Table4, it is known that if c
∈
0,0.5, v
1
⊞
(
c
⊠
v
2
) can be added to some new elements. If c
∈
(
0.5,1
), some elements might be deleted from v
2. This method can keep the diversity of the swarm and exploit the global search ability of PSO thoroughly.Definition 7.
The multiply operator of inertia weight and velocityω
⊠
v: let ω
=
1 and let ω
⊠
v
=
v.
Based on Definitions3–7, the new discrete movements of particles are followed by the following equations:
(22)
v
i
t
+
1
=
v
i
t
⊞
p
i
t
⊟
x
i
t
a
1
b
1
c
1
⊞
p
g
t
⊟
x
i
t
a
2
b
2
c
2
(23)
x
i
t
+
1
=
x
i
t
⊞
v
i
t
+
1
.


### 3.2.3. The Procedure of IDPSO for TAP-HSR

The pseudocode of the improved discrete PSO is listed in Pseudocode2.Pseudocode 2
Step  1. (Initializing)
Initialize the parameters: the max iterationN
C
max
⁡, the no-improvement iteration G
C
max
⁡, swarm size K,
each particle’s location and velocity, the local best locationp
i and the global best location p
g.
Step  2. (Updating and Fitness Calculation)
Set the iteration numbert = 1
Repeat
For each particle, generate random parameter:c
1, c
2, a
1, a
2, b
1, b
2
Update the velocity of each particle according to (22)
Update the position of each particle according to (23)
Check the new positionX
i
t
+
1 is a feasible assignment according to (8)
If (X
i
t
+
1 is not a feasible assignment) then
MutationX
i
t
+
1 to a feasible assignment
End if
Generate the scheduling sequence
Calculate the turnaround time as fitness ofX
i
t
+
1
Updatep
i, p
g
Check the improvement ofp
g
Ifp
g is improved then
c_flag = 0
Else
c_flag = c_flag + 1
End if
t = t + 1
Untillt > N
C
max
⁡ or c_flag = G
C
max
⁡
Step  3. (Final stage)
Output the best tugboat assignment, the ship scheduling sequence, the start docking time and the
completion docking time of eachship, the turnaround time of the best assignment.


## 3.2.1. Discrete Particle Representation

The most important problem in applying PSO to TAP-HSR problem is to find a suitable particle representation method. In assignment problem, each particle represents a candidate assignment matrix withm
×
n elements [34]. Each element is an integer value in {
0,1
}. For example, in (12)   X
i denotes one assignment that assigns four tugboats to five ships. Tugboat 1 is assigned to ship 1. Tugboats 2 and 3 are assigned to ship 2. Tugboats 1 and 2 are assigned to ship 3. Tugboat 4 is assigned to ship 4. Tugboats 3 and 4 are assigned to ship 5.One example of particle represented by assignment matrix is as follows:(12)
X
i
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
.


## 3.2.2. Operators Redefinition

Definition 3.
The position subtraction operatorX
i
⊟
X
j
: the subtraction of two positions can be defined as XOR (exclusive OR) operation of binary matrix:
(13)
X
i
⊟
X
j
=
¬
X
i
∧
X
j
∨
X
i
∧
¬
X
j
.
Equation (14) gives one example of the subtraction of positions X
i
t and X
i
t
+
1. 											(14)
X
i
t
=
1
0
1
0
0
0
1
1
0
0
0
1
0
0
1
0
0
0
1
1
,
X
i
t
+
1
=
1
0
1
0
0
0
1
0
0
0
0
0
1
0
1
0
1
0
1
1
,
X
i
t
+
1
⊟
X
i
t
=
0
0
0
0
0
0
0
1
0
0
0
1
1
0
0
0
1
0
0
0
.
It can be seen that the subtraction of positions is to find the different elements between two positions [34]. According to (11), the velocity is the subtraction of positions that can be represented by a set of the numerical pairs. (
v
j
)
length denotes the element number of v
j:
(15)
v
j
=
{
x
,
y
∣
x
∈
1,2
,
…
,
M
,
y
∈
1,2
,
…
,
N
}
.
In (12),    v
i
t
+
1
=
X
i
t
+
1
⊟
X
i
t
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. (
v
i
t
+
1
)
length
=
4.Definition 4.
The velocity addition operatorv
i
⊞
v
j: the addition of velocities is considered as a union of the elements in v
i or in v
j:
(16)
v
i
⊞
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
or
x
,
y
∈
v
j
}
.Definition 5.
The velocity subtraction operatorv
i
⊟
v
j: the subtraction of velocities is considered as the relative complement elements of v
j with respect to v
i. v
i
⊟
v
j is denoted by the set of elements in v
i but not in v
j:
(17)
v
i
⊟
v
j
=
{
x
,
y
∣
x
,
y
∈
v
i
,
x
,
y
∉
v
j
}
.One example of the addition and subtraction of two velocities is as follows:(18)
v
i
=
2,3
,
3,2
,
3,3
,
4,2
,
v
j
=
1,5
,
3,2
,
v
i
⊞
v
j
=
2,3
,
3,2
,
3,3
,
4,2
,
1,5
,
v
i
⊟
v
j
=
2,3
,
3,3
,
4,2
.Definition 6.
The multiply operator of coefficient and velocityc
⊠
v: let c be coefficient and let v be velocity. c is a random real number in (
0,1
):
(19)
c
⊠
v
=
v
2
a
b
c
=
v
a
b
c
∈
(
0,0.5
]
⊟
v
a
b
c
∈
0.5,1
,
where a and b are random integers and a
,
b
∈
[
1
,
(
v
)
length
]. v
a
b represents a subelement string of v
2 from the ath element to the bth element in (20). If a
=
1, b
=
(
v
)
length, v
1
(
v
)
length
=
v.Examples ofv
a
b are as follows:
(20)
v
2,3
,
3,2
,
3,3
,
4,2
v
1
3
∣
1
2,3
,
3,2
,
3,3
,
∣
3
4,2
hhhhhlh
2,3
,
3,2
,
3,3
v
2
3
2,3
,
∣
2
3,2
,
3,3
∣
3
(
4,2
)
hhhhlhh
3,2
,
3,3
v
1
4
∣
1
2,3
,
3,2
,
3,3
,
(
4,2
)
∣
4
h
h
h
h
h
h
h
2,3
,
3,2
,
3,3
,
4,2
.Based on (19), v
1
⊞
(
c
⊠
v
2
) can be represented by
(21)
v
1
⊞
(
c
⊠
v
2
)
=
v
1
⊞
v
2
a
b
c
∈
(
0,0.5
]
v
1
⊟
v
2
a
b
c
∈
0.5,1
.For illustration,v
1
=
{
1,5
,
3,2
,
(
2,3
)
} and v
2
=
{
2,3
,
3,2
,
3,3
,
(
4,2
)
}. Table 4 shows some examples of c
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).Table 4
Examples ofc
⊠
v
2 and v
1
⊞
(
c
⊠
v
2
).
c
a
b
c
⊠
v
2
v
1
⊞
(
c
⊠
v
2
)
c
∈
(
0,0.5
]
1
3
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
1
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
2
3
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊞
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
4
4
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊞
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
,
(
4,2
)
}
c
∈
(
0.5,1
)
1
3
⊟
‖
v
2
‖
1
3
=
{
(
2,3
)
,
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
1
3
=
{
(
1,5
)
}
2
3
⊟
‖
v
2
‖
2
3
=
{
(
3,2
)
,
(
3,3
)
}
v
1
⊟
‖
v
2
‖
2
3
=
{
(
1,5
)
,
(
2,3
)
}
4
4
⊟
‖
v
2
‖
4
4
=
{
(
4,2
)
}
v
1
⊟
‖
v
2
‖
4
4
=
{
(
1,5
)
,
(
3,2
)
,
(
2,3
)
}From Table4, it is known that if c
∈
0,0.5, v
1
⊞
(
c
⊠
v
2
) can be added to some new elements. If c
∈
(
0.5,1
), some elements might be deleted from v
2. This method can keep the diversity of the swarm and exploit the global search ability of PSO thoroughly.Definition 7.
The multiply operator of inertia weight and velocityω
⊠
v: let ω
=
1 and let ω
⊠
v
=
v.
Based on Definitions3–7, the new discrete movements of particles are followed by the following equations:
(22)
v
i
t
+
1
=
v
i
t
⊞
p
i
t
⊟
x
i
t
a
1
b
1
c
1
⊞
p
g
t
⊟
x
i
t
a
2
b
2
c
2
(23)
x
i
t
+
1
=
x
i
t
⊞
v
i
t
+
1
.


## 3.2.3. The Procedure of IDPSO for TAP-HSR

The pseudocode of the improved discrete PSO is listed in Pseudocode2.Pseudocode 2
Step  1. (Initializing)
Initialize the parameters: the max iterationN
C
max
⁡, the no-improvement iteration G
C
max
⁡, swarm size K,
each particle’s location and velocity, the local best locationp
i and the global best location p
g.
Step  2. (Updating and Fitness Calculation)
Set the iteration numbert = 1
Repeat
For each particle, generate random parameter:c
1, c
2, a
1, a
2, b
1, b
2
Update the velocity of each particle according to (22)
Update the position of each particle according to (23)
Check the new positionX
i
t
+
1 is a feasible assignment according to (8)
If (X
i
t
+
1 is not a feasible assignment) then
MutationX
i
t
+
1 to a feasible assignment
End if
Generate the scheduling sequence
Calculate the turnaround time as fitness ofX
i
t
+
1
Updatep
i, p
g
Check the improvement ofp
g
Ifp
g is improved then
c_flag = 0
Else
c_flag = c_flag + 1
End if
t = t + 1
Untillt > N
C
max
⁡ or c_flag = G
C
max
⁡
Step  3. (Final stage)
Output the best tugboat assignment, the ship scheduling sequence, the start docking time and the
completion docking time of eachship, the turnaround time of the best assignment.


## 4. Experimental Results

In this section, we present the computational experiments to evaluate the performance of the improved discrete PSO algorithm in this paper. The algorithms are coded in Java language with the environment of Eclipse and simulated on a PC with a 2.80 GHz Intel CPU and 4 G RAM. In the experiments, three algorithms are implemented for TAP-HSR problems, including GA, the basic discrete PSO (BDPSO), and the improved discrete PSO (IDPSO) in Section3. The basic discrete PSO is implemented without the multiple operator of coefficient and velocity c
⊠
v. The movements of particles are followed by the following equations:
(24)
v
i
t
+
1
=
v
i
t
⊞
(
p
i
t
⊟
x
i
t
)
⊞
(
p
g
t
⊟
x
i
t
)
x
i
t
+
1
=
x
i
t
⊞
v
i
t
+
1
.In IDPSO, there are two important parameters: the max iterationN
C
max
⁡ and swarm size K. Through the experiments, it can be seen that when the max iteration is fixed, the optimal solution is improved with the growth of swarm size because more particles have stronger space search capabilities. However, if swarm size is excessive, the optimal solution quality can be decreased so that it is required to increase the max iteration to get a better solution. The reason is that too many particles cause the solution dispersion so that it is difficult to converge to an optimal solution. On the other hand, the program running time will increase with the increasing of the max iteration and swarm size. Therefore, it is important to select the proper max iteration and swarm size according to the problem size shown in Table 5.Table 5
The max iterationN
C
max
⁡ and swarm size K.
Problem size
N
C
max
⁡
K
Small-sized problem
1000–2500
50–150
Middle-sized problem
2500–3500
150–250To compare the performance of IDPSO, BDPSO, and GA, the experiments consisted of 12 small-sized problems and 10 middle-sized problems that are conducted. In both IDPSO and BDPSO, we use a swarm of 100 particles for small-sized experiments. The max iteration is 2000 and the no-improvement iteration is 1000. In middle-sized experiment, we use a swarm of 200 particles. The max iteration is 3000 and the no-improvement iteration is 1500. In GA, population size is 100. The max iteration is 3000 and the no-improvement iteration is 1500. The probability of crossover is 0.8. The probability of mutation is 0.01. For the three algorithms, two stopping rules are adopted. One is max-iteration rule and the other is no-improvement rule [34]. The comparative experimental results obtained by the IDPSO, BDPSO, and GA on the different size problems are shown in Tables 6 and 7. Since PSO and GA algorithms are stochastic algorithms, each separate run of the program could result in a different result. We run each algorithm 20 times for each problem case. The values of f
b
_
min
⁡ represent the minimum turnaround time of 20 runs. The values of f
avg
_
min
⁡ are the average turnaround time of the 20 runs. The values of mean time are the computational time of average computational time.Table 6
The compared results for small-sized problem.
Problem size
Tugboats
Algorithm
f
b
_min
f
avg_min
Mean time
(ship × tugboat)
2600
3200
3400
4000
(min.)
(min.)
(s)
5 × 4
1
1
1
1
IDPSO
135
135
2
BDPSO
175
183
3
GA
135
159
2
5 × 7
1
2
2
2
IDPSO
80
80
5
BDPSO
120
136.75
7
GA
80
110.75
2
6 × 4
1
1
1
1
IDPSO
175
175
2
BDPSO
183
213.2
4
GA
175
181
3
6 × 7
1
2
2
2
IDPSO
108
110.8
7
BDPSO
123
161.3
9
GA
108
131.3
3
7 × 6
2
2
1
1
IDPSO
168
182.8
7
BDPSO
195
238.7
9
GA
168
194.15
3
7 × 6
1
1
2
2
IDPSO
160
172.35
7
BDPSO
185
229.95
9
GA
160
183.65
3
7 × 8
2
2
2
2
IDPSO
125
140.75
10
BDPSO
200
227.35
14
GA
135
174.9
3
8 × 6
2
2
1
1
IDPSO
173
197.4
8
BDPSO
193
251.5
8
GA
193
217.8
4
8 × 6
1
1
2
2
IDPSO
160
185.6
8
BDPSO
193
236.85
8
GA
185
208.3
4
8 × 8
2
2
2
2
IDPSO
135
156.3
12
BDPSO
248
282.5
25
GA
160
197.45
4
10 × 10
3
3
2
2
IDPSO
208
237.85
26
BDPSO
308
363.9
45
GA
216
279.25
6
10 × 10
2
2
3
3
IDPSO
185
218.65
25
BDPSO
305
362.2
46
GA
245
290.7
6Table 7
The compared results for middle-sized problem.
Problem size
Tugboats
Algorithm
f
b
_min
f
avg_min
Mean time
(ship × tugboat)
2600
3200
3400
4000
(min.)
(min.)
(s)
15 × 10
3
3
2
2
IDPSO
375
412.4
47
BDPSO
528
621.55
65
GA
446
509.4
22
15 × 10
2
2
3
3
IDPSO
330
398.35
47
BDPSO
509
596.7
60
GA
428
495.45
22
15 × 12
3
3
3
3
IDPSO
343
409.1
70
BDPSO
523
601
89
GA
393
515.85
28
20 × 10
2
2
3
3
IDPSO
498
547.2
79
BDPSO
701
795.25
120
GA
596
695.4
41
20 × 12
3
3
3
3
IDPSO
475
567.2
119
BDPSO
613
757.2
234
GA
588
767.65
54
30 × 12
3
3
3
3
IDPSO
959
1070.7
321
BDPSO
1257
1427.5
828
GA
1265
1433.4
115
30 × 15
3
4
4
4
IDPSO
858
970
486
BDPSO
1144
1303.1
1095
GA
1026
1243.2
151
50 × 12
3
3
3
3
IDPSO
1832
1957.85
1110
BDPSO
2276
2424
2670
GA
2167
2491.35
326
50 × 15
3
4
4
4
IDPSO
1683
1814.8
1678
BDPSO
2119
2245.65
5408
GA
2089
2252
419
80 × 15
3
4
4
4
IDPSO
3179
3387.6
5870
BDPSO
3862
4045.0
13247
GA
3834
4064.15
973Through this comparison it is observed that the quality of solutions obtained by IDPSO is always better than that obtained using BDPSO and GA in terms of the best turnaround time and the average turnaround time. Furthermore, the improvement of solutions actually becomes greater as the size of the problems increases. The results obtained by GA are bit better than BDPSO in most of the instances. The proposed IDPSO can obtain the optimal or near-optimal solutions in all cases.As far as computational efficiency is concerned, it is worth mentioning that GA requires less time when compared to BDPSO and IDPSO. On the other hand, IDPSO reports solutions for all problem sizes within reasonable time. Therefore, IDPSO is recommended for use in TAP-HSR problem, as it yields satisfactory results with reasonable computational time. All these experiments showed that the improved discrete PSO in this paper is an effective mechanism for solving the tugboat assignment in container terminals.


## 5. Conclusions

Although there is a huge amount of literature on discrete PSO, the PSO algorithm for tugboat assignment problem does not have rich literature. In this paper, we present a mathematic model of tugboat assignment problem under a hybrid scheduling rule to minimize the turnaround time of ships. Moreover, the improved discrete PSO is proposed to get solutions with good quality in a reasonable computational time. Some new redefined PSO operators and discrete updating rules of position and velocity are described in detail. The proposed IDPSO algorithm in this paper can be considered as more effective approach for TAP-HSR problem compared with GA.The proposed IDPSO in this paper for small-sized and middle-sized TAP-HSR is very effective but for large-size it is not approving. It needs to be improved in the future work such as combining heuristic rule with IDPSO. Furthermore, applying IDPSO to other discrete combinatorial optimization problems is also possible in further research.



---

*Source: 714832-2014-12-28.xml*