异构铁路系统中干扰感知的动态路线优化时间规划框架

# 异构铁路系统中基于时间规划的干扰感知动态路径优化框架 来源：https://arxiv.org/html/2606.14582

[1]\fnmPollob Chandra\surRay 1]\orgdiv计算机科学与工程系，\orgname达卡工程技术大学，\orgaddress\city加济布尔，\postcode1707，\country孟加拉国

###### 摘要

高效的路径优化对于确保铁路运营的安全性和准点性至关重要。尤其在异构多轨距铁路网络中，由于列车速度、停站模式、基础设施兼容性约束各不相同，协调复杂性显著增加。在单线系统中，所有列车共享同一条轨道，需要频繁进行轨道切换，这使得挑战进一步加剧。随机扰动事件，包括轨道阻塞、列车阻塞、引擎故障和速度降低，给运营带来额外的不确定性，并导致时刻表偏离。然而，现有研究主要集中在高级别的时刻表编排上，忽略了诸如轨道切换协调等运营细节。因此，决策权留给了人工操作员，增加了铁路运营的安全风险。本研究提出了一种基于时间规划的框架，用于异构铁路系统中的动态路径优化和扰动管理。该框架使用PDDL 2.1将铁路运营形式化为一个时间规划问题，显式地对轨距兼容性约束和多种扰动场景进行建模。它生成无冲突的时间戳运营计划，指定了优化的时刻表和可执行的动作序列。为了评估所提出的框架，我们开发了一个包含200个实例的基准问题集，使用了多达1,000个轨道点和120辆列车。采用两种最先进的时间规划器和一个计划验证器来评估该框架。实验结果表明，该框架能够有效地为异构铁路系统生成时间运营计划，处理多轨距约束和扰动，并减少对人工决策的依赖。

###### 关键词：时间规划，自动规划，铁路路径优化，铁路调度，扰动感知规划，资源受限调度。

## 1. 引言

铁路是大规模运输人员和货物更高效的方式之一，比公路运营成本更低，更具能源效率，并且能够承载大宗货运[islam2024optimizing]。随着需求增长，铁路基础设施由于网络拥堵而在确保可靠和准时的服务方面面临重大挑战[bryan2007rail]。在拥堵网络中维持可靠服务需要动态路径优化和最佳时刻表，以管理线路拥挤并减少运营延误。铁路调度确定列车在每个铁路点的出发和到达时刻[kang2024critical]，而路径优化则涉及为列车寻找行驶路径以最小化行程时间并避免冲突[wang2022train]。这两者背后都有着数十年的研究，在大规模下确实难以解决，并且已知是NP-hard问题[leutwiler2023review]。

现实系统引入了额外的复杂性层次。例如，具有不同速度曲线和停站模式的异构铁路系统比统一的捷运系统需要更高程度的协调[yan2019multi]。多轨距网络通过引入多种轨道和列车轨距类型，并要求列车移动匹配轨距类型，进一步放大了这种复杂性[sanchis2021experimental]。虽然标准轨距（1435毫米）在欧洲和许多其他地区占主导地位，但一些国家运行着多轨距系统[sanchis2021experimental, su17188336]。例如，西班牙使用三种轨距类型：伊比利亚轨距（1668毫米）、标准轨距（1435毫米）以及可容纳两者的双轨距轨道[sanchis2021experimental]。例如，西班牙铁路运营三种轨道轨距：其大部分传统网络上的伊比利亚轨距（1,668毫米）、高速线路上的标准轨距（1,435毫米）以及可容纳两者的双轨距区段。同样，孟加拉国铁路运营三种轨道轨距：米轨（1,000毫米）、宽轨（1,676毫米）以及结合两者的双轨距[br2023]。实际后果是，轨距类型决定了列车在物理上可以使用的轨道。要在特定轨道上行驶列车，必须遵守轨距兼容性约束。标准轨距列车只能运行在标准或双轨距轨道上。伊比利亚轨距列车需要伊比利亚或双轨距轨道。在孟加拉国，同样的逻辑成立：米轨列车仅限于米轨或双轨距线路，宽轨列车仅限于宽轨或双轨距线路。轨距兼容性约束极大地限制了路线选择，从而增加了运营复杂性。

此外，铁路运营不断受到随机事件的干扰：轨道阻塞、列车阻塞、引擎故障、速度降低[xiu2024passenger]。这些事件会偏离铁路计划（时刻表），需要动态重新调度和路径优化以恢复运营。已有许多研究关注铁路运营的各个方面（在第2节中讨论），例如调度、扰动处理和火车站管理。然而，大多数研究只关注选定的方面。因此，它们中的大多数生成铁路计划时没有附带可执行的动作，从而将诸如道岔（轨道切换）之类的关键决策留给人工操作员，并导致安全事故[neves2024human]。例如，在2022-2023年期间，人为错误占孟加拉国铁路运营事故的50.77%[br2023]。

为了弥补这些差距，本研究提出了一种基于时间规划的异构系统铁路路径优化框架。时间规划是自动规划的一个分支，它生成带有特定时间戳的动作序列，同时最小化总运营时间[benton2012temporal]。这些时间戳精确地指明了要执行哪些动作以及何时执行，使得时间规划特别适用于铁路调度和路径优化，因为在这些场景中，精确的时间安排、协调以及列车移动的排序至关重要。现有时间规划器可以有效地处理铁路网络中固有的复杂性，因为它们采用最优搜索算法（例如，A*、IDA*）和领域无关的启发式方法。在这项工作中，我们将安全约束、轨距兼容性和道岔操作编码到一个时间规划领域中，该领域能够自动生成解决扰动所需的低级命令。我们采用PDDL 2.1（规划领域定义语言）来设计我们的模型。在这项工作中，我们还系统地设计了一个包含200个实例（100个标称实例和100个扰动实例）的基准，通过纳入多达120辆列车和100个联锁道岔，在四个类别（小型、中型、大型和特大型）中采用单调缩放。这使得本研究能够分析随着网络密度和问题扰动严重程度同时增加时，现有规划器的性能如何变化。我们使用两种最先进的时间规划器POPF[coles2011popf2]和OPTIC[benton2012temporal]来评估我们的框架和问题集。实验结果表明，两种规划器都能有效地生成无冲突的计划，统计分析证实即使在高度扰动场景下也具有可预测的扩展性。每个生成的计划都使用时间验证器VAL[VAL_1374201]进行验证，以确认动作序列一致且排序正确，从而产生可供实际部署的可执行动作序列。通过可验证的规划领域，该框架提供了一个可扩展的解决方案来增强铁路系统的安全性和效率。

### 1.1 一个示例

我们使用一个简化的铁路网络演示我们的框架如何对铁路运营进行建模并生成可执行的计划，该网络如图1所示。该网络由六个轨道点（A、B、C、D、E、F）组成，其中B和E是联锁道岔点。联锁道岔B可以连接到点C或D（当前连接到D），而联锁道岔E可以连接到C或D（当前连接到D）。该网络还包括异构的多轨距基础设施。轨道段A-B和E-F是双轨距，允许米轨和宽轨列车通行。段B-D和D-E仅支持宽轨列车，而段B-C和C-E仅支持米轨列车。车站S1位于联锁道岔B和E之间，由两个平行的站台点C和D组成，列车可能在此停靠供乘客上车。该网络中有两辆列车运行：列车T1（宽轨）和列车T2（米轨）。任务是将列车T1从A点移动到F点，并将列车T2从F点移动到A点。列车T1还需要在D点停靠2分钟供乘客上车，而列车T2需要在C点停靠3分钟供乘客上车。假设，列车T1和T2分别以1公里/分钟（60公里/小时）和1.1公里/分钟（66公里/小时）的速度行驶。道岔操作需要1分钟来切换轨道排列。

[图1：具有六个轨道点（A–F）的铁路网络。圆圈表示车站，菱形表示联锁道岔点B和E。该网络包含宽轨、米轨和双轨距（三轨）轨道。实心黑线表示宽轨轨道，细实线表示米轨轨道，双线表示双轨距轨道；虚线表示未激活的道岔分支。B和E处的弧形箭头显示了当前朝向D的道岔设置。车站S1包含点C和D。每条轨道段上都标有距离。列车T1（宽轨，60公里/小时）从A出发，列车T2（米轨，66公里/小时）从F出发]

表1：图1中铁路路径规划问题的时间计划

表1显示了一个时间运营计划，由我们提出的模型为这个简单的铁路网络问题生成。该计划指定了一系列带时间戳的动作，包括列车移动、道岔操作和乘客上车活动。每个动作由其开始时间和执行持续时间表示。例如，动作`(drive-train T1 A B BROAD)`在时间0.000开始，持续60.0，表明列车T1在时间0.000从A点出发，并在时间60.000到达B点，对应轨道段的行驶时间。标签`BROAD`将列车T1标识为宽轨，行驶通过段A–B，该轨道与T1兼容。这个简单的例子展示了生成的时间计划如何提供一个详细的运营排程，指定了协调列车移动的确切动作顺序和时间，同时尊重轨距兼容性、车站操作和道岔约束。

### 1.2 贡献

本文贡献如下：
1. 面向异构铁路的时间规划领域：我们将动态路径优化建模为一个时间规划问题，将轨距兼容性约束和不同的列车剖面直接编码到该领域中。
2. 集成扰动管理：我们将扰动管理集成到时间规划框架内，以处理以下扰动：阻塞列车、阻塞轨道、引擎故障和速度降低。
3. 一个基准问题集：我们系统地构建了一个包含200个实例的异构铁路系统基准数据集。实例从小型网络扩展到多达1,000个轨道点，遵循单调递增的进程，旨在评估所提模型和现有规划器的可扩展性和鲁棒性。

本文是我们被ICSCA 2026录用的会议论文的扩展版本。本版本通过引入额外的扰动场景、一个大规模基准问题集以及扩展的实验评估，显著扩展了工作。

### 1.3 组织

本文的其余部分组织如下。在第2节中，我们讨论文献中现有的铁路调度和优化方法。第3节提供了时间规划及其使用PDDL建模的必要背景和语义。在第4节中，我们介绍了所提出的框架，包括时间规划领域的设计和铁路规划问题的表述。接着，我们在第5节讨论实验评估和分析，并在第6节总结我们的观点。

## 2. 相关工作

研究人员提出了各种优化模型和算法来解决列车调度问题，旨在最小化延误、减少等待时间、降低运营成本，并提高系统效率和服务可靠性。这些方法可以根据基本方法论大致分类：MaxSAT、MILP、元启发式算法和自动规划。

最大可满足性（MaxSAT）公式近年来在优化复杂运营约束下的调度方面受到关注。Lemos等人[lemos2024iterative]为瑞士联邦铁路（SBB）提出了一种迭代的基于MaxSAT的框架，该框架通过重新调度、等待策略和速度调整来处理诸如轨道阻塞和速度降低等扰动，同时最小化延误和调度成本。Gouveia等人[gouveia2025maxsat]开发了一种MaxSAT公式，用于生成具有路线选择灵活性的无冲突列车时刻表，并使用SBB和华盛顿地铁系统的真实数据集进行了评估。Gouveia等人[gouveia2025maxsat]构建了一个MaxSAT公式，该公式生成无冲突的时刻表，同时保留路线选择的一定灵活性，并在SBB和华盛顿地铁的真实数据上进行了测试。尽管这些方法在其范围内生成了无冲突的时刻表方面效果良好，但它们通常只考虑同质的列车特性。然而，它们未能捕捉涉及不同停站模式、速度和轨距的异构基础设施的复杂性。此外，它们的主要重点仍然是生成无冲突的时刻表，而不是生成带有低级动作的运营计划。

混合整数线性规划（MILP）一直是铁路调度和重新调度最常用的方法。Chai等人[chai2024branch]为城市铁路构建了一个分支切割框架，在时变乘客需求下联合优化列车排序、车站时间和联挂操作。Zhuo等人[zhuo2024demand]采取了类似的以需求为驱动的角度，根据乘客负荷的变化调整时刻表和列车编组。Ji等人[ji2024optimization]开发了一个两阶段随机优化模型来处理铁路维护持续时间的的不确定性。Ji等人完全从运营角度退一步，使用两阶段随机化处理维护窗口的不确定性，当轨道工作超出计划时间时，时刻表的其余部分必须灵活调整。针对包括轨道阻塞、机车车辆故障和时刻表调整在内的扰动管理场景，已经提出了其他基于MILP和ILP的方法[acuna2011sapi, veelenturf2016railway, fischetti2017using, x