基于惩罚函数的集装箱码头连续泊位-岸桥联合调度

刘桂云， 陈珊珊， 张小莉， 刘明涛

(宁波大学 海运学院， 浙江 宁波 315211)

基于惩罚函数的集装箱码头连续泊位-岸桥联合调度

刘桂云， 陈珊珊， 张小莉， 刘明涛

(宁波大学 海运学院， 浙江 宁波 315211)

为对连续泊位与岸桥联合调度问题进行求解，从码头运营者的角度出发，以最小化惩罚为优化目标建立数学模型，设计一种嵌套式遗传算法。在客户满意率最大的情况下，求得船舶的靠、离泊时间和位置及最优装卸序列。通过进行数值模拟案例分析，验证该优化方法可在提高客户满意率的同时，缩短船舶在港时间，对集装箱码头生产运作实践具有一定的参考价值。

交通运输经济学； 集装箱码头； 泊位与岸桥； 联合调度； 遗传算法； 惩罚函数

Abstract: An optimization method of unified scheduling for continuous berth and quay-crane is formulated to minimize the punishment from the terminal operators' perspective, and a nested genetic algorithm is designed to solve this problem. The time of docking and departure, berthing and the best loading/unloading sequence of ships are solved for the highest customer satisfaction rate. The optimization method is verified with a representative case, which indicates that the method can improve the degree of customer satisfaction as well as decrease the birthing time of ships. The method can be a reference of some kind for the actual production of the container terminal.

Keywords: traffic transport economics; container terminal; berth and quay-crane; unified scheduling; genetic algorithm; penalty function

研究集装箱码头生产调度问题对提高码头服务能力和运营效率，进而提升全球物流效率具有重要意义。泊位与岸桥调度是集装箱码头调度的核心内容，国内外很多学者都对此进行过研究，提出了具有实践指导意义的优化方法。一些成熟的理论研究己应用于码头实际生产作业中。

LI等[1]以最小化船舶在港时间为目标，将泊位与岸桥分配作为一个并行调度问题建模求解；GUAN等[2]在此基础上建立以最小化权重任务的完成时间为目标的调度模型。韩俊等[3]和靳志宏等[4]研究泊位与岸桥联合调度问题，假设服务于一艘船舶的所有岸桥必须同时结束，运用免疫遗传算法求解模型。AK等[5]引入禁忌搜索法，研究以最小在港时间和避免船舶延迟离港的惩罚费用为目标的泊位与岸桥联合调度模型。LIANG等[6]以最小化所有岸桥工作时间、等待时间和延迟时间为目标函数建立泊位与岸桥联合调度模型，并采用遗传算法求解，得出靠泊位置、时间和岸桥分配数量。BIRGER等[7]考虑岸桥作业时间超长的惩罚、偏离最佳靠泊位置的惩罚和岸桥移动的惩罚，引入滚动时间窗和船舶优先级研究联合调度问题。乐美龙等[8]建立连续泊位与岸桥分配模型，并运用Memetic求解算法。 YANG等[9]提出一种解决多用户集装箱码头泊位与岸桥分配问题的有效方法，根据泊位与岸桥的交互关系建立泊位与岸桥耦合模型，并设计改进遗传算法。桂小娅等[10]以最小化船舶在港时间为目标建立连续泊位和岸桥联合调度模型，并提出一种双层循环迭代求解算法。

此外，还有一些学者对岸桥装卸调度进行研究。赵坤强等[11]分别研究分配泊位和岸桥数量模型及岸桥装卸调度模型。余刘海等[12]在计划周期内研究泊位分配与岸桥在任务间的动态调度，建立基于任务的连续泊位与岸桥协调调度模型。YAVUZ等[13]等研究泊位分配、岸桥分配(数量)和岸桥装卸调度问题，设计一种能求解大规模问题的算法。杨华龙等[14]建立以最小化船舶在港时间和最大化岸桥利用率为目标的连续泊位与岸桥联合调度模型。吕赛赛等[15]依据作业量确定船舶的优先权，建立基于船舶优先权的泊位与岸桥耦合优化模型。

已有研究主要针对的是岸桥数量分配，对具体岸桥在任务间调度的研究较少，而在实际生产调度中，只有合理安排特定岸桥的作业顺序才能保障装卸效率；同时，已有研究大多以最小化在港时间为目标建立数学模型，考虑因素较为单一，无法满足客户多方面的需求。对此，引入惩罚函数，从提高客户满意度的角度建立泊位与岸桥联合调度模型。具体惩罚包括对超出客户最佳离港时间的惩罚、对偏离最佳靠泊位置的惩罚和对岸桥移动的惩罚。

1 问题描述

1.1问题假设

研究泊位与岸桥联合调度问题时，不仅要考虑靠泊时间和位置的最优，还要考虑岸桥对装卸时间的影响及岸桥能在多艘船舶间动态调度。根据问题的特性和现实约束，为便于分析，提出以下假设： 连续泊位各处均符合船舶靠泊水深条件；船舶靠泊和离港操作时间不计； 岸桥位于同一轨道，从左至右依次编号，两台岸桥之间存在安全距离，假定为一个贝位； 岸桥水平移动时间忽略不计； 由于船方要求和船舶大小的限制，每艘船舶都有最小和最大岸桥数限制； 船舶停泊期间不会移动； 每艘船舶都有其最优靠泊位置； 某一时刻，岸线上所有船舶的贝位从左至右依次编号。

1.2符号定义

为详细描述连续泊位与岸桥联合调度的过程，对相应符号进行定义。

1.2.1集合符号

V={1,2,…,v}为等待靠泊的船舶；Q={1,2,…,k}为岸线可用的岸桥，并从岸线左端开始依次编号，岸桥总数为|Q|；T={0,1,…,t}为计划期时间，是以1 h为单位的离散时间；L={0,1,…,l}为海岸线长度，是以100 m为单位的离散距离；Ωi={1,2,…,n}为船舶i上的所有任务。

1.2.2参数符号

1.2.3决策变量

2 调度模型

2.1目标函数

建立目标函数最小化惩罚值，分为3个部分： 第1部分涉及船舶最佳离港延迟惩罚系数，每艘船舶都有其最佳离港时间，船舶作业时间可看成在港时间； 第2部分涉及船舶靠泊位置和船舶偏离最优靠泊位置的惩罚，每艘船舶都有其最优靠泊位置，在最优位置对应的出口堆场区和进口堆场区集卡运输成本最小，一旦偏移将导致集卡运输距离增加； 第3部分是对每艘船舶分配的岸桥数量增加的惩罚。由于岸桥的移动会增加岸桥的移动成本，因此限定岸桥在船舶之间大范围移动，设置一艘船舶岸桥数量增加的惩罚。具体表达为

(1)

2.2约束条件

约束条件表达为

(2)

(3)

(4)

Si≥Ci

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

i=j,k1≠k2

(13)

i≠j,k1≠k2,n1≠n2

(14)

(15)

changeit≥Qit-Qit-1

(16)

pli=pbl(i)-dli+dri

(17)

pli+l(i)≤L

(18)

pli+l(i)-L(1-yij)≤plj

(19)

busyit+busyjt≤1+yij+yji

(20)

(21)

式(2)～式(21)中：∀i,j∈V;∀k∈Q;∀t∈T;∀n∈Ωi;∀k1,k2∈Q;∀n1,n2∈Qi。式(2)定义岸桥在第K期的位置(岸线方向)；式(3)定义岸桥在第K期开始空闲的时刻；式(4)定义岸桥服务单个任务所需要的时间；式(5)确保船舶作业开始时间在到达之后；式(6)定义船舶作业的结束时间；式(7)为码头岸桥总数量的约束；式(8)表示岸桥只有在满足上述要求时才可开始作业；式(9)表示一个岸桥在某一时刻只能为一项任务服务；式(10)定义任务的开始时间；式(11)定义任务的结束时间；式(12)表示一个岸桥只能为一艘船舶服务；式(13)和式(14)限制岸桥不可跨越作业；式(15)定义某时刻服务于同一船舶的岸桥数量；式(16)定义某一时刻到下一时刻岸桥数量的增加量；式(17)通过左偏差和右偏差定义岸桥靠泊位置；式(18)确保所有的船舶在岸线内靠泊；式(19)和式(20)确保没有两艘船舶在同一地点、同一时刻被服务。

3 求解算法

由于模型涉及的决策变量较多，这里将其求解过程分为泊位分配和岸桥分配与调度2个部分，用一种嵌套式循环算法求解。

1) 内循环1用于求解泊位分配问题，运用遗传算法迭代循环求解泊位调度最优值。

2) 内循环2用于求解岸桥分配与调度问题，运用遗传算法迭代循环求最优值。

3) 外循环算法主要用于传递2个内循环之间的参数，实现2个问题的衔接；此外，还可通过2个内循环的迭代和反馈不断改进泊位与岸桥联合调度解的质量和计划的性能。

嵌套式循环算法流程见图1，设计思路如下。

图1 嵌套式循环算法流程

1) 初始化：k=1。

2) 根据每艘船舶的装载量和卸载量，按一定的作业效率设定每艘船舶作业需要的时间。

3) 根据设定的作业时间，运用遗传算法求解泊位计划，获得每艘船舶的靠泊时间和位置。

4) 根据获得的泊位计划，把内循环1中的结果参数传递到内循环2中，运用遗传算法求解岸桥分配与调度，获得岸桥作业顺序。

5) 判断步骤“4)”获得的岸桥调度结果是否正确、合理，若“是”，进入步骤“6)”，否则重新设定初始船舶作业时间，重复步骤“3)”。

6) 判断外循环的迭代次数是否满足设定次数G，若“是”，进入步骤“7)”，否则根据当前的岸桥分配与调度结果更新船舶作业时间，重复步骤“3)”。

7) 当迭代次数满足要求时，退出循环，输出最终解。

步骤“2)”中设定初始船舶作业时间时，令每艘船舶的作业时间=船舶总作业量/岸桥平均作业效率。步骤“5)”中重新设定初始船舶作业时间时，令每艘船舶的作业时间=船舶总作业量/岸桥平均作业效率×(0.9～1.1)。步骤“6)”中在更新船舶作业时间的过程中， 船舶作业时间=∑每一贝位作业时间=∑(单循环次数×岸桥单循环效率+双循环次数×岸桥双循环效率)。

4 数值计算

以某集装箱码头生产作业为例进行数值计算。该码头前沿岸线长1 500 m，配有13台岸桥。模拟该码头24 h内靠泊的5艘大型集装箱船数据，并设定岸桥跨船移动的惩罚系数ε=20。5艘单贝位装卸类型或多贝位装卸类型集装箱船的模型参数数据见表1。案例分析中作以下假设。

表1 模型参数数据

1) 每艘集装箱船按构造分为船头、船尾和中间等3个部分，且其装卸量均匀分成4份，船头和船尾各占1份，中间部分占2份，装卸量随机分布于每一贝位，每一贝位的装卸量随机分布于每一堆垛。

2) 岸桥平均作业效率为30 TEU/(台·h)，岸桥单循环效率为28 TEU/(台·h)，岸桥双循环效率为32 TEU/(台·h)。

根据表2及已知的岸桥单循环和双循环作业效率，可得到调度模型中每一单位任务作业时间。此外，根据优化调度模型和算法可获得5艘船舶的靠泊位置、离泊时间、所分配岸桥数量和岸桥作业任务。

表2 船舶每一贝位的岸桥作业次数

用MATLAB计算，遗传算法迭代到400代时得到最小惩罚189，算法进化收敛图见图2，岸桥服务的任务见表3(表中数值为岸桥编号)。计算得出船舶靠泊位置、最后离港时刻和三部分惩罚值。调度优化结果见表4(为便于计算，离港时刻取整数)。 所设计的泊位与岸桥联合调度优化方法与传统集装箱码头作业方式相比，在保证码头作业最小惩罚的基础上，每艘船舶的作业时间都能得到相应优化。

图2 算法进化收敛图

贝位号船舶1船舶2船舶3船舶4船舶5118411121841113195111429511252962126296212721072128310731293108313103118413114118413124118413

表4 调度优化结果

5 结束语

基于惩罚函数的连续泊位与岸桥联合调度模型具有复杂性特点，这里改进传统的遗传算法，提出一种嵌套式的遗传算法。由案例的数值计算结果可知，该模型和算法在保证客户满意率最大的情况下，使每艘船舶的在港时间都得到一定程度减少。在该模型中，综合考虑了客户满意率的提升问题，未来将基于客户满意率和船舶在港时间等因素建立多目标优化模型，进一步提高码头的运营效率和服务水平。

[1] LI C L，CAI X，LEE C Y. Scheduling with Multiple-Job-On-One-Processor Pattem[J]．IE Transactions，1998，30：433-445．

[2] GUAN Y，XIAO W Q，CHEUNG R K，etal．A Multiprocessor Task Scheduling Model for Berth Allocation：Heuristic and Worst-Ease Analysis[J]．Operations Research Letters，2002，30(5)：343-350．

[3] 韩骏，孙晓娜，靳志宏．集装箱码头泊位与岸桥协调调度优化[J]．大连海事大学学报，2008，34(2)：117-121.

[4] 靳志宏，徐奇，韩骏，等．集装箱码头泊位与岸桥联合动态调度[J]．中国科技论文在线，2011，6(11)：809-814．

[5] AK A，ERERA A L．Simultaneous Berth and Quay Crane Scheduling for Container Ports[R]．Georgia Institute of Technology，2006．

[6] LIANG Chengji， HUANG Youfang，YANG Yang. A Quay Crane Dynamic Scheduling Problem by Hybrid Evolutionary Algorithm for Berth Allocation Planning[J]. Computers & Industrial Engineering, 2009, 56: 1021-1028.

[7] BIRGER R W，DULLAERT R，SCHAEREN V．An Enriched Model for the Integrated Berth Allocation and Quay Crane Assignment Problem[J]．Expert Systems with Applications，2011，38：14136-14147．

[8] 乐美龙，刘菲．基于Memetic算法的泊位和岸桥分配问题[J]．武汉理工大学学报，2011,33(11)：66-71．

[9] YANG Chunxia， WANG Xiaojun， LI Zhenfeng. An Optimization Approach for Coupling Problem of Berth Allocation and Quay Crane Assignment in Container Terminal[J]. Computers & Industrial Engineering, 2012, 63:243-253.

[10] 桂小娅，陆志强，韩笑乐. 集装箱码头连续型泊位与岸桥集成调度[J]. 上海交通大学学报，2013，47(2)：226-229.

[11] 赵坤强，韩晓龙，梁承姬. 连续泊位下集装箱码头港口泊位与桥吊协同调度优化研究[J]. 武汉理工大学学报，2011,33(11)：60-65.

[12] 余刘海，庞洪静. 集装箱码头连续泊位与岸桥联合调度[J]. 科技信息，2013(9)：196-197.

[13] YAVUZ B T, TASKIN Z C, NECATI A,etal. Optimal Berth Allocation and Time-Invariant Quay Crane Assignment[J]. European Journal of Operational Research in Container Terminals, 2013, 1-14.

[14] 杨华龙,滕川川.基于挤压算法的集装箱码头泊位与岸桥联合调度优化[J].大连海事大学学报，2014,40(3):8-12.

[15] 吕赛赛，韩晓龙. 基于船舶优先权的泊位与岸桥耦合优化[J]. 河南科学， 2014,32(4)：531-536.

UnifiedSchedulingforContinuousBerthandQuay-CraneBasedonPenaltyFunction

LIUGuiyun，CHENShanshan，ZHANGXiaoli，LIUMingtao

(Maritime College， Ningbo University， Ningbo 315211, China)

2015-10-29

浙江省软科学项目(2015C25039)；浙江省教育厅项目(pd2013097)

刘桂云(1972—)，女，辽宁鞍山人，教授，研究方向为港口与物流管理。E-mail:liuguiyun@nbu.edu.cn

1000-4653(2016)01-0115-05

U656.1+35

A