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

岸桥调度问题

诺拉 阿尔-达海瑞、阿里 迪阿拜特

概述

最近世界范围内集装箱码头运输工艺的发展极大地刺激了沿海操作和资源管理对优化模型的需求。随着船的规模和集装箱体积的增大，岸桥调度领域的进展引发了对新的建模方法的需求。这正是本文的目的所在。它旨在发展一种全新而简易的的方案来解决岸桥调度问题（QCSP)。这个项目的目的在于确定码头装卸作业的顺序以便使岸桥完成操作的时间最小化。项目主要归功于完成最小化的方式，也就是使不同域内装载量的差异最小化以及竟可能保持工作量的的均衡分配。此外，还有重要的细节需要考虑，比如起重机的双向运动，另外，完成装卸任务之前，岸桥在域间的通行能力也要考虑进来。这些现实性的假设通常会增加模型的复杂程度，但是，在目前的工作中，这些不便可以被全新的简易方案带来的方便抵消。本文针对这一问题提出一个混合整数规划（MIP）公式，通过运行不同的参数表明，这个模型可以高效的解决问题，尤其是针对小规模情景。

1. 简介

18世纪末集装箱标准化（也被称为集装箱化）的发明，引发了航运业的革命。它使货物的装卸处理更为平滑，发达的航运业增加了世界各地的联系并且带来了如同梦幻小说般巨大的收入，给世界经济带来了前所未有的增长。为了维持这一增长趋势，世界各地的码头都在努力跟进集装箱货运的极大增长，他们中的许多正面临处理装载15,000个或以上集装箱的超大型集装箱船的挑战。贝尔德提出了一个关于船的持续性规模增长和整个交通的简明的观点。集装箱运输量的快速增长与港口的发展并不匹配，成为各港口需要面对的挑战。世界范围内集装箱码头数量的增加随即带来了剧烈的竞争，客户可以做一系列选择，比较终端运营商提供的各种服务。港口运营商只有保持高品质服务，随时满足客户的需求才能吸引和保留客户。于是，港口致力于提升服务质量以吸引更大吨位的船光临，完成更大的吞吐量。海港处于一个需求更高效的运营规划和管理的临界状态，一个为之量身定做的解决方案千金难求。这方面的研究正获得越来越多的关注，以帮助提高集装箱码头的装卸能力。

世界各地的港口向船舶和货物持有者提供设施和服务。他们的服务主要可以分为海岸服务和堆场服务。服务包括一系列装卸载操作，也包含将货物从船上转移到堆场。海边的业务特别的涉及两个关键资源的利用，即码头空间和岸桥。大多数关于沿海操作规划问题的文献根据对这两个资源的优化利用划分为三个独立的方向：(1)泊位分配问题(BAP)，(2)岸桥分配问题(QCAP)，(3)岸桥调度问题(QCSP)。

当前论文的主要贡献在于所建立目标函数的新颖性，其目的在于尽量减小在不同域内集装箱装载量的相对差异。据我们所知，这一方法还从未在以前的文献中被提及，然而，本文的研究得出的目标函数可以引导岸桥以最佳的时间表运行，以此最小化运作时间，降低成本，充分利用码头资源。当前方案的重要优势在于非连续式的工作假设，以避免在全部完成指定装卸任务前岸桥在域间的移动。这个在现实中的适应性占优于其灵活性。QCSP通常更具复杂性，因此本文使用一个简单而准确的方法来生成一个简单的公式来解决充分利用时间的问题。目标公式也可以扩展到相对宽松的限制环境下，这也将在公式部分做简要的阐述。

在论文接下来的部分，第2节做关于QCSP的论文回顾，接下来第3节详述假定，问题定义和QCSP的新应用公式，第4节通过一系列实验评估模型的有效性，最后第5节为研究做结论病并提供深入研究的某个方向。

1. 文献回顾

为集装箱码头提供可以提升工作效率的模型和方法对于帮助其通过普及的供应链系统应对飞速增长的货运量是必不可少的。也因此，近年来致力于帮助港口提升作业能力的研究论文以明显态势增长。比尔沃斯和迈克尔为现存模型提供了一个分类方法。在现在的回顾中，将主要描述那些涵盖能够为QCSP导出令人满意的解决方案的问题构建方式。

达刚佐首度解决了起重机调度问题，他开发了一个船舶装载的MIP模型。他的模型需要假设不同域在相同时间段内，起重机之间的工作量保持平衡。作者提出了精确而具有新颖的解决方案，目的在于最小化由于船的耽误引起的成本增加。这与此后成为主流的最小化完工时间这一方案不同。需要注意的是，此次主要工作都不考虑起重机之间的干扰。作者用基于一些基本原理和发现发展起来的一项简单技术解决了一些小型案例。此后彼得可夫斯基和达刚佐应用分支定界法解决了更大型的案例。曾等人针对岸桥的双循环调度开发了混合整数规划模型，他们的模型考虑出港集装箱的配载图和岸桥的作业顺序。为此他们使用了被称为双水平演算法的新算法。

李等人基于岸桥的船域分配提出了一个计算公式，需要假设岸桥的个体通过率相同。他们试图最大化岸桥的货物通过率，并用了几种探索方式试图解决这一难题。随后利姆等人基于整个域提出了新的公式，他们表明岸桥非线性工作时总存在最佳的工作时间表。他们不考虑岸桥的精确工作时间也不关心工作时岸桥间隙的最小化。金姆和帕克的研究中考虑了岸桥间隙但却忽略了明确的受力环境。默西亚和科迪尔改善了这一不足，他们增加了约束，使岸桥更稳定。两个公式都被后来的研究大量引用。

一项使用了MIP的研究中，作者以分支定界算法为基础提出了有创见的方案。该算法搜集高于平均工作量水平的子集并考虑干扰提出有效的划分边界和分支的标准。他们把自己的方案与竞争对手的相比较，产出了令人满意的结果，特别是对于岸桥较少的码头，较小计算工作量作用显著。作者称方法之所以有效使因为创新地对单向时间表展开了思考。随后的研究成果只在特定的时间窗口起作用。发展MIP的目的在于最小化装卸总时间，由最新的完成时间决定所有任务。通过搜索单向时间表的解空间得出结论，最佳的解决方案一定出自单向时间表的解空间，但所得解仍然是高质量的。

刘等人所建立的方案目的在于尽量较少船舶离港的延缓时间。在模型的假设中，作者将每个域的工作总载荷作为岸桥的集装箱平均处理时间的分母，集装箱和泊位按域分配。这项研究考虑了岸桥间的间隙约束，并假定所有岸桥的工作效率相同。作者将问题切割为两个更小的相关的模型，也即集装箱层面和泊位层面。

这两者都是混合整数非线性规划问题，但是作者认为，所需要控制的计算机变量比MIP少。计算机实验表明，此法有效切高效。李等人在公式中增加了每个海湾的MIP处理优先级，并修改目标函数以使最小化每个港湾的加权完工时间。张和金姆的研究也引入了一个不同于之前文献中的目标。他们的MIP公式的目的不是最小化完工时间，而是最小化岸桥在船上循环工作的总次数，他们创造了一种新算法，通过分解工作时间表，区域优化以找到一个港内最佳的工作顺序。数据表明，多数情况下从算法都找到了执行港口运营的最佳方法。

乔等人引入新的集合覆盖方案，提出关于起重机工作顺序的MIP并解决了大型实例。他们将清洁和堆场拥挤考虑在内，后者是一个相对新颖的变量。研究中，作者用新方法解决了MIP单船模型且效果良好，该问题后来转化为一个广义集覆盖问题及其分支的精确求解。对于联运测序，堆场拥挤约束拉格朗日松弛，因此问题可以分解，在子梯度算法的每次迭代过程中都要进行二次迭代求解，作者注意到计算结果有很大不同，但在计算效率方面，拉格朗日松弛认为值得推荐使用的方法。

基于金姆和帕克的调度方案开展了不同的研究。最近，考虑QCSP岸桥分配问题的集成模型已经得以发展，这个综合问题同时确认码头吊船的分配和处理顺序。福等人提出了一个制定和解决集成模型的新方法，考虑实际因素包括岸桥的干扰。随后提出的拉格朗日松弛模型可以作为一个能取得理想结果的合适方法。

显然起重机的调度是一个范围是很大的研究课题，在达成最为准确而有效的方法的共识之前，研究者们仍在不断学习制定和结果问题的新方法。然而，有一些现实考量在达到一定程度之后在所有工作中都是不能被忽略的，首先，QCSP的目标是寻找一个岸桥为船只服务的最佳作业时间表，岸桥使重型钢结构，安装在钢轨上装船或卸货，由于是单一轨道，岸桥不能相互交叉，安琪哦啊之间必须保持安全距离。通常情况下，船被分为不同部分，每个部分最多只能被一个岸桥服务。通常，货物卸完之后，岸桥就可以在不同部分之间移动。岸桥从一部分移动到另一部分所需的时间称为旅行时间，本文的模型假设旅行时间可以忽略不计，而且在未卸货物前岸桥也可以移动。本文新颖之处在于最大限度减少海湾之间的负载差异，同时假定岸桥在完成当前装卸任务之间即可移动。假定通常合理，但若将忽略比分考虑进来将显著提高优化方案。此外，起重机的单向不予考虑，也就是说，岸桥可以双向移动，而不是通常的但不切实际的假设岸桥只能从左到右移动。预期这一方案相比现存方案会明显简化，却可以不牺牲精确度，产生一个最优解。此外，简化的计算量优于现存的几种方案，而且是一个可供研究人员进一步实施和测试的方案。

1. 问题陈述和方案

3.1 问题描述

本节探讨问题特点以及采用的建模假设。首先，这是典型的海滨作业，将船只划分为不同域，每个域内按确定序列从左到右堆放有一定数目的集装箱，在任意时间点，一台岸桥最多只能在一个域工作，也就是每台岸桥只能在指定的域内进行装卸作业。单个岸桥一次只能一个执行单元装载或卸载。考虑到岸桥的运动，最重要的就是要避免岸桥之间运作路径的交叉，将岸桥固定在分配的轨道上，也就是说，假设岸桥也按索引顺序从左到右分置在海岸边，低索引序的岸桥不会越位到高索引序的岸桥，随后的例子中会看到岸桥的分级。此外，与论文中大量讨论的不同，现有模型允许岸桥在不同的域之间移动，及时此域内的装卸还未完成。实际上很容易实施，因为多出的自由度允许更好的解决方案。这导出一个能更好反映现实生活中运转状况的模型，只要不越界这一假设得到保证。鉴于岸桥在不同域之间移动的时间可以忽略不计，可以合并为第三部分的一个扩展。

图1. 7域单船配4岸桥的图示

几位作者使用的另一限制条件是起重机必须单向移动，不存在滑移。本文中没有这个限制，它被认为是不必要的，而且也不能充分利用起重机可在不同域之间自由移动这一假设。目前采用的模式是双向的，只要轨道不交叉而且留有足够安全的间隙，岸桥可以自由的从左移动到右，现实中这也是可行的最后，假定所有的起重机有相同的服务率，而服务率这一参数也很容易调整。图1提供的图形，描述按序排列的域和岸桥，岸桥安装在轨道上，起重机之间留有安全余量，堆放的集装箱也是。将船分为不同域时已经隐形考虑了起重机之间的距离，因此本模型中未纳入安全边距。

从文献回顾中可知，通常QCSP的目的是最小化岸桥的完工时间表，以船只的最迟完工时间为衡量。可想而知，这也就是对工作量的有效均衡分配提出要求。因此，最小化域间工作量差异也可以通过均衡分配工作量间接减少工作时间。

3.2 问题陈述

本节我们用简单例子表明新方法可以产出优化方案。如图2中一艘船被分为3个域，每个域各装有100、150、125个集装箱。由两个起重机作业，岸桥布置需要得出最佳的卸载工作时间表。为了不失一般性，假设岸桥每小时卸载25的集装箱，以在尽可能短的时间内完成卸载为目的。

图2. 3域单船配岸桥的图示

基于此提出一系列可能的解决方案。

方案1将域1分配给岸桥1，域2分配给岸桥2，四小时后域1内卸载完成后岸桥1移动至域2继续卸载，为了不发生交叉，岸桥2则移动至域3.总共可用9小时完成卸载。如表1所示。

可行解1：

表1

另一个方案将岸桥1首先布置在域2，岸桥2布置在域3,4小时后岸桥1移回域1，岸桥2完成3域任务后移至域2完成剩下任务。总共需要8小时，比可行解1所需时间少。如表2：

可行解2:

表2

可以看出可行解2优于解1是因为对资源进行了合理的分配。最短时间问题可以简化为最好的资源分配问题。按此逻辑，本例中的最佳方案是使岸桥1、2一直处于工作状态。集装箱总量375，平均分配，取每岸桥188，可得最短时间为7小时31.2分钟。实际中需要更频繁的启停岸桥，但启停时间影响不大因此不予考虑。如表3所示

可行解3：

表3

从简单版本逐渐引申，我们着眼于寻找最优化资源配置的最佳方案，接下来将提供模型的建立方法。

3.3 优化模型

表示法设置如下：

表示船的域，用或者表示。

表示分配到船的岸桥，用或者，表示岸桥按从左到右

排列的序号。

表示时间，用或者表示

参数

域内需要完成的工作量。

统一的岸桥工作效率。

效率极大值M

决策变量

时刻域和域内存在的工作量的差异。

时刻域i内还未完成的工作量

以下

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

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