送箱集卡失约下多箱区箱位分配及场桥调度优化

范厚明, 马晓斌, 彭文豪, 岳丽君, 马梦知

(大连海事大学 交通运输工程学院, 辽宁 大连 116026)

符号说明

B—贝位集合,其中b为任一贝位,b∈B,Bh为箱区h内所有贝位集合,bh为箱区h内任一贝位,bhs为箱区h内固定的一个接力贝位,区间[1,bhs)表示海侧箱区贝位,区间(bhs, |B|]表示陆侧箱区贝位,bh,bhs∈Bh,Bh∈B

E—层集合,其中e为任一层,e∈E,Eh为箱区h内所有层的集合,eh为箱区h内任一层,eh∈E,Eh∈E

H—箱区集合,其中h为任一箱区,h∈H

I—失约事件发生后,场桥任务集合,其中i为任一任务,Ih1为箱区h内海侧场桥作业集港箱任务集合,Ih2为箱区h内海侧场桥作业进口箱任务集合,Ih3为箱区h海侧场桥作业出口箱任务集合,Ih4为箱区h内陆侧场桥作业集港箱任务集合,Ih5为箱区h内陆侧场桥作业进口箱任务集合,I0为各箱区中第1个任务的集合

Ky—场桥集合,其中ky为任一场桥,Kyh为箱区h内所有场桥的集合,kyh1为箱区h内海侧场桥,kyh2为箱区h内陆侧场桥,kyh1,kyh2∈Kyh,Kyh∈Ky

ly—输入变量,双场桥之间的安全贝位间距

N—失约事件发生时,待作业的集装箱集合,其中n为任一集装箱,N1为待作业集港箱集合,N2为待作业进口箱集合,N3为待作业出口箱集合,N1∪N2∪N3=N

Ohbre—输入变量,不可用箱位,若h箱区b贝r列e层已堆存集装箱则为1,否则为0

Pn—输入变量,集装箱n优先级

Qhb—输入变量,h箱区内任一贝内集装箱容量

Qhe—输入变量,h箱区内任一层内集装箱容量

Qhr—输入变量,h箱区内任一列内集装箱容量

R—列集合,其中r为任一列,r∈R,Rh为箱区h内所有列的集合,rh为箱区h内任一列,rh∈Rh,Rh∈R

t1—输入变量,场桥从缓冲支架/箱位上提取/放下1个集装箱的耗时

t2—输入变量,自动堆垛机(ASC)大车移动一个贝位的时间

t3—输入变量,ASC小车移动一列的时间

t4—输入变量,ASC翻箱一次的时间

V—失约事件发生时,作业完毕的集装箱集合,V1为已进场的集港箱集合,V2为已进场的进口箱集合,V3为已出场的出口箱集合,V1∪V2∪V3=V

ykyhij—决策变量,若场桥kyh作业完任务i后作业任务j则为1,否则为0

自动化集装箱码头各箱区同时具备装卸船和集疏港作业功能,除要求疏港箱尽快离港外,集港箱能否及时按计划送达尤为重要.虽然通过预约系统码头方可获取送箱集卡的预约时间及集港箱相关信息,但受各种主客观因素影响,实际到场时间具有不确定性.若送箱集卡未在计划规定的时间段内及时进港,不仅会导致预先制定的计划失效,还会因场桥被占用而增加后续规定时间段内送箱集卡的交箱等待时间,甚至会致使船舶滞期离港.因此,综合考虑送箱集卡实际到场时间、场桥作业效率等因素,在优化各箱区场桥作业待装船的出口箱、待卸船的进口箱和集港箱基础上,为集港箱分配箱位,确保船舶按时离港是码头亟待解决的问题.

预约系统有利于削减堆场作业高峰时段[1],部分专家针对给定预约时段内集卡送箱顺序不确定问题展开研究.Gharehgozli等[2]考虑出口箱交箱时间的动态不确定因素和船舶离港时间的不确定性,建立并求解以最小化船舶离港时间为目标的数学规划模型;Yu等[3]分析了外集卡不确定进港对箱区选择与出口箱箱位的影响,建立并求解了双目标规划模型.错过预约时段到达的集卡数量会随预约车辆增多而增多;Galle等[4]在集卡失约条件下,考虑将场桥调度、箱位分配及翻箱问题结合研究;Torkjazi等[5]设计了一种新型集卡预约系统,以平衡每日抵港集卡数并提供最佳预约时间窗;尹延东等[6]通过正态分布近似模拟失约集卡实际到达信息,建立以最小化翻箱数和场桥移动距离为目标的数学模型,该模型在失约事件发生后需重新制定箱位分配和场桥调度计划;Sha等[7]针对场桥的能耗问题,建立以场桥能耗最小化为目标的整数规划模型;Maldonado等[8]考虑集装箱船靠泊时间,以翻箱数量最少为目标建立数学模型;文献[9]中研究了双目标集装箱倒箱问题;范厚明等[10]考虑出口箱进出场、预翻箱等因素对出口箱箱位分配及场桥调度的影响,构建双层混合整数规划模型.因关于多箱区箱位分配及场桥调度优化的现有成果很少,陈超等[11]提出出口箱箱区选择与箱位分配协调调度问题,构建了箱区选择与箱位分配两阶段非线性整数规划模型.

综上可知,现有关于场桥调度的研究仅分析了出口箱集港过程,较少同时优化船舶装卸船作业、出口箱集港作业,但实际作业过程中存在双场桥同时作业进出口箱情况,双场桥之间相互限制;现有针对箱位分配的研究中仅涉及单个箱区内的箱位,欠缺在多箱区之间搜索最优箱位的考虑,但同一船舶的集港箱堆存在多个箱区,各箱区之间的集装箱可互换箱位;现有针对集卡到港时间不确定性研究多采用预测到港时间和分析到港规律等方法,但码头作业环境较复杂,实际情况常与预测或统计结果偏差较大,需针对实际集卡到港信息动态调整调度方案.因此,针对送箱集卡失约下多箱区箱位分配及场桥调度优化问题,考虑送箱集卡实际到港时间与堆场实际工作状况关系,以最小化失约集卡等待时间、场桥完工时间为目标,构建箱位分配及双场桥调度优化模型.

1 问题描述

根据船舶靠泊计划,堆场提前发布若干个预约集港时段,外集卡预约成功后需在预约时段到达.若送箱集卡错过预约时段即失约到达堆场时,将对集港完工时间、翻箱量及集卡等待时间产生影响,堆场结合预约信息及集卡实际到场信息,动态调整箱位分配和场桥调度计划,减少失约影响.

堆场通常按重箱压轻箱、长途箱压短途箱的规则堆存,且优先级较大的集港箱应堆存至上层,否则将产生翻箱作业.失约箱箱位优化如图1所示,同一时段的集港箱堆存在箱区7至箱区10.当箱区7贝39的6号箱失约,则将失约6号箱堆存至箱区8贝39(此位置暂不堆存集装箱)或箱区9贝39(箱6与箱11优先级相同),这两种情形都不会带来额外翻箱;当无法避免翻箱时,堆存至箱区10贝39位置,此时翻箱次数比堆存至初始箱位少.

结合箱位分配信息,动态调整的场桥调度计划应缩短完工时间.堆场通常采用两台自动堆垛机(ASC)接力作业集港箱和进出口箱.集卡送箱到箱区后,陆侧ASC取箱并将其送至接力贝位,海侧ASC在接力贝位提取集港箱放置指定箱位,如图2所示.进口箱作业过程与集港箱相反,出口箱只有海侧ASC作业出场过程.若双ASC同时作业进口箱和出口箱,合理的场桥调度应为:陆侧ASC将集港箱送至接力贝位后,从接力贝位提取进口箱放至指定陆侧箱位;海侧ASC将进口箱送至接力贝位后,从接力贝位提取集港箱放至指定海侧箱位,或提取出口箱放到海侧交接区.结合箱位分配计划,同时协调场桥调度计划,兼顾翻箱与完工时间.

图2 双ASCs作业任务与出口箱流转关系示意图

2 模型建立

构建动态调整模型,为预约到港集装箱分配箱位,制定双场桥调度计划实时监测集卡到港顺序.若出现失约问题影响后续集装箱箱位,则动态调整箱位分配和场桥调度计划,研究基于以下假设.

(1) 集港箱可用箱区数量已知,可根据船舶靠泊计划确定.

(2) 集港箱箱型一致.

(3) 贝内预留翻箱位,不考虑二次翻箱.

(4) 外集卡和双ASCs运输过程中不受外界干扰.

(5) 送箱集卡在预约时段内到达数量足够多,即场桥不会等待作业送箱集卡.

箱位分配和场桥调度优化模型如下:

(1)

s.t.

(2)

(3)

(4)

(5)

(6)

b∈B,r∈R,e∈[2,|E|],

n∈N1∪N2∪V1∪V2

(7)

h∈H,b∈[1,bhs),r∈R

(8)

∀h∈H,b∈B, ∀r∈R, ∀e=2,3,…,|E|, ∀z=1,2,…,(e-1)

(9)

∀h∈H,n∈N1∪N2,ky∈Ky

(10)

(11)

(12)

(13)

(14)

|N1|+|N2|+|N3|

(15)

(16)

(17)

(18)

h∈H,ky∈Ky

(19)

∀i∈Ih2,n∈N2,ky∈Ky

(20)

∀i∈Ih5,n∈N2,ky∈Ky

(21)

∀i∈Ih1,n∈N1,ky∈Ky

(22)

∀i∈Ih4,n∈N1,ky∈Ky

(23)

j∈Ih1∪Ih5,n∈N1∪N2,ky∈Ky

(24)

∀i∈Ih4,n∈N1,ky∈Ky

(25)

∀i,j∈Ih3,n∈N3,

h∈H,ky∈Ky

(26)

∀i∈Ih2,j∈Ih3,n∈N3,

h∈H,ky∈Ky

(27)

M(ykyhij-1), ∀i∈Ih1,j∈Ih3,

m∈N1,n∈N3,h∈H,ky∈Ky

(28)

∀i,j∈Ih2,h∈H

(29)

∀i∈Ih3,j∈Ih2,h∈H

(30)

M(ykyhij-1), ∀i∈Ih1,j∈Ih2,

m∈N1,h∈H,ky∈Ky

(31)

M(ykyhij-1), ∀i,j∈Ih1,

m∈N1,h∈H,ky∈Ky

(32)

∀i∈Ih3,j∈Ih1,h∈H

(33)

∀i∈Ih2,j∈Ih1,h∈H

(34)

M(ykyhij-1), ∀i,j∈Ih5,m∈N2,

h∈H,ky∈Ky

(35)

∀i∈Ih4,j∈Ih5,h∈H

(36)

M(ykyhij-1), ∀i,j∈Ih4,h∈H

(37)

M(ykyhij-1), ∀i∈Ih5,j∈Ih4,

m∈N2,h∈H,ky∈Ky

(38)

(39)

目标函数式(1)表示最小化场桥的最大完工时间.约束式(2)～(7)表示箱位分配:约束式(2)表示集港箱只能被分配到一个箱位,且落箱位在海侧箱区;约束式(3)表示进口箱只能被分配到一个箱位,且落箱位在陆侧箱区;约束式(4)～(6)表示只能在给定空间范围内堆存集装箱,不能超过箱区内贝位、列、层容量的限制;约束式(7)表示集装箱不能悬空堆存.约束式(8)和(9)表示翻箱:约束式(8)表示优先级较大的集港箱堆存在上层,其中M表示无限大的数;约束式(9)表示翻箱次数.约束式(10)～(16)表示各箱区场桥紧前紧后任务逻辑关系:约束式(10)表示若集装箱n被堆存在箱区h则会被场桥kyh作业;约束式(11)和(12)分别表示海侧场桥和陆侧场桥的任一任务只有一个紧后作业;约束式(13)和(14)分别表示海侧场桥和陆侧场桥的任一任务只有一个紧前作业;约束式(15)和(16)分别表示海侧场桥和陆侧场桥的任务量.约束式(17)表示两个场桥间留有安全作业距离.约束式(18)～(38)表示各箱区场桥作业任务时间逻辑关系约束:式(18)表示每个箱区的场桥从0时刻同时开始作业;约束式(19)表示场桥作业出口箱n的结束作业时刻;约束式(20)和(21)分别表示海侧场桥和陆侧场桥作业进口箱n的结束作业时刻;约束式(22)和(23)分别表示海侧场桥和陆侧场桥作业集港箱n的结束作业时刻;约束式(24)表示同一集装箱对应的两个任务,前一任务结束之后,后面的任务才能被作业;约束式(25)表示集卡到港之后,才可以被陆侧场桥作业;约束式(26)～(28)分别表示当出口箱n的紧前任务所属集装箱为出口箱、进口箱、集港箱时的开始作业时刻;约束式(29)～(31)分别表示当海侧场桥作业的进口箱n的紧前任务所属集装箱为进口箱、出口箱、集港箱时的开始作业时刻;约束式(32)～(34)分别表示当海侧场桥作业的集港箱n的紧前任务所属集装箱为集港箱、出口箱、进口箱时的开始作业时刻;约束式(35)和(36)分别表示当陆侧场桥作业的进口箱的紧前任务所属集装箱为进口箱、集港箱时的开始作业时刻;约束式(37)和(38)分别表示当陆侧场桥作业的集港箱的紧前任务所属集装箱为集港箱、进口箱时的开始作业时刻.约束式(39)表示决策变量的取值范围.

3 算法设计

双场桥协调调度问题被证明是NP-Hard问题,利用CPLEX等商业软件无法在有效时间内解决码头实际需求,Kress等[12]设计动态规划算法求解集装箱数量较多时的双场桥调度方案.基于此研究,考虑失约集港箱在多箱区箱位之间的分配,设计混合遗传变邻域搜索算法(Hybrid Genetic Algorithm and Variable Neighborhood Search, HGAVNS)求解,算法流程如图3所示.

图3 混合遗传变邻域搜索算法

3.1 编码方式及初始种群生成

(1) 染色体编码.染色体采用实数编码,编码长度为任务数量,如图4所示.其中,第1行表示任务,任务编号具有唯一性;第2行表示箱号,1～10表示进口箱,11～20表示出口箱,21～30表示集港箱,进口箱和集港箱均会被海侧和陆侧的场桥作业,因此其对应的相同箱号的任务有2个;第3行表示作业上述任务的场桥编号;第4行表示箱区编号,同一箱区有2个不同的场桥,按照箱区大小,场桥编号依次递增,同一箱区中编号小的是陆侧场桥;第五行表示箱位,由5位数字构成,前2位为贝位号,3和4位为列号,第5位为层号,其中,00表示箱区近陆侧的缓冲支架,41表示箱区近海侧的缓冲支架,集港箱和进口箱分别被放置到陆侧或海侧的缓冲支架后被场桥作业.因出口箱的箱位在装卸船过程中已知,故只需分配集港箱和进口箱的堆存箱位,集港箱堆存在海侧,进口箱堆存在陆侧.

图4 染色体结构示意图

(2) 生成初始种群.将所有集港箱平均分成若干份分配给各个箱区,在同一箱区中,将集港箱/进口箱分成2个任务分别分配给2个场桥,将出口箱任务分配给海侧场桥,随机生成所有任务的作业顺序,如图4第1行所示.在可堆存的箱位中,为集港箱和进口箱随机挑选箱位,且挑选的箱位是从集港箱区中所有可堆存的空箱位中随机选择,生成的染色体需满足式(2)～(8)的约束.按上述规则生成一定数量的染色体,构成初始种群.

(3) 适应度函数.取目标函数值倒数为适应度函数.

3.2 进化操作

(1) 交叉算子.计算初始种群中各染色体的适应度并升序排列,选择相邻的2个染色体作为交叉操作中染色体的父代.随机生成2个交叉点,交换其染色体基因值,若交叉后出现部分任务重复或丢失,则将重复的染色体删除,丢失的染色体补充至同箱区,如图5所示.

图5 交叉操作图

(2) 变邻域结构.按照轮盘赌的方式选择较优的父代染色体,因决策变量涉及场桥调度、箱区分配和箱位分配3种,如图6所示.采用3种类邻域结构:①随机找到同一场桥的2个任务,如任务3和任务1,交换其任务作业顺序;②随机选择一个集装箱,如集装箱25,变化其所属箱区;③随机选择同一箱区中2个集港箱的接力任务,如任务12和任务16,交换其箱位.

图6 变邻域操作图

(3) 基因修复.交叉变异过程中可能因箱位变化产生悬空的集装箱,采用如下策略进行修复:按集港箱到场时间排序,检查染色体中堆存在相同箱区、相同贝位、相同堆栈的若干集港箱,如果堆栈的顺序从下往上符合集港箱到场时间的先后顺序,则染色体无需修复,否则,将同箱区、同贝位、同栈的若干箱位,按集港箱到场顺序从上往下重新分配.

(4) 停止准则.变邻域算法中,若变邻域搜索过程中,最优解连续未改变的次数达到给定最大值,则变邻域搜索停止;遗传算法中,若迭代次数达到最大值,则算法终止.

3.3 干扰恢复策略

因码头拥堵或集卡出发时间太晚等原因导致外集卡到港时间不确定,当出现集卡失约现象时,需要系统分析和度量其对场桥调度和箱位分配方案的影响,整合包括对完工时间扰动、外集卡等待时间扰动等多类因素,使该扰动事件的影响最小.设完工时间扰动、集卡等待时间扰动的权重分别为γ1和γ2,设计扰动度量函数为

min(γ1f1(s)+γ2f2(s))

(40)

步骤1利用遗传变邻域算法生成初始计划,若当前情景与计划有出入,则识别干扰因素,度量干扰程度.

步骤2确定紧后任务集,初始化后续任务的时间窗,根据失约集卡到港时间扩展集装箱被作业的时间窗.

步骤3针对失约箱计划堆存箱区内所有集装箱重调度,同时,将失约集卡放入其他箱区,以扰动度量函数的目标值最小为目标,求解约束式(2)～(39)的扰动度量函数目标值,取两者中的较小者为最优的落箱位和场桥调度计划.

4 算例实验

4.1 算例描述

使用MATLAB 2018b编程求解,结果在Inter Core i5 3.1 GHz CPU计算机中求解.箱区规模为40贝×10列×5层,每个贝位预留4个翻箱箱位,即每个贝位有46个箱位可堆存集装箱.假设集港任务在3个箱区内进行,箱区内的初始堆存信息如表1所示.

各箱区内有两台ASC,场桥间安全距离留有4个贝位(4贝×6.096 m/贝=24.383 m)[1].单位贝位长度取7 m,场桥大车移动速度为240 m/min,小车移动速度为120 m/min,场桥提放一个集装箱的时间为0.5 min,翻箱时间为2 min/次,陆侧ASC初始位置在陆侧交接区,海侧ASC在海侧交接区.经参数调试,交叉率为0.8,变异率为0.1,箱量120以下最大遗传代数为200,否则为500,种群数量为200.为保证箱区主要作业集港任务,令集港箱、装船箱与卸船箱箱量按6∶2∶2随机生成.

4.2 算例求解和结果分析

为验证模型的有效性,随机生成9个小规模算例,采用商业计算软件CPLEX和本文HGAVNS分别对模型进行求解,结果如表2所示.随着箱量的增加,CPLEX求解时间呈现指数增长,不适用大规模计算.HGAVNS与CPLEX精确解之间平均误差最大为3.55%,当箱量增加至60时,求解时间超过10 000 s,对比可见本算法求解性能更好.

表2 CPLEX求解预优化模型与HGAVNS算法对比表

经调研可知,一些港口集装箱码头(如大连港集装箱码头)现行堆存策略为先到先作业策略,即根据已到港口集港箱次序,动态搜索临近不产生翻箱的箱位,然后分配给集港箱.将本文调度方法与港口现行调度方法进行对比,10组对比结果如表3所示.由表可知,本文算法适用于不同规模问题,虽求解时间随箱量增加相应增长,但均在合理时间内,最低改善效果为13.85%.

表3 不同规模集港箱于多箱区间分配结果

4.3 干扰恢复策略对比

表4 偏离预约时段实验结果对比

由表可知,本文策略和策略2优于策略1,而本文策略可同时兼顾外集卡等待时间和完工时间.在偏离程度不大情形下,针对小规模问题,本文策略和策略2在完工时间和外集卡等待时间差距不大,随失约规模增加,本文策略在完工时间和外集卡等待时间优势凸显.在外集卡等待时间上,策略2因失约集卡在该作业未失约集卡的时段内被作业,增加了后续任务集的集卡等待时间,故劣于本文策略.

4.4 灵敏度分析

图7 150箱量下f1对比图

图8 150箱量下f2对比图

图9 同权重下f1对比图

图10 同权重下f2对比图

由图可知:①在相同扰动权重下,随着失约规模增加外集卡等待时间逐渐减少,完工时间相差较小,这是因为外集卡大量失约后增加了可行解的数量,更有利于找到更优解;②在相同箱量、相同失约规模下,外集卡等待时间随γ2的增大而减少,完工时间相应增加,这是因为可行解中偏向外集卡等待时间更少的解增多造成的;③在相同γ2下,随着总箱量增加外集卡等待时间相应增加,这是由于在预约时段一定的情况下,集卡失约导致过多集卡集中到达,可行解数量减少造成的.

5 结论

结合预约信息和实际箱区中需作业的装船箱、卸船箱对双场桥调度影响的影响,对集卡失约下多箱区箱位分配及双场桥调度优化进行研究,具体结论如下.

(1) 码头通过预约机制能缓解码头拥堵,但当实际送箱集卡出现大规模失约时,预优化方案若不及时更新将增加集港完工时间和外集卡等待时间.

(2) 集港箱的交箱次序对送箱集卡的等待时间有较大影响,送箱集卡等待时间和完工时间随偏离程度增大而增加.

(3) 在预约时段不变的情形下,失约规模越大对外集卡等待时间影响越大,但提出的干扰恢复策略可同时兼顾集港完工时间、外集卡等待时间.

(4) 堆场增加集卡等待时间扰动的权重,可在完工时间增加不大的情形下,进一步缩短外集卡等待时间,提升服务质量.

(5) 本文设计的算法求解能力强、求解速度快、求解结果优.

(6) 结合集卡实际到达时间和预约时间,在多个集港箱区内动态调整集港箱堆存计划,可有效减少送箱集卡等待时间、完工时间,提高集港效率.

后续研究重点为集港箱与装船箱、卸船箱比例关系对接力贝位位置的影响,通过动态调整接力贝位的位置,提高集港效率.