研究报告

作者与出版信息

本文的主要作者包括 A. Jamili、M.A. Shafia、S.J. Sadjadi 和 R. Tavakkoli-Moghaddam，分别来自以下机构：Mapna Co.铁路运输部门、伊朗科技大学工业工程系和德黑兰大学工程学院工业工程系。该研究发布于期刊 Engineering Applications of Artificial Intelligence，刊号25 (2012)，页码为793-800，文章发表于2012年3月20日。

研究背景与目的

本研究属于铁路运输规划领域，着重解决单轨铁路的时刻表优化问题。本问题是铁路领域中极具挑战性的问题之一，其复杂性源于优化列车运行时间与避免延误之间的平衡。具体而言，本文旨在利用数学建模和混合元启发式算法解决单轨周期列车调度问题（Single-Track Periodic Train Scheduling Problem, SPTS）。

周期列车调度的核心问题是为单轨铁路上的列车到站及出发时间编排一个满足安全约束条件的周期性时刻表。传统的目标函数是最小化列车的总延误时间，但其他目标（例如降低燃料消耗或优化工作人员工作时间）也可以纳入考量。

背景知识方面，本领域之前的研究包括数学模型的开发、启发式或元启发式算法的应用，以及进一步的参数优化以提升计算效率。然而，之前的模型在解决大规模问题时受到计算复杂度的制约。本研究创新性提出了一种将模拟退火算法（Simulated Annealing, SA）与粒子群优化算法（Particle Swarm Optimization, PSO）相结合的混合算法，为解决大规模铁路时刻表问题提供了更高效的手段。

研究的主要目的是提出一个基于周期事件调度问题（Periodic Event Scheduling Problem, PESP）的方法，结合混合元启发式算法，为伊朗德黑兰至伊斯法罕铁路提供优化的列车时刻表。

研究流程与方法

研究流程概述

本研究主要包括以下几个部分： 1. 问题建模：基于PESP方法的数学表达。 2. 算法开发：设计混合PSO-SA算法。 3. 实验与验证：利用数值案例和实际案例对算法进行验证。

具体工作流程

（1）问题建模

PESP由Serafini和Ukovich首次提出，核心是对一系列周期性事件（如到站和出发）进行建模，使其满足固定时间周期的多种约束条件。其数学模型的输入包括： - 事件集合和活动图； - 每对事件之间的时间上下界； - 每列车通过区间所需的时间，以及出发时间的允许区间。

在SPTS模型中，列车到站和出发被定义为事件。为了确保列车在单轨线路上的安全行驶，引入了严格的相邻列车间隔约束。此外，模型目标为最小化列车在所有区段上的经过时间加权和。

数学模型中使用作业车间调度问题（Job Shop Scheduling Problem, JSP）的格式： - 目标函数为最小化列车通过区段的加权时间。 - 约束条件包括列车间的优先关系、区段内的单列通过限制及列车出发时间上下界。

（2）混合算法的开发

在算法设计阶段，PSO和SA被有机结合： - 粒子群优化算法（PSO）：模拟鸟群寻找食物的行为。每个”粒子”代表一个候选解，根据全局最优解和自身最优解动态调整位置和速度。 - 模拟退火算法（SA）：模拟固体退火过程，通过接受次优解避免陷入局部最优。SA的关键参数包括初始温度、冷却率和迭代次数。

混合算法的设计包含两阶段： 1. 初始化：首先通过随机生成多个初始解，并用SA算法优化个体粒子； 2. 动态更新：在每次迭代中，以PSO的全局搜索能力结合SA的局部优化能力，寻找最佳解。

特别的，随机密钥法（Random Keys）用于列车优先级的编码，允许通过序列化的随机数确定列车通过区段的顺序。此外，通过实验设计方法（设计因子分析），对多个算法超参数（如温度、冷却率等）进行了调优。

（3）实验设计与数据分析

研究进行了多个案例测试，包括随机生成的小规模问题和德黑兰-伊斯法罕铁路的实际案例分析。测试中，比较了以下几种算法的性能： - 混合PSO-SA算法； - 单独的SA算法； - 基于分支定界法的确切算法。

实验数据的分析评价算法的效率和解的质量。

研究主要结果

• 数值实验表明，混合PSO-SA算法的表现优于单独的SA算法和传统分支定界算法，在解质量和计算时间上获得了显著的改进。
• 与单独使用SA算法相比，混合算法在解的优化程度上平均提高了约3%，并且能够在6.5分钟内解决较大规模问题，而分支定界法需要超过1小时且规模受限。
• 在德黑兰-伊斯法罕铁路案例中，研究成功生成了基于360分钟周期的优化列车时刻表，其总列车加权延迟大幅减少。

具体而言，在实际案例中优化了8趟列车的出发和行驶时间，确保所有列车在安全约束条件下按时运行。结果表明，增加发车时间的灵活性（即出发时间容忍区间的设置）有助于改进最终结果。

研究结论与价值

• 科学价值：该研究提出了一个新的混合元启发式算法框架，为周期性列车调度问题提供了高效的求解方法。此方法对解决大规模单轨调度问题具有普适性。
• 应用价值：研究结果为铁路运营提供了可靠的工具，能显著减少列车延误，提高乘客满意度，并优化铁路运营资源。

此外，研究还首次在伊朗实际铁路线路上进行了验证，为其他国家和地区的铁路调度提供了实践参考。

研究亮点

1. 理论上的创新性——结合PESP数学建模与SA、PSO混合优化算法。
2. 实用性的体现——在实际铁路案例中证明了算法的有效性和可实现性。
3. 高效性——能在合理时间内解决复杂问题，其中算法参数的优化起到了核心作用。

展望与推荐

未来研究可进一步探索以下方向： 1. 在不确定环境下的列车时刻表优化； 2. 尝试其他元启发式算法，如遗传算法或人工蜂群算法； 3. 引入更多优化目标，例如推动低碳铁路运输。

总体而言，本研究有效解决了周期单轨铁路调度的核心问题，这一方法值得在更广泛的交通调度场景中推广应用。