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

基尔运河双向船舶交通调度：模型，扩展及运算

Frank Meisel，Kjetil Fagerholt

关键词：双向船舶交通，基尔运河，混合整数程序，启发式算法，规划

摘要：基尔运河是一条连接北海和波罗的海的人工水道，全长约100公里，与环绕日德兰半岛（丹麦）航行相比，它能使船只节省数百公里的航程。由于运河有几个狭窄的部分，大型船舶无法相互通过，因此需要决定哪些船舶必须在较宽的侧线部分等待，以确保所有船舶快速安全通过。本文针对这一交通管理问题，提出了几种新的优化模型，包括变速率、侧壁路段通行能力和船舶等待时间限制。所有模型变量都捕获相关的交通规则和安全要求，以最小化船舶的总运输时间。为了快速解决这个问题，提出了一种启发式算法。在实际数据上的实验证实了启发式算法的优良性能，并确定了为船舶提供高质量服务的潜力。

1. 导语

基尔运河是连接北海和波罗的海的人工水道，见图1。它得名于基尔市，该市位于运河进入波罗的海的地方。运河是世界上最繁忙的水路之一，每年有三万到四万艘船通过。与日德兰半岛（丹麦）相比，根据其始发港和目的港的不同，船舶平均可节省463 km，参见WSV（2018）。鹿特丹和斯德哥尔摩之间的示范路线如图1所示。通过基尔运河的捷径可以大大缩短旅行时间。如果——取决于燃料价格水平——燃料成本的节省超过使用运河所需支付的运输费用，这也可能会降低总旅行成本，见Heitmann（2013年）。

图一.北欧和基尔运河

运河是一条双向航道，意味着由东向西的船只和由西向东的船只可以同时使用它。运河的布局是狭窄的过境段和较宽的侧线段的交替序列。在过境段，只有足够小的反向航行的船舶才能相互通过，而在侧线，任何大小的船舶都可以相互通过。侧线还提供有限的等候区，供船只等候，并被同一方向行驶的其他船只超越。这就产生了一个交通管理问题，即调度船舶的行驶时间和等待时间，以尽量减少所有船舶的总过境时间。所达到的过境时间对船舶运营商将其船舶通过运河而不是绕日德兰航行的吸引力有着至关重要的影响。为了向各类船舶提供有吸引力的服务，交通管理人员力求公平对待所有船舶的交通管理。

到目前为止，Luuml;bbecke（2015）和Luuml;bbecke等人已经对基尔运河的优化交通决策进行了研究。（2018年）。他们为问题的基本版本提供了混合整数规划（MIP）公式和启发式方法。对本文的贡献有三个方面：

1. Luuml;bbecke (2015) 和 Luuml;bbecke (2018) 的基本问题和MIP模型被以下几点拓展：（1）决定船舶速度，而不是假设恒定的给定速度；（2）限制等待时间，以保证船舶的最大运输时间；（3）捕获侧线区段的有限容量。所有车型均符合相关交通规则和安全规定。
2. 本文提出了一种新的启发式算法方法来快速求解各种形式的问题。
3. 利用实际交通数据进行了综合计算评价，验证了该方法的有效性。进行了多个不同等待时间的船舶试验，为基尔运河的交通管理提供了重要的管理见解。

尽管本研究致力于基尔运河的交通管理，但本文提出的一些建模和启发式算法思想可应用于其他内河航道的管理或单轨铁路调度等相关问题。

论文概要如下。文献综述见第2节。第3节介绍了基本优化模型和三个扩展。第4节描述了启发式算法。第五节介绍了计算实验。第六节对论文进行总结。

1. 相关文献

内河航道管理的研究常常涉及到船闸的运行。在那里，决定何时使用船闸室供上下游航行的船舶使用，以及船舶在每个船闸运行周期中在哪个船闸室上操作，以便最大或总的船舶等待时间最小化，见Campbell（2007），Smith（2009），Verstichel（2015）和Passchyn（2016年）的文献。尽管基尔运河的两端也有船闸，但船闸的运行独立于交通管理，见Luy（2011）的文献。为此，船闸运行规划为交通管理提供了船舶入运河次数的输入数据，但不在本研究范围内。

人们对管理运河中船只的交通流量也越来越感兴趣。一个中心问题是双向交通问题，即在运河的某些狭窄部分或整个运河中，反向航行的船只不能相互通过。这项研究经常考虑到特定航道的具体特点。格里菲斯（1995）的早期论文考虑了苏伊士运河的布局和使用的护航系统，为苏伊士运河提供了排队模型。Ulusccedil;u等人的文献（2009）为确定船舶通过伊斯坦布尔海峡的顺序提供了一个优化模型。伊斯坦布尔海峡包含一个狭窄的部分。如果该航段是由一艘太大的船舶或一艘运载危险货物的船舶进入的，只要该船舶占用该航段，则相反方向甚至两个方向的交通都将暂停。文中详细描述了相应的交通规则，并提出了一种船舶优先排序规则。Sluiman（2017）概括了Ulusccedil;u等人的研究（2009）通过提供一个优化模型、贪婪规则方法和改进的启发式算法，对单窄段航道进行船舶调度。他们将这种方法应用于伊斯坦布尔海峡和巽他海峡的问题实例。他们还考虑了有交叉口的水道的问题。Zhang等人的文献（2017）还研究了单个双向信道段的船舶调度问题。为了使船舶在安全条件下的平均等待时间和最大等待时间最小化，提出了一种启发式方法来建立两个行驶方向的船舶批次。Lalla Ruiz等人的文献（2018）提出了一个MIP模型和模拟退火启发式算法，用于调度通过长三角进入上海港口的船舶。与之前的论文相比，三角洲提供了多条平行水道，因此每艘船必须被分配到一条水道上。在每一条航道内，对岸船舶只有在其总宽度不超过航道宽度时才能相遇。由于水路是平行运行的，分配给一条水路的船舶可以独立于其他水路调度。Tan等人（2018）进一步调查了长江世卫组织为访问沿河不同港口的船舶设计了时间表。由于船闸作业，船舶运输受运输时间不确定的大坝影响。本文提出了一个在准时到达的机会条件下，最小化燃料消耗和船舶往返时间的数学模型。Righini（2016）调查了意大利北部的一个双向和单向内陆水道网络。重点不在于确定船舶的精确时间表，而在于估计这一水道系统的容量。为此目的，他们提出了一个网络流量模型，该模型根据航道段的容量、交通规则和港口容量，最大化可以通过该系统的驳船流量。

进一步的研究是结合港口设施的泊位分配决策，分析连接港口和公海的航道的船舶交通调度。Zhang和他的团队（2016）考虑一个单独的航道，在该航道中，船舶必须规划，以便当船舶通过航道进入港口时，泊位可用。针对船舶总等待时间的最小化问题，提出了一种模拟退火算法和遗传算法。Zhen等人（2017）重点关注航道受潮汐周期影响的停泊决策。潮汐周期根据吃水深度影响船舶的各个时间窗。另一个条件规定了一次可以使用该频道的最大船舶数量。提出了一种求解该问题的列生成方法。Jia等人的研究（2018）提供了码头内有限锚地范围内的进出港船舶一览表。拉格朗日松弛启发式算法最小化了对延迟服务的惩罚和未完成服务的请求。Corry和Bierworth（2018）将航道的交通管理与泊位分配相结合，其中泊位被建模为附加航道段。该模型是基于一个并行的流动船的问题。潮汐限制被认为是这个问题的延伸。提出了求解基问题的构造性算法及其扩展。由于本文所考虑的航道没有侧线，因此没有关于航道内船舶等待时间的决定，而只是关于船舶进入时间的决定。

与上述文献所研究的水道相比，基尔运河由一系列窄段和宽段组成，船舶可以在这些宽段中等待。因此，必须对运河的不同区段做出相互依赖的船舶调度决策。Luuml;bbecke（2015）和Luuml;bbecke（2018）等人研究了相应的规划问题这些工作提供了一个基本的MIP模型，该模型描述了船舶进入时间和等待时间从一个航段到另一个航段的传播，并表明问题是N P-hard的。他们提出了一种给定恒定航速下船舶调度的标号算法，并将该算法嵌入到局部搜索和滚动视界框架中，用于求解具有24小时规划视界的大型测试实例。这些启发式方法也可以处理侧线的通行能力，尽管MIP模型中没有这一特性，本文提供的模型公式也包括侧线的通行能力、等待时间限制和速度决定，此外，还提出了一种启发式算法方法，可以处理所有这些问题的延伸。

这里考虑的问题也与在单轨上规划列车有相似之处，在单轨上，相反的列车只能在侧线或车站相遇，见Lusby等人（2011）的文献综述。在这个领域工作，如Szpigel（1973），Kraay等人（1991），克莱和哈克（1995），希金斯等人（1996），周和钟（2007），Castillo等人（2011），Lamorgese和Manino（2015）和Gafarov等人（2015）针对列车到发时间、车站停站时间等不同要求的各种设置，提出精确的启发式求解方法，双向航道的船舶交通管理不同于单线铁路调度，在一定条件下，允许对向船舶在运输区段相遇。此外，本文所考虑的特征和扩展，如船舶相关的安全距离、离散化的速度决策、侧线的容量限制和等待时间限制，仅部分包含在这些工作中，或根本不适用于这些工作。

1. 交通管理问题建模

3.1问题设置

对所考虑问题的正式描述如下。表1总结了使用的符号。基尔运河的布局示意图如图2所示。运河由23段组成，从0到22段在这里被索引。这些区段在宽的侧线和窄的运输区段之间交替。第一段和最后一段是侧线。因此，所有的侧线都有一个偶数索引号，而公交区段有一个奇数索引号。E={0，1，2...22}表示所有运河段（边）的索引集，S={0，2，4...22}表示侧线的子集，T=ES={1，3，5...21}表示运输段的子集。运河的最后一条侧线由s=22表示。每个分段sisin;E的特征是其长度ls和所谓的通过数ps。通过数反映了分段的宽度，用于确定特定尺寸的船舶是否能在分段中相遇。基尔运河的侧线sisin;s的通道数ps=12，而过境段的通道数在6到8之间。运河两端都有船闸，但中间没有船闸。运河全长约100公里。

表 1. 表示法.