基于运载能力的集装箱码头集卡调度优化方法研究

孔灵睿 计明军 关云潇 任 刚 郭兴海

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

集装箱码头是集装箱运输的关键节点,在集装箱运输体系中具有重要的地位。2019年全球前十大集装箱码头总吞吐量已达到2.44亿TEU,相比十年前增长37.1%。集装箱码头吞吐量的不断增长,对集装箱码头的作业能力提出了更高的要求。集卡作为集装箱码头水平运输系统中最为重要的机械,负责码头前沿至堆场,以及堆场内各箱区之间的运输作业任务。对集卡的作业调度进行优化,使其与集装箱码头其他作业环节相互配合,能够有效提高码头的作业效率,缩短船舶在港作业时间,提升港口的竞争力。

国内外对于集卡调度问题的研究,主要围绕着优化集卡行驶路径[1-2]、减少空驶距离[3]、缩短作业时间[4]、降低运营成本[5-6]、减少能源消耗[7]等目标展开。集装箱码头作业系统由诸多相互关联的决策过程组成[8],其中,岸桥、集卡、场桥具有很强的交互性,若将其中二者或三者进行集成调度能够进一步提升集装箱码头的装卸作业效率。因此,部分学者将集卡调度同码头的其他作业环节进行联合优化。如集卡与岸桥的集成调度优化[9-11],集卡与场桥的集成调度优化[12-13],以及岸桥-集卡-场桥三者联合的集成调度优化[14-17]。然而,现有的研究均以单位集卡重载一个集装箱为作业单元,即仅考虑了“一车一箱”的运输模式,缺乏对集卡实际运输能力的考虑。实际上,一个集卡最多可同时运输两个20 ft集装箱或一个40 ft集装箱。由于集卡的数量有限,且具有一定的维护成本,在集装箱码头的实际作业过程中,为了充分利用集卡的运载能力,对于20 ft集装箱往往采用“一车两箱”的运输模式,即一个集卡同时运输两个20 ft集装箱,如图1所示。

图1 “一车两箱”的运输模式Figure 1 The transport mode of “one truck, two containers”

以进口箱卸箱过程为例,图3和图4分别展示了“一车一箱”与“一车两箱”运输模式下某一集卡的运输过程。在“一车一箱”运输模式下,集卡在岸边提取一个集装箱后,将其直接运输至堆场的指定位置进行卸箱,完成卸箱后即可返回岸边继续提箱(将该过程称为集卡的一次作业循环);而在“一车两箱”运输模式下,集卡需要在岸边依次提取两个20 ft集装箱,然后分别将两个集装箱运输至堆场的指定位置等待场桥卸箱,当集卡所载集装箱均被场桥卸下后方可返回岸边继续提箱。对比图3和图4可知,虽然在“一车两箱”运输模式下,集卡的一次作业循环相比于“一车一箱”运输模式下的一次作业循环行驶了更长的时间,可能还会产生更多在岸桥和场桥的等待时间,但完成了“一车一箱”运输模式下需要进行两次作业循环才可以完成的任务。理论上,若是能够协调好集卡与岸桥、场桥之间的相互等待关系,以及集卡同时运输的两个集装箱在堆场的卸箱位置,“一车两箱”的运输模式能够极大缩短整个卸箱作业的时间。

图3 “一车一箱”运输模式下集卡作业示意图Figure 3 The transport mode of “one truck, one container”

图4 “一车两箱”运输模式下集卡作业示意图Figure 4 The transport mode of “one truck, two containers”

在以往仅考虑“一车一箱”运输模式的研究中,集卡调度问题只需对集卡的任务指派以及集卡的提箱顺序进行决策。而若同时考虑“一车两箱”的运输模式,集卡作业过程中除了要进行上述决策外,还应对集装箱的配对问题进行决策,即某一集卡的某一作业循环是否同时运输两个集装箱,运输哪两个集装箱,以及配对后的两个集装箱在堆场中的先后配送顺序。此外,在码头的实际作业过程中,岸桥吊具的可伸缩性允许岸桥卸箱作业存在如下三种情况:卸载一个20 ft集装箱;同时卸载两个20 ft集装箱;卸载一个40 ft集装箱。基于以上分析,考虑集卡的实际运输能力以及岸桥的三种作业情景,进口箱卸箱过程中集卡的作业任务与所面临的决策包括(如图5所示):

图5 基于实际运载能力的集卡作业决策Figure 5 Decisions of the truck based on actual transportation capacity

(1)对于岸桥一次同时卸载两个20 ft集装箱的情况,集卡在岸边应当同时完成这两个20 ft集装箱的装载,如图2所示。

图2 岸桥同时卸载两个20 ft集装箱Figure 2 Two 20 ft containers being loaded by a quay crane simultaneously

(2)对于岸桥卸载一个20 ft集装箱的情况,集卡在岸桥处装载该20 ft集装箱后,面临三种不同的抉择:1)直接运输当前集装箱至堆场;2)在原岸桥继续等待装载第二个20 ft集装箱;3)行驶到其他岸桥装载第二个20 ft集装箱。在决策过程中需要对岸桥的空闲时间、集装箱的堆场位置、集卡的运输、等待时间进行协同考虑,做出最优的配对决策,尽可能缩短岸桥的等待时间、减少集卡的运输与等待时间。

(3)对于岸桥卸载一个40 ft集装箱的情况,集卡在岸桥处装载该箱后,应直接运输至堆场。

(4)集卡在完成岸边装载任务后应将集装箱运输至堆场的指定卸箱位置,对于“一车两箱”的运输模式,同一次运输中配对的两个集装箱可能存放于不同箱区。因此需对集装箱的堆场位置、集卡的运输时间以及作业场桥的空闲时间进行协同考虑,决策配对集装箱在堆场的先后配送顺序,以缩短集卡的运输时间以及集卡在堆场的等待时间。

针对上述分析可知,若在传统研究中“一车一箱”运输模式的基础上,并行考虑“一车两箱”的运输模式,需要更好的协调岸桥、集卡、场桥之间的作业关系,做出最优的集装箱配对决策,以期能够进一步发挥集卡的运载能力,提升集卡作业效率,减少船舶的在港作业时间。本文基于集卡的实际运载能力,对集装箱码头进口箱卸箱过程中的集卡调度问题进行研究。研究涉及20 ft与40 ft两种不同箱型,考虑了作业过程中集卡与岸桥和场桥的相互等待时间,以卸箱作业完成时间最小为目标,对集卡指派、提箱顺序、集装箱配对以及配对集装箱的配送顺序进行协同优化。

本文的贡献是:基于集卡的实际运载能力,提出了一个新的科学问题,即考虑“一车两箱”运输模式的集卡调度问题,并证明了该问题是 NP完全的;理论上分析了“一车两箱”运输模式相比于“一车一箱”运输模式的优势以及所涉及的更多的作业决策;针对问题的特征,设计了混合整数规划模型与多起点自适应邻域搜索求解算法,算例实验结果验证了本文所提出方法的有效性,同时也表明本文的集卡调度方案能够充分发挥集卡运力,减少船舶在港作业时间,为集装箱码头实际运营过程中的集卡调度决策提供有益借鉴。

1.1 问题描述

1.1.1 船舶到港口后的卸箱过程描述

本文研究集装箱码头进口箱卸箱作业过程中的集卡调度问题。通常,当一艘集装箱船靠港之前,其泊位位置以及相应作业岸桥的指派与调度计划已知。当船舶靠泊后,岸桥按照相应的作业计划进行卸箱操作。卸箱时,岸桥将集装箱从船舶直接卸至集卡上,若此时岸桥处无集卡,则岸桥需要等待直至集卡到达;若集卡先到达,则集卡需在岸边等待岸桥完成其上一个作业任务。因此,集卡的调度计划应当与岸桥作业计划相互协调,以缩短岸桥与集卡的相互等待时间。当集卡在岸边提箱后需要将所载集装箱运输至堆场指定卸箱位置,通过场桥将集卡上的集装箱卸下。若集卡到达时,场桥未完成上一个作业任务,集卡需要进行等待。因此,集卡的调度计划也应当与场桥的作业相互协调,以减少集卡在堆场的等待时间。

对于进口集装箱,其在船上的位置已知,岸桥卸载每个集装箱的时间由集装箱在船上的位置决定(越靠近海侧的集装箱卸箱时间越长,层数越低的集装箱卸箱时间越长;在设计算例时也考虑了岸桥按照其作业顺序移动到另一个贝继续作业的移动时间)。每个进口集装箱在堆场的堆存位置已知(有关进口箱卸箱顺序以及堆场堆存位置优化的问题可参考Zhu等[18])。进口箱包括20 ft与40 ft两种箱型,对于40 ft集装箱,仅可采用“一车一箱”的运输模式;对于20 ft集装箱,可选择“一车一箱”或“一车两箱”的运输模式。

1.1.2 对于岸桥同时卸载两个20ft集装箱的描述

本文考虑了岸桥可以一次作业两个20 ft集装箱的情况(受岸桥的吊具结构与作业能力限制,同一次作业的两个20 ft集装箱必须在船舶同一层、同一栈、相邻两个贝的箱位中)。如图6所示,较长的长方形表示40 ft集装箱,较短的长方形表示20 ft集装箱,灰色表示不在本港口卸载的集装箱。长方形内的数字为集装箱的编号,也表示岸桥1/岸桥2的作业顺序。对于岸桥1来说,集装箱5和集装箱6可以在同一次作业循环中卸载,集装箱7和集装箱8也可以在同一次作业循环中卸载。同理对于岸桥2,集装箱1和集装箱2、集装箱6和集装箱7、集装箱9和集装箱10也分别可以被岸桥同时卸下。

图6 岸桥卸箱顺序示意图Figure 6 The unloading sequence of the quay crane

为了记录可被岸桥同时卸载的集装箱,我们定义一个集合Ω。对于20 ft集装箱i,如果其能够与集装箱i+1被岸桥同时卸载,则将i加至集合Ω中。若以符号(q,i)表示岸桥q的第i个集装箱,则对于图6来说,Ω={(1,5),(1,7),(2,1),(2,6),(2,9)}。为了充分发挥岸桥的作业效率,本文假定对于任意的(q,i)∈Ω,集装箱(q,i)和(q,i+1)被岸桥同时卸载。如若某集卡被分配装载集装箱(q,i),且(q,i)∈Ω, 则集卡必须同时装载集装箱(q,i)与(q,i+1),进行“一车两箱”的运输。而当集装箱(q,i)∉Ω时,如图5所示,集卡在提取集装箱(q,i)后,需要进行配对决策。

1.1.3 决策内容与决策结果

本研究所涉及的决策内容与决策结果如图7所示,即对集卡指派、提箱顺序、集装箱配对、配对集装箱在堆场的配送顺序四个决策进行协同优化,得到最优的集卡运输序列,以最小化整个卸箱作业结束的时间(最后一个集装箱被运至堆场并完成卸箱的时间)。

图7 研究所涉及的决策内容与决策结果Figure 7 Decisions and consequences of the study

1.2 模型构建

参数设置

C:待卸船进口集装箱集合,(q,i)∈C表示岸桥q第i次作业的集装箱;

C20:待卸船20 ft集装箱集合;

C40:待卸船40 ft集装箱集合;

B:场桥数量;

Q:岸桥数量;

S:集卡数量;

δ(q.i):岸桥卸载集装箱(q,i)所需的时间;

β:场桥作业一个集装箱所需的时间;

:场桥从集装箱(q,i)的堆场位置移动至集装箱(l,j)的堆场位置所需的时间;

:集卡从集装箱(q,i)的岸边位置行驶至集装箱(l,j)的岸边位置所需的时间(某一集装箱的岸边位置是指为了提取该集装箱,集卡应到达的位置);

:集卡从集装箱(q,i)的堆场位置行驶至集装箱(l,j)的岸边位置所需的时间;

:集卡从集装箱(q,i)的堆场位置行驶至集装箱(l,j)的堆场位置所需的时间;

O:虚拟起始任务;

O′:虚拟结束任务。

变量设置

:0-1决策变量,若集装箱(q,i)和(l,j)由同一辆集卡运输,且集装箱(q,i)为集装箱(l,j)的紧前作业(提箱过程),则否则

:0-1决策变量,若集装箱(q,i)和(l,j)由同一场桥作业,且集装箱(q,i)为集装箱(l,j)的紧前作业,则,否则

:0-1决策变量,若集装箱(q,i)和(l,j)由同一辆集卡同时运输(互为配对集装箱),且集卡在堆场先配送集装箱(q,i)后配送集装箱(l,j),那么,否则

t(q,i):岸桥开始作业集装箱(q,i)的时间;

T(q,i):场桥开始作业集装箱(q,i)的时间;

F:卸箱作业结束的时间。

基于上述参数与变量定义,建立混合整数规划模型如下:

模型的目标函数如式(1)所示,表示为最小化卸箱作业结束的时间。

式(2)定义了卸箱作业结束的时间,即变量F。

式(3)和式(4)表示任一集卡的作业任务有且仅有一个紧前任务和一个紧后任务;式(5)和式(6)表示任一场桥作业任务有且仅有一个紧前任务和一个紧后任务。

式(7)～(10)为集装箱配对决策的相关约束:式(7)表示40 ft集装箱只能由一辆集卡单独运送,不可与其他集装箱进行配对运输;式(8)表示若集装箱(q,i)和(q,i+1)由岸桥同时卸下,那么他们一定互为配对箱;式(9)表示对于任意的20 ft集装箱,最多只能有一个20 ft集装箱与其配对;式(10)定义了决策变量y与m的关系,表示若两个集装箱为同一集卡同次运输的两个配对箱,那么这两个集装箱一定互为该集卡的紧前紧后作业任务。

式(11)和(12)表示岸桥按照卸箱顺序进行连续作业的时间约束;其中,约束(11)表示若集装箱(q,i)和(q,i+1)由岸桥同时卸载,那么岸桥开始作业这两个集装箱的时间相同;约束(12)表示,若集装箱(q,i)和(q,i+1)不能被岸桥同时卸载,那么岸桥开始卸载集装箱(q,i+1)的时间要大于岸桥开始卸载集装箱(q,i)的时间加上卸载集装箱(q,i)所需的时间,以保证岸桥的作业顺序以及岸桥作业的连续性;式(13)为场桥连续作业的时间约束。

式(14)～(20)约束了集卡在各个点之间(堆场-岸边、岸边-岸边、岸边-堆场、堆场-堆场)的连续运输时间:式(14)约束了集卡从堆场行驶至岸边时的连续运输时间;式(15)约束了如下特殊情况发生时集卡从堆场行驶至岸边的连续运输时间:集卡从堆场出发去岸边提取集装箱(l,j),其紧前作业任务为集装箱(q,i),集装箱(q,i)与另一个集装箱(h,k)为配对箱且集卡在堆场运输时先配送集装箱(q,i)后配送集装箱(h,k);若式(15)成立,由于两边(时间)之和大于第三边(时间),式(15)可将式(14)覆盖,若式(15)不成立,则式(14)发挥作用;式(16)约束当两个紧前紧后作业的集装箱为配对箱时,集卡从岸边到岸边的连续运输时间;式(17)～(19)表示集卡从岸边运输集装箱到堆场的时间约束;其中式(17)表示当一个集装箱不与任何其他集装箱配对时,集卡从岸边运输该集装箱至堆场情况;式(18)约束了集装箱(q,i)是(l,j)的紧前作业集装箱、集装箱(q,i)和(l,j)为配对集装箱并且在堆场先配送集装箱(q,i)时,集卡从岸边到堆场的连续运输时间;式(19)约束了集装箱(q,i)是(l,j)的紧前作业集装箱、集装箱(q,i)和(l,j)为配对集装箱并且在堆场先配送集装箱(l,j)时,集卡从岸边到堆场的连续运输时间;式(20)约束了当两个集装箱为配对集装箱时,集卡从堆场到堆场的连续运输时间。

式(21)与(22)为集卡的数量约束;式(23)和式(24)为场桥的数量约束。

式(25)定义了变量的取值范围。

为表明问题求解时间的复杂性,本文提出如下定理并加以证明。

定理基于运载能力的集装箱码头集卡调度问题(以下简称为TSBTC问题)是NP完全问题。

证明:考虑如下特殊情况:集卡数量为1,岸桥与场桥的数量为无限,那么此时集卡在岸桥和场桥处不发生等待,且问题的目标函数值等于该集卡的运输时间加上场桥作业一次的时间。图8分别展示了当有两个待卸集装箱时,集卡进行“一车两箱”运输和“一车一箱”运输时的行驶路径。由图8可知,对于任意一种运输模式,集卡均需要行驶三段路径,经过四个节点且每个节点仅经过一次,来完成卸箱任务。若集装箱的数量为N,无论进行配对运输的集装箱的数量为多少,集卡均需要行驶2N-1段路径,经过2N个节点且每个节点仅经过一次,来完成卸箱任务。由此可知,在该特殊情况下TSBTC问题同旅行商问题(TSP)的性质类似,均为包含若干节点且每个节点仅访问一次的路径选择问题。而TSP已被证明是NP完全问题[19],因此可以使用规约方法将TSP规约至本文所研究的TSBTC问题,并说明TSBTC问题为NP问题,即可证明TSBTC问题是NP完全问题。

图8 集卡进行“一车两箱”运输和“一车一箱”运输时的行驶路径Figure 8 The driving path of the truck in “one truck, two containers” and “one truck, one container” transportation

首先,可以很容易证明TSBTC问题为NP问题:给定一个集卡调度方案,可以在o(N3)时间内验证方案的可行性(对应模型中o(N3)个线性约束),即可以在多项式时间内验证解的正确性,因此TSBTC问题为NP问题。

证明TSBTC问题能够规约至TSP,首先需要基于TSP的参数构造TSBTC问题实例。

TSP描述如下:给定n+1个节点,求从起始点出发经过所有其他点(各点仅经过一次)并返回起始点的最短回路K(假定起始点到其他n个节点的距离相等,均为k)。

构造TSBTC问题:共有n/2个待卸集装箱,因此会产生n个节点(n/2个节点为集装箱在船上的位置,n/2个节点为集装箱在堆场的卸箱位置),各个节点之间的运输时间与其所对应的TSP中各节点(除去起始点的n个节点)之间的距离相等;集卡数量为1,岸桥与场桥数量为无限,问题的目标为求得最小的卸箱作业完成时间F(场桥作业一个集装箱的时间用β表示)。

在TSBTC问题的解中,集卡的行驶路径可以看成是一个经过n个节点的不闭合的哈密顿路径,路径的长度(该条路径的运输时间/集卡的运输时间)即为F-β;为了同起始点形成闭合的回路,还需连接哈密顿路径的两个端点同起始点的两条线段;由于假定起始点到任意其他n个节点的距离均为k,所以形成的闭合回路的长度为F-β+2×k。因此,若TSBTC所求得的最小卸箱作业完成时间为F,那么可说明TSP中存在总长度为F-β+2×k的回路。

反之,若TSP的最短回路为K,那么说明在TSBTC问题中,集卡的运输任务可以在K-2×k的时间内完成,即卸箱作业可以在K-2×k+β时间内完成。

综上,TSP可以规约至TSBTC问题,又因TSBTC问题为NP问题,则可说明TSBTC问题是NP完全的。因此不存在有效的多项式算法可以对TSBTC问题进行求解,除非P=NP。因而,本文针对问题的特点,设计了启发式算法进行求解。

3.1 基本思想

本文证明了基于运载能力的集卡调度问题是NP完全问题,对于实际规模的算例,无法通过直接求解上述模型得到满意解。因此针对问题的特点,设计了多起点自适应邻域搜索算法(简称MS-ANS算法)对问题进行求解。MSANS算法流程如图9所示:(1)算法以多个初始可行解为起点进行搜索以保证解的多样性,避免过早收敛。为每个初始解赋予相同的初始权重,在每次迭代的过程中依据每个解的权重,使用轮盘赌选择机制选择一个解,对该解进行邻域搜索;(2)针对解的特点设计了多种邻域动作并赋予相同的初始权重,在每次进行邻域搜索之前,需要根据各个邻域动作的权重运用轮盘赌选择机制选择一个邻域动作,再对当前解进行该邻域动作下的邻域搜索;(3)搜索结束后需根据新解的质量对当前所使用的邻域动作的权重以及相应解的权重进行更新,然后进行下一次迭代直至满足算法的终止准则。在迭代的过程中,为了进一步避免解的过早收敛,陷入局部最优,采用了模拟退火算法中的Metropolis准则作为邻域搜索所产生的新解的接受准则:若新解优于当前解,则接受新解作为当前解,否则以一定的概率接受新解作为当前解。

图9 MS-ANS算法流程图Figure 9 The framework of MS-ANS algorithm

3.2 解的编码与解码

本文采用三层编码的方式来表示一个解的结构。如图10所示,编码的第一层表示为所有集装箱的编号;编码的第二层为集卡编号;编码的第三层表示集装箱的配对情况,其中0表示所对应第一层编码的集装箱不与其紧后集装箱配对,1表示与紧后集装箱配对且在堆场先配送其所对应第一层编码的集装箱,2表示与紧后集装箱配对且在堆场先配送紧后集装箱。

编码的前两层决定了集卡的指派结果以及提箱顺序。图10中的编码表示:共有9个待卸集装箱,集装箱(1,3)、(1,5)和(2,6)由集卡1运输,集装箱(1,1)、(1,2)和(2,7)由集卡2运输,集装箱(1,4)、(2,8)和(2,9)由集卡3运输,集卡提箱顺序即为编码第一层所表示的集装箱从左到右排列的顺序。编码的第三层决定了集装箱的配对结果以及配对集装箱在堆场的先后配送顺序。如图10所示,集装箱(1,1)所对应的编码第三层位置的数字为1,则表示集装箱(1,1)与其紧后集装箱,即集装箱(1,2)进行了配对,且集卡在堆场先配送集装箱(1,1);集装箱(1,3)所对应的编码第三层位置的数字为2,则表示集装箱(1,3)与其紧后集装箱,即集装箱(1,5)进行了配对,且集卡在堆场先配送集装箱(1,5)。如上规则,图10中编码可以解码成如图11所示的解。

图10 编码结构示意图Figure 10 The structure of a code

图11 图10中编码所对应的解Figure 11 The solution related to the code in Figure 10

在集卡到达堆场指定位置后,按照集卡到达的先后顺序由相应最近的场桥为集卡卸箱。因此当集卡的指派、集卡提箱顺序、集装箱配对结果与配对集装箱在堆场的配送顺序确定后,场桥的作业顺序也随之确定。

为了保证解的可行性,即为了保证每个解均符合模型的约束条件,解的编码需要满足如下规则:

① 第一层编码必须包含所有不重复的集装箱编号,即保证每个集装箱均被运输且仅被运输一次;

② 若某一集装箱与另一集装箱被岸桥同时卸下,那么它们一定为某一集卡的紧前紧后作业任务;

③ 若某一集装箱与另一集装箱被岸桥同时卸下,那么它们必须配对;

④ 必须保证岸桥的作业顺序:若集装箱(1,4)和(1,5)由同一集卡运输,那么集卡不可以先提集装箱(1,5),因为此时集装箱(1,4)还没有被岸桥卸下,不可先卸载集装箱(1,5);

⑤ 若某一集装箱为40 ft集装箱,则其不能与任何集装箱进行配对,如图10,若集装箱(2,8)为40 ft集装箱,那么集装箱(2,8)所对应编码第三层位置的数字必须为0,集装箱(1,4)所对应的编码第三层位置的数字也必须为0;

⑥ 若某一集装箱已与另一集装箱配对,那么它不能再与任何其他集装箱进行配对,如图10,集装箱(1,1)已与集装箱(1,2)进行了配对,那么集装箱(1,2)所对应编码第三层位置的数字必须为0。

3.3 邻域动作

针对解的编码结构,设计了如下三种邻域动作:

(1) 交换编码第一层的两个集装箱编号的位置

交换编码第一层的两个集装箱编号的位置能够调整集卡的指派结果以及提箱顺序。如若交换图10中编码第一层集装箱(2,7)和集装箱(2,8)的位置,那么集卡2和集卡3的作业序列变为如图12所示。

图12 交换编码第一层两个集装箱编号的位置所得到的新解Figure 12 The new solution obtained by exchanging two numbers in the first tier of the code

理论上,若有N个待卸集装箱,那么最多可以产生种交换结果,但为了满足3.2中所描述的条件②与④,大部分交换均不可行。因此仅需评估满足条件②④的可行交换所产生的解的目标函数值(每次交换后须对解编码的第三层进行修正以满足条件③⑤⑥,再得到目标函数值),选取其中最优的解作为此次邻域搜索所得到的新解。

(2) 变换编码第二层的一个集卡编号

变换编码第二层的一个集卡编号同样也能够调整集卡的指派结果以及提箱顺序。如把图10编码第二层第6个位置的集卡编号由1变为2,那么相当于将集装箱(2,6)从原本集卡1的运输序列中删去并插入集卡2运输序列的指定位置,使得集卡2的作业序列变为如图13所示。

图13 变换编码第二层的集卡编号所得到的新解Figure 13 The new solution obtained by changing the number in the second tier

假设集卡数量为S,那么第二层任一位置的集卡编号可有S-1种变换可能(除去原本的编号)。因此,若有N个集装箱,那么最多可以产生N×(S-1)种变换结果。为了满足3.2中所描述的条件④,大部分变换均不可行,因此仅需评估满足条件④的可行变换所产生的解的目标函数值(每次变换后须先对解编码的第二层进行修正以满足条件②,再对解编码的第三层进行修正以满足条件③⑤⑥,最终得到目标函数值),选取其中最优的解作为此次邻域搜索所得到的新解。

(3) 变换编码第三层的一个数值

变换编码第三层的一个数值可以改变集装箱的配对结果,若将图10中编码第三层第一个位置的数值变为0,那么集装箱(1,1)、(1,2)将先后由集卡2分两次进行运输,若将第三层第一个位置的数值变为2,那么集卡2的作业序列变为如图14所示。

图14 变换编码第三层的一个数值所得到的新解Figure 14 The new solution obtained by changing the number in the third tier

对于N个集装箱,共可能产生2N种变换结果(由于可变换数字为0、1或2,且不能变换为其原本的数值)。仅需对满足条件条件③⑤的可行变换进行评估(每次变换后须对解编码的第三层进行修正以满足条件⑥,再得到目标函数值),选取其中最优的解作为此次邻域搜索所得到的新解。

为了加快求解速度,在进行以上任意一种邻域动作下的邻域搜索过程中,若某一次可行交换/变换所得到解的目标函数值优于当前解的目标函数值,则邻域搜索停止,并将该交换/变换所得到的解作为邻域搜索所得到的新解。

3.4 解的接受准则

在邻域搜索得到一个新解后,根据模拟退火算法中的Metropolis准则来判断是否接受新解xnew替换当前解xcurrent,用f(xnew)表示新解的目标函数值,f(xcurrent)表示当前解的目标函数值,那么接受新解xnew的概率可表示为:

Titer为第iter次迭代时的温度值,Titer值随着迭代次数的增加越来越低,可以保证接受劣解的概率随着迭代次数的增加而下降。温度值下降的函数表示为:

T0为算法的初始温度,本文设置为T0=0.05×f(xinitial),f(xinitial)为初始可行解的平均目标函数值;α为0-1之间的小数,用来控制温度下降的速度。

3.5 权重更新

当邻域搜索得到一个新解后,需要根据新解的好坏,对当前解的权重以及当前所使用的邻域动作的权重进行更新。

式(28)为权重更新公式,f(xbest)为当前所求得的最优解的目标函数值,μ为0-1之间的小数,ω表示对新解的评估值,ω1＞ω2＞ω3＞0。式(28)可以保证新解越好,当前解的权重值以及当前所使用邻域动作的权重值就越高。本文将所有的初始权重值设为1,ω1为1.2,ω2为1.1,ω3为0.9。

3.6 终止规则

设置算法的终止规则为:总迭代次数到达指定值,算法终止。

本节以待卸载集装箱的数量为基础,设置不同规模的算例实验,对MS-ANS算法的有效性以及本文的研究意义进行验证。算例设置如下:20 ft集装箱数量与40 ft集装箱数量之比设定为4∶1;随机生成集装箱在船上的位置,每个集装箱的卸箱时间与其在船上的位置有关,取值范围在1.5 min～2.5 min之间;定义岸桥的作业顺序以一个偶数贝为单位,从陆侧到海侧、由上到下进行卸箱,卸完一个偶数贝的集装箱后再移动到下一个偶数贝进行卸箱;定义岸桥数量为2,尽量保证岸桥的作业任务量均衡;若两个集装箱属于同一偶数贝且位于同一层同一栈,那么定义这两个集装箱被同时卸下;设置场桥数量为4,在一定范围内随机生成每个集装箱的堆场位置;定义场桥作业一个集装箱的时间为1.5 min;定义集卡/场桥在任意两点之间的运输/移动时间由两点之间的距离决定。

实验运行在1.8 GHz Intel Core i5-8265M CPU和8GB内存的计算机上;所有求解方式均通过Visual Studio 2017 中的C++语言进行编码并加以实现,所调用规划求解器的版本为Gurobi8.1.0;设置MS-ANS算法初始可行解的个数为20,算法执行1000代停止;对于每个算例,MS-ANS算法运行10次取平均值;Gurobi设置为最多运行2小时停止并输出当前所求得的最优解。

4.1 算法参数值确定

为更好的应用MS-ANS算法进行求解,首先需要确定合理的算法参数值,包括Metropolis准则中参数α的值,以及权重更新参数μ的值。

为确定参数α的值,将参数μ的值固定(μ=0.9)并将参数α的值设置为0.80、0.85、0.90、0.95、0.99,分别对同一算例(集装箱数量为50,集卡数量为4)进行求解。基于α的每个取值,算法运行10次取平均值,平均目标函数值随迭代次数的变化如图15(a)所示。由图15(a)可知,当参数α的值为0.99时,算法的收敛性最差。分析原因如下:若α取值较大,在执行MS-ANS算法中的Metropolis准则时,温度下降较慢,邻域搜索的过程中接受劣解的可能性更大,导致算法不易收敛,并且最终得到的解较差;而参数α其他的4个取值均可以使算法在1000代以内收敛,验证了算法的收敛性;此外,当α取值越小时,算法的收敛速度越快,但可能使得算法过早收敛至较差的解;在5个取值中,当α取值为0.90时,尽管收敛速度不是最快,但可以使算法收敛至更优的解,因此,在后续的实验中,将α的取值设置为0.90。

同理,为确定参数μ的取值,将参数α的值固定(设置α=0.90),将参数μ的值设置为0.8、0.85、0.9、0.95、1.0,分别对同一算例进行求解。基于μ的每个取值,MS-ANS算法运行10次取平均值,平均目标函数值随迭代次数的变化如图15(b)所示。由图15(b)可知,以上参数μ的5个取值均可使算法在1000代以内收敛;其中,当参数μ取值为0.95时,算法的收敛速度较快,且得到的目标函数值最小,因此在后续的计算中将参数μ的取值设定为0.95;当μ取值为1时,算法的收敛速度较慢,最终得到的解也劣于其他方案,一定程度上表明了MS-ANS算法中加入自适应因素的作用。

图15 不同参数下的算法迭代图Figure 15 Algorithm iteration graph with different parameters

此外,本文算法为基于多起点的自适应邻域搜索算法,为验证设置多起点(初始可行解)的必要性以及确定合理的起点个数,将初始可行解的个数分别设置为1、10、20、30和40。基于每一个方案,MS-ANS算法运行10次取平均值,平均目标函数值随迭代次数的变化如图16所示。

图16 初始可行解(起点)的个数对算法收敛结果的影响Figure 16 The effect of the number of initial solutions on the convergence of the algorithm

由图16可知,对于不同的初始解的个数,算法均会在1000代以内收敛;当初始可行解个数为1时,算法在450代左右收敛,但最终所得结果最差,验证了算法设置多起点的必要性;当初始可行解个数为20、30或40时,算法均会收敛至较优的值,因此可设置MS-ANS算法的初始可行解个数为20。

4.2 算法有效性验证

基于集装箱的数量N以及集卡的数量S,选取了16个小规模算例,分别使用规划求解器Gurobi和MS-ANS算法进行求解,对算法的有效性进行验证。求解结果如表1所示,其中,

表1的实验结果表明,随着问题规模变大,Gurobi求解时间明显增加,当集装箱数量达到20及以上时,Gurobi无法在2小时内求得最优解;对于算例13、14,Gurobi无法在2小时内获得问题的可行解。而MS-ANS算法对于以上算例均能在2 s内求得近优解,平均求解时间为0.81 s;且算法求得的近优解与Gurobi所求精确解相差较小,平均相差0.7%,初步验证了MS-ANS算法的求解质量与求解效率。

表1 Gurobi与MS-ANS算法求解结果对比Table 1 Comparison of results obtained by Gurobi and MS-ANS algorithm

4.3 方案对比分析

将允许“一车两箱”运输模式的集卡调度方案同仅允许“一车一箱”运输模式的集卡调度方案进行对比,验证本文所提出的集卡调度方案的有效性。为得到仅允许“一车一箱”运输模式的集卡调度方案,对MS-ANS算法进行修改,使得算法中每个初始解编码第三层的数值都为0;此外,在进行邻域搜索时仅可选择前两个邻域动作,不可选择第三个邻域动作,可以保证集卡一次仅运输一个集装箱。将修改后的MSANS算法称为MS-ANS-Ⅰ算法,用来得到仅允许“一车一箱”运输模式的集卡调度方案。

选取了20个中等规模和大规模的算例,分别使用MSANS-Ⅰ算法和MS-ANS算法进行求解,对于每个算例算法运行10次取平均值。求解结果如表2所示,其中,由于运行10次取平均值可能会使得平均集装箱配对数量为小数,表中“配对数量”列所展示的为平均集装箱配对数量向下取整的值。

表2 MS-ANS-I算法与 MS-ANS算法求解结果对比Table 2 Comparison of results obtained by MS-ANS-I and MS-ANS algorithm

由表2中结果可知,在不同数量集装箱以及不同数量集卡的作业条件下,允许“一车两箱”运输模式的集卡调度方案均能够大幅度降低进口箱卸箱作业的完成时间,相比于仅允许“一车一箱”运输模式下的集卡调度方案平均减少了23.5%。观察表2中“配对数量”和“Gap1”列可以发现,当集装箱数量相同时,集卡数量越少,就越倾向于进行配对运输,两个方案的卸箱作业完成时间的差值也越大。这说明集卡数量越有限,进行“一车两箱”的运输就越有优势。

图17与18具体展示了集装箱数量为50,集卡数量为6的算例某一次的求解结果。图中矩形左边所对应的横轴时刻为相应集卡在岸边提取矩形中集装箱的时间,矩形右边所对应的横轴时刻为集卡将矩形中集装箱送至堆场后场桥开始卸箱的时间,灰色部分表示集卡在一个时段内同时运输两个集装箱。例如图17中集卡1的第一个矩形表示,集卡1在岸边同时提取了集装箱(1,3)和集装箱(1,4)(集装箱(1,3)和(1,4)被岸桥同时卸下),且在堆场先配送集装箱(1,3)再配送集装箱(1,4);集卡1的第三个矩形表示,集卡1首先在岸边提取了集装箱(1,10),然后行驶至另一个岸桥装载了集装箱(2,14)再返回堆场,在堆场先配送集装箱(1,10)再配送集装箱(2,14)。对比图17和图18可知,允许“一车两箱”运输模式下的集卡调度方案充分利用了集卡的运输能力,能够减少集卡的空驶时间,缩短船舶卸箱作业的完成时间。

图17 允许“一车两箱”运输模式的集卡调度方案Figure 17 The truck schedule under the transport mode of “one truck, two containers”

图18 仅允许“一车一箱”运输模式的集卡调度方案Figure 18 The truck schedule under the transport mode of “one truck, one container”

此外,对于表2中等规模到大规模的所有算例,MS-ANS算法均能在400 s内求得近优解,平均求解时间为134.9 s,进一步验证了MS-ANS算法的求解效率。

4.4 灵敏度分析

集卡在岸边的等待时间以及集卡在堆场的运输时间,均有可能成为影响集装箱配对决策的重要因素。其中,岸桥的数量是影响集卡在岸边等待时间的主要因素,集装箱在堆场的积载位置是影响集卡在堆场运输时间的主要因素。因此,在本部分对岸桥的数量以及集装箱在堆场的分布情况进行灵敏度分析,讨论不同作业条件对于集卡调度方案的影响。为了描述集装箱在堆场的分布情况,引入分散度(η)的概念,来表示集装箱在堆场的分散程度。η的值越高,表示集装箱在堆场越分散;η的值越低,表示集装箱在堆场越集中。分散度η的计算公式如下:

式(29)中C为待卸集装箱集合,N为集装箱的总数量,为两个集装箱堆场位置之间的距离 (m)。

算例设置如下:设置集装箱数量为100,集卡数量为6;岸桥的数量分别设置为1、2、3、4、5;η的取值分别设置为20、40、60、80。对于不同岸桥数量和η值的组合共生成20个算例,每个算例分别使用MS-ANS算法和MS-ANS-Ⅰ算法进行求解。算法运行10次取平均值,求解结果如图19所示,其中,

图19(a)(b)(c)(d)结果显示,对于两种运输方案均存在如下情况:当岸桥数量越多,卸箱作业完成时间(目标函数值)越小;当集装箱在堆场的分布越集中,卸箱作业完成时间越小。分析原因如下:当岸桥数量越多时,集卡在岸边的等待时间越短,当集装箱分布越集中,集卡在堆场的运输时间越短,最终使得总卸箱时间越小,符合码头实际运营情况,验证了算法的稳定性。

图19 岸桥数量和集装箱堆场分布对于集卡调度方案的影响Figure 19 The impact of the number of quay cranes and the container distribution at the yard on the truck scheduling plan

此外,观察图19可知,对于η的所有取值,均存在如下情况:岸桥数量越多,两种运输方案所对应的目标函数值相差(Gap2值)越大。

这是由于当集卡在岸边装载一个20 ft集装箱后,若是选择继续装箱进行配对运输,那么岸桥数量越多时,集卡需要等待装载第二个集装箱的时间可能越短,因此越有利于“一车两箱”的运输;此外,当η的取值越小时,即当集装箱在堆场分布越集中时,两种运输方案所对应的目标函数值相差越大。这是由于集装箱在堆场的位置越集中,两个有可能进行配对的集装箱在堆场的位置就越接近,因此,集卡进行“一车两箱”的运输时在堆场的送箱时间就越短,越有利于进行“一车两箱”的运输。

由灵敏度分析实验可知,岸桥数量与集装箱在堆场的分布情况均会对集卡的调度结果产生影响。当岸桥数量越多,且集装箱在堆场分布越集中时,越有利于集卡进行“一车两箱”的运输。允许“一车两箱”运输模式的集卡调度方案相比于仅允许“一车一箱”运输模式的集卡调度方案,卸箱作业完成时间缩短了20%左右。

本文考虑集卡对于20 ft集装箱和40 ft集装箱的实际运载能力以及岸桥的多种作业模式,以进口箱卸箱作业完成时间最小为目标构建混合整数规划模型,对集卡指派、集卡提箱顺序、集装箱配对、配对集装箱的堆场配送顺序进行协同优化。随后,证明了本文所研究的考虑运载能力的集卡调度问题是NP完全问题。为求解实际规模的问题,设计了多起点自适应邻域搜索算法进行求解,并通过不同规模的算例实验验证了启发式算法的求解质量与求解效率。最终研究结果表明,在传统研究中“一车一箱”运输模式的基础上同时考虑“一车两箱”的运输,能够进一步提高集卡作业效率,缩短船舶在港作业时间。

本文的研究成果可为集装箱码头实际运营过程中的集卡调度决策提供理论支撑,能够充分利用集卡的运输能力,提高集卡的作业效率,最终达到缩短船舶的在港作业时间的目的。目前,为了提高码头的装卸作业效率,已有很多集装箱码头实现了同装同卸的作业工艺,因此今后的研究有必要同时考虑装船和卸船的过程,对集装箱码头装船过程与卸船过程中的集卡调度问题进行联合优化。此外,随着自动化码头的发展,水平运输设备AGV受到了广泛的关注。因此,今后可针对自动化码头的装卸工艺,对多载AGV的调度优化进行讨论和研究。

猜你喜欢 集卡堆场邻域 基于混合变邻域的自动化滴灌轮灌分组算法农业工程学报(2022年7期)2022-07-09共享堆场协议下海铁联运集装箱堆场分配优化中国航海(2020年3期)2020-12-09集卡引导系统在轨道吊自动化堆场的应用优化集装箱化(2020年7期)2020-06-20大地调色板时代邮刊(2020年3期)2020-02-27集卡预约模式下集装箱码头可变闸口协同调度优化中国航海(2019年2期)2019-07-24集卡和岸桥协同下的集装箱码头集卡路径选择天津科技(2018年12期)2019-01-02基于邻域竞赛的多目标优化算法自动化学报(2018年7期)2018-08-20基于细节点邻域信息的可撤销指纹模板生成算法自动化学报(2017年4期)2017-06-15基于激光扫描测距技术的岸桥下集卡自动定位系统集装箱化(2016年8期)2016-10-20集装箱码头堆场布置形式比较集装箱化(2014年12期)2015-01-06

推荐访问:运载 调度 优化