1. INTRODUCTION
With over 80% of global trade by volume and more than 70% of its value being carried on board ships, it is obvious that ocean shipping is the most important transportation mode for international mercantile trade (UNCTAD, 2017). However, the traffic capacity of waterways connected to ports has gradually come under more pressure as ship sizes and numbers have increased. For example, in China, numerous problems are gradually emerging in main waterways connected to ports, namely that the capacity of one- or two-way waterways is insufficient, and small vessels occupy the main waterway for a lengthy period. In order to improve waterway capacity and service levels, many ports have widened their main waterways. Therefore, compound waterways have been formed in order to allow vessels with different tonnage to use the varying navigable water depth waterways efficiently. Briefly, a compound waterway means that there are two or more navigable channels with different navigable depths in the same design section of the main waterway. However, although a compound waterway significantly increases the number of vessels entering or leaving a port over a given period and saves on the idle time of berthing, other problems arise in compound waterways. More specifically, there are increased vessel types and more complex waters in the compound waterway, and increased vessel encounter situations will occur in more complex traffic situations, which may seriously affect the safety and efficiency of vessel navigation. Thus, while the opening of a compound waterway may improve the port capacity, improving safety and efficiency of vessels from an operating angle will be a more complex issue.
In reality, the compound waterway, which is an advanced mode of vessel traffic organisation from the perspective of “hardware facilities”, is still completely reliant on Vessel Traffic Service Operators' (VTSOs') management abilities and their experience. Therefore, from the perspective of “software facilities”, it is necessary to propose a scientific and reliable vessel scheduling scheme to effectively improve navigation safety and efficiency in compound waterways.
Currently, studies on vessel traffic scheduling optimisation methods in complex water have focused on two aspects: a mathematical optimisation model providing for a specific scheme and a simulation method for vessel traffic. In addition, data mining technology based on vessel Automatic Identification System (AIS) data can also provide auxiliary guidance.
Regarding mathematical models, at present, vessel scheduling optimisation models can be divided into one-way or two-way waterways. Based on the one-way waterway type, Zhang et al. (Reference Zhang, Lin, Guo and Liu2016) established a mathematical model based on channel-berth coordination and designed a simulated annealing and multiple population generic algorithm. Thereafter, a multi-object vessel scheduling model in a one-way port was presented with minimum total scheduling waiting time for vessels as the objective (Zhang et al., Reference Zhang, Chen, Ji and Yao2017). For two-way waterways, Ulus (Reference Ulus2009) considered various factors influencing transit vessels in the Strait of Istanbul and proposed a mathematical model. Lalla-Ruiz et al. (Reference Lalla-Ruiz, Shi and Voß2016) proposed a Mixed Integer Linear Program (MILP), which could allocate vessels to a waterway scheduling sequence, and then used a simulated annealing algorithm to solve the model. Sluiman (Reference Sluiman2017) proposed a linear programming model with the object of maximising the average gross tonnage throughput in a two-way waterway. In addition to waterway resources, numerous academic papers have focused on other resources or aspects related to vessel scheduling, such as the allocation of chamber lock space (Verstichel et al., Reference Verstichel, Causmaecker, Spieksma and Berghe2014), tugs (Zhen et al., Reference Zhen, Wang, Wang and Qu2017) and berth assignment (Imai et al., Reference Imai, Nishimura and Papadimitriou2001; Reference Imai, Chen, Nishimura and Papadimitriou2008; Golias et al., Reference Golias, Boile and Theofanis2006; Imaiab et al., Reference Imaiab, Hattori and Papadimitriou2007).
The optimisation models in the literature are all based on one-way or two-way waterway scheduling or other related resources. Few studies have investigated vessel scheduling in a compound waterway. In compound waterways, vessel traffic flow is very complex and numerous traffic flow conflicts exist, which can easily lead to vessel collisions. Therefore, although such research can provide an effective scheduling scheme, the results still cannot address complex traffic conflicts in a compound waterway.
In terms of simulation methods, a great deal of literature involves restricted water transit capacity. In order to evaluate canal capacity, Golkar et al. (Reference Golkar, Shekhar and Buddhavarapu1998) introduced the Panama Canal Simulation Model (PCSM), which has two major objectives: assessing pilot working conditions and evaluating canal capacity. It is worth mentioning that the PCSM includes a manual sequencing and scheduling component or Man-In-Loop (MIL), which can simulate the scheduling scheme according to actual conditions. Aiming at inland water with a multi-bridge crossing, Sang et al. (Reference Sang, Tong, Xu, Mao and Yan2017) proposed an agent-based simulation model to evaluate navigational capacity. By referring to both road and inland waterway capacity, Wang et al. (Reference Wang, Peng, Song and Zhou2015) defined seaport fairway capacity and concluded with the relationship between seaport fairway capacity and safety distance of ships with an Arena-based simulation model. Later, Wang et al. (Reference Wang, Peng, Tian and Song2017) analysed and obtained the impact of key influencing factors on improving waterway capacity. Furthermore, various scholars have used simulation software to simulate vessel traffic in certain waters. Köse et al. (Reference Köse, Başar, Demirci, Güneroglu and Erkebay2003) simulated the traffic of national and international transiting vessels based on maritime traffic regulations in the Istanbul Strait. Özbaş and Or (Reference Özbaş and Or2007) constructed a simulation platform to test the impact on vessel traffic from rules, the number of tugboats and pilots, traffic density, vessel type and meteorological conditions. Qi et al. (Reference Qi, Zheng and Gang2017) proposed a spatial-logical mapping model based on cellular automata, which could simulate the safety distance among vessel interactions and vessel speeds more accurately.
Research related to restricted water capacity and vessel traffic can be used to guide the formulation of port management measures and provide a basis for the design of coastal berths and entrance channels, as well as the construction of water-related projects. Little research has been aimed at simulating vessel traffic in a compound waterway. The work that has been done mainly involves analysing the impact of different key factors such as the arrival time of ships, weather conditions, navigation rules, etc, on waterway capacity or vessel traffic and only the existing scheduling scheme can be evaluated using the simulation method. Though these key factors have great influence on measure formulation and efficiency of vessel traffic organisation, it is difficult to obtain an optimised scheduling scheme directly.
Regarding data mining technology, work reported mainly analyses the characteristics of vessel traffic flows by means of statistical analysis of AIS data within a certain region. AIS contains a large amount of data regarding vessel traffic, such as vessel particulars, speed, location and direction. Xiao et al. (Reference Xiao, Han, Gulijk and Ale2015) analysed the statistical distributions of vessel behaviour characteristics based on AIS data. The statistics of these characteristics can be used as an input for simulation or model calibration. Mou et al. (Reference Mou, Tak and Han2010) mined the AIS data of vessels in encounter situations, then analysed the correlation of traffic characteristics, such as ship size, course, speed and Closest Point of Approach (CPA), the results of which could be used for collision risk analysis. Through historical AIS data analysis, the motion patterns of ferryboats and their probability density spatial distribution can be obtained; therefore, abnormal ferryboat behaviours can be detected, which is helpful for marine supervision (Huang et al., Reference Huang, Liu, Wen, Zhou and Zhang2017). The study of vessel traffic flow characteristics in specific waters can also be used to guide the formulation of traffic organisation measures (Liu et al., Reference Liu, Liu, Zhou and Guo2014). For example, Aydogdu et al. (Reference Aydogdu, Yurtoren, Park and Park2012) analysed traffic flow characteristics in the Istanbul Strait, and then proposed three traffic separation schemes in different locations to ensure navigation safety. Wu et al. (Reference Wu, Mehta, Zaloom and Craig2016) evaluated vessel collision frequency through an AIS-based method. A series of hotspots in which vessel conflict can very easily occur were identified in the Sabine-Neches waterway, and this can help VTSOs to manage vessel traffic more effectively. Such research can improve the precision of simulating vessel traffic and can be used to assess navigation risks and guide traffic organisation.
In summary, simulation methods can provide guidance for traffic organisation and waterway design from a macroscopic viewpoint, which cannot result in a reliable scheduling scheme for VTSOs. Mathematical optimisation models all aim at one-way or two-way waterways or other resources, which do not consider the complex traffic conflicts in compound waterways. AIS data mining and analysis are mainly used to provide some parameters for these two types of methods above. At present, work on analysing vessel traffic characteristics and establishing a scheduling model in a compound waterway is still scarce.
Taking these challenges into consideration, this paper constructs a scheduling optimisation model aiming at solving vessel traffic conflicts that exist in compound waterways and then combines a multi-objective genetic algorithm and a linear weighting method to obtain a reliable traffic scheduling scheme for VTSOs, including a traffic mode, vessel scheduling sequence and starting scheduling time for each vessel, according to daily information of vessels entering and leaving the port.
The remainder of this paper is organised as follows. Section 2 analyses the vessel navigational mode and conflicts based on a specific case. Section 3 proposes a type of simplified compound waterway prototype and establishes a Vessel Traffic Scheduling optimisation model in a Compound Waterway (VTSCW). Section 4 designs a Multi-Objective Genetic Algorithm (MOGA) to solve the VTSCW. Section 5 presents and discusses the experiment. Section 6 summarises the conclusions as well as outlining future research.
2. COMPOUND WATERWAY ANALYSIS
2.1. Overall understanding
A typical compound waterway exists in Tianjin port in China. As shown in Figure 1, the overall framework for the Tianjin compound waterway includes part of the main waterway, an auxiliary waterway and a precautionary area. Under normal circumstances, the main waterway can be used for vessels of a certain tonnage or type travelling through with a two-way or one-way traffic mode. The auxiliary waterway can only be used for small ships with a one-way mode. The north auxiliary waterway, on the northern side of the main waterway between buoy no. 29 and buoy no. 39, is used for small ships entering the port; similarly, the south auxiliary waterway, on the south side of the main waterway, is used for small ships leaving the port. The water on the west side of buoy no. 39 is known as the precautionary area, where crews need to navigate with extreme caution, and the water area where the precautionary area extends to buoy no. 47 forms a Y crossing area. On the west side of the Y crossing area are a north harbour and south harbour for berthing vessels. On the east side of buoy no. 29, which is also the entrance to the north auxiliary waterway, anchorages are distributed on both sides of the main waterway for vessels waiting to enter the harbour.
Schematic diagram of Tianjin compound waterway.
2.2. Vessel navigational mode
Every vessel entering or leaving the port has a specific navigational mode. Allocating navigational modes for vessels in a compound waterway includes allocating a proper waterway for vessels and determining the vessel traffic mode in the main waterway. As shown in Table 1, according to the navigation rules in Tianjin port, the standard depends on the vessel lengths, breadths and types, while merchant vessels entering or leaving the port can be divided into four types, namely vessels carrying dangerous cargo, oil tankers, passenger vessels and common vessels apart from the three types mentioned above.
Standard of vessel navigational mode allocation in Tianjin port.
According to the one-way or two-way traffic modes existing in the main waterway, different forms of vessel traffic flows may appear in the compound waterway, as shown in Figures 2–4. For example, when the main waterway is in two-way traffic and the auxiliary waterways are in normal conditions, we define the vessel traffic as double-in-double-out. When outbound or inbound vessels that must be in a one-way traffic mode navigate on the main waterway, the vessel traffic flow can be defined as double-out-single-in or double-in-single-out.
Double-in-double-out.
Double-out-single-in.
Double-in-single-out.
2.3. Vessel traffic conflict
The characteristics of vessel traffic conflict in the waterway vary with the water environment. For the Tianjin compound waterway, three water areas exist in the complex vessel traffic area, which are the compound waterway entrance, buoy no. 39 water area and the Y crossing area.
Following the analysis in the previous subsection, the main waterway is always in one of the three traffic modes: two-way, inbound vessels with one-way and outbound vessels with one-way mode. When vessels that must be in one-way traffic navigate from one end of the main waterway, vessels at the other end of the main waterway cannot navigate. Therefore, when the main waterway is in mode conversion from the three types of traffic above, a head-on situation often occurs at the main waterway entrance. Furthermore, according to the navigation rules of Tianjin port, whether in an auxiliary or a main waterway, the vessel behind cannot overtake the preceding vessel and a safe distance of at least six times the vessel length must be maintained between two adjacent vessels in the same direction. In summary, when a compound waterway is in a constant traffic mode, we should ensure that no overtaking will take place in the waterway. When a main waterway is in mode conversion, ensuring the safety of vessels in a head-on situation must also be considered.
Two intersecting waters exist in the compound waterway, where more than one complex multi-vessel encounter situation may occur. A traffic conflict near buoy no. 39 is illustrated in Figure 5. Two types of traffic situations with conflict exist in this region: inbound vessels from different waterways head for the same harbour simultaneously and vessels from the main waterway cross with vessels from the auxiliary waterway. The traffic conflict in the Y crossing area is shown in Figure 6: vessels from different harbours may converge in the Y crossing area; an inbound vessel towards the south harbour and outbound vessel from the north harbour may form a crossing situation.
Traffic conflicts near buoy no. 39.
Traffic conflicts in the Y crossing area.
It is important to note that based on the navigation rules of Tianjin port, the above analysis presumes that vessels shall keep navigating in the specified waterway in the whole course of navigation, which means the possibility that the vessels enter or leave the waterway from other parts of the waterway rather than the waterway entrance does not exist.
3. PROBLEM AND MODEL
The layout of main and auxiliary waterways is related to the navigation routes, the depths of waters and the distribution of berths. No unified layout exists in the compound waterway; thus, a type of compound waterway with Y-type bifurcation connected to a large harbour, which is abstracted from the port of Tianjin, is shown in Figure 7, where three key waters are extracted and marked as areas A, B and C respectively. The aim is to schedule vessels entering or leaving the compound waterway safely and efficiently.
Schematic model of type of compound waterway.
3.1. Problem hypothesis
In order to optimise vessel traffic scheduling in the compound waterway, the following assumptions are made:
1) Since berth assignment takes place prior to the vessel scheduling problem, this paper assumes that berths for every vessel are determined before the vessels are scheduled.
2) The starting place and destination of the vessel scheduling are from anchorage to berth for inbound vessels and berth to waterway exit for outbound vessels.
3) This paper considers the traffic flow conflict existing in the process of vessel sailing and does not consider the influence of the turning area produced by berthing vessels on sailing vessels.
4) During the scheduling period, the weather is fine.
3.2. Definition of variables
The notations for formulating the VTSCW are defined in Table 2.
Notation used in formulating the VTSCW.
3.3. VTSCW
Equations (1) and (2) are the two objective functions for the VTSCW.
$$\hbox{Min}\;f_1 = Tf_{{\rm max}} - Ts_{{\rm min}},Tf_{{\rm max}} \ge Tf_i,Tf_{{\rm min}} \le Tf_i,\quad \forall i \in N$$
$$\hbox{Min}\;f_2 = \sum\limits_{i \in N} {(Ts_i - Ta_i)} ,\quad \forall i \in N$$where f 1 and f 2 indicate the minimum waterway occupancy time and minimum total waiting time of the vessels, respectively. In the first formula, Tf max represents completing the scheduling time of the last vessel and Tf min represents starting the scheduling time of the first vessel in a scheduling scheme.
$$T{a}^{\prime}_i = \left\{ {\matrix{ {Ta_i\;L_i \le L_D,} \hfill & {\forall i \in N} \hfill \cr {Nts\;L_i > L_D,Ta < Nts,} \hfill & {\forall i \in N} \hfill \cr {Ta_i\;L_i > L_D,Nts \le Ta < Nte,} \hfill & {\forall i \in N} \hfill \cr {Nts_{next}\;L_i > L_D,Nte \le Ta,} \hfill & {\forall i \in N} \hfill \cr } } \right.$$
$$Nts \le Ts_i \le Nte\quad \forall i \in N,L_i > L_D$$In compound waterways, some types of large vessels need to have a minimum height of tide to transit into and out of ports. Considering tidal impact, in this paper, a specific navigational time window [Nts, Nte] is set for these large vessels. Constraint Equation (3) ensures that their applied scheduling time is set in the given navigational time window. Ta′i is the adjusted applied scheduling time and L D is the draft standard that determines whether or not vessels are constrained by the tide. Nts next is the start time of the next navigational time window. Constraint Equation (4) ensures the starting scheduling time of these large vessels is in the time window.
$$Ts_i \ge T{a}^{\prime}_i\quad \forall i \in N$$
$$T1_i = Ts_i + d1_i/v_i\quad \forall i \in N_1$$
$$T2_i = T1_i + d2_i/v_i\quad \forall i \in N_1$$
$$T3_i = T2_i + d3_i/v_i\quad \forall i \in N_1$$
$$Tf_i = T3_i + d4_i/v_i\quad \forall i \in N_1$$
$$T3_j = Ts_j + d4_j/v_j\quad \forall j \in N_2$$
$$T2_j = T3_j + d3_j/v_j\quad \forall j \in N_2$$
$$Tf_j = T2_j + d2_j/v_j\quad \forall j \in N_2$$Equations (5)–(12) are the continuity constraints for vessels, for the reason that a vessel navigating in the waterway cannot stop. Equation (5) ensures that the time of a vessel starting to schedule is not earlier than the time a vessel applies for scheduling. Equations (6)–(9) are the continuity constraints for inbound vessels. Similarly, Equations (10)–(12) are the continuity constraints for outbound vessels.
$$\left\{ {\matrix{ {Tgap0_i = 6 \times L_i/v_i} \hfill \cr {v_i \le v_j,\;i,\;j \in N_1,\;or\;i,\;j \in N_2} \hfill \cr } } \right.$$
$$Tgap2 = 6 \times \hbox{Max}(L_i,L_j)/v_i,\quad \forall i \in N_1,\forall j \in N_2\;or\;\forall i \in N_2,\forall j \in N_1$$In restricted waterways, Liu et al. (Reference Liu, Feng, Li, Wang and Wen2016) proposed a dynamic ship domain model based on different conditions to ensure vessels' safety. However, the model is too complex to be applied to this problem. Therefore, this paper proposes three safety time intervals aiming at different vessel encounter situations and the values of those time intervals are taken from practice. Constraint Equations (13)–(14) are the minimum time interval constraints for preventing overtaking and ensuring vessel safety in a head-on situation (Zhang et al., Reference Zhang, Lin, Guo and Liu2016). For intersecting waters, such as areas B and C, the area must be used exclusively by one vessel at a specific time. However, there often exist numerous crossing situations, so the relationships of different vessels from different directions navigating in those waters are mutually coupled. In order to ensure the safety and continuity of vessel navigation in intersecting waters, a time slot should be allocated for each vessel in advance by a certain safety standard. Therefore, this article uses a time interval Tgap1 to ensure that a crossing situation will not occur in those waters. For example, when the time of vessel i travelling through the intersecting water is T i, (T i − gap1, T i + gap1) is the exclusive time allocated to vessel i.
In Equations (15)–(28), the subscript variables XYZ are used to represent the vessel navigational direction, mode and berth location, assuming that 
$Ts^{X\comma Z}_{i\comma Y}\ge Ts^{X\comma Z}_{j\comma Y}$, i, j ∈ N in a scheduling scheme.
$$T1_{i,Y = 1,2}^{X = 1} = \hbox{Max}\{ T1_{j,Y = 1,2}^{X = 1} + Tgap0,\;T1_{i,Y = 1,2}^{X = 1} \}$$
$$T1_{i,Y = 0}^{X = 1} = \hbox{Max}\{ T1_{j,Y = 0}^{X = 1} + Tgap0,T1_{i,Y = 0}^{X = 1} \}$$
$$T1_{i,Y = 1}^{X = 1} = \hbox{Max}\{ T1_{j,Y = 1,2}^{X = 0} + Tgap2,T1_{i,Y = 1}^{X = 1} \}$$
$$T1_{i,Y = 2}^{X = 1} = \hbox{Max}\{ T1_{j,Y = 1}^{X = 0} + Tgap2,T1_{i,Y = 2}^{X = 1} \}$$
$$T2_{i,Y = 1}^{X = 0} = \hbox{Max}\{ T2_{j,Y = 1,2}^{X = 1} + Tgap2,T2_{i,Y = 1}^{X = 1} \}$$
$$T2_{i,Y = 2}^{X = 0} = \hbox{Max}\{ T2_{j,Y = 1}^{X = 0} + Tgap2,T2_{i,Y = 2}^{X = 0} \}$$Equations (15)–(20) constitute sub-models of Compound Waterway Slot Allocation (CWSA) for a vessel in a waterway entrance. Equations (15)–(16) ensure that inbound vessels will not overtake the others in the waterway. Equations (17)–(18) ensure that when the main waterway is in traffic mode conversion, inbound vessel i maintains a safe time interval with outbound vessel j in a head-on situation at the main waterway entrance, which is area A for inbound vessel i. Similarly, Equations (19)–(20) ensure that outbound vessel maintains a safe time interval with inbound vessel j in a head-on situation at the main waterway entrance, which is area B for outbound vessel i.
$$T2_{i,Y = 1,2}^{X = 1,z = 0} = \hbox{Max}\{ T2_{j,Y = 1,2}^{X = 1,z = 1} + Tgap0,T2_{i,Y = 1,2}^{X = 1,z = 0} \}$$
$$T2_{i,Y = 0}^{X = 1,z = 1} = \hbox{Max}\{ T2_{j,Y = 1,2}^{X = 1,z = 0} + Tgap0,T2_{i,Y = 0}^{X = 1,z = 1} \}$$
$$T2_{i,Y = 1,2}^{X = 1,z = 0} = (T2_{j,Y = 0}^{X = 1,z = 1} + Tgap1)E1_{ij} + T2_{i,Y = 1,2}^{X = 1,z = 0} E1_{ij}$$
$$T2_{i,Y = 0}^{X = 1,z = 1} = (T2_{j,Y = 1,2}^{X = 1,z = 0} + Tgap1)E2_{ij} + T2_{i,Y = 1,2}^{X = 1,z = 0} E2_{ij}$$Equations (21)–(24) constitute sub-models of traffic flow conversion of a main and auxiliary waterway in a precautionary area (MATFC). Equations (21)–(22) ensure a proper time interval in area B, when inbound vessels from different waterways will head for the same harbour simultaneously. Equations (23)–(24) allocate a time slot to inbound vessels for crossing traffic conflict resolution.
$$T3_i^{X = 0,z = 0} = (T3_j^{X = 1,z = 1} + Tgap1)E3_{ij} + T3_i^{X = 0,z = 0} E3_{ij}$$
$$T3_i^{X = 1,z = 1} = (T3_j^{X = 0,z = 0} + Tgap1)D1_{ij} + T3_i^{X = 1,z = 1} D1_{ij}$$
$$T3_i^{X = 0,z = 0} = \hbox{Max}\{ T3_j^{X = 0,z = 1} + Tgap0,T3_i^{X = 0,z = 0} \}$$
$$T3_i^{X = 0,z = 1} = \hbox{Max}\{ T3_j^{X = 0,z = 0} + Tgap0,T3_i^{X = 0,z = 1} \}$$Equations (25)–(28) are sub-models of Traffic Flow Coordination of Division and Confluence (TFCDC) in a Y crossing area. Equations (25)–(26) eliminate crossing traffic conflicts between inbound vessels for harbour S and outbound vessels from harbour N. Equations (27)–(28) ensure a proper time interval when vessels departing from harbour N and harbour S will converge in area C.
4. ALGORITHM DESIGN
Due to numerous constraints and variables in the VTSCW, vessel scheduling in the port exhibits huge time complexity; therefore, it is difficult for traditional mathematical methods and tools such as IBM ILOG CPLEX Optimization studio to obtain exact solutions when the number of scheduled vessels has a certain scale (Lalla-Ruiz et al., Reference Lalla-Ruiz, Shi and Voß2016; Sluiman, Reference Sluiman2017). Furthermore, VTSCW is a multi-objective optimisation model. However, the Genetic Algorithm (GA), first introduced by Holland (Reference Holland1992), which is a metaheuristic inspired by the process of natural selection that belongs to the larger class of Evolutionary Algorithms (EA), is commonly used to generate high-quality solutions to optimisation and search problems by relying on bio-inspired operators such as matation, crossover and selection and already has many successful applications in multi-objective optimisation problems. Therefore, a MOGA is designed according to the VTSCW characteristics.
As shown in Figure 8, the operation of population initialisation adopts four-dimensional integer encoding. Thus, the gene includes four layers, namely vessel number N, navigational direction X, navigational mode Y and berth position Z. For example, the gene 5120 indicates that vessel no. 5 will enter the port through a two-way traffic mode in the main waterway and berth in harbour N. Following this, the gene sequences are randomly arranged to produce a chromosome that represents a scheduling scheme in the genetic space. Finally, a population can be generated randomly by setting the number of chromosomes.
MOGA flow chart.
The repair procedure for chromosomes is used for ensuring that the solution is feasible. In actual port operations, when vessel i is going to approach berth m, while another vessel j is just carrying out the operation of goods in this berth, vessel i can only be permitted to schedule after vessel j has left the berth. However, in the MOGA algorithm, since the initial population and the mutation operation are randomly generated, it is difficult to guarantee the formation of a feasible solution by random permutation. Therefore, a repair operator is required, following these two operators, and is used for detecting abnormal chromosomes. By exchanging the gene position of unreasonable ships in the chromosomes, a feasible solution can be ensured. The fitness function is the reciprocal of the objective function. The selection operator is based on a nondominated sorting generic algorithm (Deb et al., Reference Deb, Pratap, Agarwal and Meyarivan2000). Then, using the tournament selection operator, the excellent chromosomes can be selected. Two-point crossover and two-point mutation is used in the MOGA.
5. EXPERIMENT AND VERIFICATION
Following investigation and study, it can be concluded that the actual situation of vessel traffic scheduling in a compound waterway is very complex and the proposed models still do not fully match actual situations. Therefore, experimental data was simulated, and a 20 vessel scheduling simulation experiment was carried out on a computer equipped with an Intel i7 3·5 GHz and 32 GB of RAM, as described in this section.
5.1. Input data description
The experimental data consist of four parts: basic information of vessels, anchorages, berths and compound waterways.
The vessel information is displayed in Table 3. In this paper, the distribution of the vessel applied scheduling time intervals is assumed as a negative exponential. The navigational mode classification standards of vessels are categorised according to Tianjin port navigation rules. In order to improve the calculation precision, the anchorage is divided into six parts manually labelled as A–F and the distances between the centre of each anchorage and the waterway entrance are simulated as shown in Table 4. There are 37 berths for vessel berthing in the model. Berths No. 1–21 and No. 22–37 are distributed in harbours S and N respectively. The distance from each berth to area C is between 0·05 to 2 nautical miles. The distance between areas A and B is simulated as 4·62 nautical miles and the distance between areas B and C is simulated as 3·19 nautical miles.
Vessel information.
Anchorage data.
5.2. Simulation experiment
5.2.1. Simulation with 20 vessels
The simulation experiment contains numerous parameters; therefore, a simple Graphical User Interface (GUI) was implemented using MATLAB R 2017a. As shown in Figure 9, 20 vessels were scheduled in the experiment. In order to simplify the model, Tgap1 is set as 6 min. In the scheduling settings unit, Nts and Nte are the navigational time window from 02:00 to 04:00 and the maximum and minimum speed limits of vessels traveling through the waterway are 13 and 5 knots, respectively. L D is 18 m, so vessels No. 2, 4 and 10 should enter or leave the port in the navigational time window.
Graphical User Interface (GUI) of VTSCW.
As shown in the algorithm parameter settings unit: quantity of populations is 200; the generation gap is 0·9; the crossover and mutation possibility are 0·95 and 0·05 respectively and the maximum number of generations is 300.
The execution time was approximately 10 min for 300 generations. The result of a simulation experiment is displayed on the left of the GUI interface. The optimal solution tends to be stationary around the 230th and 155th generations for the first and second objectives, respectively. Following 300 calculation generations, the minimum waterway occupancy time and minimum total waiting time for scheduling 20 vessels are 175 and 358 min, respectively. 12 Pareto-optimal chromosomes are generated. The Pareto-optimal front and their corresponding objective values are illustrated in Figure 10 and Table 5, respectively.
Pareto-optimal front of 20 vessel experiment.
Objective values of Pareto-optimal solution.
5.2.2. Chromosome decoding
The chromosomes for which the second objective value is minimum (Min2O chromosomes) are decoded and listed in Table 6. By interpreting the information hidden in this chromosome, vessels are divided into three groups: inbound vessels in the main waterway, outbound vessels in the main waterway and vessels in the auxiliary waterway, as listed in Tables 7–9, respectively.
Min2O chromosomes.
Timetable for inbound vessels in main waterway.
Timetable for outbound vessels in main waterway.
Timetable for vessels in auxiliary waterway.
In this scheduling scheme, the first vessel scheduled is vessel no. 1, and its starting scheduling time is 00:00, while the last vessels scheduled are vessels no. 17 and 18 in the auxiliary and main waterways, respectively, with end scheduling times that are the 235th and 318th minute, respectively, and the total waiting time is 478 min.
Similarly, the chromosomes for which the first objective value is minimum (Min1O chromosomes) is calculated and its two objective values are 175 and 2152 min.
5.3. Model rationality verification
Taking Min2O of the 20 vessel experiment as an example, from Tables 7–9 we can see the time of vessels navigating in different waters is continuous and each vessel has been allocated a reasonable navigational mode according to their own characteristics. It is impossible that traffic conflicts exist in those key waters, as there are specific time interval limits indicated in columns T1, T2 and T3. Therefore, the model rationality can be analysed from the perspective of continuity constraints, navigational mode allocation and sub-models of CWSA, MATFC and TFCDC. The Ts of vessels 2, 4 and 10 are all in the navigational time window [120 140].
According to the times of vessels travelling through areas A and B, the one-way and two-way traffic slot allocation is illustrated in Figure 11. Fifteen vessels in the main waterway are divided into five groups according to their navigation mode. Since the vessels sailing in the auxiliary waterway mainly do not require waiting, so by combining the traffic mode in the main waterway, the traffic organisation mode in the compound waterway can be obtained, as shown in Figure 12.
Traffic mode slot allocation in main waterway.
Traffic organisation mode in compound waterway.
5.4. Comparison with common scheduling method
At present, the First Come First Served (FCFS) method is frequently used by VTSOs in compound waterways. As indicated by its name, FCFS means the order of vessels is scheduled in accordance with the order of the applying for a scheduling time. With the FCFS method, during the whole high-water period, only vessels no. 1–9 can finish their scheduling. No. 10 should take the tide, but its Ts is the 296th minute which has already been exceeded Nte (the 240th minute), so no matter from the first or second objective, this scheme is not a good choice. The scheduling time of the first 10 vessels are listed in Table 10.
The scheduling time with FCFS method.
5.5. Optimal compromise scheme
It can be seen that from the aspect of waterway occupancy time, Min1O and Min2O are 167 and 318 min, respectively. Therefore, the Min1O scheme is particularly suitable for the situation of a large number of vessels waiting at the port, and all of these vessels must get ready to be scheduled at any time. For Min2O, whether from the first or the second objective value, Min2O is significantly less than for the FCFS method. With the Min2O scheme, the average waiting time of each vessel is only 24 min, so if merely from the vessel point of view, Min2O is the superior scheme.
Sometimes, there is no special need for any interested parties represented by these two objective functions, so we can use a linear weighting method to get a compromise scheme in the Pareto-optimal solution space. In Figure 10, it is easy to see that the value of the second objective is much larger than the value of the first objective, so the first objective value should be set to a larger weight. In Table 5, setting the weights of the two objective values as 10 and 1, respectively, and adding them to get a comprehensive function, for chromosome no. 7, the value of its comprehensive function is 3,326 and that is the minimum in these 25 solutions and can be selected as a compromise scheduling scheme. Chromosome no.7 is listed in Table 11.
Chromosome no.7.
6. CONCLUSIONS
In light of the analysis of vessel traffic problems existing in Tianjin port, China, this paper abstracts a simplified compound waterway with Y-type bifurcation and pinpoints three key areas in which vessel traffic is very complex. Then, a VTSCW mathematical model is proposed to solve the vessel scheduling problem in a compound waterway. Considering the number of vessels, navigational direction, navigational mode and berthing location, a MOGA algorithm with four layers of integer coding is designed. In order to verify the rationality and effectiveness of the model and algorithm, a simulation experiment scheduling 20 vessels was carried out. By comparing the optimised scheme calculated by MOGA with the FCFS method, the results indicate that VTSCW can improve scheduling efficiency. In the Pareto-optimal solution set, an optimal compromise scheme can be selected by the linear weighting method. Furthermore, based on the vessel scheduling experiment, this paper decodes the Min2O chromosome information in detail, which can provide VTSOs with specific scheduling guidance.
In the VTSCW, the purpose of the first objective value is to increase the waterway utilisation ratio as much as possible by allowing as many vessels as possible to pass through within a short period. It can also be used for improving the adaptive capacity of the port system, thereby preventing port congestion. The second objective is constructed from the vessel's perspective. Vessel waiting time optimisation can save energy and reduce exhaust emissions, so as to save on shipping costs and protect the environment. This intelligent scheduling scheme can not only relieve pressure on VTSOs, but also improve vessel navigation safety and efficiency in port waters, thereby enhancing the competitiveness of the port in future development. Moreover, it is an embodiment of a low carbon strategy in port terminals and can better support the development of green shipping. Furthermore, this scheduling method can be used in other waters that are similar to compound waterways, such as inland waters.
However, this paper is a pilot study and does not address a range of factors that will need to be taken into account before such an algorithm can be incorporated into an operational VTS. For example, the day to day operation of a VTS is regularly affected by adverse weather conditions, changing priorities for vessel arrivals and departures, conflicts in the coordination of scheduling berth assignment and vessel traffic optimisation, failure of ships to adhere to planned timings and physical problems with ships such as foul anchors or machinery breakdowns. Furthermore, the minimum safety time interval between vessels in different encounter situations, which is related to vessel particulars and manoeuvrability, should be studied further. Nevertheless, this paper has demonstrated the sound basis for mathematical tools that should be developed to provide working, easy to use, decision-making aids for VTSOs in the very complex environment of large-scale, compound waterways.
ACKNOWLEDGEMENTS
This work was financially supported by the National Natural Science Foundation of China (Grant no. 51779028), the Fundamental Research Funds for the Central Universities (Grant nos. 3132016321, 3132016315, 3132018146).
