# Robust Low-Carbon Discrete Berth Allocation under Uncertainty

Authors: Feifei Yu; Qihe Shan; Yang Xiao; Fei Teng
Journal: International Transactions on Electrical Energy Systems
 (2022)

---

## Abstract

A robust discrete berth allocation method under a low-carbon target is proposed in this study, considering the uncertainty of vessels’ arrival time and handling time. According to the actual situation of port operations, a bilevel, biobjective model is established to minimize both average carbon emission and the range of carbon emission during the berthing period. A set of alternative berth allocation schemes, namely, the set of Pareto solutions, are obtained by a heuristic algorithm based on a genetic algorithm. The effectiveness of the proposed method is verified by simulation.


---

## Body

## 1. Introduction

With the intensification of energy shortage and global warming, “low carbon” and “energy-saving and emission reduction” have gradually become the keywords in various fields. As a significant contributor to carbon emissions, port consumes great quantities of energy, and itsCO2 emissions, accounting for about 3% of the total anthropogenic CO2 emissions, [1] must be taken seriously. In this case, reducing carbon emissions in the port area is important under the “dual carbon targets,” officially put forward by China in 2020. At present, China’s ports mainly carry out emission reduction in structural and technical energy conservation methods to build green ports [2–4]. However, the carbon emission generated in the process of berthing is also a significant amount, which makes it a noteworthy means to reduce port carbon emissions from the perspective of berth allocation [5].In recent years, many research results have been obtained in the field of berth allocation. According to spatial attributes, the berth allocation problem (BAP) can be divided into continuous berth allocation problem and discrete berth allocation problem. Continuous berth regards the wharf coastline as a continuous whole, and vessels can dock at any coastline position. Frojan et al. [6] study the continuous berth allocation problem in the case of multiple terminals in a port and establish a model comprehensively considering four costs, including anchorage waiting for cost and delayed departure compensation. Chen and Huang [7] establish a dynamic continuous berth allocation model in which a penalty cost function is proposed by considering vessel departure delay and berth deviation distance. Carlos [8] studies the dynamic allocation of continuous berths and proposes a mixed-integer model to minimize the travel distance of forklifts and cranes in container operation, which was solved by a heuristic algorithm. The discrete berth is to cut the continuous coastline into individual berths, and each berth can only park one vessel at the same time. For the discrete case, Cordeau et al. [9] discuss the dynamic scheduling problem with the time window and present a tabu search heuristic together with two types of formulation. Sun et al. [10] study the influence of tide on discrete berth allocation from two aspects of the water level change in tide and the variance of vessel arrival time. Arram et al. [11] apply a bird mating optimizer algorithm, which can effectively explore and use the search space to find the global solution for solving the discrete berth allocation problem. On the other hand, according to temporal attributes, berth allocation problems can be divided into static BAP and dynamic BAP. Static BAP assumes that all vessels have arrived at the port and can berth immediately before the start of the scheduled cycle. The static model is generally applicable to the scheduling of large-area detention of vessels caused by extreme weather, [12] which is difficult to play a role in the normal production operation. Dynamic BAP means that vessels will arrive in succession during the implementation of berth scheduling. It is more in line with the actual arrival situation of vessels and can well simulate the specific constraints. [13] Therefore, the research on the dynamic BAP model is much more extensive. Comprehensively considering the actual and urgent requirements of ports for reducing carbon emissions, this study conducts the study on the discrete and dynamic berth allocation problem under a low-carbon target to be close to the real port.With the prevalence of “low-carbon” and the proposal of “dual-carbon targets,” mounting research is conducted on berth allocation with low-carbon targets. Zhao et al. [14] establish a joint berth-quay scheduling model under the strategies of variable arrival time and constant arrival time to minimize the carbon emissions of the whole terminal and the fuel consumption and the departure delay. Using port shore power technology, Peng et al. [15] propose a cooperative optimization method to minimize total cost and air pollution, in which different pollutants are uniformly expressed as economic penalties by levying an environmental tax. Wang et al. [16] consider the joint scheduling of berth, wharf crane, and yard truck and establish a multiobjective model to minimize the total carbon emission in the port area, the average waiting time, and departure delay [17] of each vessel in the port. However, the premise of optimization and scheduling in the above literature is that the vessel can arrive at a planned accurate time, ignoring various uncertain factors in the process of vessel berthing in real-life scenarios, such as arrival delay, handling delay, and equipment failure.More and more scholars have begun to notice and study the uncertainty in berth allocation in recent years [18]. Sheikholeslami and Ilati [19] propose a new port berth allocation model, which considers the destructive impact of the tide on the berth plan and the uncertainty of ship arrival time to generate an effective berth allocation plan. Umang et al. [20] study the BAP in case of interruption caused by uncertain arrival time and handling time and propose an intelligent greedy algorithm, together with an optimal recovery algorithm based on set partition. Some scholars also began to combine berth scheduling with shore bridge schedules. Liang et al. [21] study the joint scheduling problem of berth and quay crane under the environment of random vessel arrival time and handling time and reduce uncertain factors’ influence by adding delay time. Considering the uncertainty of vessel arrival and the fluctuation of container handling rate of terminal crane, Iris and Lam [22] propose an active baseline plan with reactive recovery cost, which aims to develop a recoverable robust optimization method for the weekly berth and terminal crane planning. In actual working conditions, these uncertainties not only bring great hidden dangers to the operation of the wharf but also seriously strike the reliability of its operation plan, resulting in the fluctuation of terminal carbon emissions in a large range, which is not conducive to the accounting and treatment of terminal pollution [23]. However, limited research studies have considered the impact of these uncertainties on port carbon emissions. Therefore, it is of great practical significance to consider the uncertainty when studying the berth allocation with the low-carbon target in actual working conditions.The innovations of this study are as follows:(1)
A discrete berth allocation problem is studied, which focuses on the objective of low-carbon emission in the port. Under the dual-carbon targets, the main sources of the carbon emission in the port are analyzed and the calculation formulas are given. A bilevel, biobjective model is established to reduce the average carbon emission and the range of carbon emission.(2)
The impact of uncertainty on berth allocation of a low-carbon target is considered in the model for the first time to improve the robustness. The arrival time and handling time of the vessels are set to be uncertain and modeled as time windows. A heuristic algorithm based on a genetic algorithm is used to solve this problem, and its effectiveness is verified by simulation.The rest of the study is structured as follows. Section2 analyzes the carbon emission of the port area and establishes a bilevel, biobjective model. Section 3 explains the solution algorithm. In Section 4, an example is applied to verify the effectiveness of the algorithm by comparing it to two commonly used berth allocation policies under uncertainty. Conclusions and possible research directions in the future are noted in Section 5.


## 2. A Bilevel, Biobjective Model

The carbon emissions in the port area originate from two aspects: the portland area and the port water area.In the portland area, the carbon emissions mainly come from the cargo handling equipment at the core of the port terminal, such as the shore bridge, container truck, and yard bridge. These types of equipment will produce a large amount ofCO2 in the process of providing services to berthing vessels. However, in recent years, to achieve the “dual-carbon targets,” the construction of a zero-carbon wharf has been continuously promoted. On October 17, 2021, the world’s first “smart zero-carbon” terminal was put into operation in Tianjin Port. The wharf loading and unloading equipment, horizontal transportation equipment, and production auxiliary equipment are powered by electricity, and 100% of the energy consumption comes from the “wind, light, and storage integration system.” At the same time, advanced energy-monitoring technology is adopted to carry out real-time statistical analysis on various energy consumption of the wharf to ensure zero carbon emission. In addition to all electric-driven facilities and equipment in the port area, for “large emitters” such as vessels, Tianjin Port has built an onshore power system at the wharf front. After the vessel lands, it will supply power to the vessel through the onshore power system to realize zero-emission during vessel berthing operation. Therefore, with the continuous construction of green ports, all carbon emissions in the port area will come from the water area in the future.While the carbon emissions in the port water area are mainly generated by berthing vessels, during berth scheduling, the port arranges the berthing time and berthing position of the vessels according to the relevant information provided by them to determine the berth scheduling table. After arrival, the vessel waits at the anchorage first. Once the allocated berth is free, it can sail to the berth through the channel and receive berthing services. Since the vessels can be connected to the shore power system during berthing operation, the carbon emission of the vessels in port is equivalent to the carbon emission of waiting in anchorage and navigation in the channel. When the vessel is sailing in the port, the main engine and auxiliary engine operate together. The main engine is used as the propulsion power device, and the auxiliary engine generates power to meet the power demand in the vessel. The power of the main engine is usually more than ten times that of the auxiliary engine. While the vessel is waiting at the anchorage, the main engine is turned off, and the auxiliary engine is used to generate power. Therefore, the carbon emission of navigation in the port accounts for the main part of the total carbon emission of the vessel.For the carbon emission during navigation, Hughes [24] proposed the famous “cubic law,” that is, the fuel consumption of the vessel is positively correlated with the cubic of its navigation speed. The fuel consumption fi of vessel i per sailing day can be expressed as follows:(1)fi=ri1+ri0⋅vi3,where vi represents the speed adopted by the vessel i, and ri0 and ri1 represent the skill coefficient of the driver and fuel consumption of the auxiliary engine per sailing day [25].Then, the fuel consumptionFi in the process of entering the berth through the channel of length l can be calculated as follows:(2)Fi=124⋅fi⋅lvi=l24⋅ri1⋅1vi+ri0⋅vi2.When minimizing the fuel consumption, there is an optimal sailing speedvi∗, which can be derived by the following:(3)vi∗=ri12ri01/3.Ifvi∈vi¯,vi¯, but vi∗ is not in this value interval, the smallest Fi is taken at the lower bound or the upper bound. In this study, we assume that the optimal sailing speed vi∗ is within the speed range of vessel i. The CO2 emissions of vessel i while sailing, Ci, can be further calculated by [26].(4)Ci=EF1⋅Fi,where EF1 is the emission factor of CO2 while sailing.As for the carbon emission during the waiting period at the anchorage, the vessel shuts down the main engine and uses the auxiliary engines to generate electricity to meet the power demand inside the vessel. TheCO2 emission of vessel i during this period, Qi is calculated by [27].(5)Qi=POi⋅LFi⋅EF2⋅ENi⋅ACi,where POi is the rated power of auxiliary engines of vessel i during waiting; LFi is the load ratio of auxiliary engines of vessel i; EF2 is the CO2 emission factor during the waiting period; ENi is the number of auxiliary engines working on vessel i; and ACi is the auxiliary engines’ continuous working time, that is waiting time of vessel i.The reference values ofCO2 emission factors when sailing and waiting are shown in Table 1 [14].Table 1
Carbon emission factor.
EF1 (kg/kw-fuel)EF2 (kg/kw-fuel)Emission factor3.110.683Since the emission of vessels sailing in the port accounts for the main part of the total carbon emission, the vessel speed can be directly taken as its optimal speedv∗, under the goal of reducing the total carbon emission of the port. Then, the total carbon emission of the port area during berth scheduling, P, is presented as follows:(6)P=∑iCi+∑iQi=3.11⋅l24⋅∑iri1⋅1vi∗+ri0⋅vi∗2+0.683⋅∑iPOi⋅LFi⋅ENi⋅sti−Ai,where Ai is the arrival time of vessel i, that is, the time from the waters outside the port to the anchorage; sti is the start time of vessel i, that is, the time of vessel i starting from the anchorage to the berth.A container port withn vessels and m berths is assumed. The relevant notation is presented in Table 2. The solution to the berth allocation problem will include the berth allocation information and service order information of each vessel. So a berth schedule can be described by S(X, Y), where X indicates the assignment of vessels to berths and Y indicates the service order.Table 2
Notation.
SetsI=1,…,n,i∈IThe set ofn vesselsJ=1,…,m,j∈JThe set ofm berthsParametersAiArrival time of vesseliAilLower bound ofAiAiuUpper bound ofAiAn vector of Ai valuescijHandling time of vesseli at berth jcijlLower bound ofcijcijuUpper bound ofcijCn×m matrix of cij valueslLength of port channeltiTonnage of vesseliTjTonnage of berthjvi∗Optimal speed of vesseliMA large positive numberDecision variablesxijBinary variable, 1 if vesseli is allocated to berth jXn×m matrix of xij valuesyabBinary variable, 1 ifxaj=xbj=1 and b is immediately serviced after aYn×n matrix of yab valuesstiStart time of vesseli from the anchorage to the berthftiService finish time of vesseliAuxiliary variableziAn auxiliary variable limiting the start time of vesseliIn this study, it is assumed that the arrival time and handling time of the vessel are uncertain, and the time windows are given in advance. The vesseli arrives within Ail,Aiu and has different handling time windows at different berths due to yard position and other factors. A and C contain the arrival and handling time windows of all vessels. For a given berth schedule S, sti can be determined by A and C. Because of the uncertainty of A and C, sti is also uncertain, which will lead to lower and upper bounds of the value of P. So we take the average total carbon emissions as an optimization objective function in equation (7). However, scheduling solely based on the average total carbon emissions might lead to a high range of total carbon emissions, which will result in weak robustness of the berthing schedule [28]. To deal with this problem, we construct the model as a biobjective optimization problem, introducing the minimum range of total carbon emissions as another objective function. So the model can be described as follows:(7)f1:minX,Y12maxC,AP+minPC,A,(8)f2:minX,YmaxC,AP−minPC,A,(9)s.t.Ail≤Ai≤Aiu,(10)cijl≤cij≤ciju,(11)∑j∈Jxij=1,(12)sti≥Ai,(13)stb≥sta+lva∗+∑j∈Jxajcaj−M1−yab,(14)Tj≥ti−M1−xij.Constraints (9) and (10) specify the lower and upper bounds of the vessel’s arrival time and handling time, respectively. Constraint (11) indicates that each vessel can only select one berth. Constraint (12) indicates that the start time is later than the arrival time. Constraint (13) restricts that only when the previous vessel finishes its handling operation, the latter vessel can start to the berth, and constraint (14) restricts the vessel to be serviced only in berths that meet the tonnage requirement.In both definitions of the two objective functions, the maximum and minimum values of total carbon emissions need to be calculated. To solve this bilevel optimization problem, we refer to the hierarchical optimization method proposed by Golias [29]. Since the value of P depends on C and A, let Cmax,AmaxS and Cmin,AminS be the arrival time and handling time for maxP and minP, respectively, under the schedule S. So the problem can be described as follows:(15)f3:maxC,AP=PCmax,Amax,orminC,AP=PCmin,Amin.s.t. equations (9)–(14).(16)zi∈0,1,(17)Ai−sti+M1−zi≥0,(18)∑a∈I,a≠iyai⋅sta+lva∗+∑j∈J,a∈I,a≠icajxajyai−Ai≤M1−zi,(19)Ai−∑a∈I,a≠iyai⋅sta+lva∗+∑j∈J,a∈I,a≠icajxajyai≤Mzi.Constraint (16) shows that zi is an auxiliary variable with a value of 0 or 1. Constraints (17)–(19) ensure that the start time of the vessel is the larger of its arrival time and the finish time of the previous vessel at the berth.Then, the original biobjective, bilevel optimization problem can be reorganized as follows:(20)f1:minX,Y12PCmax,Amax+PCmin,Amin,f2:minX,YPCmax,Amax−PCmin,Amin.


## 3. A Genetic Algorithm for BAP

Considering that the berth scheduling problem is a classical NP-hard problem with high computational complexity and is difficult to be solved by an accurate algorithm, we use a heuristic algorithm based on a genetic algorithm to obtain the solution under double objectives. The flow of the algorithm is roughly as follows: first, the representation of chromosomes is determined and the population is initialized; then, the objective functions corresponding to chromosomes are evaluated; the operations of selection, crossover, and mutation are carried out; and when the termination conditions are met, the iteration ends. The specific steps are described next.


### 3.1. Chromosome Representation and Population Initialization

For the berth scheduling problem, a chromosome represents a scheduling scheme, which includes the service berth and service order of each vessel. In this study, we use an integer to encode chromosomes, where the numbers represent the vessels and the berths are separated. An example is given in Figure1 for a problem instance with seven vessels and three berths. This chromosome indicates that in the first berth, the service is carried out in the order of vessel 1-2; in the second berth, the order is vessel 3-4-5; and in the third berth, the order is vessel 6-7.Figure 1
An example of a chromosome.In addition, due to constraint (14), the berthing positions of some chromosomes are not compliant, so we need to obtain a list to specify the berths that each vessel can choose. Then, we randomly generate 100 chromosomes that meet the constraints according to this list. The process of generating the initial population is described in the following procedures, where Bi represents the optional berth list of vessel i, and ch and chs represent a chromosome and a chromosome set, respectively.0: Fori = 1: n1: Forj = 1: m2: IfTj≥ti; Bi append j3: End4: End5: End0: SetL = {1, 2, …, n}1: Fork = 1: population2: Shuffle L3: Setch an empty chromosome with m berths4: Fori = 1: n5: Randomly choose a berth fromBLi6: appendLi to the chosen berth of ch7: End8:chs append ch9: End10: Returnchs.


### 3.2. Objective Function Evaluation

To evaluate the given chromosome, we need to calculate the values of the two objective functions. According to the model established above, to calculate the values off1 and f2, we need to obtain Cmin,AminS and Cmax,AmaxS first, using the minimum search heuristic and maximum search heuristic methods in reference [29].Minimum search heuristic (MISH) plans the arrival time and handling time of each vessel through the given time windows, which will affect the start time of the vessel, to minimize the value of total carbon emissions under the given chromosome. In this way,Cmin,AminS is calculated. The procedure is as follows:For each berthj:0: Setft0 = 01: Fori = 1: n2: Setcij = cijl3: Ifi = 1 or fti−1≤Ail; set Ai=Ail; set sti = Ai; set fti = sti + l/vi + cij4: Elseiffti−1>Aiu; set Ai=Aiu; set sti = Ai; set fti = sti + l/vi + cij5: ElseifAiu>fti−1>Ail; set Ai=fti−1; set sti = Ai; set fti = sti + l/vi + cij6: End7: End8: SetCmin = cij; Set Amin = Ai9: ReturnCmin, Amin.Similar to MISH, maximum search heuristic is used to determine the arrival time and handling timeCmax,AmaxS by the following procedure:0: Setft0 = 01: Fori = 1: n2: Setcij = ciju3: Ifi = 1 or fti−1≤Ail; set Ai=Aiu; set sti = Ai; set fti = sti + l/vi + cij4: Else; setAi=Ail; set sti = fti−1; set fti = sti + l/vi + cij5: End6: End7: SetCmax = cij; Set Amax = Ai8: ReturnCmax, Amax.


### 3.3. Pareto Front (PF) Selection and Improvement

When the genetic algorithm is used to solve the biobjective optimization problem, the concept of Pareto must be introduced. Pareto solutions are also called nondominated solutions. When there are multiple targets, due to the conflict and incompatibility between them, one solution is the best on one target and maybe the worst on other targets. While improving any objective function, these solutions that will inevitably weaken at least one other objective function are called nondominated solutions or Pareto solutions. The set of optimal solutions of a set of objective functions is called Pareto optimal set, and the surface formed by the optimal set in space is called the Pareto front. Pareto improvement, referring to a change that makes at least one target better without deteriorating any other target, is used to describe the optimization direction of this optimal set.In this study, a berth schedule is included in the Pareto optimal set if there is no other schedule that can improve both objectives at the same time. When the chromosomes of the previous generation are not eliminated after PF selection, it means that there is no Pareto improvement. The process of PF selection and improvement judgment is described in the following procedure, wherelb is the lower bound, ub is the upper bound, and ace and rce are the average and the range of carbon emission of the schedule.0: Set change = False1: Forch in ch s:2: Setlb = mish (ch); Set ub = mash (ch)3:ace append (lb + ub)/2; rce append (ub-lb)4: End5:i = 16: Whilei < |LS|7: Setj = i + 18: Whilej ≤ |LS|9: Ifacei=acej and rcei=rcej and chsi equals chsj or acei<acej and rcei≤rcej or acei≤acej and rcei<rcej10: LS = LS-{(acej,rcej,chsj)}; go to step 811: Elseifacei>acej and rcei≥rcej or acei≥acej and rcei>rcej12: Ifi < pre_size; change = True13: End14: LS = LS-{(acei,rcei,chsi)}; go to step 615: End16: Setj = j + 117: End18: Seti = i + 119: End20: Return change.


### 3.4. Crossover and Mutation

To generate new chromosomes, we perform crossover and mutation operations. We adopt the method of partial-mapped crossover, and the parent chromosomes are crossed as shown in Figure2. Since some genes will be repetitive, conflict detection needs to be carried out to repair the children’s chromosomes. A mapping relationship is established according to the exchanged two sets of genes. All conflicting genes are transformed through the mapping relationship to form a new pair of conflict-free genes, finally obtaining the repaired chromosomes. Due to the influence of the berth restriction list, we need to further adjust the chromosomes of offspring.Figure 2
An example to illustrate chromosome crossover.The crossover operation is achieved by the following procedure.0: Set L1 the array representation of parent_ch1; Set L2 the array representation of parent_ch21: Randomly choose an index lk as the cross point of L1 and L22: SetL3 = L1[1: lk] + L2[lk:]; Set L4 = L2[1: lk] + L1[lk:]3: Set L5 a copy of L3; Set L6 a copy of L4;4: Seti = 15: whilei < lk6: Forj = lk: |L5|7: ifL5i=L5j8: SetL5i=L4j; go to step 59: End10: End11: Seti = i + 112: End13: Seti = 114: whilei < lk15: Forj = lk: |L6|16: ifL6i=L6j17: SetL6i=L3j; go to step 1418: End19: End20: Seti = i + 121: End22: Return L5 and L6.The mutation operation is performed according to the two types illustrated in Figure3. Insert mutation is to randomly select a vessel and randomly insert it into any other optional position. Swap mutation is to randomly select two vessels and exchange their positions. Note that the mutated chromosomes must still meet the constraints. The chromosome after insert or swap operation needs to be checked whether the berth assigned to each vessel is an accessible berth according to the berth list in 3.1. If not, the vessel will be randomly assigned to any berth it can go to according to the list to ensure that the chromosome still meets the constraints. The adjusted chromosome enters the next iteration as the mutated offspring.Figure 3
An example to illustrate chromosome mutation.


### 3.5. Termination

When PF is not improved for 500 consecutive iterations or the CPU running time reaches 10 minutes, the algorithm ends.


## 3.1. Chromosome Representation and Population Initialization

For the berth scheduling problem, a chromosome represents a scheduling scheme, which includes the service berth and service order of each vessel. In this study, we use an integer to encode chromosomes, where the numbers represent the vessels and the berths are separated. An example is given in Figure1 for a problem instance with seven vessels and three berths. This chromosome indicates that in the first berth, the service is carried out in the order of vessel 1-2; in the second berth, the order is vessel 3-4-5; and in the third berth, the order is vessel 6-7.Figure 1
An example of a chromosome.In addition, due to constraint (14), the berthing positions of some chromosomes are not compliant, so we need to obtain a list to specify the berths that each vessel can choose. Then, we randomly generate 100 chromosomes that meet the constraints according to this list. The process of generating the initial population is described in the following procedures, where Bi represents the optional berth list of vessel i, and ch and chs represent a chromosome and a chromosome set, respectively.0: Fori = 1: n1: Forj = 1: m2: IfTj≥ti; Bi append j3: End4: End5: End0: SetL = {1, 2, …, n}1: Fork = 1: population2: Shuffle L3: Setch an empty chromosome with m berths4: Fori = 1: n5: Randomly choose a berth fromBLi6: appendLi to the chosen berth of ch7: End8:chs append ch9: End10: Returnchs.


## 3.2. Objective Function Evaluation

To evaluate the given chromosome, we need to calculate the values of the two objective functions. According to the model established above, to calculate the values off1 and f2, we need to obtain Cmin,AminS and Cmax,AmaxS first, using the minimum search heuristic and maximum search heuristic methods in reference [29].Minimum search heuristic (MISH) plans the arrival time and handling time of each vessel through the given time windows, which will affect the start time of the vessel, to minimize the value of total carbon emissions under the given chromosome. In this way,Cmin,AminS is calculated. The procedure is as follows:For each berthj:0: Setft0 = 01: Fori = 1: n2: Setcij = cijl3: Ifi = 1 or fti−1≤Ail; set Ai=Ail; set sti = Ai; set fti = sti + l/vi + cij4: Elseiffti−1>Aiu; set Ai=Aiu; set sti = Ai; set fti = sti + l/vi + cij5: ElseifAiu>fti−1>Ail; set Ai=fti−1; set sti = Ai; set fti = sti + l/vi + cij6: End7: End8: SetCmin = cij; Set Amin = Ai9: ReturnCmin, Amin.Similar to MISH, maximum search heuristic is used to determine the arrival time and handling timeCmax,AmaxS by the following procedure:0: Setft0 = 01: Fori = 1: n2: Setcij = ciju3: Ifi = 1 or fti−1≤Ail; set Ai=Aiu; set sti = Ai; set fti = sti + l/vi + cij4: Else; setAi=Ail; set sti = fti−1; set fti = sti + l/vi + cij5: End6: End7: SetCmax = cij; Set Amax = Ai8: ReturnCmax, Amax.


## 3.3. Pareto Front (PF) Selection and Improvement

When the genetic algorithm is used to solve the biobjective optimization problem, the concept of Pareto must be introduced. Pareto solutions are also called nondominated solutions. When there are multiple targets, due to the conflict and incompatibility between them, one solution is the best on one target and maybe the worst on other targets. While improving any objective function, these solutions that will inevitably weaken at least one other objective function are called nondominated solutions or Pareto solutions. The set of optimal solutions of a set of objective functions is called Pareto optimal set, and the surface formed by the optimal set in space is called the Pareto front. Pareto improvement, referring to a change that makes at least one target better without deteriorating any other target, is used to describe the optimization direction of this optimal set.In this study, a berth schedule is included in the Pareto optimal set if there is no other schedule that can improve both objectives at the same time. When the chromosomes of the previous generation are not eliminated after PF selection, it means that there is no Pareto improvement. The process of PF selection and improvement judgment is described in the following procedure, wherelb is the lower bound, ub is the upper bound, and ace and rce are the average and the range of carbon emission of the schedule.0: Set change = False1: Forch in ch s:2: Setlb = mish (ch); Set ub = mash (ch)3:ace append (lb + ub)/2; rce append (ub-lb)4: End5:i = 16: Whilei < |LS|7: Setj = i + 18: Whilej ≤ |LS|9: Ifacei=acej and rcei=rcej and chsi equals chsj or acei<acej and rcei≤rcej or acei≤acej and rcei<rcej10: LS = LS-{(acej,rcej,chsj)}; go to step 811: Elseifacei>acej and rcei≥rcej or acei≥acej and rcei>rcej12: Ifi < pre_size; change = True13: End14: LS = LS-{(acei,rcei,chsi)}; go to step 615: End16: Setj = j + 117: End18: Seti = i + 119: End20: Return change.


## 3.4. Crossover and Mutation

To generate new chromosomes, we perform crossover and mutation operations. We adopt the method of partial-mapped crossover, and the parent chromosomes are crossed as shown in Figure2. Since some genes will be repetitive, conflict detection needs to be carried out to repair the children’s chromosomes. A mapping relationship is established according to the exchanged two sets of genes. All conflicting genes are transformed through the mapping relationship to form a new pair of conflict-free genes, finally obtaining the repaired chromosomes. Due to the influence of the berth restriction list, we need to further adjust the chromosomes of offspring.Figure 2
An example to illustrate chromosome crossover.The crossover operation is achieved by the following procedure.0: Set L1 the array representation of parent_ch1; Set L2 the array representation of parent_ch21: Randomly choose an index lk as the cross point of L1 and L22: SetL3 = L1[1: lk] + L2[lk:]; Set L4 = L2[1: lk] + L1[lk:]3: Set L5 a copy of L3; Set L6 a copy of L4;4: Seti = 15: whilei < lk6: Forj = lk: |L5|7: ifL5i=L5j8: SetL5i=L4j; go to step 59: End10: End11: Seti = i + 112: End13: Seti = 114: whilei < lk15: Forj = lk: |L6|16: ifL6i=L6j17: SetL6i=L3j; go to step 1418: End19: End20: Seti = i + 121: End22: Return L5 and L6.The mutation operation is performed according to the two types illustrated in Figure3. Insert mutation is to randomly select a vessel and randomly insert it into any other optional position. Swap mutation is to randomly select two vessels and exchange their positions. Note that the mutated chromosomes must still meet the constraints. The chromosome after insert or swap operation needs to be checked whether the berth assigned to each vessel is an accessible berth according to the berth list in 3.1. If not, the vessel will be randomly assigned to any berth it can go to according to the list to ensure that the chromosome still meets the constraints. The adjusted chromosome enters the next iteration as the mutated offspring.Figure 3
An example to illustrate chromosome mutation.


## 3.5. Termination

When PF is not improved for 500 consecutive iterations or the CPU running time reaches 10 minutes, the algorithm ends.


## 4. Numerical Example

In this study, a numerical example of 20 vessels with four berths at a container port is used for simulation. The vessel information in Table3 refers to the data in reference [30]. The planning period is set to 24 hours. In this period, the vessels dynamically arrive from zero time and wait for berthing 60 nautical miles away from the port. We assume that the vessel works with a single auxiliary engine during the waiting period. The expected handling time of each vessel at different berths is assumed according to the tonnage and location of the berth, together with the number of containers of the vessel. The upper bound of the handling time window floats from 20% to 40% based on the expected handling time and is randomly generated according to a uniform distribution. The lower bound is lowered according to the same rule.Table 3
Arrival vessel data.
Vessel numberAilAiuri0ri1 (t/day)Number of containers101.50.091.720020.72.30.112.2133032.42.90.122.0420434.20.111.921054.560.091.910567.48.30.132.0632788.90.121.711289.3100.102.1857910.4110.092.01001011.512.30.082.06721112.813.60.162.08321213.915.10.082.110801314.916.30.081.84751416.417.10.111.71531517.719.30.101.8390161819.10.091.8400171919.70.121.72071820.9220.101.95901922.523.50.112.25552022.723.40.091.8369We apply the algorithm in Section4 to this example and get a Pareto set as shown in Figure 4. Each point represents a berth allocation solution, the abscissa represents the average carbon emission value of the solution, and the ordinate represents the carbon emission range value of the solution. The boundary formed by these solutions is the Pareto front.Figure 4
Pareto front.In this set of solutions, we choose the scheme with the lowest average total carbon emission as the solution to the problem. The berthing schedule is shown in Table4, including the berth and service order of each vessel. The average total carbon emission of this scheduling scheme is 65199.2 kg under the set uncertainty, and the range of carbon emission is 51609.4 kg.Table 4
Final berth schedule.
Berth 1Vessel 2Vessel 8Vessel 14Vessel 19Vessel 10Berth 2Vessel 3Vessel 11Vessel 16Vessel 20Vessel 13Berth 3Vessel 5Vessel 6Vessel 12Vessel 18Vessel 1Berth 4Vessel 4Vessel 7Vessel 9Vessel 15Vessel 17In practice, the port can select the desired berth allocation scheme in the set of solutions according to the specific needs and other considerations. For example, a port requires that the maximum carbon emission generated during the dispatching period shall not exceed 90000 kg. According to formulas (7) and (8), we know that the maximum carbon emission of a scheduling scheme, maxP, can be calculated by f1 and f2 as follows:(21)maxP=122f1+f2.At this time, the maximum carbon emission of the selected scheme is 91003.9 kg, which does not meet the carbon emission limit of the port. Therefore, it is necessary to reselect the qualified scheme on the Pareto front.The downward trend of the two objective functions is described in Figure5, in which the abscissa represents the number of iterations, and the ordinate represents the smallest objective function value in the PF obtained in each iteration. Both graphs show a downward trend on the whole, while Figure b shows a small increase. It is because that when the population number is controlled to 100 and the ranking is mainly based on f1, the solution with small f2 value of the previous generation may be deleted, increasing the smallest f2 in the PF of the next generation. Both objective functions have been greatly optimized through the heuristic algorithm.Figure 5
The downward trend of the two objective functions.
(a)(b)To evaluate the berth scheduling strategy proposed in this study, we compare the results with the other two commonly used strategies under uncertainty: the first come, first served with an early start (FCFS-S) strategy and first come, first served with early finish (FCFS-F) strategy [29]. The FCFS-S strategy means that the first-arriving vessel selects the berth that can serve it first according to the current berth state and selects the berth with a shorter handling time when the service start time is the same. Similarly, the FCFS-F strategy means that the first-arriving vessel selects the berth to leave first after the operation.The two objective function values of the solutions obtained by the three strategies are listed in Table5. The average total carbon emission of the PF solution decreased by 29.3% compared with the value of 92245.1 kg under the FCFS-S strategy and 43.4% compared with the value of 115235.7 kg under the FCFS-F strategy. The range of the total carbon emission of the PF solution decreased by 39.2% and 48.3%, respectively, compared to 84957 kg of FCFS-S and 99793 kg of FCFS-F. It can be seen that the performance of the proposed method is much better than the other two commonly used strategies, and both average and range values have been greatly optimized.Table 5
Results of three strategies.
AverageRangeFCFS-S92245.184957FCFS-F115235.799793PF solution65199.251609.4


## 5. Conclusions and Future Research

The carbon emission during vessel berthing is the main source of port carbon emissions. A good berth allocation schedule can effectively reduce the carbon emission of the port by planning the berthing process of vessels. In this study, a robust discrete allocation method under a low-carbon target has been proposed. The established model has considered the impact of uncertain arrival time and handling time on the scheduling table, which has been quantified as the maximum and minimum carbon emission of the scheduling scheme. While minimizing the total average carbon emission, the robustness of berth allocation has been taken into consideration to make the carbon emission of the scheduling scheme fluctuate in a small range. Also, this study has introduced the second objective function of the range value of carbon emission and established a hierarchical biobjective model. The maximum and minimum of the scheduling scheme have been searched by two heuristic methods. The model has been solved by a heuristic algorithm based on a genetic algorithm and applied to a problem example. The effectiveness has been illustrated by comparing the simulation results with those obtained by the FCFS-S and FCFS-F strategies.The research of this study is based on the discrete berth so that that future research will be extended to the continuous berth allocation problem. In addition, the uncertainty of arrival time and handling time considered in this study is directly modeled as a given time window. The internal variation characteristics of the uncertainty need to be further studied.



---

*Source: 5310004-2022-06-01.xml*