不同靠泊规则下的集装箱港口连续泊位与岸桥联合分配研究
Study on the joint allocation of continuous berths and quay cranes in container ports under different berthing rules

郭瑞军¹，周凯硕，张艺骞，王晚香
Guo Ruijun1, Zhou Kaishuo, Zhang Yiqian, Wang Wanxiang

（大连交通大学 交通运输工程学院，辽宁 大连116028）
(School of Traffic and Transportation Engineering, Dalian Jiaotong University, Dalian 116028, Liaoning, China).

摘　要：按照船舶先到先停原则进行港口泊位与岸桥分配容易造成船舶停滞和压货，导致泊位与岸桥利用率低,降低了港口的服务水平和竞争力。针对连续泊位布局方式下的集装箱港口泊位与岸桥联合分配问题，建立了基于船舶偏好靠泊位置、靠泊位置与起点的距离、可行岸线长度和可用岸桥数量的四种典型靠泊规则，并构建了考虑惩罚成本的多船动态到达泊位与岸桥联合分配多目标优化模型.同时，设计将四种靠泊规则考虑在内的启发式算法，利用遗传算法对模型进行求解，得出最优靠泊规则和调度方案。将该方法应用于某集装箱港口连续到港船舶的实际案例，计算不同规则下的集装箱码头泊位与岸桥联合分配模型的最优结果，结果显示:规则一，即按船舶偏好靠泊位置靠泊的规则为最优规则，最优方案中船舶停靠的时间及岸桥利用率分别为93.81457小时和68.617%。研究结论表明:按照船舶典型的靠泊方式建立四种靠泊规则是合理的.通过建立这种考虑惩罚成本的泊位与岸桥联合分配模型，能够对不同规则下的泊位与岸桥分配方案进行比选并得出最优规则和最优方案。
Abstract: The allocation of port berths and quay cranes according to the principle of first-come, first-stop is easy to cause ship stagnation and cargo pressing, resulting in low utilization rate of berths and quay cranes, and reducing the service level and competitiveness of ports. In order to solve the problem of joint allocation of container port berths and quay cranes under the continuous berth layout mode, four typical berthing rules based on the ship's preferred berthing location, the distance between the berthing position and the starting point, the feasible shoreline length and the number of available quay cranes are established, and a multi-objective optimization model for the joint allocation of berths and quay cranes for multiple ships considering the penalty cost is constructed. At the same time, a heuristic algorithm considering the four berthing rules is designed, and the genetic algorithm is used to solve the model to obtain the optimal berthing rules and scheduling scheme. The method is applied to the actual case of continuous arrival of ships in a container port, and the optimal results of the joint allocation model of container terminal berths and quay cranes under different rules are calculated, and the results show that the first rule, that is, the rule of berthing according to the ship's preferred berthing position is the optimal ruleIn the optimal scheme, the docking time and quay crane utilization rate are 93.81457 hours and 68.617%, respectively. The results show that it is reasonable to establish four berthing rules according to the typical berthing mode of ships. By establishing this joint allocation model of berth and quay crane considering the penalty cost, the allocation scheme of berth and quay crane under different rules can be compared and selected, and the optimal rules and optimal schemes can be obtained.

关键词：集装箱港口；泊位分配；岸桥调度；靠泊规则；遗传算法
Keywords: container port; berth allocation; quay crane scheduling; berthing rules; Genetic algorithms

Doi：

中图分类号：U691.3 文献标识码：A
CLC Number: U691.3 Document Identification Code: A

Research on the Joint Allocation of Continuous Berths and Shore Bridges in Container Ports under Different Berthing Rules

Guo Ruijun，Zhou Kaishuo，Zhang Yiqian，Wang Wanxiang

( School of Traffic and Transportation Engineering, Dalian Jiaotong University, Dalian 116028，China)

Abstract：According to the principle of first-come-first-served, the allocation of berths and bridges in ports is easy to cause ship stagnation and cargo pressure, resulting in low utilization rate of berths and bridges, which reduces the service level and competitiveness of ports. For the problem of joint allocation of berths and bridges in container ports under continuous berth layout, four typical berthing rules based on ships' preferred berthing position, distance between berthing position and starting point, feasible shoreline length and the number of available bridges are established, and a multi-objective optimization model of joint allocation of berths and bridges for multi-ships arriving dynamically is constructed by considering the penalty cost. At the same time, a heuristic algorithm taking the four berthing rules into account is designed, and the model is solved using genetic algorithm to derive the optimal berthing rules and scheduling scheme. The method is applied to the actual case of continuous arrival of ships in a container port to calculate the optimal results of the joint allocation model of berths and bridges in a container terminal under different rules, and the results show that: Rule 1, i.e., the rule of berthing according to the ship's preference of berthing position, is the optimal rule, and the docking time of the ship and the utilization rate of the bridges in the optimal scheme are 93.81457 hours and 68.617%, respectively. The conclusion of the study shows that it is reasonable to establish four berthing rules according to the typical berthing mode of ships. Through the establishment of this joint allocation model of berths and bridges considering the penalty cost, it is possible to compare the berths and bridges under different rules and derive the optimal rules and optimal programs.

Key words：container port; berth allocation; shore bridge scheduling; berthing rules; genetic algorithm

0 引言
0 Introduction

集装箱港口是国际供应链上的重要衔接点，它有着资源集中和外部环境繁复的特征。港口进出口作业系统主要包括泊位的分配和岸桥的配置两个方面，泊位与岸桥分配是否正确将会影响港口的作业效率.因其受到投资规模和地理空间的约束，所以导致泊位和岸桥成为港口运营规模中十分缺少的资源，其调度方案直接影响到码头的运营效率和运营效果。因此，如何分配泊位、如何为船舶配置合理的岸桥及数量、如何减少船舶在港时间等，这些都是港口集装箱码头运营过程中值得深思的问题。
Container ports are an important connection point in the international supply chain, which has the characteristics of concentrated resources and complex external environment. The port import and export operation system mainly includes the allocation of berths and the configuration of quay cranes, and whether the allocation of berths and quay cranes is correct will affect the operation efficiency of the portDue to the constraints of investment scale and geographical space, berths and quay cranes have become a very scarce resource in the scale of port operation, and their scheduling scheme directly affects the operational efficiency and effectiveness of the terminal. Therefore, how to allocate berths, how to allocate reasonable quay cranes and quantities for ships, and how to reduce the time of ships in port are all issues worth pondering in the operation of port container terminals.

目前，我国不同集装箱港口在船舶靠港的信息水平上差距较大，大部分的泊位和岸桥是基于船舶先到先停的原则进行分配的。根据以往的经验对船舶进行泊位和岸桥的分配有时会导致船舶停滞和压货的状况，与此同时会在很大程度上降低集装箱港口的服务水平以及竞争力。所以怎样制定更好的靠泊规则以便于集装箱港口管理者更好的协调泊位与岸桥之间的联合分配问题显得尤为重要。
At present, there is a large gap between different container ports in China in terms of the information level of ship calling, and most of the berths and quay cranes are allocated based on the principle of first-come, first-served. Based on past experience, the allocation of berths and quay cranes to ships can sometimes lead to stalled and crushed vessels, while at the same time reducing the service level and competitiveness of container ports to a large extent. Therefore, it is particularly important to formulate better berthing rules so that container port managers can better coordinate the joint allocation between berths and quay cranes.

一般来说，泊位分配有两种类型：一种是离散式泊位，另一种是连续型泊位。基于不同的目标以及约束条件，该问题已经变成了各种各样不同的组合优化问题。杨春霞和王诺^[1]总体上分析船舶平均在港时间、码头生产成本与安全质量三部分因素搭建了多目标泊位分配优化模型。秦进等^[2]基于时间窗约束建立泊位分配模型，同时利用模拟退火算法求解模型。与此同时研究时间窗约束对泊位分配影响的还有张旻媛^[3]，利用蚁群算法把最小船舶等待时间作为目标求解模型。欧阳玲萍等^[4]分析了连续型泊位和岸桥联合调度问题，搭建了非线性规划模型，并使用改进的蚁群算法进行求解。余刘海，庞洪静等^[5]不考虑靠泊时间与离泊时间的影响，分析了连续型泊位与岸桥协同调度问题，同时提出了启发式算法。
In general, there are two types of berth allocations: one is a discrete berth and the other is a continuous berth. Based on different goals and constraints, the problem has become a variety of combinatorial optimization problems. Yang Chunxia and Wang Nuo ^[1] generally analyzed the three factors of average ship time in port, terminal production cost, safety and quality, and built a multi-objective berth allocation optimization model. Qin et al. ^[2] established a berth allocation model based on the time window constraint, and used the simulated annealing algorithm to solve the model. At the same time, Minyuan Zhang [3] also studied the influence of time window constraints on berth allocation, using the ant colony algorithm to solve the model with the minimum ship waiting time as the goal. Ouyang Lingping et al. ^[4] analyzed the problem of joint scheduling of continuous berths and quay cranes, built a nonlinear programming model, and used the improved ant colony algorithm to solve the problem。 Yu Liuhai, Pang Hongjing et al^{. [5]} analyzed the problem of cooperative scheduling of continuous berths and quay cranes without considering the influence of berthing time and berthing time. At the same time, a heuristic algorithm is proposed.

码头岸桥作业包括岸桥的配置和调度。研究人员对关于岸桥的优化情况做出了研究，研究问题包括单船情况和多船情况。李晨等^[6]针对单个待卸船舶，全方面分析了甲板约束条件和岸桥碰撞影响因素，提出了两个考虑初始解的启发式规则，目的在于分析单个船舶装卸作业的岸桥调度问题，与此同时针对任务量、问题规模与岸桥特性等设计了几个算例。乐美龙等^[7]针对任务优先级、时间窗等影响因素分析了泊位分配问题。曾庆城和高宇^[8]采用遗传算法分析单船岸桥调度问题，验证了遗传算法求解该问题的可行性。Peterkofsky和Daganzo^[9]整体分析了多船条件下的岸桥配置问题，同时利用分支定界法求解目标问题。初良勇等^[10]通过考虑岸桥双吊运小车的衔接作业和自动导引车路径选择，建立了自动化码头岸桥、自动导引车与自动化轨道吊的协同调度优化的非线性混合整数规划模型。Moccia等^[11]利用分支定界法分析多船岸桥调度问题，分析了集装箱任务的优先级问题与岸桥作业间互不干涉的约束条件，但是对于大规模的实例来说，不适合用这种算法进行求解。
Quay crane operations include the configuration and scheduling of quay cranes. The researchers studied the optimization of quay cranes, and the research questions included single and multi-vessel situations. Li et al. ^[6] analyzed the deck constraints and the influencing factors of quay crane collision in all aspects for a single ship to be discharged, and proposed two heuristic rules considering the initial solutionThe purpose of this paper is to analyze the quay crane scheduling problem of a single ship loading and unloading operation, and several examples are designed for the task volume, problem scale and quay crane characteristics. Le Meilong et al. ^[7] analyzed the problem of berth allocation according to the influencing factors such as task priority and time window. Zeng Qingcheng and Gao Yu ^[8] used genetic algorithm to analyze the single-ship quay crane scheduling problem, and verified the feasibility of genetic algorithm to solve the problem. Peterkofsky and Daganzo ^[9] analyzed the quay crane configuration problem under multi-ship conditions as a whole, and used the branch delimitation method to solve the target problem. Chu Liangyong et al^{. [10]} established a nonlinear mixed integer programming model for the collaborative scheduling optimization of automated quay cranes, AGVs and automated rail cranes by considering the connection operation of the quay crane double crane and the path selection of the AGV. Moccia et al. ^[11] used the branch demarcation method to analyze the scheduling problem of multi-ship quay cranes, and analyzed the priority problem of container tasks and the constraints of non-interference between quay crane operationsHowever, for large-scale instances, this algorithm is not suitable for solving.

对泊位岸桥联合配置优化的研究分为两种，一种是离散泊位下的泊位岸桥联合配置优化研究，另一种是连续泊位下的泊位岸桥联合配置优化研究。Liang等^[12]把最小船舶在港时间与最小岸桥移动次数作为目标，并使用遗传算法求解模型，之后通上海港码头对模型与算法进行实例验证。张海永和严伟^[13]分析了离散泊位下的泊位岸桥联合优化问题，根据泊位岸桥的调用规则，搭建了基于滚动式计划下的动态模型。
There are two kinds of research on the optimization of the joint configuration of berths and cranes, one is the optimization of the joint configuration of berths and cranes under discrete berths, and the other is the optimization of the joint configuration of berths and cranes under continuous berths. Liang et al. ^[12] took the minimum ship time in port and the minimum number of quay crane movements as the goals, and used genetic algorithm to solve the modelAfter that, the model and algorithm were verified by example through the Shanghai port terminal. Zhang Haiyong and Yan Wei ^[13] analyzed the joint optimization problem of berth quay cranes under discrete berths, and built a dynamic model based on rolling planning according to the call rules of berth quay cranes。

相较于离散泊位，连续泊位可以更好的运用定量的岸线资源，却也加大了成本，包括靠泊成本与引航等人工成本。郑红星等^[14]-[15]考虑潮汐因素，分析了离散与连续泊位中泊位分配与岸桥调度集成优化问题，把最小船舶在港作业成本作为目标，搭建了线性规划模型，同时采用多阶段的改进遗传算法求解模型。焦小刚等^[16]基于泊位疏浚条件分析了泊位分配与岸桥调度问题，把最小计划期内船舶周转时长作为目标，搭建了整数线性规划模型，同时对此提出了相应的启发式算法。蒋美仙^[17]将集卡作业面和作业线相结合模式应用于模型构建过程，以计划期内所有到港船舶总费用最少为目标函数建立了连续泊位—岸桥—集卡调度模型，实现了泊位、岸桥和集卡的集成调度。针对此模型进行遗传算法的设计和编程求解，并通过求解结果得到了相对最优的调度方案。Birger^[18]在连续泊位的泊位优化问题中加入岸桥超时作业的惩罚、船舶偏离喜好泊位的惩罚和岸桥平移的惩罚系数，把最小化惩罚值作为目标函数，基于船舶的入泊优先级，同时采用基于滚动时间窗的遗传算法求解模型。
Compared with discrete berths, continuous berths can make better use of quantitative shoreline resources, but they also increase costs, including berthing costs and labor costs such as pilotage. Zheng Hongxing et al^{. [14]-[15]} considered tidal factors,The integrated optimization problem of berth allocation and quay crane scheduling in discrete and continuous berths is analyzed, and a linear programming model is built with the minimum cost of ship operation in port as the goal, and the multi-stage improved genetic algorithm is used to solve the model. Jiao Xiaogang et al. ^[16] analyzed the berth allocation and quay crane scheduling problems based on the berth dredging conditions, and built an integer linear programming model with the minimum planning period of ship turnover time as the goal At the same time, a corresponding heuristic algorithm is proposed. Jiang Meixian ^[17] applied the combination of truck operation face and operation line to the model construction process, and established a continuous berth-quay crane-container truck scheduling model with the minimum total cost of all ships arriving at the port during the planning period as the objective function. The integrated scheduling of berths, quay cranes and container trucks has been realized. The genetic algorithm is designed and programmed to solve this model, and the relatively optimal scheduling scheme is obtained through the solution results. Birger ^[18] added the penalty of overtime operation of the quay crane, the penalty of the ship deviating from the preferred berth, and the penalty coefficient of the translation of the quay crane to the berth optimization problem of continuous berths, and took the minimization penalty value as the objective function. Based on the berthing priority of the ship, the genetic algorithm based on the rolling time window was used to solve the model.

在研究连续泊位方式下的泊位与岸桥联合配置优化时，大多数学者仅以在港时间最小及船舶在港移动次数最少来实现泊位与岸桥的联合分配。而实际上泊位与岸桥的联合分配还需要考虑船舶装卸货物是否逾期以此来支付一定的惩罚费用，故本文在以往研究的基础上引入惩罚成本以得到最优的船舶靠泊规则及更合理的泊位与岸桥分配方案。
When studying the optimization of the joint configuration of berths and quay cranes under the continuous berth mode, most scholars only realize the joint allocation of berths and quay cranes with the minimum time in port and the minimum number of ship movements in port. In fact, the joint allocation of berths and quay cranes also needs to consider whether the ship loading and unloading cargo is overdue to pay a certain penalty cost, so this paper introduces the penalty cost on the basis of previous research to obtain the optimal berthing rules and a more reasonable berth and quay crane allocation scheme.

面对集装箱港口泊位分配与岸桥联合调度问题的复杂性，本文的创新点在于：
In the face of the complexity of the problem of container port berth allocation and quay crane joint scheduling, the innovation of this paper lies in:

本文在原有研究的基础上加入了惩罚成本，建立了一个以船舶在港时间、生产成本和惩罚成本最小为目标，并考虑多艘船舶动态到达的多目标泊位与岸桥联合分配模型，相对于以往的单目标优化模型来说，此模型有着更好的适用性。
Based on the original research, this paper adds penalty cost, and establishes a multi-objective berth and quay crane joint allocation model with the goal of minimizing the ship's in-port time, production cost and penalty cost, and considering the dynamic arrival of multiple ships, which has better applicability than the previous single-objective optimization model.

基于先到先服务的原则，结合船舶现有的实践靠泊经验以及港口已有的船舶靠泊方式，根据船舶偏好靠泊位置、靠泊位置与起点的距离、可行岸线长度利用率、可用岸桥数量等因素建立了四种独立的靠泊规则。
Based on the principle of first-come-first-served service, combined with the existing practical berthing experience of ships and the existing berthing methods of ships in ports, four independent berthing rules were established according to the preferred berthing location of the ship, the distance between the berthing position and the starting point, the utilization rate of the feasible shoreline length, and the number of available quay cranes.

将启发式靠泊规则与遗传算法相结合，使用改进遗传算法求解目标模型。相较于传统的遗传算法，将靠泊规则作为启发式规则嵌入目标模型，可以在保证计算精确度的同时，缩短计算时间，提高计算效率。
The heuristic berthing rules are combined with the genetic algorithm, and the improved genetic algorithm is used to solve the target model. Compared with the traditional genetic algorithm, the berthing rule is embedded into the target model as a heuristic rule, which can shorten the calculation time and improve the calculation efficiency while ensuring the calculation accuracy.

1 问题描述
1 Problem Description

码头前沿作业区的泊位分配和岸桥调度是集装箱码头作业的一个重要过程，但泊位和岸桥的资源是有限的，为了让船舶较快地完成装卸作业任务，从而让船方更加满意，需要对其安排合理的泊位岸桥分配方案。一般除去物理上必须离散的泊位外，我国的泊位是具有较长岸线的^[19]，根据离散情况分布的多泊位形式，离散泊位并未考虑岸线或泊位的连贯性。同时经过调查发现，连续泊位有着很高的经济收益，能够减少船舶平均在港时间。因此，为了更好地利用现有的泊位，本研究重点讨论连续型布局这一泊位布局方式。
Berth allocation and quay crane scheduling in the forward operation area of the terminal is an important process of container terminal operation, but the resources of berths and quay cranes are limited, in order to allow ships to complete the loading and unloading tasks faster, so as to make the ship more satisfiedIt is necessary to arrange a reasonable berth quay crane allocation scheme. Generally speaking, except for the berths that must be physically discrete, the berths in China are multi-berths with a long coastline ^[19], which are distributed according to the discrete situationDiscrete berths do not take into account the continuity of the shoreline or berths. At the same time, the survey found that continuous berths have high economic benefits and can reduce the average time of ships in port. Therefore, in order to make better use of the existing berths, this study focuses on the continuous layout of berths.

可以将集装箱船舶靠泊的岸线看作是一条连续的线段，而本研究的重点是连续型泊位布局方式下的分配问题，所以集装箱船舶能够任意随机选取靠泊位置进行停泊作业，这样的作业方式不仅增加了船舶停靠的自由空间而且能够有效地利用泊位空间资源，进而提升港口的作业效率。鉴于这种泊位选择的动态随机性，怎样制定合适的靠泊规则，联合和规整集装箱港口泊位岸桥分配系统，对集装箱码头的有序运行起着重要作用。
The shoreline of container ships berthing can be regarded as a continuous line segment, and the focus of this study is on the allocation of berths under the continuous berth layout mode, so container ships can randomly select berthing locations for berthing operationsThis operation mode not only increases the free space for ships to dock, but also can effectively use berth space resources, thereby improving the operation efficiency of the port. In view of the dynamic randomness of berth selection, how to formulate appropriate berthing rules and combine and standardize the quay crane allocation system of container port berths plays an important role in the orderly operation of container terminals。

根据不同靠泊规则，制定泊位与岸桥联合分配计划，旨在解决为到达的船舶分配停泊位置和停泊时间的问题，以及合理分配岸桥为对应船舶进行具体任务。船舶靠泊时的岸桥位置及时间如图1所示: 横坐标是靠泊的岸线位置，纵坐标是靠泊时间，每个矩形指一艘船舶的靠泊计划，矩形长是船舶的长度，矩形宽是作业时间，宽度越小表示作业时间越短。按照靠泊位置、靠泊时间、船长及作业时间四个因素来明确船舶所占的面积，把泊位分配问题转化成时间与空间的二维图，依据以上要素可以找到任一矩形(集装箱船)的信息分布。最后，再针对四种靠泊服务规则，基于先到先服务的原则根据优先权大小对船舶靠泊服务顺序做出调整，然后在较优的可行泊位分配方案上完成岸桥分配调度，以此得到泊位和岸桥的联合分配方案。
According to different berthing rules, the joint allocation plan of berths and quay cranes is formulated, which aims to solve the problem of allocating berthing places and berthing times for arriving ships, as well as reasonably allocating quay cranes to carry out specific tasks for corresponding ships. The position and time of the quay crane when the ship is berthed are shown in Figure 1: the abscissa is the position of the shoreline of berthing, the ordinate is the berthing time, each rectangle refers to the berthing plan of a ship, and the length of the rectangle is the length of the ship, the width of the rectangle is the job time, and the smaller the width means the shorter the job time. According to the four factors of berthing location, berthing time, ship length and operation time, the area occupied by the ship is clarified, and the berth allocation problem is transformed into a two-dimensional diagram of time and space) information distribution. Finally, according to the four berthing service rules, the order of ship berthing services is adjusted according to the priority based on the principle of first-come-first-served service, and then the quay crane allocation and scheduling is completed on the optimal feasible berth allocation schemeto obtain a joint allocation scheme for berths and quay cranes.

图1 靠泊的岸线位置-时间坐标系示意图
Fig.1. Schematic diagram of the shoreline location-time coordinate system of berthing

Fig.1 Berthing shoreline position - time coordinate diagram

2 数学模型
2 Mathematical model

2.1 模型假设
2.1 Model Assumptions

(1) 进行泊位分配计划时有些船舶还未到港，每艘船舶必须且只能靠泊一次，不考虑船舶靠泊后的移泊情况^[20];
(1) If some ships have not yet arrived at the port at the time of the berth allocation plan, each ship must and can only berth once, regardless of the berthing situation after berthing [^20];

(2) 每台岸桥工作效率相同，且装卸过程中不允许暂停; 每台岸桥只有服务完当前的集装箱船舶装卸的任务后，才能服务其他船舶;
(2) The working efficiency of each quay crane is the same, and it is not allowed to be suspended during loading and unloading; Each quay crane can only serve other ships after serving the current task of loading and unloading container ships;

(3) 岸桥在同一水平轨道上，依次进行编号排列。即在坐标轴上从左向右依次编号排列;
(3) The quay cranes are numbered on the same horizontal track. That is, they are numbered and arranged in order from left to right on the coordinate axis;

(4) 每艘集装箱船舶拥有各自的船舶尺寸、货物装卸量、最大岸桥数及最小岸桥数; 且可以工作的必要条件是，可用岸桥数达到最小岸桥数时才可工作;
(4) Each container ship has its own ship size, cargo handling capacity, maximum number of quay cranes and minimum number of quay cranes; And the necessary condition for work is that the number of available quay cranes can only work when the minimum number of quay cranes is reached;

(5) 码头岸线的水质深度能够达到所有到港集装箱船舶的吃水深度要求;
(5) The water quality depth of the quay shoreline can meet the draft requirements of all container ships arriving at the port;

(6) 不考虑由船舶技术或集装箱货物集散延误等情况造成的服务时间延长;
(6) Extension of service time due to delays in the technical or container cargo distribution of the vessel is not taken into account;

(7) 每艘船舶都有一个最优的靠泊位置，即偏好靠泊位置^[21];
(7) Each ship has an optimal berthing position, i.e., a preferred berthing position ^[21];

(8) 船舶的装卸货物量和码头作业效率决定船舶的装卸时间;
(8) The loading and unloading volume of the ship and the efficiency of the terminal operation determine the loading and unloading time of the ship;

(9) 若船舶分配的岸桥不止一台，则它分配的岸桥一定相邻连续且不能相互跨越。
(9) If the ship is assigned more than one quay crane, the quay cranes assigned to it must be adjacent and continuous and cannot cross each other.

2.2 靠泊规则
2.2 Berthing Rules

结合船舶现有的实践靠泊经验以及港口已有的船舶靠泊方式，根据船舶偏好靠泊位置、靠泊位置与起点的距离、可行岸线长度利用率、可用岸桥数量等因素建立了四种独立的靠泊规则^[22]，分别是：
Based on the existing practical berthing experience of ships and the existing berthing methods of ports, four independent berthing rules were established according to factors such as the preferred berthing location of the ship, the distance between the berthing position and the starting point, the utilization rate of the feasible shoreline length, and the number of available quay ^{cranes [22].}They are:

(1) 规则一：集装箱船舶进行靠泊计划时，在其可行岸线内靠泊，优先选择离偏好位置最近的，且其靠泊位置每次仅选择一个。
(1) Rule 1: When a container ship plans to berth, it shall berth within its feasible shoreline, and give priority to the nearest preferred location, and only one berthing position shall be selected at a time.

(2) 规则二：集装箱船舶进行靠泊计划时，在其可行岸线内，每艘集装箱船舶优先选择离起点最近的靠泊位置。
(2) Rule 2: When a container ship carries out a berthing plan, within its feasible shoreline, each container ship shall give priority to the nearest berthing position to the starting point.

(3) 规则三：集装箱船舶进行靠泊计划时，在其可行岸线内靠泊位置优先选择最短可用空闲岸线。
(3) Rule 3: When a container ship makes a berthing plan, it shall give priority to the shortest available free shoreline at the berthing position within its feasible shoreline.

(4) 规则四：集装箱船舶进行靠泊计划时，在其可行岸线内优先选择岸桥数量足够的靠泊位置的基础上，再选择离偏好位置最近，且靠泊位置每次仅选择一个。
(4) Rule 4: When a container ship makes a berthing plan, it shall give priority to the berthing position with a sufficient number of quay cranes within its feasible shoreline, and then select the nearest preferred positionand select only one berthing location at a time.

规则一为船舶优先选择偏好位置最近的位置靠泊，也是船舶到达港口最常用的一种靠泊方式，因偏离偏好位置靠泊会产生额外的运输成本;规则二为船舶优先选择离起点最近的靠泊位置靠泊，更适用于数量较少的船舶到达且起点可用岸线较长的港口，这样的靠泊方式会造成到港船舶集中在起点附近;规则三为船舶在港口靠泊时优先选择最短可用空闲岸线靠泊，这样的靠泊方式能够提升港口可用空闲岸线的利用效率，从而为大型船舶的停靠预留出更大的空间;规则四为船舶在优先选择岸桥数量足够靠泊位置的基础上，再选择离偏好位置最近的位置靠泊，岸桥数量是否充足直接反映了岸桥的作业时间，而岸桥作业时间决定船舶货物的装卸是否逾期从而产生一定的惩罚费用。在原有约束条件的基础上，分别将以上描述的四种规则带入进行四次编程，得到总目标约束。
Rule 1 is that ships preferentially choose the nearest preferred position to berth, which is also the most commonly used berthing method for ships to arrive at the port, and additional transportation costs will be incurred due to berthing from the preferred position; Rule 2 is that ships should give priority to berthing at the nearest berthing location from the starting point, which is more suitable for ports where a small number of ships arrive and the starting point has a long available shoreline, which will cause the arriving ships to be concentrated near the starting point; Rule 3 is to give priority to the shortest available free shoreline berthing when ships berthing at the port, which can improve the utilization efficiency of the available free shoreline of the port, thereby reserving more space for large ships to dock; Rule 4 is that on the basis of giving priority to the number of quay cranes and sufficient berthing positions, the ship will choose the nearest position to berth, and whether the number of quay cranes is sufficient directly reflects the operation time of the quay cranesThe quay crane operation time determines whether the loading and unloading of the ship's cargo is overdue, resulting in a certain penalty cost. On the basis of the original constraints, the four rules described above are brought into the four times of programming to obtain the total goal constraints.

2.3 参数说明
2.3 Parameter Description

,,船舶序号,;
,,Ship serial number,;

,,岸桥序号,;
,,quay crane serial number,;

,时间,(h：min);
,Time,(h:min);

,码头的岸线长度,(m);
, the shoreline length of the wharf, (m);

,集装箱船舶k的长度,包括水平安全预留长度,
, the length of the container ship k, including the horizontal safety reserve length,

(m),;

,集装箱港口码头配置的总岸桥数目;
, the total number of quay cranes configured at container port terminals;

,抵港的集装箱船舶总数目;
, the total number of container ships arriving at Hong Kong;

,计划期内预到港集装箱船舶集合，,,;
,Consolidation of pre-arrival container ships during the planning period,,,;

,离散化后时间段的集合,,;
,set of discretized time periods,,;

,集装箱船舶k的到港时间(h：min),;
, the arrival time of the container ship k (h: min),;

,集装箱船舶k的实际开始工作时刻(h：min), ;
, the actual start time of the container ship k (h:min), ;

,集装箱船舶k的期望离港时刻(h：min),;
, the expected departure time of the container ship k (h:min),;

,集装箱船舶k的实际离港时刻(h：min),;
,The actual departure time of the container ship K (h:min),;

,船舶在时刻的岸桥船舶间移动次数, ,;
, the number of ship movements between quay crane ships at the moment, ,;

,集装箱船舶k的装卸作业量(TEU),;
, Loading and unloading operations (TEU) of container ships k,;

,集装箱船舶k的靠泊位置,;
, the berthing position of the container ship K,;

,集装箱船舶k的最优靠泊位置,;
, the optimal berthing position of the container ship K,;

,集装箱船舶k的靠泊顺序,;
, berthing sequence of container ship K,;

,集装箱船舶k分配的岸桥数目,;
, the number of quay cranes allocated by container ships k,;

,单位岸桥的工作效率(TEU/h);
, the working efficiency of the quay crane per unit (TEU/h);

,岸桥干扰指数,g<1;
,Quay crane interference index,g<1;

,集装箱船舶k作业任务延迟完工的惩罚系数,;
, penalty coefficient for delayed completion of container ship K operation task,;

,集装箱船舶k所需的最少岸桥数,;
, the minimum number of quay cranes required for container ships k;

,集装箱船舶k可以承载的最多岸桥数,;
, the maximum number of quay cranes that can be carried by container ship k,;

,当集装箱船舶偏离偏好靠泊位置时,单位距离单箱额外运输成本(元/TEU·m);
When the container ship deviates from the preferred berthing position, the additional transportation cost per unit distance of a single container (yuan/TEU ··);

,每个岸桥每小时装卸成本(元/岸桥·h);
, the hourly loading and unloading cost of each quay crane (RMB/quay crane ·h);

,图1靠泊的岸线位置所在的坐标轴;
, the coordinate axis of the shoreline position of the berthing in Figure 1;

,如果船舶i靠泊在船舶k的左侧,,否则为0,;
, if ship i is berthed on the left side of ship k, otherwise it is 0,;

,图1靠泊的时间所在的坐标轴;
, the coordinate axis of the time of berthing in Figure 1;

,如果船舶i在船舶k之前靠泊,,否则为0,;
, if ship i is berthed before ship k, otherwise it is 0,;

,如果t时刻岸桥q为船舶k服务则为1,否则为0,;
, 1 if the quay crane q at time t serves the ship k, 0 otherwise, ;

,一个极大值。
, a maximum.

2.4 考虑惩罚成本的联合优化模型
2.4 Joint optimization model considering penalty costs

在对集装箱港口连续型泊位与岸桥联合分配的研究中王洪岩等^[23]设置了以最小化所有集装箱船舶的在港时间为目标的单目标模型，与此同时以所有集装箱船舶的在港时间为目标构建模型进行研究的还有焦小刚等^[24]，二者的目标函数相同，如下所示：
In the study of the joint allocation of continuous berths and quay cranes in container ports, Wang Hongyan et al. ^[23] set up a single-objective model with the goal of minimizing the arrival time of all container ships, and at the same time, Jiao Xiaogang et al. also constructed a model with the goal of the arrival time of all container ships^[24], the objective function of both is the same, as follows:

  (1)  基于已有模型的目标函数，本模型引入了惩罚成本，在船舶在港时间、船舶移动次数两者的基础上，将船舶移动次数相关函数优化为生产成本函数并建立了一个考虑惩罚成本的多艘船舶动态到达泊位与岸桥联合分配的多目标数学模型。
(1) Based on the objective function of the existing model, the model introduces penalty cost, which is based on the time of the ship in port and the number of ship movementsThe correlation function of ship movements is optimized into the production cost function, and a multi-objective mathematical model is established for the dynamic arrival of multiple ships at berths and the joint allocation of quay cranes considering the penalty cost.

2.4.1 改进模型的目标函数
2.4.1 Improve the objective function of the model

  (2)

  (3)

  (4)

  (5)

模型说明：目标函数式(2)为初始的总目标函数，表示泊位和岸桥分配总成本最小化，包括在港总时间，生产成本以及惩罚成本;式(3)表示船舶总在港时间;式(4)表示集装箱港口的生产成本;式(5)表示当装卸任务逾期完成时，集装箱港口的惩罚费用。
Model description: Equation (2) is the initial total objective function, which means that the total cost of berth and quay crane allocation is minimized, including the total time in port, production costs as well as penalty costs; Eq. (3) indicates the total time the vessel has been in port; Eq. (4) represents the production cost of the container port; Eq. (5) indicates the penalty fee of the container port when the loading and unloading task is overdue.

2.4.2 改进模型的约束条件
2.4.2 Improve the constraints of the model

  (6)

  (7)

  (8)

  (9)

  (10)

  (11)

  (15)

  (16)

式(6)说明同一岸桥只有在一艘船完成作业后才能服务其他船;式(7)~式(9)确保在占据港口码头岸线与在港时间内任何两艘船舶不会出现交叉;式(10)确保每艘船舶到港后再停靠岸线;式(11)说明船舶的作业完成时刻与靠泊时刻的联系，船舶的装卸箱量和码头作业效率决定作业时间;式(12)确保岸桥不可以交叉，即同一艘船分配的岸桥是连续相邻的^[16];式(13)说明当可供服务的岸桥数在船舶所需的最小和最大岸桥数之间时，岸桥才开始作业;式(14)说明在船舶间岸桥不允许交叉作业;式(15)说明任一时刻在泊船舶所用岸桥总数不能大于Q;式(16)确保任一船舶靠泊在可行的岸线。
Eq. (6) illustrates that the same quay crane can only serve other ships after one ship has completed its operation; Eq. (7) ~ Eq. (9) ensures that no two ships will cross the shoreline of the port terminal and during the time they are in port; Equation (10) ensures that each ship docks at the shoreline after arriving at the port; Equation (11) illustrates the connection between the completion time of the ship's operation and the berthing time, and the loading and unloading volume of the ship and the efficiency of the wharf operation determine the operation time; Eq. (12) ensures that the quay cranes cannot be crossed, i.e., the quay cranes assigned to the same ship are continuously adjacent ^[16]; Eq. (13) illustrates that the quay crane will only start operation when the number of quay cranes available for service is between the minimum and maximum number of quay cranes required by the vessel; Equation (14) shows that cross operations are not allowed on the quay bridge between ships; Eq. (15) shows that the total number of quay cranes used by ships at any one time shall not be greater than Q; Eq. (16) ensures that any ship is berthed at a feasible shoreline.

3 算法设计
3. Algorithm design

遗传算法由适者生存、劣者淘汰的生存机制，生成初始种群后，逐代演化生成最优解，它在全局搜索及全局优化上有很好的优势。可是针对泊位与岸桥集成调度的问题，由于问题计算的复杂性，采用运筹学方法很难在合理的时间内求出可行解。不过，启发式算法能够解决这个问题，它能够相对迅速地求出一些大型问题的可行解。然而，由于它是基于经验和判断，针对有关问题可以生成较好的解，但不能确保生成最优解。所以综合考虑，本文将通过遗传算法与启发式算法相结合，来处理集装箱港口泊位-岸桥的调度优化问题。
The genetic algorithm generates the optimal solution from generation to generation after the survival mechanism of survival of the fittest and elimination of the inferior, which has good advantages in global search and global optimization。 However, due to the complexity of the problem of integrated scheduling of berths and quay cranes, it is difficult to find a feasible solution in a reasonable time by using operations research methods. However, heuristics can solve this problem by finding feasible solutions to some large problems relatively quickly. However, because it is based on experience and judgment, it is possible to generate a good solution for the problem, but it is not guaranteed to generate an optimal solution. Therefore, this paper will use the combination of genetic algorithm and heuristic algorithm to deal with the scheduling optimization problem of container port berth-quay crane.

3.1 不同靠泊规则下的启发式算法构造
3.1 Heuristic algorithm construction under different berthing rules

根据问题描述中叙述的四种多船靠泊位置的服务规则以及数学模型中叙述的约束条件，建立启发式算法。该算法的主要步骤如下：
According to the service rules of the four multi-ship berthing positions described in the problem description and the constraints described in the mathematical model, a heuristic algorithm is established. The main steps of the algorithm are as follows:

step1: 计划周期开始时，记录到港船舶信息。开始时间为0，靠泊时间是靠泊时和开始时间之差。船舶的编号是它预期到港时间的顺序，第一艘船舶抵港后进行随机靠泊，配给它随机产生的岸桥数量进行作业，然后直接转到step6，之后再转到step2。
Step1: At the beginning of the planning cycle, record the ship information at the port. The start time is 0, and the berthing time is the difference between the time of berthing and the start time. The ship's number is the order of its expected arrival time, the first ship is berthed randomly upon arrival, assigned to its randomly generated quay crane number for operation, and then goes straight toStep6, then go to Step2.

step2: 在第一艘船舶到港停泊后，后面要到港船舶的顺序根据先到先服务和有优先权的服务两个方面进行确定，比如从第二艘到港船舶算起，若两艘船舶到港时间很接近(≤15min)，比较两艘船舶的优先级别，假如船舶k的优先级别至少小船舶k+1两个等级，则船舶k在船舶k+1之后分配。找寻船舶k靠泊时在码头工作的船舶。若没有一艘在作业的船舶，则随机安排一个靠泊位置，在它中心随机生成对应岸桥数量进行服务，转到step6，记录能够服务船舶的岸桥集合;反之测出各个空闲区间的长度和其中空闲的岸桥数，记录各个区间相邻船舶服务的岸桥编号，之后转到step3。
step 2: After the first vessel arrives at the port, the order of the subsequent ships to be docked is determined according to two aspects: first-come, first-served and priority service. For example, if the arrival time of the two ships is very close (≤15min) from the second ship, the priority of the two ships is compared, if the priority class of ship K is at least two classes of small ship K+1, then ship K is assigned after ship K+1. Look for ships that work at the dock when ship K is berthed. If there is no ship in operation, a berthing position will be randomly arranged, and the corresponding number of quay cranes will be randomly generated in the center of it for service, and it will be transferred to STEP6, which records the collection of quay cranes capable of servicing vessels; On the contrary, the length of each free section and the number of free quay cranes in it are measured, and the quay crane number of adjacent ships in each section is recorded, and then transferred to the STEP3。

step3: 当空闲区间的长度满足船舶靠泊需要的最小长度，同时空闲岸桥的数量满足需要的最小岸桥数量，则靠泊规则选择空闲岸线进行靠泊，并且转到step4; 反之延迟靠泊时间三十分钟，即：，之后再寻找新的靠泊位置，再转到step2。
s tep3: when the length of the idle section meets the minimum length required for berthing the ship and the number of idle quay cranes meets the minimum number of quay cranes required, Then the berthing rule selects the idle shoreline for berthing, and turns to STEP4; Otherwise, the berthing time is delayed by 30 minutes, i.e., after which a new berthing position is found and then transferredstep2。

step4: 更新染色体中第(k+N)个基因靠泊位置与第(k+2N)个基因岸桥数目及船舶k的靠泊时刻，记录能为船舶k服务的岸桥集合，并用实际分配的岸桥数目计算离港时间，之后转到step5。
S tep4: update the berthing position and the first (k+N) gene in chromosomes(k+2N) the number of quay cranes of genes and the berthing time of ship k, and record the set of quay cranes that can serve ship kThe departure time was calculated using the actual number of quay cranes allocated, after which it was transferred to STEP5.

step5: 令k=k+1，继续分配下一艘船舶，转到step2，直到所有船舶都已分配。
step5: let k=k+1, continue to assign the next ship, go tostep2 until all ships have been allocated.

step6: 根据所需岸桥数的基偶决定船舶对应的岸桥编号。当岸桥数是奇数时，先确定最中间的编号，再分三种情形讨论：
step6: The ship's quay crane number is determined according to the base couple of the required number of quay cranes. When the number of quay cranes is an odd number, the middle number is determined first, and then it is discussed in three situations:

(1) 理论最小编号被左侧船舶占用，则从第一个岸桥开始向右取;
(1) If the theoretical minimum number is occupied by the ship on the left, it will be taken from the first quay crane to the right;

(2) 理论最大编号被右侧船舶占用，则从最后一个岸桥向左取;
(2) If the theoretical maximum number is occupied by the ship on the right, it will be taken from the last quay crane to the left;

(3) 理论最小、最大编号都未被占用，则从确定好的最中间编号分别向两侧取。
(3) If the theoretical minimum and maximum numbers are not occupied, the middle number is taken from the determined middle number to both sides.

当岸桥数是2m个时，先找到船舶的中心位置，再分两种情形讨论：
When the number of quay cranes is 2m, first find the center position of the ship, and then discuss it in two situations:

(1) 中心位置未对齐岸桥原固定位置，类似奇数情况分三种情形确定;
(1) The central position is not aligned with the original fixed position of the quay crane, and the odd number of similar cases is determined in three situations;

(2) 中心位置对齐了岸桥原先固定位置，此时分成两种情况讨论决定哪一侧取m个岸桥，若左侧能够取m个，则右侧取(m-1)个，反之，右侧取m个，左侧取(m-1)个。
(2) The central position aligns the original fixed position of the quay crane, and at this time, it is divided into two situations to discuss and decide which side to take m quay cranes, if the left side can take m cranes, then take (m-1) on the right side, and vice versa, m on the right side, take (m-1) on the left.

在可行的岸桥集合中，如果停靠船舶左端接近左端点，此时从第一台岸桥向后选取合适数量的连续岸桥;如果停靠船舶右端接近右端点，此时从最后一台岸桥向前选取合适数量的连续岸桥;如果停靠船舶在中间位置，此时从集合中选取合适数量的连续岸桥。
In the feasible set of quay cranes, if the left end of the docked ship is close to the left endpoint, an appropriate number of continuous quay cranes are selected from the first quay crane backwards; If the right end of the docked ship is close to the right endpoint, an appropriate number of continuous quay cranes are selected from the last quay crane forward; If the docked ship is in the middle, the appropriate number of continuous quay cranes are selected from the set.

在上面构造的算法中，分配原则是按船舶到港时刻先后来配置船舶，尽管不全都是先到先服务，但基本上是先到先分配。为了达到目标函数最小总费用的条件，通过优先权法修改船舶的分配顺序，满足能够同时靠泊的情况下，首先配置优先权重较大的船舶。
In the algorithm constructed above, the allocation principle is to allocate ships according to the time of arrival of the ships, although not all of them are first-come, first-served, but basically first-come, first-served. In order to achieve the condition of the minimum total cost of the objective function, the allocation order of ships is modified through the priority method, and the ships with a large priority weight are first allocated when they can berth at the same time。

3.2 改进遗传算法的设计
3.2 Improve the design of genetic algorithms

个体编码前，首先按照船舶到港时刻顺序对船舶进行编号。柔性靠泊下的靠泊位置和岸桥分配要处理船舶靠泊时间、位置及分配的岸桥数和编号这三个问题，因此其染色体需要一同展现这三个问题的信息。所以其染色体由船舶靠泊服务权重、船舶靠泊位置和分配的岸桥数三方面构成。
Before the individual code is made, the ships are numbered in the order of their arrival at the port. The berthing position and quay crane assignment under flexible berthing deal with the three questions of the ship's berthing time, position, and the number and number of quay cranes assigned, so its chromosomes need to show the information of these three problems together. Therefore, its chromosome is composed of three aspects: the weight of the ship berthing service, the berthing position of the ship and the number of quay cranes allocated.

3.2.1 个体编码
3.2.1 Individual Code

(1) 首先，靠泊优先权重的编码。按照权重的大小对船舶比较排序，设置不同的基因码。
(1) First of all, the coding of the berthing priority weight. Compare and sort the ships according to the size of the weights, and set different gene codes.

(2) 其次，靠泊位置的编码。
(2) Secondly, the code of the berthing position.

(3) 最后，岸桥数量的编码。岸桥数量的编码方式和靠泊位置一样，每艘船舶的服务岸桥数在区域中随机生成。
(3) Finally, the coding of the number of quay cranes. The number of quay cranes is encoded in the same way as the berthing location, and the number of quay cranes served by each vessel is randomly generated in the region.

3.2.2 种群初始化
3.2.2 Population initialization

随机产生初始种群总体，把染色体分为三段，第一段基因是集装箱船舶总数的排列，第二段靠泊位置部分的基因在它们允许的区域内随机选择靠泊位置，用船舶最左端处于岸线的位置表示。设岸线最左端是0，最右端是l，靠泊位置是500，说明该集装箱船舶的最左端距离岸线端点的距离为500米。第三段基因是岸桥数目基因随机从区域中进行选取。初始生成n个染色体，其中的个体分段随机生成完后，合成一个新的个体。
The initial population population is randomly generated, and the chromosomes are divided into three segments, the first gene is the arrangement of the total number of container ships, and the genes of the second berthing location part randomly select the berthing location in the area they allow, which is indicated by the position of the leftmost point of the ship on the shoreline. Let the leftmost end of the shoreline be 0, the rightmost end is L, and the berthing position is 500, indicating the distance between the leftmost end of the container ship and the end of the shorelinefor 500 meters. The third segment of genes is the quay bridge number gene, which is randomly selected from the region. N chromosomes are initially generated, and the individuals in them are randomly generated and then synthesized into a new individual.

3.2.3 适应度函数
3.2.3 Fitness function

当前目标函数间由于量纲不一致而不容易处理，仅可以做到相对的整体最优，不能满足所有子目标同时最优。就多目标优化问题来说，如今有很多大型复杂系统的算法^[25]，本文利用传统的权值设定法，先用模糊层次分析法算出子目标的优先权值，再基于权值把多个目标函数合成一个标量效用函数，把多目标函数加权转变为单目标问题。
At present, it is not easy to deal with the objective functions due to the inconsistency of dimensions, and can only achieve the relative overall optimum, which cannot meet the simultaneous optimality of all sub-objectives. As far as multi-objective optimization is concerned, there are many algorithms for large and complex systems ^[25], and this paper uses the traditional weighting method to Firstly, the priority weight of the sub-objective is calculated by fuzzy analytic hierarchy process, and then the multiple objective functions are synthesized into a scalar utility function based on the weights, and the multi-objective function weighting is transformed into a single-objective problem.

本文目标函数的适应度函数可由待求解的目标函数经过取倒转化而成，其公式如下：
The fitness function of the objective function in this paper can be inverted and transformed from the objective function to be solved, and its formula is as follows:

  (17)

其中，是目标函数界限的保守估计值。
where is a conservative estimate of the bounds of the objective function.

运用模糊层次分析法，根据三个子目标函数的重要性，可以得到三个子目标函数的权重值：0.4、0.35和0.25。把三个子目标函数实行统一来满足遗传算法适应度的特征，使用上文的转化方式表示适应度函数，则总目标函数为：
Using the fuzzy analytic hierarchy process, the weights of the three sub-objective functions can be obtained according to the importance of the three sub-objective functions: 0.4, 0.35 and 0.25. If the three sub-objective functions are unified to meet the characteristics of the fitness of the genetic algorithm, and the fitness function is represented by the transformation method above, the total objective function is:

  (18)

3.2.4 选择、交叉、变异操作
3.2.4 Select, cross, and mutate operations

对父代进行选择、交叉，并对经上述操作处理后的个体编码进行变异操作得到全新的编码串。
The parent was selected, crossed, and mutated to obtain a new coding string by mutating the individual code processed by the above operations.

3.2.5 基因修复操作
3.2.5 Gene repair operations

在经过交叉、变异操作之后所生成的子代，可能会存在一些个体没有达到所建模型的约束要求。在种群每次完成迭代交叉与变异后，依次校验新产生染色体中有关船舶k的信息，并确保每艘船舶的靠泊位置、靠泊时间与服务岸桥集合是可行的。重点是要约束好每艘船舶k的最小和最大岸桥数量区域的岸桥数目及靠泊位置在可行岸线区域中。综上所述，若个体是可行的，就不需要做任何操作;如若不然，基于固定的靠泊时间修复好个体中的不可行基因。
There may be some individuals who do not meet the constraints of the model after the crossover and mutation operations. After each iteration of the population completes crossover and mutation, the information about ship k in the newly generated chromosomes is checked in turn, and the berthing location, berthing time and service quay crane set of each ship are feasible. The key point is to constrain the minimum and maximum number of quay cranes for each ship, and the number of quay cranes and berthing positions in the area are in the feasible shoreline area. In summary, if the individual is feasible, there is no need to do anything; Otherwise, fix the non-viable genes in the individual based on a fixed berthing time.

4 实例分析
4 Case Studies

4.1 原始数据
4.1 Raw Data

某集装箱港口码头岸线长度是1000米，有12台岸桥可供服务。12台岸桥最开始从左向右均匀分布在[40,940]的码头岸线上。从预计到港船舶作业数据中，任意抽取24艘连续到港船舶的原始数据当作原始输入数据，从而开始对连续泊位布局方式下的集装箱码头泊位与岸桥联合分配进行研究。到港时间以第一艘船到港日期的零点为基准，24 艘集装箱船舶的各相关原始数据如下表1所示。其中：E.T.A为船舶预计到港时间，E.T.D为船舶预计离港时间，岸桥作业效率为为45TEU/h，岸桥移动速度为50m/min，g为0.9，为0.005元，为150元。
The shoreline of a container port is 1,000 meters, and there are 12 quay cranes that can be served. The 12 quay cranes were initially evenly distributed from left to right along the quay line of [40,940]. From the expected arrival ship operation data, the original data of 24 consecutive arriving ships were arbitrarily extracted as the original input dataTherefore, the joint allocation of container terminal berths and quay cranes under the continuous berth layout mode was studied. The arrival time is based on the zero point of the arrival date of the first ship, and the relevant raw data of the 24 container ships are shown in Table 1 below. Among them: E.T.A. is the estimated arrival time of the ship, E.T.D. is the estimated departure time of the ship, and the quay crane operation efficiency is45TEU/h, the quay crane moving speed is 50m/min, and g is 0.9,is 0.005 yuan, which is 150 yuan.

表1 集装箱船舶原始数据表
Table 1 Original data table of container ships

Table 1 Container ship raw data sheet

每艘集装箱船都有最大和最小的作业岸桥数，前者由船的长度和操作规则决定，后者由船公司和码头运营商之间的合同和装载量的大小共同决定。岸桥的作业规则通常由岸桥的宽度和原则决定，如不穿越、不跨越等。岸桥总宽指同一边行走轨道上的两侧两组行走台车外侧缓冲器端部在自由情况下的距离的长度。
Each container ship has a maximum and minimum number of quay cranes to operate, the former being determined by the length of the vessel and the rules of operation, and the latter being determined by a combination of the contract between the shipping company and the terminal operator and the size of the loading capacity. The operating rules of the quay crane are usually determined by the width and principle of the quay crane, such as not crossing, not crossing, etc. The total width of the quay crane refers to the length of the distance between the ends of the outer buffers of two groups of walking trolleys on both sides of the same walking track in the free condition.

表2 到港船舶岸桥数据
Table 2 Quay crane data of ships arriving at the port

Table 2 Ship landing bridge data

岸桥的最大数量由30 米以下的岸桥宽度决定，同时还要考虑到船舶的长度和船舶间的安全距离。通常大于大型万吨级船舶的安全距离是15-20米之间。因此在本研究中，长度小于100米的小吨位集装箱船之间的安全距离为10米，长度大于100米的中等吨位船舶间的安全距离是15米，大于万吨级船舶间的安全距离是20米。基于船舶的相关原始数据，可得船舶最大、最小作业岸桥数量以及船舶长度与安全距离之和如表2所示。
The maximum number of quay cranes is determined by the width of the quay cranes below 30 meters, taking into account the length of the vessel and the safe distance between the vessels. Usually the safety distance is between 15-20 meters for large 10,000-ton ships. Therefore, in this study, the safety distance between small tonnage container ships with a length of less than 100 meters is 10 meters, and the safety distance between medium-tonnage ships with a length of more than 100 meters is 15 metersThe safe distance between ships larger than 10,000 tons is 20 meters. Based on the relevant raw data of the ship, the maximum and minimum number of quay cranes and the sum of the ship's length and safety distance can be obtainedAs shown in Table 2.

4.2 运行结果分析
4.2 Running Result Analysis

4.2.1 目标函数设置
4.2.1 Objective Function Settings

本文提出的模型综合考虑了三个优化目标，分别是集装箱船舶的在港时间、生产成本和罚款成本，最后形成的总目标值为三个优化目标的加权求和。
The model proposed in this paper comprehensively considers three optimization objectives, namely the on-port time, production cost and penalty cost of container ships, and finally forms a total target value of the weighted sum of the three optimization objectives.

其中，第一个子目标函数为：
where the first sub-objective function is:

  (19)

第二个子目标函数为：
The second sub-objective function is:

 (20)

第三个子目标函数为：
The third sub-objective function is:

   (21)

总目标函数为：
The total objective function is:

  (22)

4.2.2 运行参数设置
4.2.2 Running Parameter Settings

在本研究中，选用Matlab当作算法程序编程开发平台，运用包含改进遗传算法的启发式算法求解连续泊位布局方式下的泊位与岸桥联合分配模型。在模型的编程和实施过程中，经过多次实验，使算法能在可接受的时间内获得较好的优化方案，选取的遗传算法主要参数如下表3所示。
In this study, Matlab was selected as the algorithm programming platform, and the heuristic algorithm including the improved genetic algorithm was used to solve the joint allocation model of berth and quay crane under the continuous berth layout mode。 In the process of programming and implementation of the model, after many experiments, the algorithm can obtain a better optimization scheme in an acceptable time, and the main parameters of the selected genetic algorithm are as follows3.

表3 算法参数设置
Table 3 Algorithm parameter settings

Table 3 Algorithm parameter setting

4.2.3 四种靠泊规则下最优方案的适应度分析
4.2.3 Fitness analysis of the optimal scheme under the four berthing rules

将不同规则下集装箱码头泊位与岸桥联合分配模型仿真得到的结果随机取连续的20个初始解，选择各规则下总目标适应度值最优的方案进行下一步分析。
The results obtained from the simulation of the joint allocation model of container terminal berth and quay crane under different rules are randomly selected from 20 consecutive initial solutions, and the scheme with the optimal total target fitness value under each rule is selected for further analysis.

规则一下最优方案的调度结果如图2所示，描述的是根据算法获得的仿真结果适应度数值进化图。
The scheduling results of the optimal scheme under rule 1 are shown in Figure 2, which depicts the numerical evolution of the fitness of the simulation results obtained according to the algorithm。

图2 规则一适应度数值进化图
Fig.2 Numerical evolution of rule 1 fitness

Fig.2 Rule 1 Fitness numerical evolution diagram

规则一经迭代22次适应度数值进化曲线趋于稳定，其总适应度值达到0.6120。同理其余规则的适应度进化曲线及使得适应度数值进化曲线趋于稳定的迭代次数均能求得，其中规则二、规则三及规则四的迭代次数分别为20次、20次和42次。
After 22 iterations, the numerical evolution curve of the fitness tends to be stable, and the total fitness value reaches 0.6120. In the same way, the fitness evolution curve of the rest of the rules and the number of iterations that make the numerical fitness evolution curve tend to be stable can be obtained, and the iterations of rule 2, rule 3 and rule 4 are 20, 20 and 42, respectively.

四种靠泊规则下最优方案的各目标函数适应度曲线如图3所示。
The fitness curves of each objective function of the optimal scheme under the four berthing rules are shown in Figure 3.

图3 四种规则下最优方案的各目标函数适应度曲线图
Fig.3 Fitness curves of each objective function of the optimal scheme under the four rules

Fig.3 Fitness curves of each objective function of the optimal scheme under the four rules

如图3所示，不同靠泊规则下最优解的各目标函数适应度值不同，如规则一下最优解的各子目标函数适应度值分别为0.5406、0.7316、0.5587，总目标函数适应度值为0.6120;其余规则的目标函数适应度值均可求得。由于适应度函数为目标函数的倒数，即适应度数值越大，目标函数越小。而0.5707＞0.5469＞0.5447＞0.5406，对于子目标函数1(考虑在港时间最短)，基于规则三可得到最优方案。同理，对于子目标函数2(考虑生产成本最低)来说，规则一是最优的;对于子目标函数3(考虑惩罚成本最少)来说，规则三是最优的;而对于总目标函数来说，规则一的适应度值为0.6120大于其他规则下最优解的适应度值，所以基于规则一可得到船舶最优靠泊方案，即：在集装箱船舶进行靠泊计划时，在其可行岸线内靠泊，优先选择离偏好位置最近的，且其靠泊位置每次仅选择一个。
As shown in Figure 3, the fitness values of each objective function of the optimal solution under different berthing rules are differentFor example, the fitness values of each sub-objective function of the optimal solution are 0.5406, 0.7316, and 0.5587, respectively, and the total objective function fitness values are 0.6120. The objective function fitness values of the rest of the rules can be obtained. Since the fitness function is the reciprocal of the objective function, i.e., the larger the fitness value, the smaller the objective function. and 0.5707>0.5469>0.5447>0.5406, for the sub-objective function 1 (considering the shortest time in port), based onRule 3 yields the best solution. Similarly, for the sub-objective function 2 (considering the lowest production cost), Rule 1 is optimal; For the sub-objective function of 3 (considering the least penalty cost), rule 3 is optimal; For the total objective function, the fitness value of rule 1 is 0.6120 which is greater than the fitness value of the optimal solution under other rules, so it can be obtained based on rule 1The optimal berthing scheme for ships, that is, when the container ship is berthing planned, berthing within its feasible shoreline, and giving priority to the closest to the preferred locationand select only one berthing position at a time.

虽然规则一下的最优解在子目标函数1(考虑在港时间最短)的适应度值为0.5406，占据了较长的在港时间，但其生产成本和惩罚成本都比较低。从全局来看，规则一下的最优解为最优调度方案。
Although the fitness value of the optimal solution under the rule is 0.5406 in the sub-objective function 1 (considering the shortest time in port), which occupies a longer time in port, However, its production cost and penalty cost are relatively low. From a global point of view, the optimal solution under the rule is the optimal scheduling scheme.

4.2.4 四种靠泊规则下最优方案的调度结果
4.2.4 Scheduling results of the optimal scheme under the four berthing rules

图4 规则一最优解位置-时间图
Fig.4. Position-time diagram of the optimal solution of rule 1

Fig.4 Rule 1 Optimal solution position-time graph

图4描述的是规则一对应的最优解位置-时间图。同理可得出其他规则下最优泊位与岸桥分配方案的位置-时间图。
Figure 4 depicts the position-time plot of the optimal solution corresponding to rule 1. In the same way, the location-time diagram of the optimal berth and quay crane allocation scheme under other rules can be obtained.

规则一下最优方案的岸桥调度甘特图如图5所示。同理可得出其他规则下最优解的岸桥作业时间及甘特图。由岸桥作业时间及甘特图我们可以得出各规则下最优泊位与岸桥分配方案的在泊时间和岸桥利用率。
Figure 5 shows the Gantt chart of quay crane scheduling for the optimal scheme. In the same way, the quay crane operation time and Gantt chart of the optimal solution under other rules can be obtained. From the quay crane operation time and Gantt chart, we can derive the berth time and quay crane utilization rate of the optimal berth and quay crane allocation scheme under each rule.

图5 最优规则下最优解的岸桥作业甘特图
Fig.5 Gantt chart of quay crane operation with optimal solution under the optimal rule

Fig.5 Gantt chart of shore bridge operation with optimal solution under optimal rule

各规则下最优方案的在泊时间和岸桥利用率如表4所示。
Table 4 shows the berth time and quay crane utilization rate of the optimal scheme under each rule.

表4 最优规则下最优方案的在泊时间及岸桥利用率表
Table 4 The berth time and quay crane utilization rate of the optimal scheme under the optimal rule

Table 4 Mooring time and quayside bridge utilization table of optimal scheme under optimal rule

表4中规则一下最优泊位与岸桥分配方案的在泊时间及岸桥利用率分别为93.81457小时和68.617%，其在泊时间与其他规则下的在泊时间相差不大，虽不是所有最优方案中的最短，但并未出现大量船舶待泊的状况;在泊时间过短，会导致码头泊位过度空闲，资源得不到有效利用，会严重影响港方的经济效益。所以合理的在泊时间应能平衡港、航、货三方利益。规则一的岸桥利用率为所有最优方案中的最高，保证了港口的作业效率。
Table 4 shows the optimal berth and quay crane allocation schemes, and the berth time and quay crane utilization rate are respectively93.81457 hours and 68.617%, which is not much different from the berth time under other rules, although it is not the shortest among all the optimal schemes. However, there is no situation where a large number of ships are waiting to be berthed; If the berth time is too short, the berths will be overly idle, and the resources will not be effectively utilized, which will seriously affect the economic benefits of the Hong Kong side. Therefore, a reasonable berth time should be able to balance the interests of the port, shipping and cargo. The utilization rate of the quay crane in Rule 1 is the highest among all the optimal solutions, which ensures the operational efficiency of the port.

5 结论
5 Conclusion

(1) 面对集装箱港口泊位分配与岸桥联合分配问题的复杂性，结合船舶现有的实践靠泊经验以及港口已有的船舶靠泊方式，建立了四种独立靠泊规则，基于以上四种规则和连续型泊位的布局方式建立了以船舶总在港时间、码头生产成本和惩罚费用最小为优化目标的多船到港不确定优先权的泊位与岸桥分配多目标模型。对于其他传统模型来说，此模型有着更好的适用性，同时更符合船舶在靠港时的实际应用。
(1) In the face of the complexity of the allocation of container port berths and the joint allocation of quay cranes, combined with the existing practical berthing experience of ships and the existing berthing methods of ships in portsFour independent berthing rules were established, and a multi-objective model of berth and quay crane allocation with uncertain priority of multi-ship arrival was established based on the above four rules and the layout of continuous berths, with the optimization goal of minimizing the total time of ship in port, the production cost of the terminal and the penalty cost. Compared with other traditional models, this model has better applicability and is more in line with the practical application of ships when they are at port.

(2) 针对本文NP问题的特征，通过改进的算法对染色体进行分段编码、交叉和变异等操作，使算法得到更好的应用。根据四种靠泊服务规则，设计了基于遗传算法的启发式算法，并分析了该算法在四种靠泊服务规则下的求解，根据优先权大小，再按照船舶先到先服务的原则下对船舶靠泊服务顺序做出调整，较好地解决集装箱港口泊位与岸桥联合调度的优化问题。
(2) According to the characteristics of the NP problem in this paper, the improved algorithm is used to perform segmentation coding, crossover and mutation operations on chromosomesMake the algorithm better applied. According to the four berthing service rules, a heuristic algorithm based on genetic algorithm is designed, and the solution of the algorithm under the four berthing service rules is analyzed, according to the priority size Then, according to the principle of first-come, first-served service, the order of berthing service of ships is adjusted, so as to better solve the optimization problem of joint scheduling of container port berths and quay cranes.

(3) 通过实例分析，利用设计的遗传算法分别求解四种靠泊服务规则，得到泊位与岸桥联合分配的最优方案和最优靠泊服务规则为：集装箱船舶进行靠泊计划时，在其可行岸线内靠泊，优先选择离偏好位置最近的位置靠泊，且其靠泊位置每次仅选择一个。为船舶靠泊决策提供调度优化方法，为集装箱港口的泊位与岸桥调度决策提供依据。
(3) Through case analysis, the designed genetic algorithm is used to solve the four berthing service rules respectivelyThe optimal scheme and optimal berthing service rules for the joint allocation of berths and quay cranes are as follows: when the container ship carries out the berthing plan, it will berth within its feasible shoreline, and give priority to berthing at the position closest to the preferred positionAnd only one berthing position can be selected at a time. It provides a scheduling optimization method for ship berthing decision, and provides a basis for berth and quay crane scheduling decision in container port.

参考文献:
References:

杨春霞, 王诺. 基于SPEA2算法的泊位调度多目标优化[J]. 工业工程与管理, 2010, 15(03): 100-104.
Yang Chunxia, Wang Nuo Multi-objective optimization of berth scheduling based on SPEA2 algorithm[J]. Industrial Engineering and Management, 2010, 15(03): 100-104

秦进, 缪立新, 陈长彬等. 时间窗限制下港口泊位优化分配问题模型[J]. 船海工程, 2010, 39(02): 142-145.
Qin Jin, Miao Lixin, Chen Changbin, et al Model of port berth optimal allocation problem under time window constraint[J]. Marine Engineering, 2010, 39(02): 142-145

张旻媛. 基于蚁群算法的港口泊位问题的研究[J]. 物流工程与管理, 2012, 34(03): 101-103.
ZHANG Minyuan Research on port berth problem based on ant colony algorithm[J]. Logistics Engineering and Management, 2012, 34(03): 101-103

欧阳玲萍, 王锡淮, 肖健梅. 基于蚁群算法的泊位调度问题[J]. 控制工程, 2009, 16(S2): 106-109.
Ouyang Lingping, Wang Xihuai, Xiao Jianmei Berth scheduling problem based on ant colony algorithm[J]. Control Engineering, 2009, 16(S2): 106-109

余刘海, 庞洪静. 集装箱码头连续泊位与岸桥联合调度[J]. 科技信息, 2013, 30(09): 196-197.
Yu Liuhai, Pang Hongjing Joint scheduling of continuous berths and quay cranes in container terminals[J]. Science & Technology Information, 2013, 30(09): 196-197.

李晨, 陆志强, 陈璐. 具有岸桥碰撞和甲板约束的岸桥混合装卸作业调度优化[J]. 上海交通大学学报, 2010, 44(08): 1159-1164.
Li Chen, Lu Zhiqiang, Chen Lu Scheduling optimization of mixed loading and unloading operation of quay crane with quay crane collision and deck constraint[J]. Journal of Shanghai Jiao Tong University, 2010, 44(08): 1159-1164

乐美龙, 徐根龙, 文洪蕊. 基于作业均衡的集装箱码头岸桥作业调度优化[J]. 重庆交通大学学报(自然科学版), 2016, 35(03): 155-161.
Le Meilong, Xu Genlong, Wen Hongrui Scheduling optimization of quay crane operation in container terminal based on operation balance[J]. JOURNAL OF CHONGQING JIAOTONG UNIVERSITY (NATURAL SCIENCE EDITION), 2016, 35(03): 155-161

曾庆成, 冯媛君, 度盼. 面向干支线船舶衔接的集装箱码头泊位分配模型[J]. 系统工程理论与实践, 2016, 36(01): 154-163.
Zeng Qingcheng, Feng Yuanjun, Du Pan Container terminal berth allocation model for trunk and branch line ship connection[J]. Systems Engineering - Theory & Practice, 2016, 36(01): 154-163

Peterkofsky R.I,Daganzo C.F.A Branch and Bound Solution Method for the Crane Scheduling Problem[J]. Transportation Research Part B, 1990, 24(3): 159-172.

初良勇,周于佩,姚艺飞,等. 自动化码头多资源协同调度优化模型与算法 [J]. 哈尔滨工程大学学报, 2022, 43 (10): 1539-1546.
CHU Liangyong, ZHOU Yupei, YAO Yifei, et al. Optimization Model and Algorithm for Multi-resource Collaborative Scheduling of Automated Terminals [J]. Journal of Harbin Engineering University, 2022, 43 (10): 1539-1546.

Moccia, Wichmann M．Container sequencing for quay cranes with internal reshuffles．OR Spectrum, 2010, 32(3)：569-581．

Liang C, Guo J, Yang Y. Multi-objective hybrid genetic algorithm for quay crane dynamic assignment in berth allocation planning[J]. Journal of Intelligent Manufacturing, 2011, 22(3): 471-479.

张海永, 严伟. 基于规则的泊位与岸桥联合调度[J]. 浙江交通职业技术学院学报, 2011, 12(02): 39-43
Zhang Haiyong, Yan Wei Joint scheduling of berths and quay cranes based on rules[J]. Journal of Zhejiang Jiaotong Vocational and Technical College, 2011, 12(02): 39-43.

郑红星,尹昊,曹红雷等.考虑潮汐影响的离散型泊位和岸桥集成调度[J].运筹与管理,2017,26(06):167-175.
Zheng Hongxing, Yin Hao, Cao Honglei, et al. Integrated scheduling of discrete berths and quay cranes considering tidal influence[J].Operations Research and Management,2017,26(06):167-175.)

郑红星, 张敬涛, 刘保利. 考虑潮汐影响的连续泊位和岸桥集成调度[J]. 计算机集成制造系统, 2018, 24(10): 2599-2611.
Zheng Hongxing, Zhang Jingtao, Liu Baoli Integrated scheduling of continuous berths and quay cranes considering tidal influence[J]. Computer Integrated Manufacturing Systems, 2018, 24(10): 2599-2611

焦小刚, 郑斐峰, 徐寅峰等. 考虑泊位疏浚的连续型泊位和动态岸桥联合调度[J]. 运筹与管理, 2020, 29(02): 47-57.
Jiao Xiaogang, Zheng Feifeng, Xu Yinfeng, et al Joint scheduling of continuous berths and dynamic quay cranes considering berth dredging[J]. Operations Research and Management, 2020, 29(02): 47-57

蒋美仙,王志意,郑建鹏等.连续泊位——岸桥——集卡调度模型构建及应用[J].浙江工业大学学报,2018,46 (02):184-191.
Jiang Meixian, Wang Zhiyi, Zheng Jianpeng, et al. Construction and application of continuous berth-quay crane-container truck scheduling model[J].Journal of Zhejiang University of Technology,2018,46 (02):184-191.)

Schaeren V D R B .An enriched model for the integrated berth allocation and quay crane assignment problem[J]. Expert Systems With Applications,2011,38(11):14136-14147.

李娜.集装箱码头连续泊位与岸桥调度联合优化研究[D].大连海事大学,2011.
Li na. Research on joint optimization of continuous berth and quay crane scheduling in container terminal[D].Dalian Maritime University,2011.

王军,郭力铭,杜剑等.基于动态学习的泊位调度方案优化[J].交通运输系统工程与信息,2018,18(05):197-203.
Wang Jun, Guo Liming, Du Jian, et al. Optimization of berth scheduling scheme based on dynamic learning[J].Transportation Systems Engineering and Information Technology,2018,18(05):197-203.)

蒋大培,胡志华,胡少龙.考虑偏好泊位的泊位和岸桥集成分派问题[J].广西大学学报(自然科学版), 2014, 39(03):663-672.
JIANG Dapei,HU Zhihua,HU Shaolong. Considering the integrated allocation of berths and quay cranes considering preferred berths[J].Journal of Guangxi University(Natural Science Edition), 2014, 39(03):663-672.)

禹美凤.基于柔性靠泊的集装箱港口泊位和岸桥的调度优化[D].浙江工业大学,2013.
YU Meifeng. Scheduling optimization of container port berth and quay crane based on flexible berthing[D].Zhejiang University of Technology,2013.

王洪岩. 考虑潮汐影响的连续型泊位指派与岸桥分配联合优化研究[D].大连海事大学,2021.
WANG Hongyan. Joint optimization of continuous berth assignment and quay crane allocation considering tidal influence[D].Dalian Maritime University,2021.

焦小刚,郑斐峰,徐寅峰等.潮汐影响下泊位和岸桥双目标联合调度仿真[J].计算机仿真,2020,37(02):403-410.
Jiao Xiaogang, Zheng Feifeng, Xu Yinfeng, et al. Simulation of dual-objective joint scheduling of berth and quay crane under tidal influence[J].Computer Simulation,2020,37(02):403-410.)

初良勇,梁冬. 基于DQN的自动化集装箱码头AGV多目标调度优化 [J/OL]. 哈尔滨工程大学学报, 2024, (05): 1-9
CHU Liangyong,LIANG Dong. Multi-objective Scheduling Optimization of AGV in Automated Container Terminal Based on DQN [J/OL]. Journal of Harbin Engineering University, 2024, (05): 1-9.