英语原文共 12 页

用于将船舶放入船闸的精确和启发式方法

摘要

船舶安置问题构成了潮汐河港规划者的日常挑战。实质上，它需要将一组船舶定位在尽可能少的锁定室中，同时满足许多一般和特定的放置约束。这些限制使得船舶放置问题不同于传统的2D箱式包装。提出了该问题的数学公式。此外，开发了一种分解模型，允许在合理的时间内计算最优解。介绍了船舶放置问题的多阶最佳拟合启发式算法，并将其性能与左右后左启发式算法的性能进行了比较。在模拟和现实生活实例上的实验表明，多阶最佳拟合启发式算法通过滑坡击败了其他启发式算法，同时保持了可比较的计算时间。最后，新启发式的最优性差距很小，而它在计算时间方面明显优于精确的方法。

引言

进入或离开港口时，船舶通常会通过一个或多个闸室。 驳船在水道网络上行驶也是如此。 在船坞装载或卸载时，船闸为船舶提供恒定的水位，或者它们控制内陆水道的流量和水位。

越来越多的集装箱运输对海港提出很高要求（Wiese,Suhl,amp;Kliewer,2010）。改善船舶处理可缩短港口时间，使海港在经济上更具吸引力，在（地理上接近的）海港之间产生强烈竞争（Bish.2003; Chen.Bostel.Dejax.Cai , Xi,2006; Cullinane amp; Khanna ,2000; Guuml;ntheramp;Kim,2006）。虽然在海港处理船舶和集装箱的许多方面都得到了广泛的研究（Stahlbock amp;Voszlig;, 2008），港口基础设施的一个关键组成部分却很少受到关注：闸室。然而，闸的容量的次优使用可能会大大增加船的处理时间。当闸无法及时转移给定船舶时，该船可能会错过其在终端的时间窗口，导致港口总时间的大幅增加和终端的效率降低。因此，改进这些闸的操作可以在提高端口效率和经济吸引力方面起重要作用。

多式联运的预期增长是提高内陆水道锁定效率的主要动力（欧洲委员会，2009年，2011年）。多式联运是单一运输链中多种运输方式的组合，无需更换货物的集装箱。内陆航运是多式联运链中最有前途的运输方式，其在网络中的可用性和环境友好性是最重要的好处。在比利时和西欧的情况下尤其如此，内陆水道在主要海港的腹地通道中起着至关重要的作用（Notteboom amp; Rodrigue, 2005）。因此，通过更好的锁定作业提高（多式联运）驳船运输的效率是支持未来货运流量和增加内陆航运市场份额的关键问题。

文献评论

只有少数学术论文专注于锁定计划。 Wilson（1978）研究了不同排队模型对锁定能力分析的适用性。 研究表明，对于单室闸具存在良好的排队模型，但对于具有平行室的锁具则不存在。 其他一些研究主要集中在密西西比河上游（UMR）。 在那条河上，驳船连接在一起进行运输，然后需要通过通常比拖曳本身小的单室闸来转移。 拖曳被分成不同的驳船组，这些组一次一个地转移，之后它们重新加入下一阶段的旅行。Nauss（2008）提出了具有设置时间的单腔闸的拖船/驳船的最佳排序。 该方法允许一次转移一个拖船/驳船。 此外，它认为在第一次锁定之前所有的拖船/驳船都存在于闸。Smith，Sweeney和Campbell（2009）提出了一种模拟模型，用于比较不同策略以缓解密西西比河上游的拥堵问题。这些策略旨在提高闸的吞吐量，并构建了一个模拟工具来验证它们。 史密斯等人（2011）使用基于启发式和MIP模型的更复杂的决策规则进一步提高了这些闸的性能。

锁定调度文献的另一部分集中于具有（并行）腔室的闸，其能够将多个船舶一起转移。最近的一项贡献（Verstichel＆Vanden Berghe，2009）涉及规划一个带有三个平行腔室的闸，其中两个是相同的。所提出的方法允许多个船同时在一个腔室中转移，并考虑腔室的独立操作。特定问题的左右后左启发式结合晚期接受爬山者产生了良好的质量结果。在Verstichel，De Causmaecker和Vanden Berghe（2011）中研究了具有相同平行腔室的闸的腔室操作的调度。该贡献将问题识别为具有序列相关设置时间和发布日期的相同并行机器调度问题，并呈现数学模型。考虑具有固定处理时间的内陆闸和具有船相关处理时间的海港闸，提出了一种针对该问题的元启发式方法，并将其性能与先到先得的决策规则进行了比较。 Coene，Spieksma和Vanden Berghe（2011）专注于规划锁定操作，而不考虑船内实际放置船舶的情况。

本文考虑具有至少一个但可能具有不同性质的多个平行腔室的闸。 每个腔室具有有限的容量，基于其尺寸和一定的锁定持续时间，即将腔室中的水位从一侧的水平面改变到另一侧的水平面所需的时间。 具有相同尺寸和锁定持续时间的腔室具有相同的腔室类型。 因此，当一些腔室相同时，锁定将包括比腔室数量更少的腔室类型。 在计划通过锁定运输时，可能会出现不同的问题。

例如，转移多艘船只所需的时间取决于它们的尺寸和机动性。将船舶定位在舱室中甚至可能比实际的舱室锁定操作花费更长的时间，特别是在转移需要拖船的大型船舶时。当只有内陆船只被转移时，定位船只所需的时间可以被认为是恒定的，因为这些船只要小得多并且可以很容易地定位在舱室内。将船舶定位在腔室内所需的时间甚至可以包括在腔室的锁定时间内。操作平行腔室的策略也不同。一些闸使用成对的腔室，其必须同时操作，而其他系统允许腔室的独立操作。尽管有这些不同的方法，但所有上述情况都需要解决船舶放置问题。当几艘船可以在一个锁定中同时转移时，更好的船舶放置程序可能会大大提高锁的效率。闸在运输链中起着至关重要作用的两个例子是安特卫普港和比利时的Albertkanaal。

本文介绍了船舶布局问题的数学模型，并比较了三种算法：（i）基于精确分解的整数规划方法，（ii）改进的左右后左启发式算法（Verstichel＆Vanden Berghe，2009），以及（iii）多阶最佳拟合启发式。 第（i）部分的主要贡献是对船舶放置模型及其特征的深入分析，以及引入最佳解决方案的分解方法，即使对于非常大的实例也是如此。

第3节介绍了问题的细节和船舶放置问题的数学模型。 第4节描述了应用于该问题的三种解决方案。 第5节讨论了实验装置和结果，然后是第6节中的结论。

问题定义和模型

问题定义

船舶构成了船舶安置问题的第一个主要组成部分。 它们的特征在于宽度wi和长度li。 通过假设矩形船舶，我们简化了放置约束的评估。 这种简化是常见的做法，因为船舶的确切形状通常不能用于锁定操作员。 当船舶在一个腔室中放置在一起时，必须保持船舶之间的一定安全距离。 根据船舶的尺寸，类型和使用的拖船数量，为每对船舶定义这些距离。 问题的第二个组成部分是锁，它由一个由宽度W和长度L限定的单个腔室组成。船舶和舱门之间必须满足某些距离，既安全（碰撞）又实用（系泊柱）原因。

鉴于n艘船的有序列表，船舶放置问题旨在最小化放置所有船舶所需的锁定数量，受到许多特定的放置和顺序约束。这个问题让人联想到众所周知的二维装箱问题（或2D矩形SBSBPP（Wauml;scher, Hauszlig;ner, amp; Schumann, 2007）），其中一组矩形物品（船舶）需要定位在尽可能少的矩形箱（锁）内，以及不允许旋转物品的地方。但是，存在一些相关的差异。首先，在船舶放置问题中，存在一个序列约束，规定船舶需要以先到先得（FCFS）的方式处理它们在船舶清单中的位置。如果我们假设锁定按其索引排序，并且船舶清单中位置i处的船舶位于锁定k中，那么此列表中位置jgt; i的船舶不允许在任何具有索引l的锁定中ķ。其次，所有船舶应放置在它们所适合的第一个锁定中。这意味着如果最佳锁定数量为5，并且船舶7可以放置在锁定3或锁定4中，则应将其置于锁定状态3中。似乎这些约束对于船舶放置本身没有立即使用，它们在将船舶放置问题连接到锁定调度问题的时间部分时是至关重要的。由船舶放置算法生成的锁定可以由用于广义锁定调度问题的调度算法使用。如果从调度的观点来看所获得的锁定是次优的，则调度算法可以改变船舶订单，有效地为船舶放置算法生成新实例。通过在两种解决方案方法之间进行迭代，可以找到针对锁定调度问题的全局更好的解决方案。如果没有序列约束，这种子问题交互将更难实现。

第三个区别是系泊约束的集合：每艘船必须系泊在码头或另一艘船上。 据称，当船舶i在其整个长度上与船舶j相邻时，船舶i被称为系泊船舶j。 这种约束意味着每艘船将通过较大的船舶或通过相同尺寸的船舶连接到码头。 应该注意的是，船的宽度不会影响系泊约束的评估。 不满足该系泊约束的解决方案的示例在图1（d）-（f）中可视化，而标准2D箱打包约束在图1（a）-（c）中可视化。

虽然上述系泊约束在仅考虑内陆船舶的大多数情况下是足够的，但在其他设置中可能需要一些额外的系泊/安全约束。 例如，海船只能停泊在码头上。 在混合海上/内陆交通的情况下，内陆船舶通常不允许停泊在海船上。 此外，在某些船闸中，当水面以上的船体高度差异太大时（例如满载和空载船舶），船舶不能相互停泊。 这些附加约束可以被建模为群组系泊约束，其仅允许系泊到属于特定群组的船只。

最后一组附加约束涉及船舶放置问题的典型安全距离。必须向船舶提供一些“空间”，允许进行修正以防止在进出舱室时发生碰撞，并且在锁定操作期间可能发生轻微事故。对于内陆环境而言，对于所有船舶元组而言，这些安全距离可以被认为是相同的，而海港的交通需要更加个性化的方法。图2显示了不同船舶元组的安全距离限制。根据两艘船的尺寸和类型，可以计算出最小的横向和纵向安全距离（图2（a））。当两艘船都使用拖船时，横向安全距离也必须足够大，以便在锁定操作开始之前离开舱室时拖船在船之间航行（图2（b））。每个船和舱室门之间确定最后一个距离（图2（c））。这些都暗示着安全性（即避免与门碰撞）和实际原因（船舶可以停泊的系泊杆的位置）。该距离取决于腔室类型和船舶尺寸。

图1.锁定调度问题的系泊约束的直观表示。（OK：船以正确的方式放置，NOK：船违反了系泊约束）。

图2.锁定调度问题的安全距离约束的直观表示。（OK：船以正确的方式放置，NOK：船违反安全距离约束）。

在没有系泊和安全限制的情况下，船舶安置问题是NP难的。 这是根据Leung，Tam，Wong，Young和Chin（1990）的结果得出的结论，即确定一组给定的正方形是否适合给定的正方形是NP完全的。

人们可能想知道系泊约束是否真的使问题复杂化，换句话说，是否存在传统的二维装箱问题需要比船舶放置问题更少的箱（锁定）的实例。这个问题的答案是肯定的，我们提供了两个具有此属性的实例。第一个实例如图3所示。这里，船舶放置约束的应用导致具有两个锁定的解决方案，而2D箱包装问题仅需要一个箱。由于船舶数量有限，这个例子可以通过4.2节中的模型在不到100秒的时间内解决到最优。所获得的解决方案确认在考虑船舶放置约束时需要两个锁定来放置所有船舶。这8个项目有以下几个尺寸：12* 3，10* 4，9* 4，7* 6，7* 4，6* 3，6* 3和5* 2，腔室的尺寸是19* 13。第二种情况考虑了完美的包装，其中物品必须放置成三排以获得最佳的单箱解决方案。所有14个矩形的宽度为1，长度为27（2件），12（5件），10（6件）和6（1件），而腔室的尺寸为60* 3。对于给定实例，存在六种不同的最优解决方案，其中每个都违反至少一个船舶放置约束。因此，当该实例被视为船舶放置问题时，至少需要两个锁定。图4显示了这些单箱解决方案，并突出显示违反船舶放置限制的物品。为简单起见，在这些示例中省略了组系泊和安全约束。 考虑到这一点，最佳解决方案之间的差异将变得更大。

图3.没有可行的单箱装船放置解决方案可以找到这个问题，而构建单个箱2D装箱解决方案是微不足道的。 （挪威克朗：船舶违反船舶安置限制）。

图4.针对该问题的六个最佳2D箱包装解决方案都违反了至少一个船舶放置约束。 （挪威克朗：船舶违反船舶安置限制）。

MILP模型

我们提出了一种用于船舶布局问题的混合整数线性规划模型，该模型部分基于Pisinger和Sigurd（2005）的模型。该模型包含两个额外的船（i = 0和i = n 1），分别代表左和右码头。这些船只允许直接实施系泊约束，因为现在可以将码头视为具有固定位置的大型船舶，船舶可以停泊在该船舶上。该模型还使用一组MOOR i，其中包含船舶i，i = 1，...，n允许停泊的所有船舶。在内陆环境中，该套装包含的所有船舶都比船舶i长，因为船只只能停泊至少同等长度的船舶。在更一般的设置中，该组可能仅包含某种类型的船只。例如，海船可能经常只停泊在码头上，而没有船只可以停泊在海船上。通过更改MOOR i中可用的船舶，可以在此模型中实施任何此类系泊限制。该模型包括船舶之间以及每艘船与舱门之间的安全距离。这些距离取决于船舶属性，如船舶尺寸，船舶类型以及船舶是否需要拖船。虽然海船和驳船之间的横向安全距离可能平均为1.5米，但两艘需要拖船的海船之间的最小横向距离可能高达12米。

主要目标（1）是最小化放置所有船舶所需的锁定次数（）。 在具有相同数量的锁定的不同解决方案中，有利于将所有船舶放置在具有最低可能指数的锁定中的那个（）。 换句话说，当船舶i可以放置在锁定k或锁定k 1中时，当得到的解决方案具有相同的锁定总数时，它应该被置于锁定k中。 为了确保锁定的总数总是比放置船舶的锁定更重要，主要目标是乘以K，它应该足够大，例如。

约束条件（2）-（4）确保在同一个闸室中转移的两艘船不重叠。

所有船舶必须放在舱室的尺寸内，这由约束（5）和（6）建模。

约束（7）模拟了两艘相邻船舶之间的安全距离，见图2。该安全距离取决于两艘船的性质。

两艘相互铺设的船舶的安全距离要求在约束条件（8）中建模，并在图2中可视化。

约束条件（9）和（10）确保船舶与腔室的前门和后门之间的最小距离得到遵守。该距离由安全要求和码头

资料编号：[4173]