0.   引言

随着铁水联运的普及, 集装箱码头作为铁水联运的主要发生场所, 其高效、协调的管理调度关乎整个运输系统的效率和周转。然而, 码头内复杂且相互关联的集装箱操作问题以及空间和装卸设备能力的有限都对其管理产生了较大的影响。同时, 铁路作业区的引入, 使得管理者不仅需要考虑码头前沿与堆场间的协调配合问题, 还需要考虑码头前沿与铁路作业区间的协调配合问题。因而, 如何快速有效地完成集装箱在船舶与列车间的装卸作业也就成为了这些问题中重要的一个。

从目前的国内外有关研究发展现状看, 对该领域的研究还不够深入和系统。有学者对集装箱铁水联运港站装卸作业相关的问题进行了研究^[1-5]。姚瑶研究了铁水联运港站的设备配置问题, 主要关注装卸设备的配备, 并考虑了运营和时间成本^[1]; 刘勇等在研究铁水联运港站的设备配备问题中引入了允许作业时间的概念, 并设计了基于使用权分配的遗传算法对问题进行求解^[2]; 武慧荣研究了单个设备间的调度问题^[3]; 冯力源等研究了不同设备的联合调度问题^[4-5], 其中冯力源考虑了作业过程中的作业顺序、作业时间间隔、作业设备使用等约束^[4], 常祎妹等考虑了装卸同步、龙门吊间的干扰和安全距离、龙门吊(Gantry Crane, GC) 和场桥走行时间及缓冲区等现实约束, 但是缓冲区的引入增加了集装箱落地的次数, 并且该文献研究的是堆场与铁路作业区间的装卸作业调度^[5]。

目前, 大多数学者都关注与集装箱港口设备的集成调度问题。有学者研究了集装箱港口2种设备间的集成调度问题^[6-9]。Lee等研究了泊位分配和场吊调度的集成调度问题, 建立了混合整数规划模型, 目标是为了缩短集装箱码头的总成本, 并设计了模拟退火启发式算法进行模型求解^[6], 但研究只考虑了一个场吊负责一个场区的情况; Niu等研究了集卡调度与集装箱堆场堆存分配的集成调度问题, 考虑了集卡的准备时间, 提出了粒子群优化算法和细菌部落优化算法求解问题^[7]; Zhen等研究了岸桥(Quay Crane, QC) 和集卡(Inner Truck, IT) 的集成调度优化问题, 建立了混合整数规划模型, 并采用基于求解方法的粒子群算法求解模型^[8]; Luo等研究了自动化集装箱码头车辆调度与集装箱存储相结合的集成调度问题, 建立了混合整数规划模型, 并设计了遗传算法求解模型^[9]。

另外, 还有一部分学者研究了集装箱港口3种设备间的集成调度问题^[10-22]。Lau等研究了岸桥、自动引导车与自动堆垛机间的集成调度问题^[10-11]; Xue等研究了岸桥调度、集卡调度与场区位置分配的集成调度问题^[12]; 周鹏飞等研究了岸桥、集卡和场桥间的集成调度问题^[13-22], 其中, 周鹏飞等都研究了集装箱码头调度中的不确定性^{[13, 21]}, 但并未关注铁路作业区与码头前沿间的配合问题。

很多文献在研究该类问题中都考虑了很多现实约束, 比如Chen等在模型的建立中考虑了优先关系、准备时间和阻塞等约束条件^{[14, 16]}, 但是Chen等研究了装载和卸载2个过程^[14], Zeng等仅对装载过程进行了研究^[16]; Chen等在文献[14]的研究基础上, 考虑了集装箱分开堆存的模式, 采用禁忌搜索算法求解模型^[15]; 胡少龙等考虑3种设备的全自由调度问题, 并利用仿真分析, 提出了岸桥、集卡和场吊在不同数量组合下的任务排序和作业时间安排^[18]; Chen等考虑场吊、集卡和岸桥空驶的走行时间, 并利用三阶段算法进行模型求解^[20]。

为了更好地求解模型, 很多文献设计了新颖的求解算法。Lau等设计了遗传算法与最大匹配算法相结合的算法求解问题^[10]; Mak等设计了基于模拟退火原理的新的遗传算法^[17]; 邢曦文设计了改进的蚁群算法求解问题^[19]; He等设计了遗传算法和粒子群算法相结合的混合算法^[22]。

总体来讲, 大多数学者都只局限于研究集装箱码头前沿和堆场2个区域内的装卸作业问题, 而随着铁水联运的发展, 铁路作业区也将影响整个港站的效率, 但这方面的研究不够丰富。另外, 尽管已有越来越多的学者在多种设备的集成调度中考虑了许多现实的约束, 如岸桥间不能相互跨越、安全距离以及装卸的优先限制等约束, 但是较少有人将设备的不确定性考虑在内, 如岸桥、集卡的速度变化等因素。有的学者虽然研究了集装箱码头前沿与铁路作业区间的装卸作业集成调度问题, 但是并未考虑不确定的因素, 因此本文在前人研究成果的基础上, 对集装箱铁水联运港站码头前沿与铁路作业区间的装卸作业集成调度问题展开研究, 并考虑装卸同步作业、岸桥、龙门吊间干扰和安全距离等实际约束条件以及生产调度中可能存在的不确定因素。

1.   问题描述与建模

1.1   问题描述

以集装箱卸船装车作业流程为例: 船舶到达码头后, 事先分配好的岸桥将集装箱从船上卸下, 装至集卡上; 集卡将集装箱从码头前沿运输至铁路作业区龙门吊处; 龙门吊将集装箱从集卡上卸至事先等待好的列车上。卸车装船过程与之相反。图 1为集装箱铁水联运港站铁路作业区与码头前沿装卸作业过程。

在进行集装箱装卸作业时, 一些不确定的因素会对整个作业过程产生较大的影响, 这些不确定因素可分为3类^{[13, 21]}。

(1) 系统外的不确定性

集装箱铁水联运港站的生产调度不是孤立的行为, 它会受到整个运输链前后信息的影响与制约。通常情况下, 这些信息不能事先确定, 并处于动态变化, 例如, 集装箱到港数量、集装箱到港时间、船舶到港时间以及船舶的积配载计划等。这些系统外的不确定因素势必会影响港站生产调度计划的实施与运行。

图  1  集装箱码头车船间装卸作业过程

Figure  1.  Handling operation process between trains and vessels in container terminal

下载: 全尺寸图片 幻灯片

(2) 正常生产调度中的不确定性

这类不确定因素指的是码头生产调度过程中由于设备自身、人为操作以及设备等待或干扰等原因而使得设备作业效率和装卸能力降低的因素。它既来自于港站内复杂的生产调度过程, 又源于数据难于收集。因而, 这类不确定性增加了模型建立的困难性。

(3) 离散异常

这类不确定性包括设备故障、仪器失效、突发事件、事故和外界环境较大幅度分变化等。通常, 在数学上用离散程度来表示, 但在实际的处理过程中采用动态反馈策略对调度模型进行重新优化计算, 从而确保方案的最优性。

本文主要关注第2类不确定性因素, 即正常生产调度中的不确定性, 包括岸桥的走行速度、集卡空驶速度、集卡重载速度、龙门吊的走行速度以及岸桥和龙门吊提箱和放箱的单位时间。这些因素将使模型更符合实际情况, 同时它们也对港站的效率有极大的影响。

本文在以往研究的基础上构建改进模型, 即以整个装卸过程完成时间最小为目标, 建立装卸同步下的岸桥、集卡以及龙门吊集成调度模型, 其中不仅考虑了岸桥和龙门吊间的安全距离、相互间不可跨越等现实约束条件, 还考虑了岸桥走行速度、集卡空驶速度、集卡满载速度、龙门吊走行速度以及岸桥和龙门吊提箱和放箱的单位时间等不确定因素。

1.2   模型假设

为了更加合理地构建模型, 提出了如下假设。

(1) 所有进行装卸作业的船舶和列车都已准备就绪, 等待装卸作业的开始。

(2) 集装箱在船舶和列车上的位置已知。

(3) 岸桥的装卸任务已知, 但是具体的装卸顺序未知。

(4) 所有集装箱列车都只能单层装载。

(5) 为了方便起见, 海运集装箱和铁运集装箱不涉及集装箱换装情况, 且所有装卸的集装箱尺寸均相同。

1.3   模型描述

本文的目标是为了减少整个装卸作业过程中的总完成时间, 因此, 以整个作业过程中的总完成时间T最小为目标函数

式中: F_q、F_k分别为岸桥q和龙门吊k结束装载或卸载作业的完成时间。

式(1) 表示的是集装箱作业过程的总完成时间即为岸桥或者龙门吊完成装卸作业的最大值。

为了确定岸桥、龙门吊和集卡的作业结束时间和开始时间, 设定约束条件为

式中: O₁、O₂分别为龙门吊需要进行装载作业和卸载作业的集装箱的集合; f_i^q为岸桥q完成对集装箱i装载或卸载作业的时间; Q为岸桥q的集合; f_i^k为龙门吊k完成对集装箱i装载或卸载作业的时间; K为龙门吊k的集合; s_i^q为岸桥q开始对集装箱i进行装载或卸载作业的时间; γ_q为随机变量, 表示岸桥q的单位提箱/放箱时间; w_i^q为岸桥q在对集装箱i进行装载或卸载作业时与接续的集卡产生的等待时间; d_ij为任意2个集装箱i, j之间的距离, i≠j; v_q为随机变量, 表示岸桥q的走行速度; α_ij^q为0-1决策变量, 如果岸桥q完成对集装箱i的操作后立即对集装箱j进行操作时, 则为1, 否则为0;γ_k为随机变量, 表示龙门吊k的单位提箱/放箱时间; w_i^k为龙门吊k在对集装箱i进行装载或卸载作业时与接续的集卡产生的等待时间; v_k为随机变量, 表示龙门吊k的走行速度; β_ij^k为0-1决策变量, 如果龙门吊k完成对集装箱i的操作后立即对集装箱j进行操作时, 则为1, 否则为0;f_i^l为集卡l完成对集装箱i装载或卸载作业的时间; s_i^l为集卡l开始对集装箱i进行装载或卸载作业的时间; w_i^lq为集卡l在对集装箱i进行装载或卸载作业时与接续的岸桥q产生的等待时间; $\vartheta_{i}$为0-1决策变量, 如果需要对集装箱i进行的操作是装车卸船, 则为1, 如果需要对集装箱i进行的操作是卸车装船, 则为0;w_i^lk为集卡l在对集装箱i进行装载或卸载作业时与接续的龙门吊k产生的等待时间; ζ_l为随机变量, 表示集卡l空载时的速度; θ_ij为0-1决策变量, 表示集装箱i和j为同一设备连续操作的2个集装箱, 如果它们要进行的操作均为装车卸船或卸车装船作业, 则为1, 否则为0;η_l为随机变量, 表示集卡l重载时的速度; L为集卡l的集合; s_j^q为岸桥q开始对集装箱j进行装载或卸载作业的时间; w_ij^lq为岸桥q在完成2个连续作业的时候, 因集卡l未到而产生的等待时间; s_j^k为龙门吊k开始对集装箱j进行装载或卸载作业的时间; w_ij^lk为龙门吊k在完成2个连续作业的时候, 因集卡l未到而产生的等待时间; s_j^l为集卡l开始对集装箱j进行装载或卸载作业的时间。

式(2)、(3) 表示的是岸桥或龙门吊完成所有集装箱装卸作业的总时间与岸桥或龙门吊完成每一个集装箱装卸作业的时间的关系; 式(4) 表明岸桥q完成对集装箱i的操作时间包括岸桥开始作业的时间、提箱和放箱时间、等待时间以及移动到下一作业位置所需时间; 式(5) 表明龙门吊k完成对集装箱i的操作时间包括龙门吊开始作业时间、提箱和放箱时间、等待时间以及移动到下一作业位置所需时间; 式(6) 表明集卡l完成对集装箱i的操作时间包括集卡的开始作业时间、集卡与岸桥或龙门吊衔接需要的等待时间以及集卡从当前作业位置到下一位作业置的走行时间; 式(7) ~ (9) 表示岸桥、龙门吊或集卡在完成上一个集装箱的装卸任务后开始对下一个集装箱进行作业的实际开始时间, 以式(7) 为例, 岸桥对下一个集装箱作业的实际开始时间是岸桥结束上一集装箱的作业后移动到下一集装箱的时间和集卡到达该集装箱的时间中较大的一个。

为了确定岸桥、龙门吊和集卡的等待时间以及设备间的等待时间, 设定如下约束条件

式中: i′为集装箱的编号, 且与集装箱i和j的装卸作业不同; 其余变量与式(2) ~ (9) 中的含义相同。

式(10) ~ (13) 表示岸桥、龙门吊和集卡等待时间与开始时间和结束时间之间的关系, 以式(10) 为例, 它表明岸桥开始下一作业时, 可能由于接续的集卡还未结束上一作业而产生的等待时间, 即接续集卡完成上一作业的时间大于岸桥开始下一作业的时间; 式(14)、(15) 表示岸桥、龙门吊在完成2个连续作业的时候, 因集卡未到而产生的等待时间与各设备的开始时间与结束时间之间的关系。

为了确定集装箱在龙门吊、岸桥和集卡间的作业顺序, 设定如下作业顺序约束

式中: x_i^q为0-1决策变量, 如果岸桥q对集装箱i进行装载或卸载作业, 则为1, 否则为0;y_i^k为0-1决策变量, 如果龙门吊k对集装箱i进行装载或卸载作业, 则为1, 否则为0;z_i^l为0-1决策变量, 如果集卡l对集装箱i进行装载或卸载作业, 则为1, 否则为0;μ_ij^l为0-1决策变量, 如果集卡l完成对集装箱i的操作后立即对集装箱j进行操作, 则为1, 否则为0。

式(16) ~ (18) 表示的是每个集装箱能且只能被一台岸桥、一台龙门吊或者一辆集卡进行操作; 式(19) ~ (24) 表示的是同一岸桥、龙门吊和集卡能且只能操作一个前序或后续集装箱作业。

为了确保岸桥和龙门吊在进行装卸时的安全, 设定约束条件为

式中: q′为岸桥的编号, 且与岸桥q不同; 其余变量与式(16) ~ (24) 中的含义相同。

式(25)、(26) 表示相邻岸桥或龙门吊间要有一定的安全距离, 不可跨越。

2.   求解算法

因为本文建立的是多种设备间的集成调度模型, 且该问题已经被证实为NP-hard问题, 所以无法在多项式时间内求出精确的结果。因而, 为了求解模型, 本文采用启发式算法。在众多的启发式算法中有较多的文献中采用遗传算法对集成调度模型进行求解, 如Kaveshgar等应用遗传算法对岸桥和集卡的集成调度问题进行求解^[23]; Homayouni等应用遗传算法对岸桥、自动引导车和存储平台之间的集成调度问题进行求解^[24]; Skinner等应用遗传算法对岸桥、跨运车和集卡间的集成调度问题进行求解^[25]。

因而, 本文也应用遗传算法对问题进行求解, 同时考虑到模型的复杂性, 本文设计了改进的多层遗传算法对模型进行求解, 不仅在遗传算法中引入蒙特卡罗方法确定随机变量的值, 还引入均衡算子: 利用上层遗传算法确定龙门吊和岸桥的作业序列, 下层遗传算法确定集卡的作业序列。具体的算法流程见图 2。

2.1   染色体编码

在上层染色体中采取自然数编码的方式进行编码, 如2-5-3-4-1-6, 表示的是2台龙门吊负责对6个集装箱进行装卸作业的作业序列, 其中规定龙门吊1负责对集装箱1、2和3进行装卸作业, 龙门吊2负责对集装箱4、5和6进行装卸作业。因此, 通过编码可以确定龙门吊1的作业序列为集装箱2、3和1, 龙门吊2的作业序列为集装箱5、4和6。同理, 规定这6个集装箱由3台岸桥进行装卸作业, 其中岸桥1负责集装箱1和2, 岸桥2负责集装箱3和4, 岸桥3负责集装箱5和6。因此, 岸桥1的作业序列为集装箱2和1, 岸桥2的作业序列为集装箱3和4, 岸桥3的作业序列为集装箱5和6。

图  2  改进的多层遗传算法流程

Figure  2.  Procedure of improved multi-layer genetic algorithm

下载: 全尺寸图片 幻灯片

下层染色体表示的是集卡任务的分配情况, 在上层作业序列的基础上插入0来表示。以1-2-0-5-6-0-3-4为例, 表示的是集卡1负责集装箱1和2, 集卡2负责集装箱5和6, 集卡3负责集装箱3和4。上、下层初始个体均随时生成, 并且下层的每辆集卡的分配序列必须与上层个体的集装箱作业序列相一致。

2.2   选择操作与适应度函数

为了尽可能地保留较优的个体, 在上下层遗传算法中首先按照轮盘赌的规则进行选择操作, 之后将选择出来的种群中适应度函数值最高的个体完整地复制到下一代的种群当中。这样的方法就可以保证在算法终止的时候, 输出的结果中都是每一代出现过的适应度最优的个体。

遗传算法的收敛速度以及能否找到优化解都与适应度函数有着很大的关系, 因而需要选取合适的适应度函数。因此, 本文将目标函数的倒数作为适应度函数。

2.3   交叉操作

交叉的方法有很多, 本文在上层算法中采用部分匹配交叉的方法, 具体的交叉方法见图 3。

由于下层编码的复杂性, 因而本文采用改进的部分匹配交叉的方法, 即将其中一个父代的部分序列和基因结构传递给子代, 再将另一父代的剩余基因按顺序传递给子代, 见图 4。

图  3  上层部分匹配交叉

Figure  3.  Upper-layer partially mapped crossover

下载: 全尺寸图片 幻灯片

图  4  下层改进的部分匹配交叉

Figure  4.  Sub-layer improved partially mapped crossover

下载: 全尺寸图片 幻灯片

2.4   变异操作

变异的操作方法也有很多种, 本文在上下层遗传算法中都选用置换方法: 随机选取2个基因交换位置, 并将这2个位置上的基因进行交换, 见图 5。

图  5  变异操作

Figure  5.  Mutation operation

下载: 全尺寸图片 幻灯片

2.5   均衡算子

集装箱在多辆集卡间进行分配时, 可能存在这样的一种情况: 某一集卡分配到的集装箱很多, 而另一集卡分配到的集装箱很少, 这种情况不仅影响集卡的作业效率, 还会延长整个过程的完成时间。因此为避免这种现象的出现, 本文在下层遗传算法中引入了均衡算子, 其作用就是保证集装箱的操作任务在各个设备间均衡分配。

在下层遗传算法中完成所有的选择、交叉和变异等遗传操作后, 均衡算子开始选择运输集装箱数量最小和最大的集卡, 并将这些集装箱以均匀的方式重新分配给每一辆集卡, 进而一个新一代的下层个体生成, 并能得到它的适应度函数值。之后, 将新的适应度函数值与原来的适应度函数值进行比较, 如果新值更优, 则用新生成的个体替换原有的个体。

2.6   随机变量的处理方法

由于本文在模型的建立中涉及了一些随机变量, 而随机变量的确定有一定的难度。因而在计算龙门吊、集卡以及岸桥的作业完成时间的时候可以通过蒙特卡罗法进行计算, 通过该方法对岸桥、龙门吊的走行速度、提箱/放箱时间以及集卡的走行速度进行估算, 从而得出模型的较优解。

3.   算例分析

本文选取SRMG5507型龙门吊和GCS0903-00SM1型岸桥作为试验中的装卸设备, 表 1、2分别为龙门吊和岸桥的相关参数, 表 3为模型的相关参数。

表  1  龙门吊的基本参数

Table  1.  Basic parameters of GC

下载: 导出CSV 

| 显示表格

表  2  岸桥的基本参数

Table  2.  Basic parameters of QC

下载: 导出CSV 

| 显示表格

表  3  模型基本参数

Table  3.  Basic parameters of model

下载: 导出CSV 

| 显示表格

为了使试验结果具有更好的收敛性, 通过多次试验对算法的基本参数进行调试, 最终的多层遗传算法的参数见表 4。

表  4  多层遗传算法基本参数

Table  4.  Basic parameters of multi-layer genetic algorithm

下载: 导出CSV 

| 显示表格

首先对模型与算法的可行性进行验证, 选取不同数量的龙门吊、集卡和岸桥, 进行9组试验, 每组试验的龙门吊、集卡、岸桥和集装箱数量见表 5, 并且每组试验进行30次, 将每组30次试验得到的作业完成总时间以及龙门吊、集卡和岸桥的作业完成时间求平均值, 作为输出结果, 故9组试验的作业完成总时间以及龙门吊、集卡和岸桥的作业完成时间的结果见图 6。

表  5  龙门吊、集卡、岸桥和集装箱数量

Table  5.  Numbers of GC, IT, QC and container

下载: 导出CSV 

| 显示表格

为了验证引入均衡算子的必要性, 进行了引入均衡算子与未引入均衡算子的对比试验, 选取3台龙门吊、5辆集卡及3台岸桥对50FEU的集装箱进行作业, 图 7、8分别为引入均衡算子与未引入均衡算子的作业完成总时间和集装箱分配的对比结果。通过图 7、8可以看出: 引入均衡算子后的作业完成总时间比未引入均衡算子的作业完成总时间减少了760.3s, 同时每辆集卡的作业时间基本相同, 并且集装箱在集卡间均匀分配。这是因为未引入均衡算子时, 一些集卡需要等待较长的时间开始对它们负责的第1个集装箱进行操作, 因此, 本文引入均衡算子对整个问题的求解有较好的效果。

图  6  作业完成时间试验结果

Figure  6.  Experiment result of makespan

下载: 全尺寸图片 幻灯片

图  7  引入均衡算子前后作业完成总时间对比

Figure  7.  Comparison of total makespans before and after introducing balanced operator

下载: 全尺寸图片 幻灯片

图  8  引入均衡算子前后集装箱数量对比

Figure  8.  Comparison of numbers of container before and after introducing balanced operator

下载: 全尺寸图片 幻灯片

最后, 考虑到岸桥和龙门吊都是集装箱码头的紧缺资源并且投入成本较高, 而集卡作业机动灵活, 并且成本较低, 因而, 在固定岸桥和龙门吊的数量的基础上, 改变集卡的数量, 从而得到较优的设备配比。

试验中设定岸桥的数量为4台, 龙门吊的数量为3台, 集装箱的数量为80、90和100FEU。每组试验进行30次, 并将每组试验30次得到的不同集装箱和集卡数量下的作业完成总时间求平均值, 作为最后的输出结果, 故不同集装箱和集卡数量下的作业完成总时间见图 9, 可以看出: 随着集装箱数量的增加, 装卸作业完成总时间也随之增加, 同时也可以看出, 在固定岸桥和龙门吊数量的情况下, 随着集卡数量的增加, 装卸作业完成总时间在同一数量的集装箱下会随之减少。

图  9  不同集装箱和集卡数量下的作业完成总时间

Figure  9.  Total makespans under different numbers of containers and ITs

下载: 全尺寸图片 幻灯片

引入边际效益对不同集卡数量下的作业完成总时间进行评估, 边际效益值为每增加一辆集卡后作业完成总时间的增量。根据图 9中不同集装箱和集卡数量下的作业完成总时间可以计算出相应的边际效益值, 见表 6, 可以看出: 这3种数量的集装箱在不同设备配比下出现了相似的规律: 当集卡数量从8辆增加到10辆的时候, 边际效益值较大, 但是当集卡数量继续增加时, 边际效益值明显变小。因而综合考虑作业完成总时间以及边际效益值, 可以得出在集装箱数量为80、90、100FEU时, 较优的设备配比为3台龙门吊、10辆集卡和4台岸桥。

4.   结语

(1) 本文建立了集装箱码头车船间装卸作业集成调度模型, 除了考虑装卸同步、岸桥、龙门吊间干扰和安全距离等实际约束条件, 还着重考虑了装卸作业过程中可能存在的不确定性。这些都将为今后研究铁水联运港站的相关问题提供一定的参考依据。为了有效求解模型, 本文设计了改进的多层遗传算法, 引入均衡算子以保证集装箱在集卡间均匀分配, 并利用蒙特卡罗法处理随机变量。最后, 通过实际算例对模型和算法的可行性和有效性进行了验证, 证明了引入均衡算子的优越性, 并给出了集装箱数量为80、90、100FEU的最优设备配比。

表  6  边际效益

Table  6.  Marginal benefits

下载: 导出CSV 

| 显示表格

(2) 在今后的研究中, 为使问题更贴近实际, 可以将堆存问题与装卸调度问题相结合, 也可以在装卸调度中考虑集卡的堵塞等约束。同时, 为了提高求解效率, 还将对新的求解算法进行研究和设计。