Dynamic Tugboat Scheduling for Large Seaports with Multiple Terminals

Abstract

Effective utilization of tugboats is the key to safe and efficient transport and service in ports. With the growth of maritime traffic, more and more large seaports show a trend toward becoming super-scale, and are divided into multiple specialized terminals. This paper focuses on the problem of large-scale tugboat scheduling. An optimization problem is formulated considering the cross-region constraints and uncertainties during tugboat operation. An improved genetic algorithm is proposed based on the reversal operation (GA-RE) to solve the formulated Tug-SP. A task-triggered strategy is designed for dynamic scheduling and dealing with uncertainties. Taking Zhoushan Port as a representation of multi-terminal seaports, simulation experiments are carried out to demonstrate the effectiveness of the proposed method. Compared with historical scheduling data and the standard GA, the proposed method shows good performance in solving different scale instances (including a large-scale instance of 191 ships) in terms of solution quality and computational time.

1. Introduction

The world’s shipping trade volume has been growing continuously in recent years [1]. As a link between land and sea transportation, the throughput of ports has also increased with the continuous increase of shipping trade volume. Congestion in port terminals has intensified. A significant problem busy ports face is the need for reasonable and efficient port operation and management. As the backbone of port services, tugboats provide auxiliary services such as escort, towing, berthing, and departure assistance for large ships. The so-called “shallow water deep utilization” has become popular in many seaports with limited shoreline resources. Tugboats are indispensable for every operation where ships exceed the design scale in the port. Because the channel and port are very crowded and narrow, and the speed of navigation in restricted water areas is low, the maneuverability of the ship is reduced, and it is necessary for the tug to push or tow the ship to ensure it sails in the correct direction [2,3]. Without the assistance of tugboats, large ships are vulnerable to wind and shallow water when berthing and unberthing, and may lose control and crash into nearby ships, berths or other port facilities [4,5]. Therefore, solving the tugboat scheduling problem (Tug-SP) in order to use tugboats effectively, has become key to safe and efficient transport and service in ports. Effective and timely tugboat scheduling is not only the key to improving service levels in the port [6,7], but it can also reduce fuel consumption, thereby reducing pollutant emission [8].

The Tug-SP is to schedule a limited number of tugboats to assist a given number of ships. Essentially, it is an optimization problem to allocate the limited tugboat resources in the port area. In existing research, the frequently used objectives include minimizing tugboat utilization, minimizing ship waiting time, minimizing the time taken to perform all tasks [9,10], minimizing tugboat travel costs and penalties for delays [11], minimizing the total operating cost [12], or a combination of these objectives [13,14]. The constraints considered include tugboat availability, assignment guidelines, and shipping demand. However, these studies focus on ports with a single tugboat base.

With the growth of maritime traffic, large seaports show a trend toward becoming super-scale, and are divided into multiple specialized terminals. Examples of super-scale seaports include Zhoushan Port and the Port of Rotterdam (Figure 1). Tug-SP faces new challenges. Firstly, to facilitate a fast response, multi-terminal seaports usually have multiple tugboat bases. Tugboats in each base usually serve the ships in the corresponding region, while cross-regional work is also allowed when needed. This fact makes the Tug-SP for multi-terminal ports more complex. Secondly, large seaports serve hundreds of ships daily, while the scale of cases studied in existing research is usually small. For example, Zhong et al. investigates the Tug-SP for Guangzhou Port [15]. However, the maximum number of ships served in cases where the Tug-SP was solved was 36. This is much a lower number than the number of ships actually served in large seaports. Thirdly, most existing research focuses on static scheduling, i.e., generating a scheduling plan based on the current given information. In practice, the ship’s arrival time and the tugboat’s towing operation are uncertain. Ignoring the uncertainties may make the schedules not achievable.

This paper focuses on the large-scale Tug-SP for seaports with multiple terminals. An optimization problem is formulated to minimize tugboats’ total driving distance and utilization rate while all the operational requirements are satisfied. The main contributions of this study are as follows:

• The Tug-SP for seaports with multiple terminals is formulated considering cross-region constraints and uncertainties during tugboat operation.
• A task-triggered scheme and an improved genetic algorithm based on reversal operation are proposed. These can efficiently solve multi-terminal Tug-SP of varying difficulty.

The rest of this article is organized as follows. Section 2 describes the Tug-SP and its assumptions. In Section 3, the Tug-SP for multi-terminal seaports is formulated. Section 4 proposes the improved genetic algorithm (GA-RE) and a task-triggered strategy to solve the Tug-SP. In Section 5, computational experiments are carried out to analyze the effectiveness of the proposed model and methods. Section 6 concludes the main findings of this article and outlines future research directions.

2. Related Work

Although tugboats are indispensable for port operations, little attention has been paid to tugboat scheduling.

Table 1. The existing research on Tug-SP.

Ref.	Model	Solver		Tugboat Terminals		Scale *		Computational Time (s)
	Objective	Exact	(Meta) Heuristic	Single	Multiple	Ship	Tug
[16]	Min. the latest completion time of the tugs		√	√		50	22	17,220
[17]	Min. the maximum running time of all tugs	√		√		5	7	3600
[18]	Min. ship waiting time		√	√		25	10	10.48
[11]	Min. tugboat travel cost and penalty for delays	√		√		40	8	1818
[19]	Min. maximum deviation between the arrival or departure times and the scheduled start times	√		√		11	25	11
[12]	Min. total tugboat travel cost	√		√		40	20	690.42
[9]	Min. turnaround time of ships		√	√		10	10	4
[15]	Min. tug’s max completion time and total fuel consumption		√		√	36	25	-
[3]	Min. total tugboat operation cost	√		√		28	20	1158
[20]	Min. total cost		√		√	120	71	1026.2
[21]	Min. ship waiting time		√	√		60	20	17.92
[10]	Min. total operation time for tugs		√	√		30	12	-
[22]	Min. ship waiting time and tug overflow horsepower		√	√		-	-	-
[23]	Min. total cost of vessel and pilot paths	√			√	96	26	3335.4
[24]	Min. time taken for bulk cargo transshipment	√			√	40	12	320.44
[25]	Min. ship waiting time and loss of the tug horsepower		√	√		-	-	-
[14]	Min. total cost		√	√		150	32	-
[26]	Min. total weight service time of tug operation	√		√		50	12	333.78
[27]	Min. total process cost for container ships	√		√		100	12	34,925

* Scale: the number of ships being served and tugs in the problem.

summarizes the existing research on Tug-SP. Most studies consider seaports with a single tug base, i.e., the tugboats start from the same origin.

A Tug-SP is usually formulated as an optimization problem. Common optimization objectives are designed from two perspectives: minimizing the total cost or maximizing resource utilization. The total cost being considered includes the sailing distance of the tugboat, the waiting time of the ship [9,18,21,24], the operation time or cost of the tug [10,26,27], and the fuel cost of the tugboat [12,15,28], etc. Maximizing resource utilization refers to ensuring that tugboat resources are fully utilized, minimizing idle time [16,17]. There is also research that considers both perspectives [11,19,25], balancing the utilization of the tugboats and the waiting time of the served ships.

When it comes to solving optimization problems, there are two main approaches: (meta-)heuristics and exact algorithms. The exact methods are mathematically elegant and suitable for solving small- or modest-sized problems. The solution quality of such methods is highly dependent on the established model and its constraints. Existing research generally uses mature commercial solvers such as CPLEX, Gurobi, etc. Additionally, Branch and Bound (B and B) methods are frequently used, as the Tug-SP is usually formulated as Mixed Integer Programming (MIP) [3]. Similar methods include the branch pricing method, Benders decomposition method, Lagrangian relaxation algorithm [23], etc. Due to the computational complexity of the exact algorithm, some scholars have begun to study the acceleration techniques of the exact algorithm, such as relaxing the assumptions of the objective, using a priori generating nodes such as enumeration methods, or combining heuristic algorithms with exact solutions to improve the solution speed.

When the model is complex, the exact solution method is time consuming. Therefore, the calculation examples of this kind of method are generally small, i.e., no more than 40 [11,12,17]. However, Tug-SP is an NP-hard problem. The size of the solution space may be exponential. Thus, (meta-)heuristic algorithms are designed to find near-optimal solutions in a reasonable timeframe, such as Ant Colony Optimization (ACO) [28], Particle Swarm Optimization (PSO) [9], greedy algorithm [21], genetic algorithm [15], and their variants [29]. However, the maximum number of examples that have been studied is 150 [14], which is far from the actual situation in large seaports.

Moreover, most research focuses on static scheduling; that is, generating a scheduling plan based on current information. However, the operation of tugs and ships is full of uncertainties; for example, the ship’s arrival time and the tugboat’s towing operation time. Research on dynamic scheduling usually discretizes the whole scheduling process into multiple time windows to reduce the time needed to update scheduling plans, and to deal with uncertainty by updating the scheduling plan.

Existing research may also be used to solve larger-scale Tug-SPs. However, Tug-SPs with more ships and tugs are computationally challenging. The computational time of the existing research is provided in Table 1. It is observed that those methods need a long computational time, even in small-scale cases. If those methods are used to solve large-scale problems, it will be time consuming.

To conclude, existing research on Tug-SP mainly assumes that tugboats start from the same origin. Both exact and (meta-)heuristics methods are applied. However, the existing studies are often based on small- or modest-sized problems. Research on large-scale Tug-SPs is lacking. Nevertheless, less attention has been paid to dynamic scheduling that considers the uncertainties during tug operations.

3. Tugboat Scheduling Problem Formulation

This section formulates the Tug-SP in multi-terminal harbors as an MIP. First, the operation process of tug services is elaborated. Then, the Tug-SP is formulated to minimize the total idling distance and considers a soft constraint on tugs’ cross-region work.

3.1. Problem Description

The operation process of the tug service for ships coming in and going out of a port is shown in Figure 2. For navigation safety and operational efficiency, especially berthing operations, ships need the assistance of tugs. Typically, the number of tugboats required for different sizes of ships is different. The port authority makes schedules after ships report their information and demand for tugs. This includes service time, position and destination, and type of operations. The ships are served following a “First come, first served” rule. The tugboat is moored at each tugboat base at the beginning and goes to the service place after receiving the schedules. After completing the towing and/or escorting mission, the tug goes to the new task position or stands by at the site. Tugs return to the tugboat terminal after all the tasks are completed.

3.2. Problem Formulation

The following assumptions are held when formulating the Tug-SP for multi-terminal ports:

(1)

The tugboats are expected to provide uninterrupted service without any faults or incidents.

(2)

The tugboat, ship, and berth are treated as points, and the distance is calculated according to their latitude and longitude coordinates.

(3)

The travel time of the tugboat in the port is only related to the position between the berths and the speed of the tugboat, and other factors are not considered.

(4)

The number of the tugs and the service time for each ship is known.

Table 2. Variables for tugboat scheduling problems.

Symbols	Definitions
$I$	set of berths, $I=\left\{i\right|i=1,2,\cdots ,m\}$, where $m$ is the total number of berths in the port.
$J$	set of ships, $J=\{j,l|j,l=1,2,\cdots ,n\}$, where $n$ is the total number of ships entering and leaving port that need tugboat assistance in a day.
$K$	set of tugboats $K=\left\{k\right|k=1,2,\cdots ,z\}$, where $z$ is the total number of tugboats in the port.
$W$	set of ship tasks by tugboat $k$, $W=\left\{w\right|w=1,2,\cdots ,z\}$.
$p_k^{\mathrm{s}}$	The starting position of tugboat $k$ to perform task $w$, superscript $\mathrm{s}$ means start.
$p_k^{\mathrm{d}}$	The destination of tugboat $k$$\mathrm{to}\mathrm{perform}\mathrm{task}w-1$, superscript $\mathrm{d}$ means destination.
$D_k$	The idling distance of tugboat $k$ (refers to the distance when the tugboat $k$ is not assisting a ship).
$H_j$	The total power of tugboats that ship $j$ requires.
$h_k$	The power of tugboat $k$.
$V_k$	The speed of tugboat $k$.
$S_j$	The number of tugboats required by ship $j$.
$T_j^{\mathrm{s}}$	The starting time of berthing/unberthing operation of ship $j$, superscript $\mathrm{s}$ means start.
$T_{kj}^{\mathrm{s}}$	The task starting time of tugboat $k$ assist ship $j$, superscript $\mathrm{s}$ means start.
$T_{kj}$	The task process time of the tugboat $k$ assist ship $j$.
$T_{kij}$	The sailing time required for a tugboat $k$ to go to berth $i$ to assist ship $j$.
$T_{kj}^{\mathrm{e}}$	The task ending time of tugboat $k$ assist ship $j$, superscript $\mathrm{e}$ means end.
$M$	A large positive number.
$X_{kj}^w$	Binary variable that equals 1 if a ship $j$ is tugged by tugboat $k$; otherwise, it equals 0, superscript $s$ represents the $w$th task of tugboat $k$.

summarizes the relevant parameter definitions for Tug-SP. The main task of tug scheduling is to allocate limited tugboats ($I=\left\{i\right|i=1,2,\cdots ,m\}$) to serve a given number of ships ($J=\{j,l|j,l=1,2,\cdots ,n\}$) from a given start position ($p_k^{\mathrm{s}}$) to a destination ($p_k^{\mathrm{d}}$). Maximizing the utilization rate of the tugboats is the key to improving efficiency. In large ports with multiple tugboat bases, cross-regional work is not encouraged, but is allowed when necessary. Cross-regional work means the idling distance of the tugs ($D_k$) will significantly increase. The idling distance of the tugboats is defined as $p_k^{\mathrm{s}}-p_k^{\mathrm{d}}$, i.e., the sailing distance of the tugboat $k$ to the target berth $i$ of the ship $j$ to be assisted. Therefore, in this paper, the objective is to minimize the idling distance, making cross-regional work an implicit soft constraint. Under the condition of satisfying various constraints, the algorithm avoids the generation of scheduling plans for tugboat cross-regional operations as much as possible by minimizing the objective function. The total power and the number of tugboats required by ship $j$ is determined by the tonnage of the ship and the port regulations. To match tugboats with ships and to determine the service process ($T_j^{\mathrm{s}}$, $T_{kj}^{\mathrm{s}}$, $T_{kj}$, $T_{kij}$), additional variables are needed. These are a large positive number $M$ and binary variables $X_{kj}^w$ that indicate the status of the tugs. For large ports, the total number of port tugboats $K$ is variable and is not included when the tugboat is in need of maintenance or other services. Therefore, uninterrupted service in the port can be guaranteed.

Setting the objective as minimizing the idling distance of the tugboats, the Tug-SP in multi-terminal seaports is formulated as follows:

$$\mathrm{Minimize}:D={\displaystyle \sum _{j\in J}{\displaystyle \sum _{w\in W}{\displaystyle \sum _{k\in K}(p_k^{\mathrm{s}}-p_k^{\mathrm{d}})}}}{X}_{kj}^w$$

(1)

$$\mathrm{Subject}\mathrm{to}:\forall k\in K;\forall i\in I;\forall j,l\in J;j>l;\forall w\in W$$

$$D_k=p_k^{\mathrm{s}}-p_k^{\mathrm{d}}$$

(2)

$$T_{kij}=D_k÷V_k$$

(3)

$${\displaystyle \sum _{k\in K}{\displaystyle \sum _{w\in W}{X}_{kj}^w=}}{S}_j$$

(4)

$${\displaystyle \sum _{k\in K}{\displaystyle \sum _{w\in W}{X}_{kj}^w{h}_k\ge }}{H}_j$$

(5)

$$X_{kj}^w\times X_{kj}^{w+1}\times (T_l^{\mathrm{s}}-T_j^{\mathrm{s}})\ge 0$$

(6)

$${\displaystyle \sum _{j\in J}{X}_{kj}^w}-{\displaystyle \sum _{j\in J}{X}_{kj}^{w+1}}\ge 0$$

(7)

$$X_{kj}^w>X_{kl}^{w+1}$$

(8)

$$T_{kj}^{\mathrm{e}}=T_{kj}^{\mathrm{s}}+{\displaystyle \sum _{j\in J}{X}_{kj}^w}{T}_{kj}$$

(9)

$$T_{kj}^{\mathrm{s}}\le T_j^{\mathrm{s}}-T_{kij}+M\times (1-X_{kj}^w)$$

(10)

$$T_{kj}^{\mathrm{s}}+M\times (1-X_{kj}^w)\ge T_j^{\mathrm{s}}$$

(11)

$$X_{kj}^w\in \{0,1\}$$

(12)

$$T_j^{\mathrm{s}},T_{kj}^{\mathrm{s}},T_{kj},T_{kij}\ge 0$$

(13)

Objective (1) minimizes the running idle distance of tugboats; that is, the total idle distance taken to complete all towing tasks. Constraint (2) means the running idle distance of the tugboat $k$ from the $w-1$th task position to the $w$th task position. Specifically, the distance refers to the distance generated when the towing task is performed. The smaller the distance, the lower the driving cost of the tugboat; this also means that no cross-regional operation is performed. Constraint (3) defines the time required for the tugboat to sail to the target berth when assisting the ship. Constraints (4) and (5) are the number and horsepower constraints of the tugboats required by ships, respectively. Constraint (6) means that each tugboat can assist, at most, one ship at a time to avoid the phenomenon that the tug serves multiple ships at the same time. Constraints (7) and (8) limit the task order of the tugboat, and each tugboat gives priority to the ship in accordance with the planned task order. Constraint (9) represents the relationship between the task’s start and end time during which the tugboat assists the ship. Constraints (10) and (11) ensure that multiple tugboats that assist a ship start working simultaneously. Constraint (10) indicates that if ship $j$ is the $w$th task of tugboat $k$, then the start time of the $w$th task of tugboat is the start time of berthing or unberthing operation of ship $j$ minus the sailing time of the tugboat $k$ to the target berth $i$ of ship $j$. The constraint (11) represents that the end time of the $w$th task of the tugboat $k$ is equal to the completion time of ship $j$. Constraints (12) and (13) define the value range of variables.

4. Improved Genetic Algorithm for Solving Tug-SP

In this section, a task-triggered scheduling framework is designed, as presented in Figure 3. First, after the Tug-SP is formulated, the scheduling time is divided into phases for fast computation and to deal with uncertainties during tug operation. Then, an improved genetic algorithm for solving Tug-SP is proposed with the reversal operation, i.e., GA-RE. Subsequently, after a task is completed, the status of the tugs is updated. If the number of available tugboats is larger than those needed for next task, the scheduling phase will slide and update. New scheduling will be triggered. Moreover, new scheduling will also be triggered if there is an emergency during the procedure. Details about the algorithm are introduced below.

4.1. Task-Triggered Strategy

In practice, uncertainties are inevitable. Uncertainties refer to unexpected events that influence the effectiveness of the schedules. For example, the ships being served may not arrive on time. The time taken for a tug to complete a task may be longer or shorter than expected. In this paper, a task-triggered strategy is designed to deal with uncertainties during tugboat operations. The main function of the algorithm is to decompose the whole Tug-SP into multiple phases, according to the availability of the tugboat for the next service task. New scheduling is triggered when a tugboat is released (the tugboat completes the current task and is not occupied). The released tugboat is added to the pool of available tugboats for a new schedule phase. When the number of tugboats in the available tugboat pool meets the number required for the next ship to be served, a new scheduling phase is triggered. Furthermore, in the case of emergencies or other uncertainties during the execution of the tugboat’s operations, a phase update is triggered to address uncertainties in the tugboat’s operational processes. The pseudo-code of the task-triggered scheduling is shown in Algorithm 1.

The task-triggered strategy is similar to the event-triggered scheduling strategy. There are two main ways to deal with the uncertainty problem. One is to use the sliding time window to dynamically process through rolling optimization [30,31]. The other is handled by proactive/reactive strategy [32]. In addition, [26] have combined reactive scheduling strategies with active scheduling strategies. The rescheduling is triggered when the number of available tugboats in the pool meets the number of tugboats required by the next ship or when there are unexpected events. The available state of the tugboat is dynamically updated. Together with the fast computational time, the schedules can be updated quickly to deal with the uncertainties. This method has the characteristics of flexibility and real-time capability of the above two methods, and avoids local minima that may cause by the sliding time window.

Algorithm 1: task-triggered scheduling

Input: The list of arriving ships; the setting data of GA-RE

Output:$\mathrm{The}\mathrm{tugboat}\mathrm{schedule}\mathrm{plans};\mathrm{the}\mathrm{minimum}\mathrm{idling}\mathrm{distance}{D}_k$

Begin

1.  For iter < $J$

2.  Generate a initial optimal solution $S$

3.  Record the prediction $T_{kj}^{\mathrm{s}}$, $T_{kij}$ and prediction $p_k^{\mathrm{s}}$, etc. of each k in the S

4.  If $T_{kij}$ of $k$ < $T_j^{\mathrm{s}}$ of the $i$th $j$, the $X_{kj}^w$ = 1 of these $k$

5.   Record the schedule plan of $j$ before iter

6.   While iter < $J$

7.    Add tugboats with $X_{kj}^w$ = 1 to the available tugboat pool

8.    The optimal solution $S$ is generated from the $i$th ship $j$

9.    Update $T_{kj}^{\mathrm{s}}$$T_{kij}$$p_k^{\mathrm{s}}$$X_{kj}^w$ etc. relevant information

10.  iter+ = 1

11.  end while

12. end if

13. end for

end

4.2. GA-RE Algorithm

4.2.1. Encoding

Binary encoding in large-scale optimization problems leads to considerable encoding and decoding work, making the problem more complex and wasting computing resources. In the encoding, the current n ships are first sorted and renumbered in chronological order, and then the tugboats are assigned according to the ship’s serial number sequence. The chromosome length corresponds to the total number of tugboats working in the current stage.

Table 3. Individual encoding.

Ship Serial Number	1	2	2	3	3	4	4	4	5	6	6	7	7
Tugboat	2	13	5	21	14	5	8	9	11	22	10	2	19

provides an example of the specific encoding. Seven ships are in service at this stage. The repeated ship serial number represents that the ship needs multiple tugboats, e.g., Tug 13 and Tug 5 service ship 2. The chromosome length is 13, meaning 13 tugboats are required for this stage.

4.2.2. Setting of the Individual and Initial Population

The population is a candidate solution set composed of n chromosome individuals, and each chromosome individual represents a candidate solution. Initialization is the first process in GA that is responsible for preparing the initial population, which is generally generated randomly [33]. In this paper, according to the number of tugs and amount of horsepower required by the ship to be served in the current stage, a chromosome individual with a length equal to the total number of tugs needed in the current stage is randomly generated in the set of available tugs, and an individual with an initial feasible solution is obtained. Then, according to the setting of population parameters by genetic algorithm, the above method of generating individuals is repeated to generate a corresponding number of individuals to form an initial population. Each individual in the initial population represents a feasible solution. The population initialization example is depicted in the Figure 4. Each number in the figure represents a tugboat. The individual length corresponds to the number of tugboats required for the current stage. For instance, in the ongoing stage requiring 35 tugboats to serve 16 ships, the first ship necessitates one tugboat, the second ship requires three tugboats, and the population size is denoted as N.

4.2.3. Calculation of Fitness

The reciprocal of the objective function, minimizing the idling distance, is used as the fitness function. According to the previous sections and encoding methods, the fitness value is the idling distance generated by each chromosome individual performing a tugboat schedule service. First, the chromosome individuals satisfying constraints (4), (5), and (6) are generated. From each chromosome individual, the task of each tugboat and the ship it serves, the decision variables $X_{kj}^w$, $p_k^{\mathrm{s}}$, and $p_k^{\mathrm{d}}$ are obtained. Then, the task’s start and end time are calculated according to constraint (9). In addition, in cases where two or more tugboats serve the same ship simultaneously, constraints (10) and (11) ensure that multiple tugboats are assigned to the same ship and start service simultaneously. According to constraint (7) and constraint (8), the corresponding position information of each tugboat and the related parameters, such as task start and end time, are updated. This schedule’s minimum idling distance is calculated according to constraint (2) and Formula (1).

4.2.4. Reverse Operation

The continuous evolutionary reversal operation is introduced after selection, crossover, and mutation to improve the local search ability of genetic algorithms (see Algorithm 2). The reversal operation plays a role in accelerating evolution and improving population fitness. The “evolution” here refers to the unidirectionality of the reversal algorithm. Only individuals with improved fitness values after reversal are accepted; otherwise, the reversal is invalid. The reverse specific operation is to reverse the generated population after the selection, crossover, and mutation procedures. Firstly, two random integers r1 and r2 are generated, r1 and r2 $\in$ (1, individual length); and then the gene fragments between r1 and r2 columns in the population matrix are reversed and sorted to generate new populations and new individuals. Finally, the objective function values of the individuals after the reversal are calculated, and the individuals with better objectives are replaced to form a new population. After the evolution of the entire population is reversed, the fitness function is introduced for calculation and evaluation, and the individual with the largest fitness value is selected for the next generation of crossover mutation and evolutionary reversal operations.

Algorithm 2: REVERSE algorithm

Input: Selected individuals, the data list of arriving ships

Output: Individual after evolution reversal

Begin

1. For each Individual i

2.  Generate two random numbers r1, r2 within the range of the Individual’s column number

3.   If Individual code between r1 and r2

4.    Individual = Individual which code reverse order

5. end if

6. Calculate the fitness values of each individual

7. Merged new populations

8. Select the optimal solution

9. end for

end

4.2.5. GA-RE Algorithm

Combining the reversal operation with the conventional genetic algorithm, the proposed GA-RE algorithm is shown in Algorithm 3. During the operation of the algorithm, different iterations (lines 11 and 14) are set to help the algorithm explore more solution spaces, improve the diversity of solutions, and avoid falling into local optimal solutions.

Algorithm 3: GA-RE algorithm

Input: The data list of arriving ships; the setting data of GA-RE

Output:$\mathrm{The}\mathrm{tugboat}\mathrm{schedule}\mathrm{plans};\mathrm{the}\mathrm{minimum}\mathrm{idling}\mathrm{distance}{D}_k$

Begin

1. Initialize P(0)

2.  t = 0

3.  While (t <= T) do

4.  for i = 1 to MAXGEN do

5.   Evaluate the fitness of P(t)

6.   if $T_{kij}$ < $T_j^{\mathrm{s}}$ do

7.    The fitness of P(t) = M (an infinite integer)

8.   end if

9.   Select the operation to P(t)

10.  end for

11.  for i = 1 to MAXGEN /9 do

12.   Crossover operation to P(t)

13.  end for

14.  for i = 1 to MAXGEN /5 do

15.   Mutation operation to P(t)

16.  end for

17.  for i = 1 to MAXGEN do

18.   Reverse operation to P(t)

19.   Reinsert the reversed offspring into the P(t)

20.   P(t + 1) = P(t)

21.  end for

22.  t = t + 1;

23. end while

24. For each objective

25.  Calculate the idling distance of each individual

26. End for

end

5. Simulation Experiments

This section tests the effectiveness and applicability of the proposed model and the algorithm by comparing the results with the actual scheduling history during a 10-day period. The simulations are carried out on AMD Ryzen R7-6800H CPU 3.20 GHz processor and 16 G RAM, using MATLAB 2020. The parameters of GA/GA-RE are as follows: population size N = 200, evolution generation MG = 1000, crossover probability pc = 0.9, mutation probability pm = 0.5, generation gap GGAP = 0.9.

5.1. Parameter Setting

Zhoushan Port is chosen to represent a large seaport with multiple terminals. The Zhoushan Port comprised four berthing groups distributed across four terminals (see Figure 1a). Currently, there are 36 available tugboats in the port, and the number of available tugboats varies slightly daily due to factors such as the state of the tugboat itself or the execution of other rescue missions. The port serves an average of about 150 ships per day. The number of tugboats in each port area and the number of tugboats of varying horsepower are shown in

Table 4. Tugboat configuration of Zhoushan Port.

Terminal	Power
	<4000 HP	4000–5600 HP	>5600 HP
BL	0	10	2
DX	0	6	3
MS	0	6	0
ZH	4	5	0

. In Zhoushan Port, the Port Authority stipulates the number and type of tugs providing services for ships entering the port. The port authority determines the target berths for incoming ships and the required number and type of tugs. Details of the ships and the number and type of tugs needed are shown in

Table 5. Details of ships entering port (part).

Ship	Target Berth	Type of Job	Estimated Operation Time	Number of Required Tugboats	Length of Ship
1	A	berthing	August 8th 0:15	2	125.8
2	B	berthing	August 8th 0:15	1	99.8
3	C	berthing	August 8th 0:30	2	182.5
4	D	unberthing	August 8th 1:00	2	109.8
5	E	unberthing	August 8th 1:30	2	158.6
6	E	unberthing	August 8th 1:30	3	234.9
7	F	unberthing	August 8th 1:30	2	170.2
…	…	…	…	…	…

.

The scheduling results are compared with historical data (10 days) with the same number of ships entering Zhoushan Port, tug service demand, and available tug configuration. Two cases are considered; i.e., medium-scale and large-scale. In the medium-scale instances, the number of ships entering the port is less than 170, while in the large-scale instances, the number is more than 170.

5.2. Results and Discussion

5.2.1. Medium-Scale Instances

The results obtained by the proposed method are shown in

Table 6. Results of historical instances with schedule model.

	Number of Ships (J)	Number of Tugs (K)	Idling Distance (km)		Computational Time (s) (avg.)
			Proposed Method (avg.)	Historical Schedule
Inst1	138	36	2669.448	3228.7	48.680
Inst2	137	37	2128.12446	2638.9	38.243
Inst3	114	36	2076.2449	2596.8	49.126
Inst4	122	36	1933.71108	2558.1	37.212
Inst5	108	39	2091.85422	2789.6	32.253
Inst6	170	42	3005.4218	3443.4	51.724
Inst7	127	38	1861.78874	2714.1	46.175
Inst8	156	41	2622.98472	3948.8	42.014
Inst9	150	41	2676.10334	3927.7	41.424
Inst10	124	41	2619.88448	3520.5	39.651

. The first three columns in the table show the name of the instance, the number of ships arriving at the port on the day, and the available tugboats. The value of the objective function value, i.e., the idling distance of the tugs, and the computational time of the proposed method and the actual schedule are also provided. In all ten instances, the total idling distance of the tugboat is significantly reduced using the proposed method while meeting all berthing and departure requests within 52 s.

As the proposed GA-RE is an heuristic method, the values are the average of five runs. A detailed analysis of the results is provided in Figure 5. The idling distances from the proposed scheduling model and solution strategy are much shorter than they have been historically; this is true even in the worst case. Moreover, the boxplot of the five runs also shows that the quality of the solutions is stable. For the same instance, the best, worst, and average performances using the method are similar.

5.2.2. Large-Scale Instance

For the large-scale instance, we chose the day in which the largest number of ships arrived in Zhoushan Port in the last three years. The total number of ships arriving at the port is 191. The computational time is 53.262 s, and the results are shown in Figure 6. Each row of different colors represents a tugboat. Each matrix block represents a tugboat towing task. The number of matrix blocks in the same row represents the total number of tasks of a tug on a given day. The length of the matrix block is equal to the task duration. The Gantt chart shows that the proposed method performs well for large-scale instances with more than 190 ships. Several longer matrix blocks in the figure indicate that the tugboat performs cross-regional towing tasks, indicating that the number of tugboats in a particular port area is not enough in a large-scale instance. For the whole schedule, the total idling distance is 3533.949 km.

The complete schedule is shown in

Table 7. Example of an optimal tugboat schedule plan.

Tug ID	Number of Ships Served	Schedule
1	11	(44,58,62,73,18,20,22,29,183,158,118)
2	12	(4,50,59,62,76,81,85,87,33,101,107,37)
3	9	(5,55,63,69,72,75,82,88,112)
4	8	(128,191,190,145,180,181,183,39)
5	7	(127,133,137,143,148,151,118)
6	11	(4,127,63,13,15,21,30,94,105,107,112)
7	15	(44,57,67,74,79,80,85,87,90,93,96,103,104,110,115)
8	11	(42,46,125,170,172,173,139,145,151,100,40)
9	16	(41,121,168,169,171,174,175,176,82,84,87,91,92,155,111,119)
10	9	(41,46,11,66,14,19,87,109,115)
11	10	(2,43,188,170,172,142,179,180,182,195)
12	10	(51,131,141,178,179,148,95,98,160,161)
13	9	(166,126,129,142,144,147,149,99,116)
14	9	(124,129,67,74,75,78,86,91,116)
15	12	(123,131,138,76,83,84,88,153,156,157,108,38)
16	8	(120,131,134,136,26,96,160,161)
17	10	(49,54,55,68,19,20,28,91,94,37)
18	4	(59,17,194,195)
19	11	(125,170,171,174,178,145,180,181,97,104,35)
20	7	(122,58,71,78,81,27,38)
21	8	(168,169,130,140,144,90,34,40)
22	10	(120,56,69,135,143,147,148,154,106,117)
23	14	(163,165,167,123,125,127,143,145,148,151,153,156,159,114)
24	8	(168,169,130,140,144,90,34,40)
25	10	(120,56,69,135,143,147,148,154,106,117)
26	14	(164,166,48,51,52,56,65,71,16,23,29,93,184,187)
27	10	(164,191,192,193,24,32,152,183,184,187)
28	12	(3,53,57,61,68,13,81,27,33,154,108,113)
29	13	(1,7,53,56,64,70,81,26,95,99,102,111,35)
30	10	(6,45,47,64,70,25,31,105,109,36)
31	9	(7,9,60,61,175,77,86,89,114)
32	12	(1,8,54,56,132,137,176,179,24,28,30,39)
33	9	(45,52,129,139,146,149,102,106,117)
34	8	(8,165,167,170,173,177,147,113)
35	10	(5,43,129,72,143,146,148,150,159,162)
36	10	(3,10,60,66,73,12,25,150,98,36)

. The first column of the schedule plan represents the tug ID of the service task. The second column is the total tasks the tug performs. The third column is the ship that the tugboat serves on the day. The start time and end time of each task are shown in Appendix A. It can be seen that the task frequency of each tugboat on the day is relatively uniform, further illustrating the applicability of the proposed schedule strategy and GA-RE. For example, Tug 105 assists the berthing operations of ships 44, 58, 62, and 73; Tug 351 is the busiest, assisting 16 ships in berthing and unberthing tasks.

5.3. Comparision of GA-RE and GA

Based on the historical data of Zhoushan Port, 20 research cases are generated, and the number of available tugboats in the control cases is constant, i.e., 36 tugs. The number of ships arriving at the port in one day in these 20 cases is in the range of 110–180, which represents most of the actual entry and exit conditions and extreme conditions of Zhoushan Port.

The comparative experimental results are shown in

Table 8. The idling distance of tugs (GA vs. GA-RE).

	Ship	GA			GA-RE
		Min.1	Avg.1	Max.1	Min.2	Avg.2	Max.2
Inst1	175	3933.0182	4080.0782	4376.4105	3467.4570	3532.9762	3575.3824
Inst2	180	4192.1460	4376.1581	4498.3376	3603.1388	3681.0423	3738.1779
Inst3	158	3660.2934	3890.2715	4195.6519	3302.1118	3442.8430	3495.2379
Inst4	163	4736.7347	4851.6691	5073.8956	4056.3440	4213.5062	4361.2050
Inst5	181	5911.7334	6043.4582	6287.6904	5261.6367	5409.1310	5589.4818
Inst6	179	3736.9897	3778.2652	3823.7315	3127.3627	3222.1313	3290.7223
Inst7	167	4070.5440	4291.7800	4415.1567	3505.6298	3667.2208	3771.8520
Inst8	177	3977.7035	4067.7019	4169.8771	3345.3512	3532.1610	3614.6524
Inst9	166	4926.7494	5140.0774	5292.3956	4432.0075	4566.1285	4673.6856
Inst10	143	5877.2137	6240.6200	6584.9354	5263.5158	5381.3164	5481.3050
Inst11	148	4043.7714	4177.5315	4381.7922	3569.7424	3717.3163	3852.7495
Inst12	167	4445.6448	4677.3916	4870.9333	3885.6021	4063.1603	4186.1847
Inst13	141	3329.0254	3449.3172	3563.8662	2826.8228	2856.6444	2883.0241
Inst14	136	4295.0311	4370.1940	4467.6297	3464.5143	3594.8727	3715.0846
Inst15	163	6501.8813	7195.1020	7230.0504	5516.3326	5819.4719	6077.7211
Inst16	137	5109.4924	5243.0229	5362.2916	4297.1647	4381.5132	4517.6082
Inst17	167	5013.2531	5222.9508	5410.0615	4667.4744	4720.6660	4745.2162
Inst18	158	3694.0345	3762.4250	3943.6179	3225.5052	3273.5127	3327.5241
Inst19	143	4824.3381	4999.3929	5242.4086	3938.1803	4078.6762	4280.9460
Inst20	130	4783.4989	5266.4084	5662.4534	3603.7245	3720.8510	3853.5178

. The first column in the table is the name of the case, and the second column is the number of ships arriving at the port on the same day. The maximum and minimum columns are the maximum and minimum values of the two algorithms running five times, respectively, and the mean is the average of the results of the five runs. In the 20 cases, the average value of the objective function of the GA-RE algorithm is less than the average value of the standard GA, i.e., the idling distance of the tugs using the GA-RE is about 700 km less.

Figure 7 provides the maximum, minimum, and the average values of the idling distance of the 20 instances using GA-RE and GA. It is evident that the proposed GA-RE performs better than the standard GA. The reversal operation incorporated in the GA-RE algorithm further enhances the fitness of the initial population, thereby facilitating the acquisition of optimal solutions in subsequent iterations. As depicted, the GA-RE algorithm exhibits a narrower range between the maximum and minimum values, indicating better stability in the solution quality. This observation underscores that the evolutionary reversal operation improves overall population quality and enhances solution performance.

6. Conclusions and Future Research

This paper addresses the complex problem of tug scheduling in large seaports with multiple terminals. There is a particular focus on Zhoushan Port as a representative case study. The formulated optimization problem aims to minimize tugboats’ idling distance while ensuring compliance with operational requirements. To tackle this problem, an innovative genetic algorithm with the reversal operation (GA-RE) is proposed; this demonstrates superior performance compared to historical scheduling data and the standard GA, especially in handling large-scale instances.

The introduced task-triggered strategy is designed for dynamic scheduling, and for effectively managing uncertainties inherent in tugboat operations. Through comprehensive simulation experiments, the proposed method proves its effectiveness in terms of solution quality and computational time, showcasing its applicability, not only to Zhoushan Port, but also to other large seaports with multiple terminals; for example, the Port of Rotterdam.

Future directions for research can include delving into the integration of artificial intelligence and human intelligence in tugboat scheduling. Human operators may consider other factors besides marching rules and port regulations. The manual schedule includes the experiments and preferences of human operators. This implies that there are factors that have not been considered in the mathematical model. Integrating artificial intelligence with human intelligence to uncover and incorporate these hidden factors into the mathematical model could enhance scheduling accuracy and adaptability. Furthermore, combining it with the other schedules such as berth allocation would greatly improve the port’s comprehensive operation efficiency.