考虑场桥调度的集装箱码头船舶配载研究_丁一.pdf

第 卷第 期重 庆 交 通 大 学 学 报（自 然 科 学 版）年 月 （）：考虑场桥调度的集装箱码头船舶配载研究丁 一，张 杨（上海海事大学 物流研究中心，上海）摘要:为了提高码头配载作业效率,对集装箱码头的场桥调度船舶配载问题进行了研究。结合船舶预配总图、岸桥作业计划和堆场堆存情况,建立了目标为堆场翻箱量最少和场桥箱区间移动时间最短的混合整数规划模型;利用C P L E X对小规模数据模型进行求解,检验了模型的准确性;针对中、大规模问题,设计了一种基于嵌套循环的禁忌搜索算法(N L T S)来寻找解,并与禁忌搜索算法进行对比。研究结果表明:N L T S算法优化效果和运算速度均优于禁忌搜索算法,且优化模型能有效地减少场桥移动时间和翻箱量。关 键 词:交通运输工程;集装箱码头;船舶配载计划;场桥调度;基于嵌套循环的禁忌搜索算法中图分类号:U 1 6 9.6文献标志码:A文章编号:1 6 7 4-0 6 9 6(2 0 2 3)0 1-0 9 1-0 8S h i pS t o w a g e i nC o n t a i n e rT e r m i n a lC o n s i d e r i n gY a r dC r a n eS c h e d u l i n gD I NGY i,Z HANGY a n g(L o g i s t i c sR e s e a r c hC e n t e r,S h a n g h a iM a r i t i m eU n i v e r s i t y,S h a n g h a i 2 0 1 3 0 6,C h i n a)A b s t r a c t:I no r d e r t o i m p r o v e t h ee f f i c i e n c yo fw h a r fs t o w a g eo p e r a t i o n,t h ep r o b l e mo fs h i ps t o w a g e i ny a r dc r a n es c h e d u l i n go f c o n t a i n e rt e r m i n a l sw a ss t u d i e d.C o n s i d e r i n gt h es h i pp r e c o n f i g u r e dg e n e r a ld r a w i n g,q u a yo p e r a t i o np l a na n dy a r ds t o r a g e,am i x e di n t e g e rp r o g r a mm i n g m o d e lw a se s t a b l i s h e dw i t ht h eo b j e c t i v eo fm i n i m i z i n gt h en u m b e ro f c o n t a i n e r so v e r t u r n e di nt h ey a r da n dt h es h o r t e s tm o v i n gt i m eb e t w e e nt h eb r i d g eb o x e si nt h ey a r d.C P L E Xw a su s e dt os o l v e t h es m a l l-s c a l ed a t am o d e l a n dv e r i f yt h ea c c u r a c yo f t h ep r o p o s e dm o d e l.At a b us e a r c ha l g o r i t h mb a s e do nn e s t e dl o o p(N L T S)w a sd e s i g n e dt os o l v em e d i u ma n dl a r g e-s c a l ep r o b l e m sa n dw a sc o m p a r e dw i t ht h et a b us e a r c ha l g o r i t h m.T h er e s e a r c hr e s u l t ss h o wt h a tt h eo p t i m i z a t i o ne f f e c ta n dc o m p u t a t i o ns p e e do fN L T Sa l g o r i t h ma r eb e t t e r t h a nt h o s eo f t a b us e a r c ha l g o r i t h m,a n dt h eo p t i m i z e dm o d e l c a ne f f e c t i v e l yr e d u c et h em o v i n gt i m eo fy a r dc r a n ea n dt h ea m o u n to f c o n t a i n e r t u r n o v e r.K e yw o r d s:t r a f f i c a n d t r a n s p o r t a t i o ne n g i n e e r i n g;c o n t a i n e r t e r m i n a l;s h i ps t o w a g ep l a n n i n g;y a r dc r a n e s c h e d u l i n g;t a b us e a r c ha l g o r i t h mb a s e do nn e s t e d-l o o p s 引 言集装箱运输在全球贸易中扮演着重要角色，各大集装箱港口都在致力于通过提高作业效率来满足日益增长的集装箱运输需求。配载作为码头作业系统的重要组成部分，其质量高低直接影响着装船作业的运作水平。国内外学者对码头集装箱船舶配载优化问题有着不同程度的研究。针对船舶配载模型问题，等首次提出了船舶配载规划问题（）的初步模型；在此基础上，将模型在堆场位移评估和稳定性约束方面进行了丰富和改进。针对适航性的影响问题，等将目标定义为最小化船上的倒箱和最大化船舶的稳定性；等在模型中加入剪力和弯矩约束，并引入一种混合整数线性规划（）模型，通过最小化超载和调整力矩相关的总成本来产生载荷计划；等采用定倾中心高度、倾斜值和纵 收稿日期：；修订日期：基金项目：国家重点研发计划项目（；）第一作者：丁 一（），男，上海人，副教授，博士，主要从事港口运作优化和信息化方面的研究。：通信作者：张 杨（），男，浙江舟山人，硕士研究生，主要从事港口运作优化方面的研究。：倾值来测量船舶的稳定性。针对配载求解的问题，等采用自适应 启发式框架进行求解；等和 等分别采用蒙特卡罗树搜索和强化学习网络解决配载规划问题。配载作业效率很大程度上受堆场作业影响。在船舶实配载计划已知基础上，为提高堆场作业效率，范厚明等针对箱位分配和场桥调度协同优化问题，构建了双层混合整数规划模型，并设计改进了遗传模拟退火算法，通过不断平衡上下层最优解使得问题最优。考虑配载与堆场协同优化研究，丁一等考虑了堆场作业不均衡的约束，采用禁忌搜索算法对问题进行了求解，并检验了鲁棒性；刘志雄等针对船舶配载与堆场取箱顺序联合优化问题进行了建模分析；等以最小化倒箱、场桥移动和集装箱间重量差为目标，建立了组间配载模型，通过设计一种 混合算法来解决这一问题；郭文文等将配载问题简化为装船顺序，将场桥调度问题进行联合优化。高效配载规划主要的目标是最小化船舶靠港时间，同时也应考虑船舶航行稳定性、码头机械利用率、港口堵塞等因素。配载问题研究的关键是通过合理调度港口机械，为船舶提供装载合理且快速的规划方案。配载与堆场作业协同优化问题虽已有一定程度研究，但现有研究简化了配载问题，无法为港口提供完整的实配载计划。故笔者的研究目标是从码头运营商角度出发，为场桥调度的配载问题构建可靠的数学模型，利用 求解器求解小规模实例来验证模型的正确性；设计基于嵌套循环的禁忌搜索算法（）对中、大规模实例进行求解，优化配载计划和场桥作业，为集装箱码头配载作业提供决策支持，提高码头服务效率。问题描述码头实际管理通常采用分层方法。实际装船作业中的配载问题可以分解成两部分。在场箱的配载船位配载船位规划包括两个连续阶段：第 阶段由船东执行，根据航线上各挂靠港出口箱数量及类型，划分出各港口的船舶装箱区域，规划结果为预配载计划；第 阶段由码头方根据预配载计划及出口箱堆场堆存情况，编制实配载计划来确定各出口箱的具体装载船位，集装箱与船箱位的匹配必须满足预配要求。为码头企业根据航运公司的预配载计划编制的部分船位的实配载计划如图。图 部分船位的实配载计划 在场箱的装船顺序图 为堆场翻箱示意。图 中：若 箱先于 箱离场，则定义 箱为阻碍箱，场桥需将 箱移至同一贝位的其它栈才能完成后续作业，显然该操作可能产生不必要的翻箱；同时，若目标箱与上一个提取箱位于同一箱区，场桥无需在箱区间移动即可完成作业，反之场桥则发生移动。配载船位的变化会导致装船顺序的改变，从而造成不同目标箱的选择，进而影响场桥移动的时间，导致翻箱量及场桥移动时间不同，反之亦然。因此，配载船位和场桥调度相互影响，为提高码头作业效率，港口在配载问题的优化中就应当考虑场桥调度问题。图 堆场翻箱作业 码头企业优化配载问题的最终目的是减少总装船时间，总装船时间由 个区域的作业组成：场内：堆场内作业时间由翻箱、场桥移动和集装箱装卸所产生。堆场到船：集装箱水平运输时间由集装箱到岸桥距离决定。船上作业：码头为提高作业效率，通常会在集装箱船到达前提前分配泊位和岸桥，并在装卸作业开始之前设计岸桥的工作顺序。在此基础上，确定了岸桥作业计划，船上的作业时间由岸桥作业计划确定。重 庆 交 通 大 学 学 报（自 然 科 学 版）第 卷综上，笔者在结合船舶预配载计划、岸桥作业计划和出口箱堆存情况的基础上，考虑轻压重、箱槽最大承载重量与船舶稳性等常规船舶配载约束，同时考虑场桥作业约束，建立了混合整数规划模型以最小化场桥箱区间移动时间和堆场翻箱量，着重于优化配载计划及配载作业中的场桥调度，缩短总装船时间，提高港口配载作业效率。数学模型文中模型赋予如下信息：）船舶贝、行和层的配置（船舶贝位图）及基于类的预配载计划；）船舶岸桥作业计划：在船舶靠港之前由码头制定，明确各岸桥分配到的船位装箱任务；）所有待装载集装箱的类别、目的港、重量、箱号和位置。集 合笔者定义相关集合如下：为出口箱集合，；为出口箱堆存箱区集合，；为集装箱船舶待装箱位集合，；为所有分钟段集合，为作业总时间，；为所有单位时间段集合，若单位长度为 ，（）则表示取小于等于（）的最小整数值，则（），（），；为船舶预配载计划中船栈集合，；为船舶船栈 中的箱位集合，；为与在场箱 的箱区、贝、堆栈相同，但层高于 的集装箱集合，；为与船舶箱位 的贝、船栈相同，但层高于 的箱位集合，。参 数笔者定义相关参数如下：为集装箱 到船舶箱位 的水平运输时间；为场桥从箱区 移动到箱区 的时间；为箱区 在第 时间段内的场桥数量；为集装箱 的重量；为箱位 最晚装箱时间；为船栈 的最大承重量；为场桥单次翻箱的时间；为场桥单次取箱的时间；为箱区 初始场桥数量；为单位时间段内场桥的最大工作能力；为最大可安排场桥数量；为二维 的 矩阵，其中 表示当且仅当出口箱 位于箱区；为二维 的 矩阵，其中 表示当且仅当计划船箱位 的箱位类型、尺寸、卸货港等要求满足出口箱；为足够大的正数。决策变量笔者定义决策变量如下：，当且仅当出口箱 先于 离场，其中；，当且仅当场桥在 时间段从箱区 移动到，其中；，当且仅当出口箱 在 时间从箱区离场，且被安排到船箱位。假设条件）码头当前只服务目标船舶，且只考虑出口箱装船作业，进口箱均已卸载；）仅虑 的集装箱作业，且码头已对危险品箱和冷藏箱进行特定安排；）仅当堆场同一箱区同一堆栈内，下层待装箱先于上层待装箱离场计入翻箱操作，若上层堆存集装箱不为待装箱则计为正常取箱操作；）码头有足够数量和类型的岸桥来完成作业，且岸桥信息已知；）场桥工作参数一致，如移动速度、转角速度、作业时间和移动成本等；）不考虑场桥在移动过程中的堵塞问题；）场桥须在各时间段结束前完成当前时间段中的安排的所有任务。目标函数和约束条件 目标函数）最小化堆场翻箱量（）最小化场桥箱区间移动时间（）针对两个不同的目标函数，笔者引入单次翻箱作业时间，采用堆场翻箱作业时间长短来表示堆场翻箱量，通过优化整体作业时间来达到同时优化堆场翻箱量和场桥箱区间移动时间的目的。整合后的目标函数如式（）：()（）约束条件，（），（）第 期丁 一，等：考虑场桥调度的集装箱码头船舶配载研究，（），（），（），（）（）（），（）（），（）（）()（）（），（）（），（）（）（）（）（），（）其中，式（）、式（）为匹配约束，即船舶箱位和在场箱必须一一对应；式（）为集装箱的配载必须满足船箱位预配要求；式（）为在场箱装箱时间必须早于最晚装箱时间；式（）为轻压重约束，即船舶同船栈上层集装箱重量不得大于下层；式（）为船舶船槽的载重约束，规定船栈内的集装箱重量总和不得超过该船栈的最大载重量；式（）为在场箱离场先后顺序与翻箱的关系；式（）、式（）为各箱区一次只能移动一台场桥，且箱区最多存在一个场桥；式（）为箱区场桥数的总和不能超过可调度最大场桥数；式（）为任意箱区在同一单位时间内若存在场桥移进（或移出），则不会发生移出（或移进）；式（）为箱区场桥数随时间变化关系；式（）为箱区场桥数与初始场桥数的关系；式（）为场桥单位时间段作业量约束。模型验证待装船集装箱信息如表。表 中：该批出口箱堆存在 个箱区，且均为单一目的港；笔者引入 来表示待装箱堆存情况，为出口箱堆存箱区数；为堆场内堆存 个出口箱的堆栈数，、以此类推。通过 求解器对模型求得最优解，满足约束条件结果，如表。表 待装船集装箱信息 集装箱信息算例箱量 箱待装箱堆存情况卸货港数 个场桥数 个箱重范围（，）（，）表 计算结果 集装箱信息算例总装船时间 翻箱量 箱场桥移动时间 计算时间 图、图 为算例 求解得到的配载方案和场桥调度方案。模型在较短时间内可完成求解，针对 箱量的实例，只需 的求解时间，解得配载方案满足模型的配载约束，最短场桥箱区间移动时间为 。对比、的运算时间可发现，当数据规模变大时，的求解性能也开始下降。因此笔者就这一问题重新设计了算法，以达到快速解决大规模问题的目的。图 配载方案 重 庆 交 通 大 学 学 报（自 然 科 学 版）第 卷图 场桥调度方案 基于嵌套循环的禁忌搜索算法文中研究的问题由两个子问题组成：配载规划问题（）和场桥调度问题（）。这两个问题均可通过有效算法来解决。因此，解决文中问题的关键是如何实现 和 之间的交互和反馈。基于此，笔者设计了一种基于嵌套循环的禁忌搜索算法（）。该算法包括两个内环和一个外环。首先，将船舶配载初始解输入内环，内环 根据初始解生成新的船舶配载结果作为输出，内环 根据内环 输出计算生成相应的场桥调度方案。将两个内环结果同时输入外环，并计算出相应的船舶装船作业时间。为了实现耦合变量传输，外环基于禁忌搜索算法将上述新的船舶配载结果作为内环 的新输入，以开始下次迭代。初始解求解配载问题需要在场箱配载船位、在场箱装船顺序等信息。将出口箱 与船箱位 一一对应，可用来表示计划配载的结果，如式（）：（）初始解会直接影响到算法解的优劣及计算时间。根据码头实际作业情况，笔者首先按卸货港、箱位尺寸对船位和在场箱作升序排序，对于同一卸货港和箱位尺寸的箱位再根据贝位、层位和行位作升序排序；对于同一卸货港和箱尺寸的集装箱再根据重量作降序排序；最终可得到一个满足预配和轻压重约束的初始解。内环（问题）将船舶配载结果作为输入值输入内环，程序将构造集装箱配载问题的可行解，并将合适的解储存在外环的候选解集内，同时计算翻箱时间。内环 中解的编码和解码如图。图 内环 中解的编码和解码 首先程序对所有待装箱进行预处理，分别记录各个待装箱及和该箱同卸货港同尺寸且箱重小于等于该箱的集装箱，作为此待装箱的置换集合，根据输入值，优先选取产生堆场翻箱作业的集装箱作为节点。以集装箱 为例，图 中灰色集装箱为箱 的置换集合，在集合内选取一个待装箱作为另一个交换节点得到新的解作为值输出。该方法可减少算法验证解是否满足重压轻等约束条件时的计算负担，所得到的新解亦能满足配载问题基本约束。内环（问题）内环 为船舶配载可行解制定场桥调度方案并计算方案的场桥移动时间，内环 中解的编码和解码如图。将内环 输出值输入内环，根据作业时间，将间隔符号“”添加到计划的工作序列中，每两个“”之间代表时间段内要完成作业的集装箱编号；场桥作业的初始解保证在该计划时间段内分配给场桥的任务数不能超过场桥的工作能力；新解的交换的节点只会在同一时间段内选取，通过迭代得到输入值的最优场桥调度方案作为输出，并计算该方案的移动时间。图 内环 中解的编码和解码 外 环外环关键点是实现耦合变量的传输。两个内环之间的相互作用将提高调度质量。外环根据翻箱时间和场桥移动时间来判断解的优劣，总装箱时间越短则方案越合理。在外环中设置判断，若某次迭代中当前的禁忌对象对应状态的适配值较优时，忽略其禁忌属性并仍将其作为当前选择；当计算达到最大迭代数时，选择禁忌表中最小值为整个问题的最第 期丁 一，等：考虑场桥调度的集装箱码头船舶配载研究优解，若在一定迭代次数内当前最优解无优化趋势，则提前跳出搜索过程。算法步骤步步骤骤 ：确定外环的最大迭代次数、最大禁忌频率、禁忌长度、候选解个数、空候选解集，设置空禁忌表，预处理所有待装箱的可置换集合，进入步步骤骤 ；步步骤骤 ：输入初始解，设置当前迭代次数，禁忌次数，为无穷大，判断 是否满足船舶箱槽重量约束，否，进入步步骤骤 ，反之则进入步步骤骤 ；步步骤骤 ：优先选取产生堆场翻箱作业的集装箱作为节点，通过该箱的可置换集合得到新解，返回步步骤骤 ；步步骤骤 ：将配载结果作为输入，通过内环 获得新的配载结果，令最优解，计算当前解翻箱时间，进入步步骤骤 ；步步骤骤 ：根据步步骤骤 中获得的配载结果，在内环 中求解，获得相应的堆场起重机计划 及起重机移动时间，然后进入步步骤骤 ；步步骤骤：若 ，则执行步步骤骤，将得到的可行邻域解置于 中，直至 中的候选解数目达到 ，并计算候选解集中的最小值，进入步步骤骤 ，反之进入步步骤骤 ；步步骤骤 ：令总装船时间，如果，将 置于 中；否则，则为邻域中非禁忌的最优，并将 置于 中，进入步步骤骤 ；步步骤骤 ：判断 是否小于等于，若是，进入步步骤骤 ；否则，进入步步骤骤 ；步步骤骤 ：判断 是否大于等于，若是，进入步步骤骤 ；反之进入步步骤骤 ；步步骤骤 ：，返回步步骤骤 ；步步骤骤 ：返回、，结束。算例分析 算例数据笔者将从上海洋山港码头获得的配载数据分成 组，箱区规模为：个贝位 个堆栈 个堆层，算例数据见表。表 上海洋山港码头配载数据 集装箱信息算例箱量 箱待装箱堆存情况 卸货港数 个场桥数 个箱重范围（，）（，）（，）（，）（，）（，）（，）算例分析根据码头实际作业情况确定模型中的部分参数。假定单位时间段为 ，每个场桥单位时间段的最大工作量 箱，一次翻箱作业的时间，各集装箱从堆场到岸的水平运输时间为常数。模型参数确定后，在 中通过算法对模型进行求解，算法相关参数定义如下：候选解个数，禁忌长度 取大于算例集装箱数量一半的最小整数，算法迭代的最大次数 ，优化达到最大禁忌频率 时可提前结束计算，结果如表。表 算法优化结果 算例箱量初始解总装船时间 翻箱量场桥移动时间 优化结果总装船时间 翻箱量场桥移动时间 计算时间 重 庆 交 通 大 学 学 报（自 然 科 学 版）第 卷（续表）算例箱量初始解总装船时间 翻箱量场桥移动时间 优化结果总装船时间 翻箱量场桥移动时间 计算时间 由表 可知：算法能在较短时间内完成优化，值得注意的是，实例规模虽略大于，但 运算时间却高于，这是由于两个实例中集装箱种类的数量差异较大，卸货港的数量远大于，从而影响了计算时间。大量集装箱种类使得问题具有很强的约束性，故能在很短的时间内找到可行解，但最优解可能会出现大量重复且不可避免的迭代。图 为翻箱量优化分析示意。受初始解及数据规模影响，实例、不存在翻箱作业优化；在剩下实例中，、的优化效果较为突出，平均优化率达。图 翻箱量优化分析 图 为场桥移动时间优化分析示意。各实例的优化效果较稳定，均保持在 左右，甚至随着数据复杂度上升，优化效果有所提高。图 场桥移动时间优化分析 算法比较为进一步验证算法优越性，笔者将文中提出的 算法与禁忌搜索算法进行比较，验证了 算法的有效性。为保证对比的严谨，算例及两种算法的初始解仍使用表、表 中的数据，对比结果如表。表 求解结果与 求解结果对比 算例箱量总装船时间 翻箱量场桥移动时间 计算时间 总装船时间 翻箱量场桥移动时间 计算时间（）总装船时间 翻箱量场桥移动时间 由表 可知：针对小规模问题的求解，两种算法的优化效果相近；但针对中、大规模问题的优化，算法能更快地得到优化结果，且与禁忌搜索算法相比，翻箱量减少了 左右，场桥移动时间缩短了 左右，总装船时间缩短了 左右。这表明 算法够更好地解决文中的问题。第 期丁 一，等：考虑场桥调度的集装箱码头船舶配载研究 结 语不同于配载的优化问题，考虑场桥调度的自动配载计划可在保证船舶公司装船要求前提下最大程度地缓解码头堆场作业压力，同时加快码头服务船舶效率，因此对调度方案的优化要求更高。笔者重点研究了考虑场桥调度的船舶配载规划问题，将最小化集装箱码头装船作业时场桥调度时间和翻箱次数定为目标，考虑基本的配载约束和场桥作业约束，建立数学模型来最小化装船时间；通过算例采用 对模型进行求解，验证了模型的准确性。针对中、大规模问题优化，设计了基于嵌套循环的禁忌搜索算法（）来寻找问题的解；算例结果显示：组实例均在较短时间内完成运算，且与算法初始解相比翻箱量平均减少，场桥移动时间平均降低，与现有的文献对比，算法比禁忌搜索算法减少 左右翻箱量、缩短 左右的场桥移动时间、缩短 左右的总装船时间。这表明笔者所提出的 算法能更好地解决考虑场桥调度的配载规划问题。参考文献（）：，：，：，（）：，：，：，：，（）：，：，：，（）：，：范厚明，孔靓，岳丽君考虑出口箱进出场及预翻箱的箱位分配与场桥调度协同优化运筹与管理，（）：，（）：丁一，龚杰，林国龙考虑箱区作业均衡的 船舶配载研究计算机应用与软件，（）：，（）：丁一，田亮，龚杰考虑箱区作业均衡的 船舶配载鲁棒优化研究计算机工程与应用，（）：，（）：刘志雄，钱翰文，颜家岚集装箱码头船舶多贝位配载与堆场取箱协同优化研究系统仿真学报，（）：，（）：，：郭文文，计明军，祝慧灵，等集装箱码头装船顺序和场桥行驶路径联合优化交通运输系统工程与信息，（）：，（）：郭文文，计明军，祝慧灵，等集装箱码头场桥调度优化模型研究重庆交通大学学报（自然科学版），（）：，（），（）：，（）：（责任编辑：刘 韬）重 庆 交 通 大 学 学 报（自 然 科 学 版）第 卷