基于启发式算法的集装箱船配载外文翻译资料

 2022-10-27 10:10

英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料

基于启发式算法的集装箱船配载

丁丁sup1;，梅布尔.周sup2;

Ding Dingsup1;, Mabel C. Chousup2;

  1. 对外经济贸易大学 国际经济与贸易学院，北京 100029，中国
  2. 新加坡国立大学 管理学院 决策科学系，新加坡 119245，新加坡

摘 要：考虑到在集装箱船配载中，按照船舶到港顺序操作集装箱仅能从栈顶开始存取，从而造成到某些港时，有的集装箱会因为各种各样的原因被暂时卸下，之后又被重新装载上，这种非生产需要的集装箱移动叫做倒箱，这种活动往往伴随着大量时间和成本的消耗。从参考文献中我们了解到，在现实装箱问题中由于其变量与约束条件繁多，应用二元线性规划方法求解该类问题是行不通的，因此，我们针对这一问题设计了在配载中能使得倒箱量控制在合理范围之内的启发式算法。大量的计算实验验证了这一算法比Avriel等人提出的悬挂启发式算法(SH算法)执行效果更好。据我们所知,SH算法在配载计划问题中是一种领先的启发式算法。

关键词：配载计划；集装箱移动；倒箱；启发式算法

1 引言

当今集装箱化货物运输发生了革命性变化，据世界航运公会统计大约有百分之五十二的世界国际海运贸易额被转移到集装箱贸易上。世界集装箱港口吞吐量继2012年的4.97%、2011年的8.63%增长率之后，2013年集装箱港口吞吐量同比增长5.58％，达到6.51亿标准箱（20英尺箱），世界排名前二十的集装箱港装载标准集装箱量为2.99亿，达到世界集装箱装载总数的46%。因集装箱贸易的关系，2006年至2013年间全球的集装箱船以平均每年7.9%的速度快速扩张，到2013年为止20ft标准集装箱的数量已迅速增长至1990万左右。集装箱船的平均装载量由2004年1月的2259TEU增长到2009年1月的3161 TEU，再到2014年1月的4449TEU（所有数据来源于联合国贸易暨发展会议，2014年）,至今，世界上最大的集装箱能够装载约19224个标准集装箱（数据来源：维基百科，2015年）。

集装箱船会根据其预定的路线依次停靠各个港口，将在停靠港口需要卸下的集装箱卸下，将之后停靠港口的集装箱装上船，且集装箱只能从顶部进行访问（存取）。在同一港口对一个集装箱进行的卸下和装载移动叫做倒箱。倒箱操作出现在后续港的箱子堆在当前港箱子的上面时，或者在当我们需要重新调整集装箱顺序以减少后续倒箱次数时，通常把前一种倒箱操作叫做必要的倒箱，后一种称为主动倒箱。

倒箱操作既增加了集装箱的运输成本，又延长了船舶在港时间，因此集装箱在船上进行配载布置以减少倒箱量对实现高效率运作是至关重要的。确定集装箱装载位置的任务称为集装箱配载计划或者主贝计划。除了之前提到的辅助约束，还有很多约束条件影响着集装箱配载计划，比如集装箱船的横向和纵向稳性约束，甲板上集装箱堆叠在一起时的重量约束，当不同尺寸的集装箱相互堆叠时的混装约束，温度控制集装箱的电力供应约束以及危险品箱的隔离约束等等。

1989年Aslidis提出了以重排政策为核心的动态规划算法解决贝内配载问题，这种重排政策在后来的工作中被广泛采用。1993年Avriel和Penn针对仅考虑可达性约束的单贝配载问题提出二元动态规划算法以寻找的最优箱位，但这个算法被繁多的二元变量和约束所限制，得不到广泛应用。集装箱配载问题中的二元线性规划算法所涉及的约束包括可达性约束，Botter and Brinati（1992年）、Ambrosino等人（2004年）、Avriel等人（2006年）、Sciomachen和Tanfani（2007）、Delgado等人（2012年）以及Ding 和 Chou（2015年）所提到的稳性约束，重量约束和混装约束。其中，Botter等人（1992年）及Avriel等人表示集装箱配载问题是一个NP-hard问题，目前所出现的配载方案即使世界上领先的优化软件都需要大量的时间和资源。

Avriel等人在1998提出的悬挂启发式算法(SH算法)是一个求解动态配载计划的规划方法,据我们所知,这个算法是为了解决这类集装箱配载问题而提出的较为先进的启发式算法之一。各类启发式搜索算法已被广泛应用于类似问题中，如遗传算法、分支定界法、禁忌算法、模拟退火算法、贪婪算法、树搜索法等等，然而，这些算法的有效性及复杂性仍需被验证。读者可参考Zhang等人（2008年），Sciomachen和Tanfani（2007年）以及Delgado等人（2012年）的文献进行广泛的文献综述。

在这篇文章中，我们提出了一种较Avriel等人于1998年提出的悬挂启发式算法更有效的启发式算法，尤其在集装箱船舶挂靠港数量较多、船舶容量较大的情况下有效性更明显，同时大量的计算实验表明我们设计的算法通常比SH算法更行之有效。此外，SH算法仅适用于所有港口装/卸载集装箱信息已知的条件下，然而，我们设计的算法只需要当前港口的这些信息便可制定配载计划。

论文的组织形式如下所示：第二章节，对集装箱船配载问题作出明确定义；第三章节，介绍启发式算法并举例阐述该算法的工作过程；第四章节，根据大量的计算实验分析该算法的性能；第五章节，对整篇文章进行总结。

2 问题描述

对集装箱船最常用的集装箱位置寻址标记就是贝-列-层系统，更具体详细的描述可参见Ambrosino等人于2004年写的文献。在这篇文章中，我们采用相似的标记方式并仿照Avriel等人的定义方式定义参量，由于采用标记系统类似，在进行结果对比时更易观察数据变化情况。同时，这两个标记系统可以很容易的进行相互转变。

集装箱船由多个矩形的贝组成，贝包含多列多层，在水平方向上对Bay进行列编号r=1,...,R，垂直方向上对层编号c=1,...,C。位置处在第r列第c层表示为（r,c）。假设集装箱都为20英尺的标准箱且每个载位都能被一个集装箱装满，则集装箱船的装载量P=R·C，这个公式中为了简单起见假设单个贝为矩形贝，对于多个贝，因为公式不考虑列的位置故将所有列顺序标记。对于不规则贝，往往是将其转化成一个带一些假想位置的矩形贝，并在航行过程中通过附加约束装载一些假想的集装箱。假设集装箱船舶依次挂靠港口1，2，hellip;，N，在1港口，装载2港口至N港口的集装箱，在i=2，hellip;，N-1港口，i港口的所有集装箱从船舶上卸下并装上i 1，hellip;，N港口的集装箱，在这些港口不论是被迫倒箱还是主动倒箱都有可能发生。船舶在港口到港口之间的航行过程中集装箱不被移动，当到达第N个港口时所有集装箱被卸下。

如果j集装箱的目的港是j港口，则所有j集装箱在j港口之前被装载上船，在到达j港口时统统被卸下；如果一个j集装箱的起始地为i港口则集装箱可命名为i,j集装箱。如果存在jrsquo;集装箱的位置为(rrsquo;,c),j集装箱的位置为（r,c）且有jrsquo;gt;j、rrsquo;lt;r,则jrsquo;集装箱阻塞了j集装箱卸载通路，jrsquo;集装箱称为j集装箱的阻塞箱，当出现集装箱装卸载受阻时倒箱操作必不可少。

令为Ntimes;M阶装箱矩阵，表示i,j集装箱的装载编号 ，其中i,jisin;{1，hellip;，N}，且对所有i,j都有gt;0，对所有ige;j有=0。如果依次每个港口所装集装箱总数不超过集装箱船的容量，则装箱矩阵可行的。从技术层面来说，当且仅当T满足下列式子时，装箱矩阵可行：

如果T不可行，则需要决定哪些集装箱装载甲板上，超出了我们的考虑范围。因此，本篇文章只考虑装载矩阵可行的情况。

令集装箱装载总数，L和U分别表示在整个航行过程中装载和卸载集装箱总数，注意，如果在船舶挂靠第一个港口之前没有箱子装载在甲板上，则L=U。由于每个集装箱都至少需要进行一次装载一次卸载操作，故倒箱总次数Z=L U-2Kge;0。此外，定义Z/（2K）为倒箱比例，作为研究装载计划性能指标。

备注：

⒈ 如果Nle;3，则不论给定任何T,R,C，配载计划中都将不会出现倒箱操作。

⒉ 如果R=1，则不论给定任何T,N,C，配载计划中也不会出现倒箱操作。

⒊如果Nge;4、Rge;2，对于任意C，总会存在T使得倒箱操作不可避免的发生。

具体细节参阅在线补充的Ding amp; Chou（2015年）的材料。

备注表明我们仅需考虑Nge;4、Rge;2的配载情况。注意到C=1的情况在Aslidis1989年文章中研究过，所以我们着重于Cgt;gt;1的现实配载问题。

3 启发式算法

3.1. 准备

如果一列既不是空着的也不是装满的则称为可用列，在非空列中，相邻的j集装箱形成j层。一列中最顶端的一层称为第一层，与第K层相邻并处在第K层下方的一层称为第（K 1）层。如果第K层为一列的最底层则将第（K 1）层视为N层，并没有之后的第（K 2）层存在。如果第一层是l层的则该非空列称为l-top列，如果在这列中最近的目的港集装箱为l集装箱则称该列为l-min列。

如果一列或者一栈中没有阻塞箱则按顺序依次装卸箱，否则不按顺序装卸箱。列的阻塞箱数是假设之后港口没有集装箱再装入该列时所进行的必要倒箱操作次数。一列中若没有lle;m的阻塞箱l，则该列重新装载m。一列重新装载m，则所有lgt;m的l集装箱都装在lle;m的箱子下面。对于“重新装载”这一名词Avriel等人在1998年也有过类似定义，Aslidis等人也把它叫做重新布置。

1989年Aslidis证明了当在一列中装载多个集装箱时通常按照其顺序进行装载较好，即根据目的港的远近进行装载，较远目的港的装载先装较近的后装，有时候，在装载之前我们也会卸下一些装载混乱的集装箱以减少之后的倒箱次数。在我们设计的算法中，这种自动倒卸箱操作是由近似自动倒箱决断程序决定的。

把尝试装载一组集装箱的情况考虑到在港口i装载一组集装箱于合适的列c中称为尝试配载。假设i集装箱和i的阻塞箱都已被卸载，注意到当我们在试配载时需配载的集装箱数会超出c列中空着的载位数，故假设在试配载的列c中集装箱最近的目的港为k,最远的目的港为u。

在试装载集装箱于c列之前，为了减少后续倒箱量我们可能要先卸载列c中的一些集装箱以重新配载m。在目的港jge;k卸载的集装箱则形成一个新的集合称为卸载集，并将卸载集装箱的目的港jlt;k的箱子忽略（因为我们设计的算法在按减少目的港数方式处理集装箱时，这些箱子会在后面被处理）。尽可能多的使试配载集装箱和卸载集中相同目的港的箱子将按顺序载入c列，并且卸载集的箱子须在试配载集装箱之前装载。

当时不卸载任何箱子，直到一列中只剩下l集装箱且之后，m被重新排布。另一方面，这一重新配载过程与所有mge;u的港口集装箱配载相同，因此，我们只需要考虑重新配载标准m，其中misin;{k-1,hellip;,u}。对于每一个重新配载m标准，最小卸载量需满足假设的G(m)值，即G(m 1)ge;G(m)。此外，定义H(m)为卸载操作之后试配载集中能装入列c中的最大集装箱量。令B(0)为对列c进行任何操作之前该列的阻塞箱量，B(m)为对列c完成所有操作之后的阻碍箱量,因此，我们可令H(m)近似等于B(m) G(m)-B(0)。MVSD程序选择所有m值中选择使得H(m)最大的m值，或者选择在使得H(m)最大的m值相当的值之中又使得B(m) G(m)最小的m值，再或者选择使得H(m)最大、B(m) G(m)最小的值中又使得B(m)最小的最小m值。具体细节参阅2015年Ding 和 Chou所诉的MVSD程序案例。

3.2. 主要算法

给定N,R,C值，给定一个可行装载矩阵T,算法产生矩阵，其中，是一个Rtimes;C阶矩阵，也相当于配载计划，它记录着贝位在当前i港口的状态。令为航行前的初始配载计划，因为所有贝都为0，所以是Rtimes;C阶零矩阵。令港口i的装载矢量为,其中为在i港口装载在甲板上的集装箱数量。在每一个i港口操作集装箱之前的初始值都有，当每卸载一个或者装载一个集装箱时分别加1或者减1，并且在离开i港口时为变为0。该算法生成是基于与从i=1到N-1顺序取值求的。注意到和列状态是不断更新且随着每个集装箱的操作之后仍存在的，因此在算法中我们不需要重复的描述。

在算法执行过程中，有时我们需对可用于装载集装箱的列进行处理并指定相应的集装箱装载顺序。当我们说“根据的优先顺序对列进行装载”可理解为：1）在所有可行装载列中，列最先装载；2）所有可行列，可行列最先装载；3）列均可行，且任意列都能第一个装载。

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[153751]，资料为PDF文档或Word文档，PDF文档可免费转换为Word

主要算法：

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章