自动化集装箱码头同轨双堆垛起重机交接缓冲贝位优化

秦 磊 磊，胡 志 华，郑 玉 馨，田 曦 丹

(上海海事大学 物流研究中心，上海 201306)

0 引 言

随着世界经济一体化迅速发展，全球贸易量持续增长，作为国际货物运输的重要枢纽，集装箱码头承担了大量的中转交接工作，对集装箱运输的经济性和可靠性具有直接影响[1]．与传统的集装箱码头相比，自动化集装箱码头集成了自动化、信息化、智能化等现代物流技术，不仅从技术层面提高了码头整体作业效率，也通过优化管理模式提升了码头多级作业的高效性和稳定性，具有低人工成本等优势，对满足日益增长的生产发展需求具有重要意义．从系统化作业流程来看，自动化集装箱码头主要由闸口到堆场、堆场到岸线、岸线到船舶3部分组成．其中，堆场作业效率是评估码头整体运作效率的重要指标，与闸口和泊位服务水平息息相关．国内外现有的自动化集装箱码头大多采用垂直岸线式堆场布局，设置单箱区双堆垛起重机[2]．与单起重机调度问题不同，双堆垛起重机共享同一轨道，在同一区域进行装卸作业．在该作业模式下，同轨不可穿越的双堆垛起重机并非两个独立的个体，在作业过程中，二者之间可能产生干扰，导致空载或拥堵，设备利用率和安全性显著降低[3]．为保证堆场作业稳步高效进行，码头通常在堆场中设置缓冲贝位，并以此为界进行划分，两台起重机分别在缓冲区两侧进行装卸，通过双堆垛起重机的接力作业完成海陆两侧的存取箱任务，将双堆垛起重机作业干扰范围缩小至缓冲区，降低设备调度的复杂性[4-5]．

基于此，自动化集装箱码头堆场缓冲区选址以及任务处理顺序优化成为同轨双堆垛起重机协同调度的关键．本文构建以最小化任务完工时间为目标的混合整数规划模型，决策缓冲贝位和双堆垛起重机调度序列，并设置算例和数据集，研究安全时间间隔、起重机移动速度、小车处理时间3个模型参数的敏感性．此外，分析缓冲贝位存在与否和缓冲贝位发生变化时，对任务完工时间的影响，以期为优化双堆垛起重机调度方案提供参考．

1 同轨双堆垛起重机调度

集装箱码头双堆垛起重机调度的部分文献见表1．对于双堆垛起重机的调度问题，Briskorn等提出了新型龙门调度算法，对起重机装卸任务进行优先排序，降低起重机调度问题的求解难度[6]．Gharehgozli等将双起重机的调度问题建模为具有优先约束的多重不对称广义旅行商问题，并开发自适应大规模邻域搜索算法，快速得到近似解[7]．Yu等设计了滚动时域调度算法，优化一个混堆集装箱码头的堆场起重机调度问题[8]．梁承姬等研究了集装箱码头AGV和双场吊之间的联合调度问题，考虑了起重机与自动化导引车之间的耦合约束，利用遗传算法得到相应的调度方案[9]．

表1 同轨双堆垛起重机调度优化研究Tab．1 Research on optimal scheduling of the same-track double stacking cranes

在双堆垛起重机的干扰管理方面，Choe等对起重机预备工作进行设置，促进两台堆垛起重机之间的合作，避免相互干扰[10]．Hu等通过分析两台堆垛起重机之间的最小时间间隔来确定起重机之间的干扰[11]．Lu等为了控制双堆垛起重机的调度，通过分析任务间的时间重叠，建立了干扰模型．当设备间作业工序存在耦合时，缓冲区设置是解除设备之间干扰的有效方式[12]．Carlo等设置了一个缓冲区作为临时存储位置，以便将一台起重机的请求留给另一台起重机完成，并设计了14个优先级规则进行比较[13]．Gharehgozli等研究了缓冲区对堆场双堆垛起重机性能的影响，考虑了缓冲区位置设置、区域大小和区域数量等因素[14]．Han等在双堆垛起重机之间设立一个缓冲区，考虑了4种干扰模式来避免冲突[15]．

在上述双堆垛起重机干扰管理方面的文献中，缓冲贝位在模型中是预先给定的，而本文把缓冲贝位作为一个决策变量，将双堆垛起重机之间的移动干扰转移到缓冲贝位上，并开发混合整数规划模型，以优化缓冲贝位和起重机作业序列，研究缓冲贝位对双堆垛起重机调度方案的影响．

2 问题描述

当前，自动化堆场通常采用垂直于海岸线的工艺布局．堆场的一个箱区由nb个贝位、若干列和位于箱区两端的交接区组成，每个交接区有若干交接位(I/O)，并设有位于同一个轨道上的两台不可穿越的堆垛起重机在箱区内协同执行海陆两侧的装卸工作．但由于任务的目标箱位会出现交叉情况，即堆区一侧的堆垛起重机需要在堆区另一侧进行作业，为了该任务的顺利执行，另一侧堆垛起重机需要让出空间，甚至需要离开堆区，这将会增加任务的完工时间，影响箱区作业性能．为了规避两台堆垛起重机之间的干扰，在箱区内某一贝位设置缓冲区，用于临时堆放集装箱．在执行任务的过程中，两台堆垛起重机可以借助缓冲贝位完成任务．经过缓冲贝位的集装箱依次由两台堆垛起重机处理，先由靠近任务起点位置的一侧堆垛起重机将集装箱从起始位置运送到缓冲贝位，接着由另一侧堆垛起重机将集装箱从缓冲贝位运送到目标位置，箱区布局如图1所示．

图1 堆场箱区布局示意图

本文针对一批到达堆场缓冲区(I/O)的集装箱任务，以最小化所有任务的完工时间为目标，研究缓冲贝位的优化以及同轨双堆垛起重机调度问题．数据与集合的设置如下：

集合

B={0，1，…，nb}，堆场箱区的贝位集合，其中0表示到达集装箱位于的I/O点．

N={1，2，…，n}，任务集合，以i、j索引．

K={p，c}，起重机集合，以k索引，由主起重机p和协作起重机c组成．

参数

Oi∈B，任务i的起始位置．

Di∈B，任务i的目标位置．

Ts，两台堆垛起重机之间的安全时间间隔．

Tm，起重机移动一个贝位的时间．

Th，起重机小车吊起/放下一个集装箱的时间．

M1、M2、M3，足够大的数．

决策变量

bik∈B，起重机k执行任务i的起始贝位．

dik∈B，起重机k执行任务i的目标贝位．

sik，起重机k执行任务i的开始时间．

eik，起重机k执行任务i的结束时间．

xijk∈{0，1}，1，起重机k处理完任务i后立即处理任务j；0，否则．

yi∈{0，1}，1，任务i通过缓冲贝位；0，否则．

uij∈{0，1}，1，起重机p在起重机c开始任务j之前完成任务i；0，否则．

z，双堆垛起重机完成所有任务的完工时间．

w，缓冲贝位，w∈B．

3 模 型

基于第2章的问题描述，本文构建了基于缓冲贝位的双堆垛机(ASC)调度模型，模型的域约束如下：

sik，eik，bik，dik≥0；∀i，k

xijk，yi，uij∈{0，1}；∀i，j，k

3.1 基于任务排序的模型约束

约束(1)～(4)给出了双堆垛起重机调度模型，是基于旅行商问题模型建立的．其中，约束(1)、(2)表示每个任务至多只有一个后继任务和一个前继任务，并受(3)和(4)的约束，确保这些任务由两台起重机依次处理一次．

(1)

(2)

(3)

(4)

3.2 基于任务处理时间的模型约束

在起重机协同执行任务的过程中，不管任务i是否通过缓冲贝位，该集装箱都需要起重机p进行运送，式(5)表示起重机p处理该任务的开始时间和结束时间之间的关系；式(6)表示当任务i通过缓冲贝位时(yi=1)，任务i由起重机p和c协同操作，起重机c处理任务i的开始时间和结束时间的关系满足不等式eic≥sic+Tm(dic-bic)+2Th；式(7)表示当任务i和j由同一台起重机执行，且任务j是任务i的后继任务时，两个任务的旅行时间由sjk≥eik+Tm(dik-bjk)计算；约束(8)表示每个任务的结束时间必须晚于开始时间．以上约束中式(6)、(7)的M1=2nnbTm+2nTh．且当任务是取箱作业时，式(5)、(6)中的dik-bik应转换为bik-dik，使任务起始贝位与目标贝位间的差值为非负．

eip≥sip+Tm(dip-bip)+2Th；∀i

(5)

eic≥sic+Tm(dic-bic)+2Th+M1(yi-1)；∀i

(6)

sjk≥eik+Tm(dik-bjk)+M1(xijk-1)；∀i，j，k

(7)

eik≥sik；∀i，k

(8)

3.3 基于起重机安全时间间隔的模型约束

为了规避起重机在缓冲贝位上的干扰，模型引入安全时间间隔，式(9)表示当起重机p在缓冲贝位完成任务i时，起重机c执行任务j的开始时间必须晚于任务i的结束时间加上安全时间间隔，即uij=1⟹sjc≥eip+Ts．式(10)表示起重机p在协作起重机c处理任务j后处理任务i(uij=0)，则应满足不等式eip≥sjc+2Th+Ts，即任务i的结束时间要晚于任务j的开始时间加上安全时间间隔和两个任务的堆垛起重机吊起/放下集装箱的时间之和；其中M2=2nnbTm+2nTh+Ts．式(11)表示起重机按顺序在缓冲贝位处理集装箱；式(12)表示对于一个任务，主起重机p总是在协作起重机c之前处理．

sjc≥eip+Ts+M2(uij-1)；∀i，j

(9)

eip≥sjc-M2uij+2Th+Ts；∀i，j

(10)

(11)

uii=yi；∀i

(12)

3.4 基于缓冲贝位的模型约束

在执行任务的过程中，两台堆垛起重机可以借助缓冲贝位完成任务，也可以不借助缓冲贝位完成任务．式(13)表示主起重机p总是在任务的起始位置开始任务．式(14)～(17)表示如果任务i没有通过缓冲贝位，则主起重机p在任务的目标贝位完成任务，否则在缓冲贝位完成任务前半段．

bip=Oi；∀i

(13)

Di≥dip-M3yi；∀i

(14)

dip≥Di-M3yi；∀i

(15)

w≥dip+M3(yi-1)；∀i

(16)

dip≥w+M3(yi-1)；∀i

(17)

式(14)～(17)满足如下关系：

yi=0⟹dip=Di

yi=1⟹dip=w

式(18)～(21)表示如果任务i通过缓冲贝位，由协作起重机c在缓冲贝位开始后半段任务，并在任务目标贝位完成任务．

w≥bic+M3(yi-1)；∀i

(18)

bic≥w+M3(yi-1)；∀i

(19)

Di≥dic+M3(yi-1)；∀i

(20)

dic≥Di+M3(yi-1)；∀i

(21)

同理，式(18)～(21)满足如下关系：

yi=1⟹bic=w

yi=1⟹dic=Di

式(22)表示如果任务i未通过缓冲贝位，缓冲贝位位于目标贝位的右侧；否则，缓冲贝位位于目标贝位的左侧．式(23)表示若任务i通过缓冲贝位，则协作起重机c将集装箱从缓冲贝位运往目标贝位，否则，协作起重机c不执行任务i．式(14)～(22)中，M3=B．

M3yi≥Di-w；∀i

(22)

(23)

3.5 基本模型

3.5.1 不借助缓冲贝位的基本模型 以最小化所有任务的完工时间为目标，当起重机不借助缓冲贝位完成任务时，所有任务都由主起重机执行，此时双堆垛起重机调度模型相当于解决旅行商问题(travelling salesman problem，TSP)，主要决策主起重机的最优作业序列，目标函数如下：

min {z≥eik；∀i，k∈{p}}

3.5.2 借助缓冲贝位的基本模型 以最小化所有任务的完工时间为目标，缓冲贝位作为一个已知参数，模型主要研究借助固定缓冲贝位规避移动冲突的双堆垛起重机调度，将双堆垛起重机移动冲突转移到缓冲贝位上，主要决策双堆垛起重机最优作业序列，目标函数如下：

min {z≥eik；∀i，k}

3.6 扩展模型

在扩展模型中，将缓冲贝位作为一个决策变量考虑，仍以最小化所有任务的完工时间为目标，模型的主要决策不仅包含双堆垛起重机的最优作业序列，还有最优缓冲贝位的选择，其目标函数如下：

4 数值实验

4.1 生成数据集

本文数据集是根据对上海洋山港自动化集装箱码头的调查确定的．堆场的一个箱区由28个贝位和两端的I/O点构成，每个堆垛起重机在箱区内的行驶速度设置为2.5 m/s，在箱区内吊起/放下一个集装箱的速度设置为2.0 m/s，在实际操作过程中还需要25～30 s的校准时间来调整要操作的集装箱位置．因此，本文假设堆垛起重机的移动速度为6 s/bay，吊起/放下一个集装箱的时间为30 s，两台起重机之间的安全时间间隔为9 s，实际中港口每批到达任务通常为10～20个，因此将任务数分别设置为5、10、20，将任务分成4类，分别用o、a、l、u表示，其中o类任务的目标贝位靠近海侧箱区，在[1，nb/3]内随机生成；a类任务的目标贝位处于箱区中心位置，在[nb/3，2nb/3]内随机生成；l类任务的目标贝位则靠近陆侧箱区，在[2nb/3，nb]内随机生成；u类任务的目标贝位均匀分布在箱区内部，在[1，nb]内随机生成．这些任务的起始贝位均默认为0，即为两端的I/O点．

4.2 算例证明

采用CPLEX求解器求解上述数学规划模型，计算机配置为Intel(R)-32Core(TM)i5-4300U@1.90 GHz．在该模型中，约束(1)、(2)是难约束，增加了模型求解难度．使用拉格朗日松弛法将该模型松弛可获得一个新的模型，从而求得原问题一个较优的下界．算例从两方面评估所提混合整数规划模型的性能，一是模型的计算时间，二是最优解与理论下界的GAP．表2给出了使用求解器分别求解5、10、20个各类任务的计算时间和最优目标，其中算例5o表示5个o类任务，其他算例的注解类似．实验结果表明，求解器在求解5个任务的小型算例时，GAP都较小，且能快速得到局部最优解；在求解10、20个任务的中型算例时，求解器的性能会降低．因此，本文为了保证求解器在求解中型算例时，在可接受的时间内找到可行解，将求解的时间设为3 600 s．在限定的求解时间内，当算例规模为10时，其GAP为45%～75%；当算例规模为20时，其GAP在90%上下．在未来的研究中，可以使用梯度下降法优化拉格朗日乘子，不断提高理论下界值，降低GAP．图2是对在集装箱堆场中均匀分布的7个u类任务的求解结果．该结果表示在贝位7处产生一个最优缓冲区，起重机p的作业序列为2→0→3→4→6→5→1，起重机c的作业序列为2→0→3→4→6→5，所有任务的最小完工时间为1 239 s．

表2 模型求解的目标值和计算时间Tab.2 Target value and calculation time for model solution

图2 7个均匀分布的u类任务的求解结果Fig.2 The solution results of seven uniformly distributed u-type tasks

4.3 实验设计

在7个任务的基础上设计5组实验场景，前3个实验研究模型中3个参数的敏感性，分别分析安全时间间隔(Ts)、堆垛起重机小车吊起/放下集装箱的时间(Th)、堆垛起重机移动速度(Tm)发生变化对结果的影响；实验4研究缓冲贝位发生变化对结果的影响；实验5研究缓冲贝位存在与否对结果的影响．实验目标、设置与结果如表3所示．

表3 实验目标、设置与结果Tab.3 Experiment goals,settings and results

4.4 实验结果及其分析

实验1分析安全时间间隔对各类任务总完工时间的影响．如图3所示，以安全时间间隔Ts=6 s 为基准，当Ts上升到30 s后，o类任务的完工时间增加了14.9%，且对于目标贝位分布在靠近海侧的堆场区域内的o类任务，随着安全时间间隔的增加，目标函数的增长曲线显然更陡峭，表明o类任务完工时间对安全时间间隔的变化更敏感．

图3 安全时间间隔对结果的影响Fig.3 The impact of safe time interval on makespan

实验2分析堆垛起重机小车吊起/放下集装箱的时间对各类任务总完工时间的影响．如图4所示，以小车处理时间Th=15 s为基准，随着Th的增加，4类任务的完成时间均呈上升趋势，且o类任务的完成时间上升幅度最大，l类任务的完成时间上升幅度最小．可见对于小车处理时间的变化，o类任务完工时间的敏感性最强，l类任务完工时间的敏感性最弱．

图4 起重机小车处理时间对结果的影响Fig.4 The impact of crane trolley processing time on makespan

实验3分析堆垛起重机移动速度对各类任务总完工时间的影响．如图5所示，以起重机移动速度Tm=6 s/bay为基准，当Tm增加到18 s/bay时，4类任务的完工时间均呈平稳上升趋势，其中l类任务的完工时间上升幅度最大，o类任务的完工时间上升幅度最小，表明l类任务完工时间对堆垛起重机移动速度的敏感性最强，o类任务完工时间对堆垛起重机移动速度的敏感性最弱．

图5 起重机移动速度对结果的影响Fig.5 The impact of crane moving speed on makespan

实验4分析与最优缓冲贝位(在本例中位于贝位7)相比，任务在其他贝位进行缓冲对总完工时间的影响．如图6所示，当缓冲贝位向最优缓冲贝位靠拢时，每台起重机的工作量慢慢接近均衡状态，起重机分配的任务量以及任务序列发生变化，对堆垛起重机的移动距离造成直接影响，任务完工时间逐渐变短；当缓冲贝位达到最优状态后，任务完工时间的跨度急剧增加，且大部分任务由主起重机运送到目标贝位，另一台协作起重机执行的任务较少，相较于最差缓冲贝位，最优缓冲贝位能提高49.40%的任务完工时间．

图6 缓冲贝位变化对结果的影响Fig.6 The impact of the change of the buffer bay on makespan

实验5分析缓冲贝位存在与否对任务总完工时间的影响．如图7所示，当起重机不借助缓冲贝位完成任务时，所有的进箱任务都由主起重机完成，其任务完工时间是1 380 s．当起重机借助缓冲贝位完成任务时，在未达到最优缓冲贝位时，起重机不借助缓冲贝位能更快地完成任务，而随着缓冲贝位达到最优状态，其任务完工时间相较于不借助缓冲贝位能提高11.38%．

图7 缓冲贝位对结果的影响Fig.7 The impact of the buffer bay on makespan

综上，由图3～5可知，安全时间间隔、起重机小车处理时间以及起重机移动速度对任务完工时间的影响与任务的分布有关，当任务集中分布在紧凑的空间内时，需要大量的时间来同步两台起重机．因此，在起重机调度过程中，应尽量均衡海陆两侧的任务量，从而减少起重机的移动时间和任务完工时间．根据图6，起重机的任务量分配以及作业序列会影响起重机的移动距离，因此，在最优缓冲贝位的选择过程中应尽量平衡两台起重机的任务量，以提高堆场作业效率．根据图7，缓冲贝位的选择和起重机作业序列必须作为集成决策同时进行优化，只有在缓冲贝位和起重机作业序列共同达到最优状态时，堆场才能拥有最佳作业效率．

5 结 语

自动化集装箱码头同轨双堆垛起重机交接缓冲贝位优化问题是影响堆场作业效率的关键问题，对海陆两侧设备的集成调度以及码头服务水平有直接影响．在自动化集装箱码头同轨双堆垛起重机作业过程中，缓冲贝位的设置是解除两台起重机干涉的有效方式，如何优化交接缓冲贝位是堆场作业的关键问题，最优贝位选取有利于提升堆场的作业性能．本文研究在自动化堆场箱区内的缓冲区选址和双堆垛起重机调度问题，缓冲区作为一个临时存储区，解除两台起重机因耦合而存在的干涉．即在调度过程中，起重机可将集装箱临时堆放到缓冲区，协调两台起重机完成集装箱的存取任务．因此，缓冲区的设置把两台起重机的干涉转移到箱区的缓冲贝位上．缓冲区存在下，两台起重机依次执行任务：主起重机从起始位置抓取并堆放集装箱到缓冲贝位之后，协作起重机从缓冲贝位抓取并移动该集装箱到目标位置．故缓冲贝位的选取决定了两台起重机的移动距离．

本文的建模场景是以任务数量和起止贝位已知为前提，但实际码头运作较为复杂，当作业中断或新任务到达时，起重机调度计划最优性将发生改变，从而影响堆场装卸作业效率．因此，考虑任务需求不确定性与动态性的交接缓冲贝位优化是未来研究的主要方向之一．此外，自动化集装箱码头多级物流作业是相互耦合的，每一个任务需求都由多种作业设备协调完成．因此，码头集成调度对交接缓冲贝位的影响还有待进一步的研究和探索．