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

图1 失约箱箱位优化图

Fig.1 Optimization diagram of non-engagement block location

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

图2

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

Fig.2 Relationship between double ASCs operation task and export container flow

2 模型建立

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

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

(2) 集港箱箱型一致.

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

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

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

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

min f=

$\underset{i \in I}{m a x}$

$T_{i}^{2}$

(1)

s.t.

$\underset{h \in H b \in\left[1, b_{h s}\right) r \in R \in \in E}{ } x_{h b r e}^{n}=1, \quad \forall n \in N_{1}$

(2)

$_{h \in H b \in\left(b_{h \mathrm{~s}},|B|\right] r \in R \quad e \in E}x^{n}_{hbre}=1,\forall n∈N_{2}$

(3)

$_{n∈N_{1} N_{2}h∈H r∈R e∈E} X^{n}_{hbre}+_{n∈V_{1}UV_{2} h∈H r∈R e∈E _{h∈H r∈ e∈E}}X^{n}_{hbre}+_{h∈H r∈R e∈E}O_{hbre}\le Q_{hb}, b∈B$

(4)

$\sum_{n \in N_{1} ⋃ N_{2}} \sum_{h \in H} \sum_{r \in R} \sum_{e \in E} x_{h b r e}^{n}$ +

$\sum_{n \in V_{1} ⋃ V_{2}} \sum_{h \in H} \sum_{r \in R} \sum_{e \in E} x_{h b r e}^{n}$ +

$\sum_{h \in H} \sum_{b \in B} \sum_{e \in E}$ O_hbre≤Q_hr, ∀r∈R

(5)

$\sum_{n \in N_{1} ⋃ N_{2}} \sum_{h \in H} \sum_{r \in R} \sum_{e \in E} x_{h b r e}^{n}$ +

$\sum_{n \in V_{1} ⋃ V_{2}} \sum_{h \in H} \sum_{r \in R} \sum_{e \in E} x_{h b r e}^{n}$ +

$\sum_{h \in H} \sum_{b \in B} \sum_{r \in R}$ O_hbre≤Q_he, ∀e∈E

(6)

$x_{h b r e}^{n}$ ≤

$x_{h b r (e - 1)}^{n}$ +

$x_{h b r (e - 1)}^{n}$ +O_hbre, ∀h∈H, b∈B, r∈R, e∈[|E|], n∈N ₁∪N₂∪V₁∪V₂

(7)

P_m(

$\sum_{e \in (0, e_{1})} x_{h b r e}^{m}$ -

$\sum_{e \in (0, e_{1})} x_{h b r e}^{n}$ )≤P_n+M(1-

$x_{h b r e_{1}}^{n}$ ), ∀m,n∈N ₁, h∈H, b∈[1,b_h_s), r∈R

(8)

$G^{n}_{hbre}=\left \lceil \frac{_{n\in N_{3}\left \lceil exp(_{n\in N_{3}} P_{n}L^{n}_{hbr(e-z)}-_{n\in N_{3}}P_{n}L^{n}_{hbre}) -1\right \rceil }}{exp(_{n \in N_{3} L^{n}_{hbre}\left \lceil exp(n\in N_{3}P_{n}L^{n}_{hbr(e-z)-_{n\in N_{3}}}P_{n}L^{n}_{hbre})-1 \right \rceil })} \right \rceil, \\ \forall h\in H,b\in B,\forall r\in R,\forall e=2,3,\dots,|E|, \forall z=1,2,\dots,(e-1)$

(9)

$\sum_{i \in I_{h_{1}} ⋃ I_{h_{4}}} y_{k_{y h} i} u_{i k_{y}}^{n}$ =2

$\sum_{b \in B} \sum_{r \in R} \sum_{e \in E} x_{h b r e}^{n}$ , ∀h∈H, n∈N ₁∪N₂, k_y∈K_y

(10)

$\sum_{j \in I_{h_{1}} ⋃ I_{h_{2}} ⋃ I_{h_{3}}} y_{k_{y h} i j}$ =1, ∀i∈

$I_{h_{1}}$ ∪

$I_{h_{2}}$ ∪

$I_{h_{3}}$

(11)

$\sum_{j \in I_{h_{4}} ⋃ I_{h_{5}}} y_{k_{y h} i j}$ =1, ∀i∈

$I_{h_{4}}$ ∪

$I_{h_{5}}$

(12)

$\sum_{i \in I_{h_{1}} ⋃ I_{h_{2}} ⋃ I_{h_{3}}} y_{k_{y h} i j}$ =1, ∀j∈

$I_{h_{1}}$ ∪

$I_{h_{2}}$ ∪

$I_{h_{3}}$

(13)

$\sum_{i \in I_{h_{4}} ⋃ I_{h_{5}}} y_{k_{y h} i j}$ =1, ∀j∈

$I_{h_{4}}$ ∪

$I_{h_{5}}$

(14)

$\sum_{k_{y h} \in K_{y}} \sum_{i \in I_{h_{1}} ⋃ I_{h_{2}} ⋃ I_{h_{3}}} \sum_{j \in I_{h_{1}} ⋃ I_{h_{2}} ⋃ I_{h_{3}}} y_{k_{y h} i j}$ =|N₁|+|N₂|+|N₃|

(15)

$\sum_{k_{y h} \in K_{y}} \sum_{i \in I_{h_{4}} ⋃ I_{h_{5}}} \sum_{j \in I_{h_{4}} ⋃ I_{h_{5}}} y_{k_{y h} i j}$ =|N₁|+|N₂|

(16)

$b_{k_{y h 2}}^{T}$ -

$b_{k_{y h 1}}^{T}$ ≥l_y

(17)

$T_{i}^{1}$ =0, ∀i∈I ⁰

(18)

$T_{i}^{2}$ ≥

$T_{i}^{1}$ +(2t₁+max{t₂b_n,t₃r_n}+t₄

$g_{h b r e}^{n}$ )

${u_{n}}_{i k_{y}}$ , ∀i∈I _h3, n∈N₃, h∈H, k_y∈K_y

(19)

$T_{i}^{2}$ ≥

$T_{i}^{1}$ +(2t₁+t₂b_h_s)

${u_{n}}_{i k_{y}}$ , ∀i∈I _h2, n∈N₂, k_y∈K_y

(20)

$T_{i}^{2}$ ≥

$T_{i}^{1}$ +(2t₁+max{t₂b_n,t₃r_n})

${u_{n}}_{i k_{y}}$ , ∀i∈I _h5, n∈N₂, k_y∈K_y

(21)

$T_{i}^{2}$ ≥

$T_{i}^{1}$ +[2t₁+t₂(b_h_s-

$\sum_{b \in B}$ b

$x_{h b r e}^{n}$ )]

$u_{i k_{y}}^{n}$ , ∀i∈I _h1, n∈N₁, k_y∈K_y

(22)

$T_{i}^{2}$ ≥

$T_{i}^{1}$ +[2t₁+t₂(B-b_h_s)]

$u_{i k_{y}}^{n}$ , ∀i∈I _h4, n∈N₁, k_y∈K_y

(23)

$T_{j}^{0}$ ≥

$T_{i}^{2}$ -M(1-

$u_{i k_{y}}^{n} u_{j k_{y}}^{n}$ ), ∀i∈I _h4∪I_h2, j∈I_h1∪I_h5, n∈N₁∪N₂, k_y∈K_y

(24)

$T_{i}^{0}$ ≥

$T_{n}^{0}$ -M(1-

$u_{i k_{y}}^{n}$ ), ∀i∈I _h4, n∈N₁, k_y∈K_y

(25)

$T_{j}^{1}$ ≥

$T_{i}^{2}$ +t₂b_n

$u_{j k_{y}}^{n}$ +M(

$y_{k_{y h} i j}$ -1), ∀i,j∈I _h3, n∈N₃, h∈H, k_y∈K_y

(26)

$T_{j}^{1}$ ≥

$T_{i}^{2}$ +t₂(b_h_s-b_n)

$u_{j k_{y}}^{n}$ +M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h2, j∈I_h3, n∈N₃, h∈H, k_y∈K_y

(27)

$T_{j}^{1}$ ≥

$T_{i}^{2}$ +t₂(|

$\sum_{b \in B}$ bx_mbre-b_n|)

$u_{i k_{y}}^{m} u_{j k_{y}}^{n}$ +M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h1, j∈I_h3, m∈N₁, n∈N₃, h∈H, k_y∈K_y

(28)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂b_h_s}+M(

$y_{k_{y h} i j}$ -1), ∀i,j∈I _h2, h∈H

(29)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h3, j∈I_h2, h∈H

(30)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂

$\sum_{b \in B}$ b

$x_{b r e}^{m} u_{i k_{y}}^{m}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h1, j∈I_h2, m∈N₁, h∈H, k_y∈K_y

(31)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂(b_h_s-

$\sum_{b \in B}$ b

$x_{b r e}^{m}$ )

$u_{i k_{y}}^{m}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i,j∈I _h1, m∈N₁, h∈H, k_y∈K_y

(32)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂b_h_s}+M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h3, j∈I_h1, h∈H

(33)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h2, j∈I_h1, h∈H

(34)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂(b_m-b_h_s)

$u_{i k_{y}}^{m}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i,j∈I _h5, m∈N₂, h∈H, k_y∈K_y

(35)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ }+M(

$y_{k_{y h} i j}$ -1),∀i∈I_h4, j∈I_h5, h∈H

(36)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂(|B|-b_h_s)}+M(

$y_{k_{y h} i j}$ -1), ∀i,j∈I _h4, h∈H

(37)

$T_{j}^{1}$ ≥max{

$T_{j}^{0}$ ,

$T_{i}^{2}$ +t₂(|B|-b_m)

$u_{i k_{y}}^{m}$ }+M(

$y_{k_{y h} i j}$ -1), ∀i∈I _h5, j∈I_h4, m∈N₂, h∈H, k_y∈K_y

(38)

$x_{h b r e}^{n}$ ∈{0,1},

$y_{k_{y h} i j}$ ∈{0,1}

(39)

目标函数式(1)表示最小化场桥的最大完工时间.约束式(2)~(7)表示箱位分配:约束式(2)表示集港箱只能被分配到一个箱位,且落箱位在海侧箱区;约束式(3)表示进口箱只能被分配到一个箱位,且落箱位在陆侧箱区;约束式(4)~(6)表示只能在给定空间范围内堆存集装箱,不能超过箱区内贝位、列、层容量的限制;约束式(7)表示集装箱不能悬空堆存.约束式(8)和(9)表示翻箱:约束式(8)表示优先级较大的集港箱堆存在上层,其中M表示无限大的数;约束式(9)表示翻箱次数.约束式(10)~(16)表示各箱区场桥紧前紧后任务逻辑关系:约束式(10)表示若集装箱n被堆存在箱区h则会被场桥k_y_h作业;约束式(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 混合遗传变邻域搜索算法

Fig.3 Hybrid genetic variable neighborhood search algorithm

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

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

图4

图4 染色体结构示意图

Fig.4 Chromosome structure

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

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

3.2 进化操作

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

图5

图5 交叉操作图

Fig.5 Crossover

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

图6

图6 变邻域操作图

Fig.6 Variable neighborhood search

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

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

3.3 干扰恢复策略

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

min(γ₁f₁(s)+γ₂f₂(s))

(40)

式中:f₁(s)为情景s下的完工时间;f₂(s)= $\sum_{n \in N_{1}} \sum_{i \in I_{h 4}}$ ( $T_{i}^{2}$ - $T_{n}^{1}$ ) $u_{i k_{y}}^{n}$ ,为情景s下的集卡等待时间.干扰发生后优化流程如下:

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

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

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

4 算例实验

4.1 算例描述

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

表1 各箱区各贝位初始堆存情况

Tab.1 Initial storage of shells in each box area

箱区1				箱区2				箱区3
贝位	存量	贝位	存量	贝位	存量	贝位	存量	贝位	存量	贝位	存量
1	37	21	30	1	42	21	42	1	42	21	38
2	32	22	32	2	34	22	22	2	41	22	39
3	40	23	43	3	41	23	37	3	33	23	40
4	38	24	41	4	36	24	35	4	33	24	33
5	40	25	29	5	37	25	32	5	31	25	23
6	40	26	28	6	40	26	40	6	45	26	36
7	34	27	37	7	34	27	35	7	34	27	40
8	35	28	39	8	36	28	36	8	38	28	38
9	38	29	29	9	33	29	37	9	36	29	39
10	39	30	35	10	40	30	42	10	37	30	31
11	45	31	37	11	36	31	43	11	43	31	35
12	30	32	37	12	36	32	41	12	37	32	36
13	33	33	37	13	36	33	42	13	40	33	36
14	42	34	44	14	39	34	28	14	32	34	33
15	36	35	36	15	43	35	40	15	38	35	45
16	36	36	29	16	39	36	36	16	42	36	43
17	36	37	33	17	33	37	37	17	36	37	28
18	38	38	43	18	42	38	35	18	40	38	32
19	39	39	45	19	30	39	42	19	37	39	41
20	0	40	35	20	0	40	32	20	0	40	45

各箱区内有两台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算法对比表

Tab.2 Comparison of CPLEX solving pre optimization model and HGAVNS algorithm

序号	箱区规模	箱量	CPLEX		HGAVNS算法		$\frac{f_{2} - f_{1}}{f_{1}}$ /%
序号	箱区规模	箱量	f₁/min	计算时间/s	f₂/min	计算时间/s	$\frac{f_{2} - f_{1}}{f_{1}}$ /%
1	1×40×10×5	16	12.62	3.58	12.62	6.85	0
2	1×40×10×5	21	17.26	9.31	17.26	10.45	0
3	3×40×10×5	16	10.65	45.16	10.65	60.03	0
4	3×40×10×5	21	14.64	149.15	15.14	78.93	3.4
5	3×40×10×5	30	17.64	323.00	18.22	126.22	3.28
6	3×40×10×5	36	26.42	1 452.31	27.36	150.42	3.55
7	3×40×10×5	42	28.64	3 485.68	29.58	164.20	3.28
8	3×40×10×5	52	35.64	8 468.24	36.83	186.72	3.33
9	3×40×10×5	60	—	>10 000	37.09	270.25	—

注:符号“—”表示Cplex无法在10 000 s之内求得算例的可行解.

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

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

Tab.3 Distribution results of port container of different sizes in multiple container sections

序号	总箱量	先到先服务策略 f₁ /min	本文策略		$\frac{f_{1}-f_{2}}{f_{2}}$ /%
序号	总箱量	先到先服务策略 f₁ /min	f₂ /min	计算时间/s	$\frac{f_{1}-f_{2}}{f_{2}}$ /%
1	30	26.58	19.60	138.59	26.26
2	60	43.66	37.09	270.25	17.71
3	90	66.14	54.33	488.99	17.86
4	120	84.76	68.84	662.68	18.78
5	150	107.33	88.08	961.50	17.94
6	180	129.00	101.31	1 396.32	21.47
7	210	142.40	121.03	1 834.14	15.01
8	240	162.08	139.64	2 402.24	13.85
9	270	183.48	153.76	3 132.09	16.20
10	300	201.77	170.46	3 587.80	15.52

4.3 干扰恢复策略对比

为验证所提干扰恢复策略的有效性,将本文策略与其他两个策略对比.其中,策略1不考虑失约集卡的影响,继续按原计划堆存;策略2基于贪婪思想,通过就近原则达到局部最优.现行港口竞争激烈,为贴近实际取γ₁=γ₂=0.5,从表3序号9中随机取5、10、20、30、40个集港箱偏离预约时段,令集卡偏离预约抵港时刻标准差σ=5,验证送箱集卡在T⁰_n±σ_n、T⁰_n±2σ_n、T⁰_n±3σ_n、T⁰_n±4σ_n和T⁰_n±5σ_n五种偏离状态下对集港完工时间、外集卡等待时间的影响,对比结果如表4所示.

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

Tab.4 Comparison of experimental results of deviation from appointment period

偏离程度	失约数量	完工时间/min			外集卡等待时间/min			计算时间/s
偏离程度	失约数量	策略1	策略2	本文策略	策略1	策略2	本文策略	计算时间/s
T⁰_n±σ_n	5	156.59	158.88	153.85	13.67	12.99	9.04	336.21
	10	157.20	159.29	157.54	14.42	14.08	9.86	614.74
	20	159.40	160.24	157.71	16.09	14.81	6.53	1 152.57
	30	159.82	158.78	160.97	15.37	15.41	5.24	1 727.04
	40	160.39	162.89	162.45	15.62	16.82	3.66	1 853.59
T⁰_n±2σ_n	5	161.14	159.22	151.80	15.29	12.85	8.22	334.60
	10	164.79	162.96	156.78	15.23	12.58	9.38	635.42
	20	165.62	163.29	159.91	18.40	13.87	8.06	1 140.15
	30	171.53	167.22	163.83	20.60	18.30	5.67	1 692.83
	40	173.85	170.80	163.82	20.60	18.33	3.47	2 243.80
T⁰_n±3σ_n	5	177.21	167.87	159.38	18.96	14.21	11.20	330.19
	10	179.28	172.64	160.48	24.62	18.08	9.78	704.33
	20	181.22	173.25	163.59	25.46	20.43	8.39	1 293.72
	30	182.15	176.47	164.86	26.36	23.15	6.41	1 721.61
	40	187.13	178.63	163.63	28.49	25.16	3.58	2 436.29
T⁰_n±4σ_n	5	186.08	175.85	150.93	22.54	16.57	8.92	348.53
	10	191.05	178.33	166.04	22.64	16.04	11.05	706.58
	20	185.06	173.14	164.33	26.49	20.87	8.93	1 236.50
	30	192.48	179.29	162.61	32.44	25.81	5.65	1 783.83
	40	193.81	182.98	158.98	34.00	30.34	3.74	2 386.66
T⁰_n±5σ_n	5	218.94	205.25	163.78	27.15	17.22	9.87	290.43
	10	220.90	212.09	167.85	30.12	20.45	7.30	710.48
	20	240.24	222.44	160.29	36.14	25.06	5.54	1 185.01
	30	248.41	230.48	170.39	39.14	30.21	4.93	1 895.23
	40	259.18	227.71	172.75	43.09	36.33	4.02	2 277.01

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

4.4 灵敏度分析

不同堆场对于完工时间和外集卡送箱等待时间的侧重各不相同,为探究不同失约情景下不同γ₁和γ₂对码头作业规划的影响,随机选取T⁰_n±2σ_n下,不同箱量、不同失约规模的实验数据进行验证,结果如图7, 图8, 图9,图10所示.

图7

图7 150箱量下f₁对比图

Fig.7 Comparison of f₁ with 150 containers

图8

图8 150箱量下f₂对比图

Fig.8 Comparison of f₂ with 150 containers

图9

图9 同权重下f₁对比图

Fig.9 Comparison of f₁ under the same weight

图10

DOI:10.1016/j.ejor.2017.12.040 URL [本文引用: 1]

图10 同权重下f₂对比图

Fig.10 Comparison of f₂ under the same weight

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

5 结论

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

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

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

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

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

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

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

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

参考文献

原文顺序

文献年度倒序

文中引用次数倒序

被引期刊影响因子

[1]

马梦知, 范厚明, 计明军, 等.

集装箱码头送箱集卡预约与场桥调度协同优化

[J]. 交通运输系统工程与信息, 2018, 18(3): 202-209.

[本文引用: 2]

针对送箱集卡随机到港引起的场桥作业不均衡，以及高峰时段场桥资源紧缺、集装箱码头拥堵等问题，构建送箱集卡预约与场桥调度协同优化的二层规划模型.上层目标为集卡在闸口的排队等待时间、预约集港导致集港时段调整的集卡数及所有预约时段未完成作业量所需的场桥时间最小，下层目标为每个预约时段未完成作业量所需的场桥时间最小.设计并行遗传算法求解模型，并以天津东方海陆集装箱码头为例进行算例分析.结果表明，预约集港能够降低集卡在闸口的排队等待时间，且送箱集卡预约和场桥调度的协同优化比独立决策更有利于提高集港效率.

Mengzhi

, FAN

Houming

, JI

Mingjun

, et al.

Integrated optimization of truck appointment for export containers and crane deployment in a container terminal

[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(3): 202-209.

[本文引用: 2]

The randomness of truck arrivals often leads to many problems, such as workload imbalance of cranes among different period, shortage of cranes and terminal congestion during the peak arrival period. An bi-level programming model integrates truck appointment and crane deployment is developed. The minimum truck waiting time at the gate lanes, total number of trucks that shifted their originally intended arrival times, and total crane minutes of workload left at the end of each planning period are taken as the upper programming objectives. And the minimum crane minutes of workload left at the end of each period is taken as the follower programming objective. Then, the parallel genetic algorithm is designed to solve the model. Finally, numerical experiments based on the data of Tianjin Oriental container terminal are given. Calculation result shows that truck appointment for export containers is able to reduce the truck waiting time at the gate lanes. And the integrated optimization of truck appointment and crane deployment is more effective than the independent optimization for improving the efficiency of the container delivery process.

[2]

GHAREHGOZLI

, ZAERPOUR

Stacking outbound barge containers in an automated deep-sea terminal

[J]. European Journal of Operational Research, 2018, 267(3): 977-995.

[3]

, NING

J Z

, WANG

, et al.

Flexible yard management in container terminals for uncertain retrieving sequence

[J]. Ocean & Coastal Management, 2021, 212: 105794.

DOI:10.1016/j.ejor.2018.05.007 URL [本文引用: 1]

[4]

GALLE

, BARNHART

, JAILLET

Yard Crane Scheduling for container storage, retrieval, and relocation

[J]. European Journal of Operational Research, 2018, 271(1): 288-316.

[5]

TORKJAZI

, HUYNH

, SHIRI

Truck appointment systems considering impact to drayage truck tours

[J]. Transportation Research Part E: Logistics and Transportation Review, 2018, 116: 208-228.

DOI:10.1016/j.tre.2018.06.003 URL [本文引用: 1]

[6]

尹延冬, 靳志宏.

集装箱码头失约集卡出口箱落箱位选择优化

[J]. 科学技术与工程, 2021, 21(25): 10956-10966.

YIN

Yandong

, JIN

Zhihong

Optimization of slot selection of export containers under truck no-showing situation in a container terminal

[J]. Science Technology and Engineering, 2021, 21(25): 10956-10966.

DOI:10.1016/j.cie.2016.03.022 URL [本文引用: 1]

[7]

SHA

, ZHANG

, LAN

, et al.

Scheduling optimization of yard cranes with minimal energy consumption at container terminals

[J]. Computers & Industrial Engineering, 2017, 113: 704-713.

[8]

MALDONADO

, GONZÁLEZ-RAMÍREZ

R G

, QUIJADA

, et al.

Analytics meets port logistics: A decision support system for container stacking operations

[J]. Decision Support Systems, 2019, 121: 84-93.

DOI:10.1016/j.dss.2019.04.006 URL [本文引用: 1]

[9]

DE MELO DA SILVA

, ERDOĞAN

, BATTARRA

, et al.

The block retrieval problem

[J]. European Journal of Operational Research, 2018, 265(3): 931-950.

DOI:10.1016/j.ejor.2017.08.048 URL [本文引用: 1]

[10]

范厚明, 孔靓, 岳丽君.

考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化

[J]. 运筹与管理, 2021, 30(6): 26-34.

DOI:10.12005/orms.2021.0176 [本文引用: 1]

为降低送箱集卡到场的不确定性对出口箱堆存和装船效率的影响,以最小化堆场进出场作业系统总作业时间为上层模型的目标,以最小化同一批入场出口箱的堆存时间下层模型的目标,构建了双层混合整数规划模型为进出场的出口箱分配箱位并优化场桥调度。设计改进的遗传模拟退火算法求解上层模型可得出口箱箱位分配方案,求解下层模型可得预翻箱和场桥调度方案,通过不断平衡上下层最优解使堆场堆存和装船作业效率最优。通过数值实验验证了算法和调度策略有效性,研究结果可丰富集装箱码头运营系统优化理论,为提高出口箱堆场作业效率提供决策参考。

FAN

Houming

, KONG

Liang

, YUE

Lijun

Yard crane scheduling and storage space allocation considering container storage, retrieval, and pre-marshalling

[J]. Operations Research and Management Science, 2021, 30(6): 26-34.

DOI:10.12005/orms.2021.0176 [本文引用: 1]

The efficiency of the outbound container storage allocation and yard crane scheduling has an important impact on terminal yard operation. In order to improve the yard wndes uneertain envivonment, a bi-level programming model is proposed considering the relationship between the outbound container stacking and loading work. The upper level model whose object is to minimize the working time of the loading and stacking operation aims to find a plan of the outbound containers storage allocation. According to the plan, the lower level model, serving upper level model, improves the pre-marshalling work first and then the stacking work. The final result is obtained through continuous balance between the loading and stacking work. To solve the model, Imrsoved gebetuc sunykaeed abbeakubg akgirutgn is designed. Through numerical experiments, the validity of the model and IGSAA is verified. The research is conducive to improving the efficiency of yard operations.

[11]

陈超, 台伟力, 杨逸蓝, 等.

出口箱随机入港下的箱区选择与箱位分配协调调度

[J]. 上海交通大学学报, 2014, 48(4): 544-550.

CHEN

Chao

, TAI

Weili

, YANG

Yilan

, et al.

Coordinated scheduling problem for block choice and slot arrangement under outbound container random arrival

[J]. Journal of Shanghai Jiao Tong University, 2014, 48(4): 544-550.