多码头间运输数学模型

A mathematical model of inter-terminal transportation

Kevin Tierney；Stefan Voß；Robert Stahlbock

摘要

我们提出了一种新颖的整数规划模型，用于分析新建和扩建海港的码头间运输 (ITT)。 ITT 是集装箱在港口内码头（海运、铁路或其他）之间的移动。 ITT 是集装箱转运延迟的重要来源，这会花费港口资金并影响港口的声誉。我们的模型可帮助港口分析新基础设施、码头布置和 ITT 车辆投资的影响。我们提供了两个港口的 ITT 分析，德国汉堡港和荷兰鹿特丹港的 Maasvlakte 1 & 2 区域，其中我们解决了车辆流与多商品集装箱流相结合的问题。基于拥塞的时空图优化。我们引入了一个两步求解过程，该过程计算整个 ITT 问题的松弛，以便更快地找到解决方案。我们的图包含特殊结构来模拟车辆的长期装卸，我们的模型足够通用，可以模拟 ITT 的许多重要的现实世界方面，例如交通拥堵、惩罚集装箱延迟交付、多种 ITT 运输模式、和港口基础设施改造。我们表明我们的模型可以扩展到现实世界的大小，并为港口的长期决策提供重要信息。

1 引言

在世界各地，越来越大的港口正在建设中，以跟上集装箱运输的增长。 港口通常包含多个码头，为集装箱船、铁路、驳船和其他形式的腹地运输提供服务。 集装箱在不同运输方式之间转运时，往往要在码头之间转运。 集装箱在码头之间的移动，称为码头间运输 (ITT)，不仅是港务局和码头运营商要处理的运营问题，也是规划新码头和集装箱港口时要考虑的战略问题。

正确选择码头布局和它们之间的交通连接，以及车辆类型和车辆数量，是港口必须做出的昂贵且关键的决定。 高效的 ITT 系统的目标是最大限度地减少集装箱在码头之间移动的延迟，从而减少并在理想情况下消除集装箱的延迟离港。 为此，我们引入了一个基于时空图的优化模型，以确定 ITT 场景中车辆和集装箱的最佳流量，以协助港务局的决策过程。

我们使用 ITT 运营的抽象视图，使用具有最大弧容量和节点吞吐量的时空图将车辆建模为通过网络的流量，并将运输需求作为多商品流给出。 我们专注于最大限度地减少集装箱的整体延误，这是港口规划者的一个重要考虑因素，因为延误出货的成本通常非常高。

以前在 ITT 战略分析领域的工作主要涉及模拟鹿特丹港 Maasvlakte 地区的码头间运营，并分析由此导致的集装箱提货和交付延迟（Ottjes、Duinkerken、Evers和 Dekker，1996 年） , 2006, Duinkerken 等人, 2006)。 与这项工作相比，我们优化了集装箱在网络中的流动，以便为港口规划者提供更好地估计使用特定车辆、道路设计、新基础设施或交通规划的成本。 因此，本文提供了以下新的贡献：

1. ITT第一个完全定义的数学模型，
2. 最小化 ITT 交付延迟的两种精确方法，
3. 服务于多商品流的车辆设置中的拥堵建模。

本文组织如下。 我们首先在第 2 节中概述了 ITT，然后在第 3 节中进行了简短的文献综述。然后我们在第 4 节中介绍了我们的数学模型，以及我们构建时空图的方法和两步求解方法 用于解决我们的整数规划 (IP) 模型。 我们在第 5 节中提供了计算结果，表明我们的模型不仅提供了有关 ITT 的有用信息，而且可以在合理的时间内由 CPLEX 计算。 最后，我们在第 6 节总结并讨论未来工作的方向。

2 多码头间运输

3 文献综述

Vis 和 De Koster (2003) 描述了转运的一般过程，包括 ITT。与 ITT 最相关的工作是 Ottjes 等人（1996 年，2006 年）和 Duinkerken 等人（2006 年），它们都描述了鹿特丹港 ITT 的模拟法。这些研究的目标是衡量不履约的数量，即在规定时间后到达目的地码头的集装箱数量。虽然仿真方法能够对 ITT 操作的许多细节进行建模，例如装载和卸载程序以及多拖车系统中载人牵引装置的使用，但该方法除了调整优化参数外不执行优化运行以尝试减少非性能。特别是，Ottjes 等人（2006 年）在模拟方法中考虑的不仅仅是 ITT，还包括集装箱从船舶到堆垛的码头侧移动。我们的模型与这些方法形成对比，因为我们使用网络流优化 ITT，为港口提供不同的非性能视图。

4 数学模型

我们在时空图上对 ITT 进行建模，该图具有几个专门设计的结构，以便对交通拥堵以及车辆的装卸进行建模。 我们创建了一个通用模型，该模型基本上可以包含用于 ITT 的任何类型的车辆，以及不同类型的基础设施。 我们的图表使用精心设计的结构来模拟驳船等缓慢装载车辆的处理，并包括能够模拟交通拥堵的组件。

我们的模型基于几个关键假设。 第一个假设是，除了在码头装卸集装箱外，不同类型的车辆不会相互影响。 这意味着图形弧上没有多种车辆类型行驶。 这种假设大大减少了模型的大小，大大减少了节点和弧的数量。 这是由于车辆的速度、装载时间和拥堵特性不同造成的。 其次，我们假设 ITT 集装箱应该因迟到而受到惩罚，但允许早到。这与 Duinkerken 等人 (2006) 相反，但我们认为提前交付的集装箱是码头内运营的责任。此类集装箱可以堆放在院子里，也可以存放在滚动缓冲区中。第三，我们认为所有类型的集装箱都需要一个单位容量的车辆。实际上，情况并非如此，因为有 20 英尺和 40 英尺集装箱，以及必须在码头之间运输的超限集装箱。我们的模型能够在稍作改动的情况下处理此类集装箱，但这这工作留待未来的研究。最后，我们抽象出短期的车辆活动，例如将拖拉机连接到装载有 MTS 中​​集装箱的拖车。虽然许多短期活动会随着时间的推移而累加，但在网络工作流中对它们进行建模需要过于精细的离散化。然而，由于此类活动的时间较短，将它们排除在模型之外并不代表主要的误差来源。 

4.1 图结构

4.1.1 静止弧

4.1.2 长期装卸

4.1.3 拥塞

交通拥堵是许多 ITT 系统面临的一个关键问题，因为它们经常使用对一般交通开放的道路。对拥堵的基本影响进行建模是我们模型的重要组成部分。例如，这些使我们能够评估高峰时间对 ITT 的影响、港口区域内 ITT 车辆高占用率/优先车道的影响、隧道避免交通的影响，或港口内道路网络如何增加准时的 ITT 交付。因此，我们对可以在某些弧上行驶的车辆数量施加了容量。该容量对应于特定时间可以同时使用道路（或水路）的最大车辆数量，并限制了每个时间段的交叉口总吞吐量。因此，拥塞被建模为从一个时间段到另一个时间段的溢出，因为静止弧没有容量限制。也就是说，当一个弧或交叉口已满时，车辆必须等到下一个时间段才能使用它。通过这种方式，对过度使用的道路和交叉路口实现了延迟。我们为未来的工作保存了更详细的拥塞模型，例如 Kaufman、Nonis 和 Smith（1998 年）或 Köhler、Langkau 和 Skutella（2002 年）中的模型，因为它们建模的细节对于当前需要的时间离散化来说太精细了解决ITT问题。此外，两种拥塞模型都无法考虑我们的多商品流或 LT 节点，这意味着将此类技术集成到 ITT 模型中并非易事。

4.1.4 弧的性质

4.1.5 时空网络图节点的性质

4.2 需求

4.3 时空网络图示例

图 2 显示了我们的汉堡港模型在 25 分钟内使用 5 分钟离散化的时空图。大多数连接都在公共道路上，尤其是在 B、E、I1 和 I2 之间。每条弧线根据车辆的连接定义了车辆所需的行驶时间，并且所需的行驶时间可以在模型中的不同时间变化，以表示高峰时段或严重的交通中断。请注意，为清楚起见，我们不会显示以时间 25 之后的节点为目的地的弧。在图中，在 t = 0 时，有一辆车辆位于节点 E。在 t = 0 时，需求源自 B，并且必须在时间 15 之前到达 E，以避免每个离散化周期 5 个单位的损失。红线显示了 ALV 在没有集装箱的情况下从 E 行驶动到 B 的路径。 ALV 在到达 B 并在同一时间段内离开时在 t = 10 装载集装箱，因为 ALV 快速装载，然后返回到 E. 蓝线显示了需求从下达到交付的位置。首先，在被 ALV 接收并通过 I2 传输到 E 之前，需求在精致弧上停留在 B 两个时间段。由于集装箱延迟交付一个时间段，因此产生 5 个单位的罚款。请注意，这是此实例的最佳惩罚，因为由于 ALV 在时间 0 的位置，无法提前交付集装箱。 

标题汉堡港 ALV 在 25 分钟时间内的时空图，离散化为 5 分钟。 实心弧代表道路，虚线弧代表静止弧。 码头A、T、B 和 E 通过交叉点 I1 和 I2 连接。 从 E 到 B，通过交叉路口节点 I2 的车辆路径以红色突出显示，从 B 到 E（在时间 0 释放）的需求路径以蓝色突出显示。 （为了解释这个图例中对颜色的引用，读者可以参考本文的网络版本。）标题

4.4 整数规划模型

4.5 流优先两阶段解法

除了在 IP 求解器中一次性简单地求解上一小节中的 IP 模型之外，我们还提出了一种称为流优先方法的两步求解方法。 首先，我们发布约束（5）-（9），它们对应于集装箱多商品流，并求解相应的IP。 这个 IP 通常需要很少的时间来求解，因为像 CPLEX 这样的求解器对多商品流结构有很强的切割。 然后我们发布约束（2）-（4），它控制车辆的流动并确保集装箱由车辆携带。 最后，我们使用纯多商品流问题的解决方案作为起始解决方案（尽管不可行）重新解决了 IP。 

尽管由于车辆的路线安排，多商品流解决方案基本上总是不可行的，但 CPLEX 能够使用该解决方案作为解决更大问题的内部指南。 这背后的想法是，一旦车辆进入问题，多商品流中集装箱的许多路径仍然有效，并且通过在没有车辆复杂化的情况下计算这些路径，CPLEX可以专注于完成运输 解决完整问题时更困难的集装箱。 或者，CPLEX 可以使用修复机制来尝试修复解。 我们在以下计算评估中确定了这种方法的有效性。

5 数值实验

本节描述了对基于汉堡港和鹿特丹港的 Maasvlakte 1 & 2 区域的生成数据集的 IP 模型的评估。 我们表明，我们的模型为 ITT 系统的规划提供了有价值且可操作的信息。

5.1 数据生成

我们根据鹿特丹港关于 Maasvlakte 2 扩建的信息，以及在互联网上从汉堡港收集的数据，生成了一个人工数据集。我们对 AGV、ALV 和 MTS 在装载/卸载时间、车辆速度和容量方面使用与 Duinkerken 等人（2006 年）相同的车辆属性，使 AGV、ALV 和 MTS 的速度分别为 5.0 米/秒、4.0 米/秒, 6.6 米/秒。 AGV 和 ALV 可以各自携带一个集装箱，而一个 MTS 最多可以携带 5 个集装箱。我们允许 AGV 以每台起重机每小时 30 次移动的速度装卸集装箱。我们允许 MTS 每小时移动 35 次，这与通过将多个集装箱快速装载到一组拖车中所获得的效率相对应。请注意，我们没有详细了解涉及拖拉机单元耦合和解耦的 MTS。我们允许 ALV 具有基本上无限的加载和卸载速率。 Duinkerken 等人（2006 年）报告称，ALV 需要大约一分钟来装载或卸载集装箱，但与 AGV 和 MTS 不同，它们不必排队等待起重机。由于我们的模型无法考虑 ALV 之间的这种细粒度交互，因此我们允许它们在端口上具有快速加载/卸载时间。我们在零时刻在码头之间均匀分配车辆，如果车辆数量不能被终端数量整除，则随机分配剩余车辆。

我们假设模型中的驳船容量为 50 个集装箱，并且以 2.2 米/秒（略低于 5 节）的速度行驶，因为这是港口中常见的最大速度。 驳船可以以每小时 30 次移动的速度装载和卸载集装箱，我们假设使用两台起重机装载/卸载驳船，每小时移动 60 次。

5.1.1 拥堵

我们考虑了拥堵情况，其中道路（弧线）和交叉口（节点）在每个时间段内具有最大吞吐量。 虽然这样的模型缺乏车辆转弯方向的细节并且不处理特定的车辆与车辆之间的交互，但它能够对港口吞吐量提供合理的良好限制，这对我们的模型来说是最重要的。 此外，对车辆运动进行精确建模的拥堵详细视图将需要更多的变量，当存在数百辆车时，可能太多而无法找到解决方案。

5.1.2 需求

每个需求是通过随机均匀分布选择一个港口内的两个不同的码头，然后选择两个码头之间必须中转的少于50个集装箱的集装箱数量，最后设定一个放行时间和到期时间来产生的。为了防止明显不可行的实例，我们在 [0, tmax-2time(a,b)] 范围内随机均匀地选择释放时间，其中 tmax 是模型的最大时间减去常数 tc ，我们设置为 汉堡实例1小时，Maasvlakte实例2小时，a和b是需求选择的两个码头，时间(a,b)是最慢的车型在a和b之间行驶所需的最短时间。 为了防止出现无论用何种车辆类型都无法解决的不可行实例，我们根据港口地区大小选择tc的值。我们使用简单的全对最短路径算法（simple all-pairs shortest path algorithm）计算时间（a，b）。我们将此时间乘以 2 以进一步防止明显不可行的实例。 如果 tmax-2time(a,b) 是负数，我们在区间 [0, tmax/10] 中选择一个发布时间。 然后我们选择一个在发布时间加上时间（a，b）之间的需求到期时间，最大值为 tmax。 请注意，这可能意味着某些要求对于慢速车辆的交付是不可行的。 我们认为这是评估此类车辆类型的必要部分，因为只有生成适用于所有车辆类型的数据才能使慢速车辆在紧迫的期限内交付需求时看起来与快速车辆一样有效，这并不总是 这种情况。每个需求都与一个惩罚函数相关联，以阻止迟到。 我们对代表低、中和高优先级集装箱的需求使用三个惩罚函数。 我们使用三角形分布将大部分需求分配为低优先级需求，大约 30% 为中优先级，其余为高优先级（略高于 10%）。

5.2 汉堡港

我们在基础图中用 4 个码头和 2 个交叉点对汉堡港进行建模，并在 8 小时内用 5 分钟的离散化计算 ITT 性能。 我们为 500、1000、1500 和 2000 个集装箱生成 10 组需求。 然后，我们生成具有不同数量的道路车辆（50、100、150 和 200）、有 2 艘驳船和没有驳船（在下表中用 b 标记）以及均匀分布下的交通量 (U) 和高峰时间的交通量（RH）。 我们对包含非港口交通的特定弧线的高峰时段交通进行建模。 在高峰时段的第一个和最后一个小时，这些弧线的穿越时间比其他 6 小时要长。 

表 1 显示了汉堡实例的时空图的大小。 图的大小与容器的数量无关。 由于车辆的速度不同，弧线的数量因车辆类型而异。 8 小时结束时的某些连接无法通过慢速车辆完成。 出于类似原因，RH 实例的弧数略低。 也就是说，由于高峰时间，一些弧线需要更长的时间来遍历，因此在 8 小时窗口内没有终点。

我们使用 CPLEX 12.4 和 AMD Opteron 2344 HE 处理器（每个进程最多 3 GB 的 RAM 和最长 1 小时的 CPU 时间）将汉堡数据集中的实例求解为最优。表 2 给出了汉堡实例的平均惩罚（以千为单位），我们展示这些数据是为了展示我们的模型可以提供给决策者的数据类型。惩罚是集装箱数量、驳船数量、基础设施类型和车辆类型的每种组合的所有 10 次运行的平均值。在模型无法找到最佳惩罚的情况下，我们使用 LP 松弛。我们能够这样做是因为 LP 松弛值非常接近我们数据集中的最优解值。在我们求解到最优的 382 个实例中，有 500 个有驳船和没有驳船的容器，其中 91% 在根节点的 LP 松弛值等于最优解。这个百分比也适用于 1000 和 1500 个容器实例。我们无法将许多 2000 个容器实例求解为最优，但是在我们解决的 7 个实例中，它们都具有等于最优解的 LP 松弛。虽然这可能是幸存者偏差的一种情况，但我们注意到解决的问题在 CPU 时间范围内从几秒钟到几乎整个小时不等。当我们将超时降低到半小时而不是整小时时，我们看到已解决实例的百分比差异很小，它们的 LP 松弛等于最佳解决方案，即使已解决的实例较少。

在计算平均惩罚时，我们还结合了运行一次性模型的结果，其中我们将整个 IP 模型插入到 CPLEX 中，以及第 4.5 节中的流优先模型。 如果一种方法将问题解决到最优，则使用该目标，或者如果一种方法发现实例不可行，则即使另一种方法超时试图证明这一点，该实例也会被声明为不可行。 在讨论了这两种方法找到的解决方案之后，我们对这两种方法的运行时间进行了分析。

总体而言，MTS 在所有实例中提供最低的惩罚性交付。 然而，AGV 与驳船结合在 500 和 1000 个集装箱的情况下提供了几乎同样好的性能，在统一和高峰时段的情况下，与 MTS 和驳船相比，罚款仅增加 6.5%。 只有 50 辆车，只有 MTS 能够在所有 500 个集装箱的情况下提供所有货物的交付，在大多数情况下，也能完成1000 个集装箱的交付。 我们的模型表明，在给定的假设下，100 辆道路车辆通常足以执行 ITT，由于道路拥堵，增加额外的车辆无法减少处罚。

MTS 在所有实例中提供最低的惩罚性交付、AGV 与驳船结合在 500 和 1000 个集装箱的情况下提供了几乎同样好的性能

100 辆道路车辆通常足以执行 ITT，由于道路拥堵，增加额外的车辆无法减少处罚。

当 AGV 和 ALV 的数量增加时，可以看到我们的拥堵模型的效果，其中交叉路口每个时间段的吞吐量最大。当AGV 和 ALV的数量从 50辆增加到100辆时，通常在所有实例类型和集装箱数量中提高。 然而，尽管容量增加了，但从 100 辆到 150 辆或更多车辆的性能并没有得到同样的提高。 我们得出结论，这是由于交叉路口充满了 AGV 和 ALV，导致拥堵，这是港口当局需要注意的重要结果。

我们不包括 1500 和 2000 个容器实例的驳船结果，因为我们的模型由于它们的大小而在实例上超时。 超过 1500 个容器，AGV 和 ALV 开始不足以满足所有需求，并且实例被证明是不可行的。 AGV 和 ALV 的低承载能力是它们的主要缺点，尽管与 MTS 系统相比，它们的速度较慢也无济于事。 在这些场景中，ALV 更快的加载能力似乎并没有超过这些缺点。

我们接下来展示了用于解决 IP 模型的流优先方法和一次性方法的 CPU 时间结果。 流优先方法的第一步，解决了多商品流问题，这在 CPLEX 中通常只需要几秒钟。 即使有我们的装卸限制和 LT 弧容量限制（分别为约束 (8) 和 (9)）等侧面约束，生成的模型也没有太大的困难。

表 3 显示了一次性和流优先方法在汉堡实例上的 CPU 时间和超时次数。在 CPU 时间方面，流优先方法在 1000 个或更少容器的非驳船实例上优于一次性方法。在 500 个容器实例上，流优先方法的平均 CPU 时间是一次性方法非插入实例的 53%。然而，在驳船实例上，平均性能几乎相同，流优先方法在 AGV 和 ALV 实例上略胜于一次性方法，但在 MTS 实例上表现不佳。对于 1000 个容器实例，流优先方法的平均 CPU 时间为 380.56 秒，而一次性方法的平均 CPU 时间为 956.11，这意味着它只需要略低于一次性方法的 CPU 时间的 40%方法，忽略超时。尽管流优先方法在 1000 个容器驳船实例上有多次超时，但一次性方法与大多数实例的超时时间非常接近，以至于两种方法之间的平均时间没有太大差异。

在 1500 个容器实例上，流优先方法在 1500 个容器实例上的平均 CPU 时间（包括 3600 秒的超时）仅为 1242.51 秒，而一次性方法的平均 CPU 时间为 1539.91 秒，节省了 19% . 但是，在 2000 个容器实例上，流优先的平均运行时间仅为 1810.73 秒（包括之前的超时），而流优先方法的平均运行时间为 1921.41 秒，增加了大约 6%。

在高峰时段的 ALV 实例上，我们看到流优先方法通常在小实例上表现更好，在大实例上被一次性方法主导。 这可能表明，当弧受到显着限制并且有许多集装箱时，流动优先方法需要更强的松弛才能找到初始解。

在超时方面，在整个数据集上，一次性方法比流优先方法实现更少的超时，只有 116 次超时，50 辆车 126 次超时，100 辆车超时 98 次对 105 次，200 次超时 91 次对 105 次 车辆。 在 150 辆车的情况下，流优先方法比一次性方法少 2 次超时，只有 98 次超时而不是 100。但是，这些超时中的大多数是由于驳船实例，流优先方法 一旦集装箱数大于 500 就无法处理。仅查看非驳船实例，流优先方法只有 113 次超时，而一次性为 136 次。 我们假设使用 LT 弧的驳船装载和卸载限制使得在流动优先方法中找到一个好的多商品流动解决方案比在仅道路运输的情况下更困难，并且在未来的工作中，我们将研究增加削减以防止这种情况 从发生。

我们得出结论，流优先方法最适合非驳船实例，即使它在 CPU 时间方面在驳船实例上具有竞争性的性能。 然而，鉴于这两种方法即使在同一实例上的性能也经常存在很大差异，因此可以采用启发式选择方法，例如 Kadioglu、Malitsky、Sellmann 和 Tierney (2010) 的 ISAC 方法来选择是否 将流程优先方法应用于未来工作中的实例。

5.3 马斯莱可迪 1 & 2

6 结论与研究展望

码头间运输（ITT）是新港口建设和现有港口扩建决策过程中的关键因素。 这些项目代表关键的、长期的和昂贵的基础设施投资，需要决策者对 ITT 进行有效分析。 为此，我们提出了一个整数规划模型，以最大限度地减少集装箱交付延迟，该模型考虑了 ITT 的关键组成部分，包括交通拥堵、多种车辆类型和装卸时间以及任意码头配置。 我们还提供了一个两阶段的方法来求解模型的最优性。 我们注意到我们的模型无法处理在同一弧线上行驶的多种类型的车辆，我们打算扩展我们的模型以便能够在未来的工作中解决这个问题。

我们的模型可扩展到实际港口的大小、时间段和集装箱吞吐量，如使用鹿特丹港和汉堡港的 Maasvlakte 地区的示例所示，不仅对可行性进行了重要分析，而且 集装箱到达目的地的延误进行了分析。 我们的 ITT 模型是第一个结合优化车辆路线和集装箱流的模型，以便为港口和码头提供特定车辆和基础设施配置能够提供的最佳性能。 该模型代表了一类特别困难的时空模型，其中相互作用的车辆流、多商品流和拥堵约束都相互作用。

对于未来的工作，我们打算使用我们的模型来帮助分析建设新基础设施和/或购买新型车辆的成本与港口效率的提高和延误的减少。 此外，我们将使用该模型将输入引导至离散的港口模拟中，从而全面了解战略决策对港口效率的影响。 我们的模型还可用于帮助港口从工程角度确定最适合其港口的车辆特性。 最后，我们还打算调查长距离对港口设计的影响，例如在中国上海港或马斯平原地区以外的鹿特丹港发现的那些。

目标函数：最小化集装箱延迟

在零时刻在码头之间均匀分配车辆