考虑泊位疏浚的连续型泊位和动态岸桥联合调度
2020-10-23焦小刚郑斐峰徐寅峰
焦小刚， 郑斐峰， 徐寅峰， 刘 明
(1.东华大学 旭日工商管理学院，上海 200051; 2.宁夏大学 信息工程学院，宁夏 银川 750021; 3.同济大学 经济与管理学院，上海 200092)
0 引言
全球经济一体化进程和国际贸易的迅速发展，推动了作为世界经济纽带的航运业迅猛增长。为了在激烈的国际航运业竞争中获得优势和追求规模经济效益，各航运公司近年来竞相建造了许多超大型船舶。船舶大型化趋势势必给航运业终端的港口带来巨大压力和影响。为了能够适应这种趋势，吸引这些“巨无霸”靠泊，给港口带来更大的经济效益，港口势必要改造和升级现有的基础设施以提供优质的服务保障。港口泊位水深是港口的重要技术指标之一，它决定了港口的船舶接纳能力。由于潮汐、台风、泥沙和地质等原因造成的回淤使港口泊位在使用过程中不断淤积泥沙，减少了泊位水深，从而降低了泊位的靠泊能力和靠泊安全性。为此，港口需要定期地进行海事测量和泊位疏浚工作。以天津港为例,天津港深水泊位众多且大多数分布在泥沙回淤严重的口门附近, 泊位回淤速率达1.5～3.4米/年，设计备淤深度为1米，为此每年需要进行2至4次常规维护疏浚[1]。根据在上海洋山港的实地走访调研得知，洋山深水港泊位大约一至两年就需要疏浚一次，每次耗时约一周，而且仅直接费用往往就要几百万元，具体时间长度还受到疏浚船只的工作效率、数量以及天气情况等多种因素的影响。
为了在泊位疏浚工作期间，最大可能地保留港口靠泊装卸服务能力以减少对正常工作的影响，这是每个港口都值得思考的问题，这也是本研究的出发点。针对集装箱港口泊位进行疏浚工作时部分泊位陆续不能使用的现实情况，对如何更好地协调码头前沿泊位和岸桥这两个重要关键资源开展了联合调度，旨在降低船舶周转时间，提升港口服务水平。本文创新之处在于：(1)考虑了泊位疏浚对泊位-岸桥联合调度的影响；(2)考虑了每艘船舶装卸期间岸桥数可变的岸桥调度情形，提高了岸桥的利用率进一步缩短船舶服务时间；(3)为了防止岸桥频繁移动影响其工作效率，限定服务每艘船舶的岸桥数变化不超过1，即仅允许位于船舶最前端或最后端的岸桥在当前船舶任务未完成的情况下移动至相邻船舶进行服务；(4)设计了三个启发式算法进行求解并对它们的性能进行了比较。
1 文献综述
集装箱港口作业区域主要分为码头前沿和后方堆场两大部分，其中码头前沿是港口运营和管理中最为重要的场所。泊位和岸桥是设置在码头前沿的两种重要稀缺资源，它们的工作效率在很大程度上影响着客户满意度和港口运营成本。因此，关于泊位和岸桥的优化调度问题引起了国内外众多学者的关注。为了更好地了解这方面内容，可以参见Bierwirth[2,3]和Carlo[4]等人的综述性文献。这些文献将泊位与岸桥的调度研究划分了层次，形成了三个子问题：泊位分配问题(BAP: Berth Allocation Problem)，岸桥分配问题(QCAP: Quay Crane Assignment Problem)和岸桥调度问题(QCSP:Quay Crane Scheduling Problem)。近年来学术界对这些子问题及其联合问题进行了广泛的研究，以下将对国内外一些相关文献作一个简要的介绍。
Park和Kim[5]开创性地研究了连续型静态泊位和岸桥联合调度问题，该问题被划分为二个阶段进行求解，第一阶段采用次梯度优化方法给出了船舶的靠泊位置和时间以及分配的岸桥数量，在此基础上第二阶段用动态规划方法确定了岸桥的调度方案。Giallombardo等[6]首次提出了QCAssignment Profiles概念，用于解决泊位和岸桥联合调度的策略层问题。 Meisel和Bierwirth[7]建立了一个解决泊位和岸桥联合调度问题的完整框架并分解为三个阶段逐步求解。Hu等[8]为了对船舶燃油消耗，温室气体排放和船舶服务时间进行权衡把连续型动态泊位问题和岸桥分配问题进行了集成，构建了一个非线性多目标混合整数规划模型，为了降低求解复杂度该模型被转化为一个二阶混合整数锥规划模型并设计了对应算法进行求解。Zhen[9]研究了周期性到达的集装箱班轮装卸时长具有随机性的策略级(tactical-level)泊位分配问题。针对装卸时长概率分布已知和未知两种情形分别建立了随机规划模型和鲁棒优化模型并对这两个模型进行了分析和比较。Turkogullari等[10]将岸桥分配数量可变的泊位和岸桥联合问题分解为主次两个子问题，并开发了精确算法进行求解。Zhen等[11]针对具有流量控制和潮汐影响航道的集装箱港口制定每日操作级(operational-level)生产计划的现实问题建立了一个整数规划模型，为了克服问题复杂性带来的求解难度，该模型被转化为一个集合划分问题并利用列生成方法进行求解。Wang等[12]将码头前沿泊位-岸桥分配问题和后方堆场存放空间分配问题集成到一个混合整数线性规划模型中并基于问题特性设计了一个基于列生成方法的启发式算法，通过对大量实际问题算例的求解验证了算法的有效性。Jiao等[13]研究了考虑潮汐航道的连续型泊位和动态岸桥联合调度问题，设计了遗传算法、混合粒子群算法和混合模拟退火算法分别进行求解并对其性能进行了比较，最后通过模拟试验分析了潮汐对泊位和岸桥利用率的影响。
周鹏飞和康海贵[14]建立了考虑船舶到港时间和服务时间随机性的泊位和岸桥联合调度问题并设计了一种改进的遗传算法进行求解。董盼等[15]以船舶在港总成本最小化为目标建立了离散型泊位与岸桥集成分配混合整数规划模型，通过实例分析了不同等待成本与装卸成本比率以及不同可用岸桥数量设置对在港总成本的影响，并得出了最佳的等待成本与装卸成本比率和最合适的岸桥配置数量。乐美龙和刘秀玲[16]将船舶实际靠泊位置与最优靠泊位置的偏差以及岸桥同时工作时的相互干扰这两个因素加入到泊位-岸桥联合调度问题中，以船舶在港时间最短为目标建立了一个混合整数线性规划模型。模型以宁波某集装箱港口实际数据为输入用Gurobi软件和一个两阶段启发式算法进行了测试并给出了一些对企业的生产有实际价值的建议。杨华龙和滕川川[17]构建了以最大化岸桥利用率和最小化船舶在港时间为目标的非线性模型，并设计了一种启发式自适应算法-挤压算法进行优化求解。郝杨杨等[18]从考虑船舶等待和岸桥分配两者公平性为出发点，扩充了现有的泊位与岸桥联合分配模型并设计了一个三阶段领域搜索算法。郑红星等[19]将潮汐的因素加入到泊位和岸桥联合调度问题中，以岸桥作业成本，岸桥移动成本和船舶滞期成本之和最小化为目标建立了一个混合整数规划模型，并用一个嵌入启发式规则的遗传算法进行算例求解。
2 问题描述与建模
2.1 问题描述
为了不中断港口对外业务，集装箱码头泊位疏浚工作通常按照分段分时的原则进行开展，以最大程度地使用泊位，如图1所示，坐标系横轴和纵轴分别代表调度时间和岸线，按照相关文献[7,10,23]方法本文同样将时间和岸线划分为若干个时间段(time step)和泊位段(berth segment)，其中每个时间段为1小时，每个泊位段为50米；船舶的装卸工作量采用Liu等[24]文中的岸桥单位时间段的装卸量(QC-time-step)为单位进行衡量。在泊位疏浚期间船舶动态到达，到达后船舶将被分配足够多的泊位段和岸桥工作时间段以尽快完成其装卸任务，其中靠泊泊位段和靠泊时间不能与任何泊位段的疏浚工作冲突，岸桥分配采用动态分配模式既岸桥可以在各靠泊船舶间移动。
图1 考虑泊位疏浚的船舶调度示意图
本文研究将基于以下几点基本假设：(1)船舶在泊位疏浚期间动态到达；(2)船舶对靠泊位置没有偏好，靠泊后不能改变位置；(3)每条船舶可分配岸桥数量应在预先设定好的范围内；(4)岸桥可以在靠泊的船舶间移动服务，但在同一个时间段内不得移动；(5)为了不影响岸桥在岸线上的布局和减少岸桥工作准备时间，限定船舶在各服务时间段间岸桥的数量变化不超过1；(6)由于物理上的限制，岸桥不能跨越式移动。
2.2 模型构建
集合类参数：
I:调度周期内所有船舶的集合，I={1,2,3,…,|I|}；Q:集装箱码头岸线上所有岸桥的集合，Q={1,2,3,…,|Q|}；B:泊位段的集合，B={1,2,3,…,|B|}；K:调度周期内实施疏浚工作的泊位段序号集合，K={1,2,3,…,|K|}；T:调度周期内时间段的集合，T={1,2,3,…,|T|}。
指标类参数：
i,i′：表示船舶，i,i′∈I；q,q′：表示岸桥，q,q′∈Q；b,b′:表示泊位段，b,b′∈B；k：表示泊位疏浚位置的序号，k∈K；t,t′：表示时间段，t,t′∈T。
输入参数：
决策变量：
(1)优化目标函数：
目标函数为最小化所有船舶的周转时间总和。
(1)
(2)服务时间约束条件:
ai≤si,∀i∈I
(2)
(3)
(4)
(5)
(6)
∀i∈I,∀t∈[2,|T|]
(7)
∀i∈I,∀t∈[1,|T|-1]
(8)
Pit≥1-M(1-Sit),∀i∈I,∀t∈T
(9)
Pit′+Pi,t-1-Pit≤1,∀i∈I,∀t∈[2,|T|),
∀t′∈[t+1,|T|]
(10)
(11)
ei=si+pi-1,∀i∈I
(12)
不等式(2)指船舶到达后才可以开始服务。等式(3)和(4)分别计算船舶服务的开始和结束时间。等式(5)和(6)保证船舶i只能在某一个时段t开始或结束服务。不等式(7)和(8)保证船舶i在服务开始之前或服务结束之后，均处于非服务状态，即Pit=0。不等式(9)表示如果船舶i在t时段开始服务，则马上处于服务状态。不等式(10)保证船舶被服务的连续性。等式(11)和(12)分别计算船舶i的服务时长和结束时间。
(3)泊位分配约束条件:
(13)
(14)
(15)
(16)
(17)
∀i∈I,∀t∈T,∀b∈[2,|B|),∀b′∈[b+1,|B|]
(18)
yi+li-1≤|B|+M(1-Pit),∀i∈I,∀t∈T
(19)
(20)
(21)
∀i∈I,∀b∈B,∀t∈[1,|T|-1]
(22)
∀i∈I,∀b∈B,∀t∈[1,|T|-1]
(23)
∀i∈I,∀b∈B,∀t∈[1,|T|-1]
(24)
∀i∈I,∀b∈B,∀t∈[1,|T|-1]
(25)
(26)
yi+li-1 (27) Yii′+Yii′≤1+M(2-Pit-Pi′t), ∀i,i′∈I,i≠i′,∀t∈T (28) Yit′+Yi′i≥1-M(2-Pit-Pi′t), ∀i,i′∈I,i≠i′,∀t∈T (29) 不等式(13)表示在t时刻所有靠泊船舶的总长度不超过岸线长|B|。等式(14)表示如果t时刻船舶i在服务，其船头一定处在某个位置。不等式(15)和(16)确定船舶i的船头位置。等式(17)保证船舶靠泊时给其分配足够多的泊位段。不等式(18)确保泊位分配的连续性。不等式(19)保证任意船舶的船尾不超出岸线。不等式(20)和(21)确定船舶i的船体位置范围。不等式(22)至(25)保证船舶在服务期间不改变靠泊位置。不等式(26)表示任意泊位段在任一时刻只能分配给一艘船既保证船舶的靠泊位置不冲突。不等式(27)表示在时间-岸线图中如果船舶i在船舶i′下方，则船舶i的船尾位置小于船舶i'的船头位置。不等式(28)和(29)保证在时间-岸线图中船舶i和船舶i'只能有一个在另一个的下方。 (4)岸桥分配约束条件： (30) (31) (32) (33) (34) (35) ∀q∈[2,|Q|),∀q′∈[q+1,|Q|] (36) ∀i,i′∈I,i≠i′,t∈T,∀q,q′∈Q,q≠q′, (37) ∀i∈I,∀t,t′∈T,t≠t′ (38) ∀i∈I,∀t,t′∈T,t≠t′ (39) (5)泊位疏浚约束条件: (44) 等式(40)表示泊位段在疏浚时不能分配给任何船舶。不等式(41)指在某泊位段疏浚工作之前开始服务的船舶若占用该泊位段，则要在该泊位段疏浚开始前结束服务。不等式(42)表示在某泊位段疏浚工作之后结束服务的船舶若占用该泊位段，则该船舶的服务开始时间一定在该泊位段疏浚完成之后。不等式(43)和(44)指当船舶i在某泊位段疏浚时还在进行服务，则其只能靠泊在该疏浚泊位段的上方或下方。 (6)决策变量取值约束: (45) ∀i,i′∈I,i≠i′,∀b∈B,∀t∈T,∀q∈Q,∀k∈K (46) Lim[25]在1998年已经证明了泊位分配问题属于NP-难，因此，本文所研究的考虑泊位疏浚的连续型泊位和动态岸桥联合调度问题也是NP-难，因为它可以退化至泊位分配问题。为此，本文在被广泛应用于组合优化问题中的遗传算法(GA)、粒子群算法(PSO)和模拟退火算法(SA)基础上，结合本文问题特点设计出相应的混合遗传算法(HGA)、混合粒子群算法(HPSO)和混合模拟退火算法(HSA)。接下来本文将详细阐述算法具体原理和解决问题的思路。 图2 一个6艘船舶解编码示意图 在本文提出的三个启发式算法最优解搜索过程中，为了比较解的好坏，需要计算解编码所对应的目标函数值。为此，需要完成以下3个步骤： Step1通过BAP贪婪算法确定每艘船舶靠泊的时间和位置； Step2通过QCAP贪婪算法为每艘船舶靠泊服务期间的每个时间段分配岸桥并判断当前的解是否可行； Step3如果该解可行，那么通过式(1)计算其对应的目标函数值，否则，将其目标函数值设置为充分大的正整数M，这意味着该解将在算法的迭代过程中淘汰。 3.2.1 BAP贪婪算法 为了确定每艘船舶的靠泊时间和位置，本文将泊位分配问题抽象为一个二维空间的装箱问题，如图1所示，可以根据泊位疏浚工作的时间和位置将它们抽象为若干个矩形先行摆放在时间-岸线空间中。根据船舶的长度和解编码中预先生成的靠泊服务时长可以刻画出代表每艘船舶的矩形大小，接下来为每艘船舶按照编码中的靠泊顺序依次搜寻合适的位置使其尽可能早地靠泊，以最大可能地减少船舶的周转时间，其具体步骤如算法1所示，其中关于找寻船舶所有可能被放置的位置时本文参考了Chazelle[26]的算法。在图3中，船舶5的到达时间为a5，其所有可能的停放位置被找到并按照从下到上从左到右的顺序依次编号并尝试停靠，最终确定位置4为符合约束的最早靠泊位置。 图3 泊位分配示意图 图4 岸桥分配示意图 3.2.2 QCAP贪婪算法 上一小节的算法确定了每艘船舶的靠泊位置和时间，接下来本文设计了一个贪婪算法确定每艘船舶在每一个服务时间段中的岸桥分配情况。如算法2中所示，每个船舶每个时间段内的岸桥数目由该时间段内所有船舶的任务紧迫程度决定，既其剩余任务量和剩余服务时间的比值在该时间段内所有船舶中所占的比重越高则给其分配的岸桥数也越多，但同时还需要满足模型中关于岸桥分配时的一些约束。为了更好地理解该算法，图4和表1给出一个示意图和相应的求解过程。其中，船1～5的工作量为{8,9,15,16,19}，最大岸桥数量为{2,3,3,4,4}，distr{t,3}列中括号内为算法第24行直接求得的船舶岸桥分配数目，由于其超出了船舶可使用岸桥数目的范围，算法又对其进行了调整。 表1 岸桥分配算法实例 算法2 求解岸桥数目可变岸桥分配问题的贪婪算法输入:船舶靠泊时间si和位置yi输出:船舶的岸桥分配方案和解的可行性f1f=true; 2for t=1 to|T|3 distr{t,1}=Ø,distr{t,2}=0,distr{t,3}=Ø; 4 for i =1 to|I|5 if船舶i在时间段t正在靠泊服务中6 distr{t,1}=distr{t,1}∪{i};7 distr{t,2}=distr{t,2}+1;8 endif9 endfor10endfor11for t=1 to|T|12 sum=0,avg=Ø,percnt=Ø;13 for j=1 to distr{t,2}14 i=distr{t,1}(j) ;15if船舶i在t时刻开始靠泊服务16remainconi=Ui, remaintimi=pi;//其中pi是解编码中为船舶i预设的靠泊服务时长17endif18avgj=remainconi/remaintimi;19sum=sum+avgj;20endfor21for j=1 to distr{t,2}22 i=distr{t,1}(j) ;23percntj=avgj/sum;24distr{t,3}(j)=round(|Q|∗percntj);25if distr{t,3}(j) 本文将遗传算法、粒子群算法和模拟退火算法的基本原理和研究问题自身特点相结合设计了相应的混合遗传算法(HGA)、混合粒子群算法(HPSO)和混合模拟退火算法(HSA)。混合遗传算法将上文中的两个贪婪算法加入到适应度值的衡量中。在混合粒子群算法中，引入了遗传算法的交叉基因操作用于每一个粒子与其自身和全种群最佳位置的信息交换过程中。混合模拟退火算法的迭代过程中需要产生新的解，本算法采用了遗传算法中的基因变异操作。以上两个算法在解的质量衡量时依然需要上一小节中的两个贪婪算法。由于篇幅的原因，三种算法的基本原理不在这里赘述，请读者参考相关文献[27～29]。 为了验证本文模型的正确性并衡量求解算法的性能，本部分将进行数值模拟测试。本文的问题是一个复杂的NP-难问题，算法求解时间会随着问题的规模呈指数级增长，CPLEX能在可接受的时间内得到小规模问题的精确解但无法解决大规模问题，所以本文分两个部分进行测试。首先，用CPLEX和本文设计的三个算法对小规模数据进行测试；其次，针对大规模数据对三个算法进行测试并比较其各自的性能。 数值模拟测试在Intel Core i7 4790K 4.0GHz CPU，16G内存的Windows 7 个人计算机上进行，CPLEX12.6 在MATLAB 2014b中调用，三个算法也均用MATLAB 2014b编制测试。 如2.1节所述，本文设定每个时间段为1小时，每个泊位段为50米，全部泊位段依次进行疏浚，每个泊位段的疏浚工作时长均设置为5个时间段。参照Rodriguez-Molins等[30]，船舶到港时间的间隔服从参数为2的指数分布；船舶以相同比例分为小型、中型和大型，相应的船舶参数列于表2，其中船舶长度和工作量分别以一个泊位段(berth segment)长度和一个岸桥单个时间段工作量(QC-time-step)为单位。 算法的参数设定如下：(1)混合遗传算法种群规模为200，进化代数为150，通过实验比较选取交叉率和变异率为0.9和0.1；(2)混合粒子群算法种群规模和迭代次数分别设置为200和150；(3)混合模拟退火算法的初始温度和终止温度分别设定为1000和0.001，其中每个温度下的链长设置为200，降温速率为0.9，新解接受与否的依据选择Metropolis准则。由于三个算法具有不同的解搜索策略，为了更公平地对算法进行比较，进行大规模数据测试时不再指定相应的迭代次数而是将它们的运算时间全部设置为2000秒。另外，由于这三种算法解搜索的随机性，下文表格中列出的解均为算法5次运行结果中的最佳解。 表2 船舶参数 表3 未考虑泊位疏浚小规模数据计算结果 表4 考虑泊位疏浚小规模数据计算结果 表5 未考虑泊位疏浚大规模数据计算结果 表6 考虑泊位疏浚大规模数据计算结果 本文研究了泊位疏浚情况下泊位和岸桥联合分配问题，为了更符合真实生产环境，泊位采用连续型的分配方式，岸桥允许在相邻的船舶间进行移动。该问题被刻画为一个以船舶周转时间最小为目标的整数线性规划模型并设计了混合遗传算法(HGA)、混合粒子群算法(HPSO)和混合模拟退火算法(HSA)进行求解。通过分别对小规模和大规模数据的数值模拟测试，验证了模型正确性并比较了三个算法的性能。 集装箱码头生产调度问题十分复杂，本文在泊位岸桥联合分配问题中并未考虑岸桥的调度优化问题以及集卡的联合调度，这将是今后进一步的研究拓展方向。
3 算法设计
3.1 解编码
3.2 解编码目标函数值计算
3.3 三个启发式算法设计
4 仿真实验
4.1 参数设定
4.2 小规模数据测试
4.3 大规模数据测试
5 结论
