送箱集卡失约下多箱区箱位分配及场桥调度优化
Container Allocation in Multi-Blocks and Optimization of Yard Crane Dispatching in Non-Engagement of Container Delivery Truck
通讯作者: 岳丽君,博士生;E-mail:yuelj11@163.com.
收稿日期: 2022-12-7 修回日期: 2023-01-24 接受日期: 2023-02-21
基金资助: |
|
Received: 2022-12-7 Revised: 2023-01-24 Accepted: 2023-02-21
作者简介 About authors
范厚明(1962-),教授,博士生导师,从事交通运输规划与管理等研究.
船舶进港前,为避免到港船舶无法按班期及时离港,码头需在规定时间内完成集港作业.堆场按送箱集卡预约到港时间制定箱位分配及场桥调度计划,若送箱集卡失约会导致计划失效,进而产生翻箱问题,影响装船效率.针对送箱集卡失约对箱位分配计划、场桥调度计划及集卡等待时间的影响,提出送箱集卡失约下多箱区箱位分配及场桥调度优化问题.考虑集卡预约时段、场桥间安全距离等约束,以集港时间最短为目标,建立混合整数规划模型.设计混合遗传变邻域算法求解模型,在改进遗传算法的基础上增强其局部搜索能力,通过对比不同算法的实验结果可以看出,该算法收敛速度快,求解结果优.结合集卡实际到港时间,衡量失约对不同情景内完工时间和集卡等待时间扰动,提出干扰恢复策略.实验表明,提出的干扰恢复策略能缩短作业完工时间、降低因送箱失约导致的翻箱量,缩短送箱集卡等待时间,提高堆场作业效率.
关键词:
Container collection should be completed within the specified time limit to prevent the arriving ships from being unable to leave the port on schedule. The storage yard should formulate a container allocation plan and yard crane scheduling plan based on the scheduled arrival time of container delivery and loading. Otherwise, the plan will become invalid, which will lead to the problem of container turnover and loading inefficiency. Aimed at the impact of the non-engagement of container delivery and truck collection on the container location allocation plan, yard crane scheduling plan, and the waiting time of the truck, an optimization problem of container location allocation and yard crane scheduling in multi-container areas under non-engagement of container delivery and truck collection is proposed. Considering the constraints such as the booking period of the truck and the safe distance between the two yard cranes, a mixed integer programming model is established with the goal of minimizing the time of port concentration. The hybrid genetic variable neighborhood algorithm is used to solve the model. A comparison of the experimental results of different algorithms indicates that the algorithm in this paper has a fast convergence speed and excellent solution results. Based on the actual arrival time of the container truck, a disturbance recovery strategy is proposed to measure the impact of non-engagement on the completion time and container truck waiting time in different scenarios, an interference recovery strategy is proposed. Experiments show that the interference recovery strategy proposed in this paper not only shortens the job completion time and the number of containers overturned due to box delivery breach, but also reduces the waiting time of container delivery trucks.
Keywords:
本文引用格式
范厚明, 马晓斌, 彭文豪, 岳丽君, 马梦知.
FAN Houming, MA Xiaobin, PENG Wenhao, YUE Lijun, MA Mengzhi.
符号说明
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翻箱一次的时间
T0i—中间变量,场桥最早可开始作业任务i的时刻
T1i—中间变量,场桥开始作业集装箱i的时刻
T2i—中间变量,场桥结束作业任务i的时刻
T0n—输入变量,集装箱n计划到达箱区的时刻
T1n—输入变量,集港箱n实际到达箱区的时刻
V—失约事件发生时,作业完毕的集装箱集合,V1为已进场的集港箱集合,V2为已进场的进口箱集合,V3为已出场的出口箱集合,V1∪V2∪V3=V
自动化集装箱码头各箱区同时具备装卸船和集疏港作业功能,除要求疏港箱尽快离港外,集港箱能否及时按计划送达尤为重要.虽然通过预约系统码头方可获取送箱集卡的预约时间及集港箱相关信息,但受各种主客观因素影响,实际到场时间具有不确定性.若送箱集卡未在计划规定的时间段内及时进港,不仅会导致预先制定的计划失效,还会因场桥被占用而增加后续规定时间段内送箱集卡的交箱等待时间,甚至会致使船舶滞期离港.因此,综合考虑送箱集卡实际到场时间、场桥作业效率等因素,在优化各箱区场桥作业待装船的出口箱、待卸船的进口箱和集港箱基础上,为集港箱分配箱位,确保船舶按时离港是码头亟待解决的问题.
预约系统有利于削减堆场作业高峰时段[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位置,此时翻箱次数比堆存至初始箱位少.
图1
结合箱位分配信息,动态调整的场桥调度计划应缩短完工时间.堆场通常采用两台自动堆垛机(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) 送箱集卡在预约时段内到达数量足够多,即场桥不会等待作业送箱集卡.
箱位分配和场桥调度优化模型如下:
s.t.
目标函数式(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 算法设计
图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,设计扰动度量函数为
式中:f1(s)为情景s下的完工时间;f2(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
箱区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
序号 | 箱区规模 | 箱量 | CPLEX | HGAVNS算法 | ||||
---|---|---|---|---|---|---|---|---|
f1/min | 计算时间/s | f2/min | 计算时间/s | |||||
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
序号 | 总箱量 | 先到先 服务策略 f1 /min | 本文策略 | ||
---|---|---|---|---|---|
f2 /min | 计算时间/s | ||||
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 干扰恢复策略对比
表4 偏离预约时段实验结果对比
Tab.4
偏离程度 | 失约数量 | 完工时间/min | 外集卡等待时间/min | 计算时间/s | |||||
---|---|---|---|---|---|---|---|---|---|
策略1 | 策略2 | 本文策略 | 策略1 | 策略2 | 本文策略 | ||||
T0n±σ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 | ||
T0n±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 | ||
T0n±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 | ||
T0n±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 | ||
T0n±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 灵敏度分析
图7
图8
图9
图10
由图可知:①在相同扰动权重下,随着失约规模增加外集卡等待时间逐渐减少,完工时间相差较小,这是因为外集卡大量失约后增加了可行解的数量,更有利于找到更优解;②在相同箱量、相同失约规模下,外集卡等待时间随γ2的增大而减少,完工时间相应增加,这是因为可行解中偏向外集卡等待时间更少的解增多造成的;③在相同γ2下,随着总箱量增加外集卡等待时间相应增加,这是由于在预约时段一定的情况下,集卡失约导致过多集卡集中到达,可行解数量减少造成的.
5 结论
结合预约信息和实际箱区中需作业的装船箱、卸船箱对双场桥调度影响的影响,对集卡失约下多箱区箱位分配及双场桥调度优化进行研究,具体结论如下.
(1) 码头通过预约机制能缓解码头拥堵,但当实际送箱集卡出现大规模失约时,预优化方案若不及时更新将增加集港完工时间和外集卡等待时间.
(2) 集港箱的交箱次序对送箱集卡的等待时间有较大影响,送箱集卡等待时间和完工时间随偏离程度增大而增加.
(3) 在预约时段不变的情形下,失约规模越大对外集卡等待时间影响越大,但提出的干扰恢复策略可同时兼顾集港完工时间、外集卡等待时间.
(4) 堆场增加集卡等待时间扰动的权重,可在完工时间增加不大的情形下,进一步缩短外集卡等待时间,提升服务质量.
(5) 本文设计的算法求解能力强、求解速度快、求解结果优.
(6) 结合集卡实际到达时间和预约时间,在多个集港箱区内动态调整集港箱堆存计划,可有效减少送箱集卡等待时间、完工时间,提高集港效率.
后续研究重点为集港箱与装船箱、卸船箱比例关系对接力贝位位置的影响,通过动态调整接力贝位的位置,提高集港效率.
参考文献
集装箱码头送箱集卡预约与场桥调度协同优化
[J].针对送箱集卡随机到港引起的场桥作业不均衡,以及高峰时段场桥资源紧缺、集装箱码头拥堵等问题,构建送箱集卡预约与场桥调度协同优化的二层规划模型.上层目标为集卡在闸口的排队等待时间、预约集港导致集港时段调整的集卡数及所有预约时段未完成作业量所需的场桥时间最小,下层目标为每个预约时段未完成作业量所需的场桥时间最小.设计并行遗传算法求解模型,并以天津东方海陆集装箱码头为例进行算例分析.结果表明,预约集港能够降低集卡在闸口的排队等待时间,且送箱集卡预约和场桥调度的协同优化比独立决策更有利于提高集港效率.
Integrated optimization of truck appointment for export containers and crane deployment in a container terminal
[J].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.
Stacking outbound barge containers in an automated deep-sea terminal
[J].DOI:10.1016/j.ejor.2017.12.040 URL [本文引用: 1]
Flexible yard management in container terminals for uncertain retrieving sequence
[J].
Yard Crane Scheduling for container storage, retrieval, and relocation
[J].DOI:10.1016/j.ejor.2018.05.007 URL [本文引用: 1]
Truck appointment systems considering impact to drayage truck tours
[J].DOI:10.1016/j.tre.2018.06.003 URL [本文引用: 1]
集装箱码头失约集卡出口箱落箱位选择优化
[J].
Optimization of slot selection of export containers under truck no-showing situation in a container terminal
[J].
Scheduling optimization of yard cranes with minimal energy consumption at container terminals
[J].DOI:10.1016/j.cie.2016.03.022 URL [本文引用: 1]
Analytics meets port logistics: A decision support system for container stacking operations
[J].DOI:10.1016/j.dss.2019.04.006 URL [本文引用: 1]
The block retrieval problem
[J].DOI:10.1016/j.ejor.2017.08.048 URL [本文引用: 1]
考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化
[J].
DOI:10.12005/orms.2021.0176
[本文引用: 1]
为降低送箱集卡到场的不确定性对出口箱堆存和装船效率的影响,以最小化堆场进出场作业系统总作业时间为上层模型的目标,以最小化同一批入场出口箱的堆存时间下层模型的目标,构建了双层混合整数规划模型为进出场的出口箱分配箱位并优化场桥调度。设计改进的遗传模拟退火算法求解上层模型可得出口箱箱位分配方案,求解下层模型可得预翻箱和场桥调度方案,通过不断平衡上下层最优解使堆场堆存和装船作业效率最优。通过数值实验验证了算法和调度策略有效性,研究结果可丰富集装箱码头运营系统优化理论,为提高出口箱堆场作业效率提供决策参考。
Yard crane scheduling and storage space allocation considering container storage, retrieval, and pre-marshalling
[J].
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.
出口箱随机入港下的箱区选择与箱位分配协调调度
[J].
Coordinated scheduling problem for block choice and slot arrangement under outbound container random arrival
[J].
An exact solution approach for scheduling cooperative gantry cranes
[J].
DOI:10.1016/j.ejor.2018.07.043
[本文引用: 1]
We consider a scheduling problem for two gantry cranes moving on the same rails at a single storage block. Containers originating at the seaside have to be stored in the block and containers that are already stored in the storage area at the beginning of the planning horizon have to be delivered to the landside handover point within given time windows. Most commonly in seaport operations, the berthing time of vessels is to be minimized. Thus, the objective considered in this article is to minimize the makespan of seaside container processing while guaranteeing on-time processing of landside containers and while considering non-crossing constraints among cranes. We allow preemption of seaside container processing. This means that one crane may move a seaside container to an intermediate storage slot, and the other crane takes it to its designated position. This has previously been shown to be an effective method of reducing the makespan when compared to classical approaches. We present a dynamic programming (DP) algorithm and a related beam search heuristic. The DP method makes use of bounding techniques and applies dominance properties of optimal solutions. In computational tests, we show that the DP approach clearly outperforms CPLEX and that it is able to quickly solve instances with real-world yard settings. The beam search heuristic is shown to be capable of quickly improving solutions of heuristic approaches that have previously been introduced in the literature. This allows both algorithms to be applied in real-world online settings, where container data is revealed incrementally. (C) 2018 Elsevier B.V.
/
〈 |
|
〉 |
![](../../../richhtml/1006-2467/richHtml_jats1_1/images/1.png)