基于序优化方法求解列车运行调整模型的算法研究概要

文章编号:1001-8360(2010 03-0001-08 基于序优化方法的列车运行调整算法研究 陈雍君, 周磊山

(北京交通大学 交通运输学院, 北京 100044

摘 要:用计算机自动编制列车运行调整方案是铁路行车调度指挥系统中的一个核心和难点问题,其目的是 保证列车能够安全、快速、正点运行。以列车旅行时间最少作为优化的目标函数,在建立复杂路网列车运行调整 模型的基础上,对其先进行快速初步的评估计算,再引入序优化理论和方法进行求解是解决列车运行调整问题的 一个新方法。详细论述了序优化方法求解算法的实现步骤,并用大秦重载铁路的一个实际算例来证明,序优化理 论能够确保以足够高的概率求取到足够好的解,尤其对于计算量大的复杂优化问题,序优化能够大大提高计算效 率,比一般的启发式算法至少可节约一个数量级的计算量,较好地满足工程实际的需要。

关键词:序优化;列车运行调整;复杂路网;列车运行时刻表 中图分类号:U292.42 文献标志码:A

Study on the Algorithmic for Train Operation Adjustment Based on Ordinal optimization

CHEN Yong-jun, ZHOU Lei-shan

(School of Traffic and Transportation, Beijing Jiaotong University, Beijing, 100044, China

Abstract: It is a core and difficult problem in railway transportation dispatch mechanism to automatically compile train operation adjustment plan with computer, which aim is to ensure safe, fast and punctual running of trains. Based on building the model of train operation adjustment under the conditions of railway netted lines, we take

minimum travel time of train as objective function of optimization, and after fast preliminary evaluation calculation on it we introduce the theory and method of Ordinal Optimization to solve it. This paper discusses in detail the implementation steps of solving algorithm by Ordinal Optimization, and use a practical calculation example of Da-qin heavy haul railway to prove that Ordinal Optimization can ensure to get good enough solution with high probability, especially for complex optimization problems with large amount of calculation Ordinal Optimization can greatly increases

computational efficiency, and it can save at least one order of magnitude of calculation amount than general heuristic algorithm, thus it can well satisfy the requirement in engineering practice.

Key words:Ordinal optimization; Train Operation Adjustment; Railway netted line; Train running timetable

随着列车运行速度的提高和运行密度的增大, 对列车运行调整的质量和效率提出 了更高的要求。 目前我国铁路正在逐步实现铁路调度指挥自动化, 研究适合铁路特点

──────────

收稿日期:2008-11-07;修回日期:2009-07-30

的列车运行调整方法,能够满足现场实际作业的需求,不单停留在理论方法的研究, 而是针对铁路调度指挥的现状, 采用切实可行的方法去解决实际问题是研究的重点之 一。

列车运行调整问题是一个高维数、 非线性混合整数目标优化问题。 国内外相关方 面的专家学者对列车运行调整算法进行了大量的研究, 也取得了丰富的成果。 线性规 划、非线性规划、混合整数规划、分枝定界法、遗传算法、拉格朗日松弛法等各种优 化方法 [1-8]都已在求解过程中得到应用。如文献 [1]研究了在给定列车出发时间和最高 旅行速度条件下的列车运行调整问题。文献 [2]对所构建的列车运

行调整满意优化模 型使用了遗传算法求解。文献 [3]把调度问题视为一个混合整数规划问题并利用分枝 定界法求解。文献 [4]枚举出所有可行的交会、越行方案,然后选择一个让列车总晚 点时分最小的方案。文献 [5]提出最早冲突优化方法,克服了组合化解冲突产生的巨 大方案数,具有较高的运行效率。文献 [6]以总延误费用为目标函数,引入启发式搜 索函数形成的一种加速算法,该方法能显著的减少搜索节点数从而提高了求解速度。 文献 [7]提出一个自动生成优化运行方案的方法,该方法使用拉格朗日松弛法将原问 题进行分解,然后利用分层方法求解每个子问题。文献 [8]构建了分层决策和滚动优 化的方法设计列车运行计划与调整模型的通用算法。 这些优化方法均致力于求解最优 规划方案, 其计算量随着规划问题规模的增大呈指数级增长。 对于大规模或超大规模 的复杂路网上的列车运行调整问题, 计算量往往难以忍受。 这是制约各种数学优化方 法广泛应用于求解复杂路网的列车调整问题的主要瓶颈。

近年来, 仿真优化方法逐渐成为研究离散事件动态系统的一种有效工具, 序优化 方法也是属于一种仿真优化。 由于列车运行调整问题涉及因素众多, 建立系统的最优 化数学模型在实际中很难做到。 众所周知, 调度优化问题, 是一个有约束的组合优化 问题, 在数学界和计算机界一直被称为 NP 难题 (Nondeterministic Polynomial Problem, 非确定型的多项式问题 。尽管目前存在众多求解 NP 问题的智能算法,如遗传算法、 模拟退火算法、蚁群算法等等,但是这些算法都是概率搜索算法,耗时比较长,满足 不了实时性要求。序优化为求解列车运行调整问题提供了一种新的思路。

1序优化方法

序优化(ordinal optimization,简称为 OO 诞生于 1992年,由哈佛大学何毓琦 教授(Y . C. Ho提出 [9],并发展成有数百篇论文的研究领域,是求解仿真优化问题 的一个重要方法, 特别是解空间异常庞大的问题。 序优化有如下两个主要的基本思想。

第一, “序”比“值”要容易比较得多(“ order ” versus “ value ” 。这与人们的 生活经验相一致。 例如, 双手各拿一个球, 只要稍微掂量一下就很容易判断出哪个球 更

重, 但若要精确判断出重多少克, 就非常困难了。 这种思想在基于仿真的优化中同 样适用。 原系统的一个计算上简单的粗糙模型虽不足以精确判断两个解之间的性能差 别是多少, 但却可以相当准确地指出两解之间孰优孰劣。 如果只想将解空间的解排序 (指出哪个解更好而不是好多少 ,那么通常粗糙模型就足够了。例如在列车运行调 整模型式①中, 一次短时间的仿真或者基于很少几条样本轨道 (甚至只有一条 的平 均值都是这样的粗糙模型。 由于粗糙模型在计算时间 (或经济成本 上与精确模型相 比有很大优势, 这为节约计算量提供了可能。 这就是序比较的思想, 是序优化第一个 基本思想。

第二,目标软化(goal softening 。在解空间异常庞大,精确求解问题的最优解 在计算量上不可行或者相当困难时, 从工程角度出发, 最终结果可以放松到 “足够好 解”即可。即找到一组足够好的解即可,未必一定要求找到最好的那一个。这对于大 规模优化问题是可行的。且由于“足够好解”的标准还可以自行定义。此时,能求得 一个“足够好解”常常就可以满足工程需要了。这就是目标软化的思想,是序优化第 二个基本思想。

反映在列车运行调整问题上可以这样理解:当列车晚点, 影响到其它列车的正常 运行; 增加或减少一列或多列列车的运行计划; 有故障发生或正常维修等情况下, 需 要调整列车运行计划或处理各种冲突时。行车调度员不必先精确的去计算列车与列 车、 列车与区间以及列车与车站之间的准确值, 再去做调整, 而是在很短时间内去调 整运行线的顺序(序比较 ,改变列车在车站的到发时间,寻找一系列最佳安排,满 足一定的约束条件,仅凭经验(足够好解疏解各种冲突,这个过程和“序优化”的 思想不谋而合。 而列车运行调整问题是属于复杂优化问题, 解空间的结构信息非常复 杂, 其大小随求解问题规模的增大而呈指数级增长。 目标函数的计算十分复杂, 计算 量也很大, 通常需要通过长时间计算, 往往很难满足列车运行调整实时性的需求。 因 此,可采用序优化方法进行求解,能很快获得“足够好解” 。 凭借以上两个重要特性, 序优化大大减少了优化求解的计算量, 在工程界得到了 广泛应用, 并获得理想结果。 下面将序优化方法应用到列车运行调整领域, 详细论述 其在复杂路网上的列车运行

调整模型的算法及其实现步骤中, 并用一个算例证明了此 方法比一般的启发式算法至少可节约一个数量级的计算量。

2 列车运行调整模型

为了更好的表示铁路路网上的列车事件 [8]和车站的拓扑结构,可以采用双层节点 图来描述。 上层节点图是以中间站、 技术站到发场和线路所为顶点, 各个顶点的连线 为边组成的图记为 (, G V E 。 下层节点图是以轨道电路绝缘节、 道岔中心、 曲线交点、 到 发 线 中 心 为 节 点 , 各 节 点 间 连 接 的 最 短 轨 道 线 路 为 边 组 成 的 图 记 为 (, , j j j G V E j V ∈,如图 1所示。

图 1:铁路路网车站下层节点拓扑图

在建立列车运行调整模型前,先定义如下符号和变量:

{|1, 2,..., }V j j n ==为 车 站 集 合 ; {(, |, }E j j j j V ′′=∈为 区 间 集 合 ; {|1, 2,..., , }j j t V v t m j V ==

∈为车站 j 下层图中的轨道电路绝缘节、道岔中心、曲线交