一种启发式方法在单轨铁路上的列车路径规划和时刻表制定中的应用评估：巴西的案例研究

《Case Studies on Transport Policy》：Evaluation of a heuristic approach for train pathing and timetabling on a single-track railway: A case study in Brazil

　　

亨里克·马奎斯·德·阿劳霍|毛罗·桑帕约

巴西费伊大学工业工程系

摘要

研究目标

本研究旨在评估一种启发式方法在巴西单轨铁路上的列车路径规划和时刻表编制方面的有效性，并与目前采用的手动流程进行比较。总体目标是在现实运营约束条件下，评估基于启发式的调度方法的可行性、性能及其实际限制，同时尽量减少延误并确保列车运行的安全性。

设计/方法/途径

本研究采用了案例研究方法，将Lee和Chen（2009年）开发的启发式算法应用于一个实际运营场景，该场景涉及28列列车和15个车站。该方法结合了优化技术、启发式搜索和仿真技术，以评估其可行性和性能。

研究结果

研究结果表明，与手动方法相比，启发式方法通过减少延误和提高整体调度效率来优化了列车时刻表编制。然而，扩展的计算运行时间成为一个关键限制因素。

研究局限性

本研究仅限于巴西的一个单轨铁路段，这可能限制了研究结果的外部有效性。此外，该方法较高的计算需求需要进一步改进算法，以提高其实际应用性。

实际意义

本研究为巴西单轨铁路的列车调度优化提供了管理和政策相关的见解。启发式方法显示出提高运营效率、减少延误的潜力，并能更好地适应运营约束。通过揭示性能提升和计算限制，研究结果为决策者和交通部门提供了关于在何种条件下可以实际采用先进决策支持工具的信息。

原创性/价值

本研究填补了现有文献中的空白，现有文献主要关注多轨系统，而本研究在巴西单轨铁路的具体背景下评估了一种启发式方法。研究的创新之处在于，在现实的制度、运营和计算约束条件下对已知启发式算法进行了实证适应和压力测试，为单轨货运铁路中决策支持工具的实际应用提供了可转移的见解。

引言

铁路系统的运营规划是一项复杂的任务（Adenso-Diaz等人，2001年；Upadhyay和Bolia，2014年；Yue等人，2016年；Zhang等人，2022年；Wang等人，2023年）。在单轨铁路上，列车时刻表编制的任务是在确保准时性、安全性和遵守运营约束的前提下，尽量减少来自不同起点和终点的列车总行驶时间（Cole & Cooper，2005年）。有效的调度需要确定列车交叉和超车的最佳时间窗口和位置，以减少延误和偏离计划时刻表的情况。这必须严格遵循安全协议，包括避免碰撞和保持适当的车头时距。在单轨货运走廊中，这些决策与更广泛的运营和政策挑战密切相关，如容量利用率、服务可靠性和投资优先级，特别是在基础设施受限的铁路系统中。

大量文献（包括学术和工业研究）已经探讨了列车调度的挑战（DeHayes，1973年；Jovanovi?和Harker，1991年；Leal等人，2004年；Sauder和Westerman，1983年；Szpigel，1972年；Lee等人，2017年；Zhang和Ni，2022年），采用了各种方法论方法，如精确优化、启发式程序、元启发式算法和基于仿真的模型。然而，大多数研究集中在欧洲和北美的多轨铁路系统上。相比之下，巴西的铁路基础设施由单轨线路组成，因此需要调整和评估现有方法，以更好地反映国家运营实际情况（Wanke，2014年）。因此，关于现有的调度启发式算法在新兴经济体中的实际单轨货运铁路上的表现，目前实证证据仍然有限，这些经济体的制度、运营和基础设施约束与文献中通常假设的情况有很大不同。

为填补这一空白，本研究旨在将Lee和Chen（2009年）提出的启发式方法适应并应用于巴西单轨环境的列车路径规划和时刻表编制，并评估其在实际调度操作中的计算可行性和实际有效性。与原始模型不同，原始模型假设了两小时的无列车运行窗口，并优先考虑固定的发车间隔，而我们的改进版本引入了与当地运营实践相关的新的约束，例如消除空闲时间和对偏离期望发车时间的显式控制。这些修改使该方法更适用于巴西的实际规划操作。此外，我们使用铁路运营商提供的实际数据来配置问题实例，并在现实条件下评估算法的性能。通过这种方式，研究重点从纯粹的方法论性能转向了这种启发式方法如何与实际运营规则、管理实践和决策约束相互作用的应用评估。

以下问题指导了本研究：

•

Lee和Chen（2009）的启发式方法在单轨铁路上的列车路径规划和时刻表编制方面有多大改善作用？

•

这种启发式方法在巴西铁路系统的实际运营环境中是否具有计算可行性？

•

在时刻表效率和遵守运营限制方面，这种启发式方法是否优于铁路运营商采用的手动调度方法？

•

这种应用能为铁路规划者和政策制定者提供哪些关于先进调度工具在何种限制和条件下可以实际部署的见解？

本研究的主要目标是评估Lee和Chen（2009）提出的启发式算法在列车调度方面的计算可行性和运营效果。这是通过将其应用于巴西单轨铁路上一个繁忙路段的28列列车和15个车站的案例研究来实现的，该研究观察时间为2021年12月的高需求运营期——在此期间，调度效率至关重要。本研究的目的不是提出一个可以立即部署的决策支持工具，而是生成关于模型调整、可扩展性和实际可行性的可转移经验，以便为类似单轨货运走廊的政策讨论和运营规划提供参考。

本文的其余部分组织如下：第2节回顾了相关文献并概述了启发式方法的理论基础。第3节介绍了案例研究并讨论了计算结果。第4节讨论了研究结果在巴西案例之外的可转移性及其更广泛的政策意义。第5节总结了主要发现，并指出了未来列车时刻表研究的方向。

章节片段

理解铁路调度的层次结构

铁路公司经常依靠运筹学方法来应对与列车调度相关的复杂和多方面的挑战。如图1所示，这些挑战通常在一个顺序和层次的框架内进行处理，每个层次获得的最佳解决方案会为后续阶段的决策提供信息并对其进行约束（B?se，2011年；Schlechte，2012年；Fu等人，2015年）。铁路公司经常使用运筹学技术来

案例研究和计算结果

本案例研究调查了一个位于巴西的实际单轨铁路系统，全长约350公里，包含15个车站，从最北端的车站（车站1）延伸到最南端的车站（车站15）（见表2）。

该案例研究基于巴西单轨货运铁路的真实运营数据，其中列车流向的定向不对称性是由以出口为导向的运营所驱动的结构性特征。

这项研究能带来什么启示？

这项研究的贡献不仅在于为巴西铁路获得的特定数值结果，还在于在现实的运营和制度约束下，对现有调度启发式算法进行了调整、测试和批判性评估。

一个关键的见解是，如果在其他背景下开发的列车调度启发式算法在其基本假设得到仔细处理的情况下，它们在单轨货运走廊中仍然可以有效。

结论

本研究旨在评估和调整Lee和Chen（2009）最初提出的启发式方法，以解决巴西单轨铁路系统中的列车路径规划和调度挑战。研究重点不是提出一个可以立即部署的操作工具，而是评估调整后的启发式框架在现实运营和制度条件下的适用性、性能和限制。

CRediT作者贡献声明

亨里克·阿劳霍：撰写——原始草稿，验证，调查，形式分析，数据整理。毛罗·桑帕约：写作——审阅与编辑，监督，方法论，形式分析，概念化。

利益冲突声明

作者声明他们没有已知的可能会影响本文所述工作的竞争性财务利益或个人关系。