单线铁路列车运行调整优化模型及算法

1、 第 3 期 , 单线铁 路 列 车 运 行 调 整 优 化 模 型 及 算 法 : 第 三 可 将 (1 1 式作 代 换 多 一多 一 瑞 , , , 得 到 非 负约 束 多 , 。 。而 把 (1 1 省 去 。 这样 可 简 化 模 夕。; 型 并 得 到 与标 准 线性 规 划 模 型 相 对 应 的形 式 第四 ( , I 是 一 个 特殊 的线性 规 划 模 型 , , , 与 一 般 线 性 规 划 的 不 同 之 处 在 于 洲护 。 中虽 然 包 可将 其 视 ” 含了 6 组 约 束 但不 必 全 部 满 足 只 需 满 足 其 中 一 组 即 可 , 。 (1 2 .

2、 1 一 (1 2 3 式 同 理 . 。 为 一 般 线 性 规 划 的 一 种 松 弛 形 式 目 前 尚未 见 过 这 种形 式 的模 型 不 妨 称 之为 约 束 可选择 的 线性 规 划 模 型 3 , “ 此外 如果 保证 有 , r。 : 人 , 则( 6 、 ( 7 式 的 最 后 两个 不 等 式可 省 去 。 关 于 模 型 的解 法 线 性 规 划 的算 法是 运 筹 学 中 最 为 完善 的 算 法 之 一 而 ( , I 的结 构 与 一 般 的 线性 规 划 基 本 的特 殊 结 构 , 一 致 不 同 之 处 在 于 部分 约 束 的 可选 择 性 , 。 下 面

3、 结 合模 型 ( , 。 I 讨 论 线 性规 划 的 对 偶 算法 对 于 ( , I 的可 行 性 对 偶 算 法 是从 某 个 正 则 解 开 始 在 保 证 最 优 性 不 发 生 变 化 的前提 下 。 进行 迭 代 逐 步 消 除 不 可 行 性 而 最 终 得 到 最 优 解 对于( I , , 很 容 易 得 到 一 个 正 则 解 只 要 令 各 次 列 车 均 不 停 车 通 过 中间 各 站 即可 。 : 。 从 初始 , , 正 则 解开 始 进行 使 约 束条 件 逐 步 可 行 的迭 代 , , , 对 形 如 (8 一 . (1 1 . 的 约 束 没 有选 择

4、 余 地 这 跟 3 的 约束 。 , 一 般 线 性 规 划 没 有 任 何 区 别 关 键 是 形 如 (2 一 (7 和 (1 2 , , 1 (1 2 我 们知 道 这 些 , 约 束 只 要 分 别 满 足 其 中 一 组 即 可 因 此 可 以 从 (2 开 始 根 据 对 偶 算 法 选 择 出 入 基 变量 的 原 则 进 行 选择 在 (2 一 ( 7 中选 择 可 使某 组 约 束 得 到 满 足 又 使 目 标 函 数 增 幅 最 小 的入 基 变 量 进 行 迭代 。 一 旦 使 得 某组 约 束 得到 满足 其 它 。 , 5 组 约 束 均 不 考虑 , 。 2 对

5、 (1 , . 1 (1 2 . 3 同理 。 可见 , 上 述 过 程 与 一 般 线 性 规 划 的 对 偶 算 法 是 一 样 的 如 果 问题 有 可行 解 则 最 终 一 定 能 得 到 一 个 可 行解 亦 即 最 优 解 , 由 上 述 分 析可 见 将 对 偶算 法 应 用 于 ( , , I 不 存 在 任何 障 碍 只 需 作 一 点简 单 的 技 术 处 理 , 。 。 由于 对偶 算 法 是 一 种 非 常 成 熟 的 算 法 在 此 不 作赘 述 在 实际 求 解 时 我 们注 意 到 了 ( , I 的 一 些 非 常 有 利 的性 质 并采 取 一 些有 效 的技

6、 巧 , , 。 首先 ( , I 中 的 每 个 约 束 最 多 只 有 两 个变 量 可 见 ( , I 的 约 束 矩 阵 是 非常 稀 疏 的 。 。 多年 来 求 解 线 性 规 划 的经 验 告诉 我 们 这是 一 个 非 常 有 利 的 性 质 川 (只存 非 零 元 素 , , 此 外 可 以 采 用 特 殊 的存 贮 方 法 笋 * , , 从 而 大量 压缩 存 贮 空 间 , 。 其次 在 求 解 时 把 形 如 ( , , 8 一 (1 0 , 式 ( 约 束 (1 已 代 入其 它 约 束 中 以 隐去 变 量 , (1 1 已 变 换 成非 负 约 束 的 必 然

7、约 束 排 在前 面 迭 代 时先 满 足这 些 约 束 再 考 虑 可 选 择 性 约 束 第 三 稍 作 比 较便 可发 现 约 束 ( 第 一 个 不 等式 写 成 一 。 6 式 和 ( 7 式的 唯一 不 同是 第 一 个 不 等 式 。 把( 7 式 中 x , . 一x + 过 , 。 这 样 其 变 量 系 数 正 好是 ( , 6 式 , 中 第 一 个 不 等式 变 量 系 数 的 相 反 数 , 因此 可先将 ( , 6 式 、 ( 7 式 作 为 同 一 组 约 束考 虑 当 需 要 考虑 ( 7 时 只 要 将 第 一 个 不 等式 的 变 量 系 数 改 为 负即

8、可 。 这 样 可大 大 简 化 模 型 约束( , 。 4 式 和 ( 5 式 也具 有对 称 性 可 以 采 用 同样 的方 法 处 理 , , 。 第 四 在 实 际 运 行 调 整 中 常 常采 用 客车优 先 , “ ” 、 “ 晚 点 让 正 点 等 准则 , , ” 。 在 此 对 于某 些正 。 , 点 的 旅 客 列 车 可 在 构 模 前 将 其按 图 定 运 行 线 先 固 定 下 来 这 样可 简化 模 型 要 再 作小 范 围调 整 , 。 在 求解 后 如 有 必 对 部 分 高 级 别 的 正 点 货 物 列 车 也 可 采 用 同样 方 法 这 要 视 实 际

9、情 况 而 , 铁 道 学 ” 报 “ 第 1 卷 6 ” , 定 。 对 于 个 别 特 殊 情 形 例 如 需 要 丢 一 线保 一 片 或 丢 一 片 保 一 线 等 可 以 通过调 整 相 应 的 。 , “ 目标 函 数 系 数 来 反 映 如 对 前 一 种 情 形 可 将 准备 丢 的 列 车所 对 应 的 目标 函 数 系数调 到 足 够 , “ ” 小 则 模 型 的 最优 解 自然就 反 映 了 这种 需 要 4 , 。 对 后 一 种 情 形 则 恰好 相 反 , 。 结 束语 (1 本 文 结 果 可 作 为 解 决 问 题 的 初 步 方 法 提 供 一 个优 化 的

10、 初 始 方案 作 为 结 合 其 它 因 。 , , 素 (模 型 中 未 考 虑 的 因 素 进 行适 当 调 整 的 基 础 对 于 问 题 的 圆 满 解决 尤 其 在 研 制 供 实 际 运 营 , 用 的 应 用 软 件 时 应 最 大 限 度地 采 用 有 利 于 问 题 解 决 的各 种 技 术 和 手段 包 括 先进 的 计 算机 软 , , 件 技 术 各 种 智 能化 手 段 运 营 经 验 和 人 机交 互 的 方 式 等 等 (2 , , 、 、 一 。 从理 论 上 讲 本 文给 出 的优化 模型 和 算 法很 容 易嫁 接到 双 线 区 段 上 去 并 且 会 更

11、 简 。 , 化 这 个 工 作 目前 正 在 进 行 之 中 5 参考 文 献 赵 宏 源 王叔 衡 , . 利用 计算机编制单线非追踪运行图 . 铁道运输与经济 . , 19 7 8 ; ; (1 : 6 2 : 孙 焰 李致 中 , . 单 线 区 段 货物 列 车 运 行 图 的 一 种 优 化 方 法 a 铁道 学 报 a , 19 9 1 n s 1 3 (1 0 6 , B . S z p ig e l O p t im . l t r a in . s e h e d u lin g . o n s n e i g l tr a e e n k r a il w y , Op

12、o e ra t io R e s e a r e h 2 0 (1 9 7 2 e g l 一 34 3 B in s e to n g u C he n tr a . a n d P , T . H a rk e r r Tw o m o m ts e s o t im a t i n f th e a de l y o n s 一n t r a ek ra il lin e s 、 it h h ed , e ld ffie T r a n s po ta io n S e ie n e e 24 (1 9 9 0 , 26 1 . 程 宇 孔庆 铃 程 宇 秦作睿 Ka tta . 用

13、 计算 机 编 制 列 车运 行 调 整 计 划 的 研 究 列 车 运 行 调 整 专 家系 统的 研 究 ty , . 铁道 学 报 , , 19 8 8 : ; 1 。(2 : 1 4 , . 铁道学报 I 19 2 9 n ; 4 1 (2 e a r 3 4 o G . M u r L in e a r C o m p le m e n ta r it y . In e a r a n d No i ln Pr g r a m m in g , H e l d e r m a n n , e B r in , 1 988 T H E O P T IM IZ A T IO N MO D

14、 E L A N D IT S A L G O R IT H 一 M FO R A D - JU S T IN G T R A IN D IA G R A M O N S IN G L E T R A C K R A IL L IN E S Ca T o Jia m in p o r ta t lo n g E n r a n s g . e D pt . , So er u t hw e es t J la o to n g U n iv e r s 一ty , C he n g du 610031 o A b s tr g ae t In t h is p a p n il l一 e s

15、. w e s tu dy t h e o p t im t a s o iz a t i n f t he pro g a u dj s tm e n t o o f tr a a n s a in d i g ra m o n s in - le 一 tr a e k ra W eo n e o n stru e pe e la . l lin It 15 e r e a r v e r ra m m in g m t he de l d in ea ll it t h is a s th e n li e e a r pro g n o t ra m m in g w it h y to

16、 a s e le e t a b le s e o n s t r a in t s e ifie d th a t v a r ia b le g o m o d l f a re n e e es sa r be o r t r a in g d in t h e in e a r te g se t . A ft e r d e so m o n s t r a t in t he fe w ib ilit y g e t an o e u s - in g t iv e t he a du o r a l lg . t i hm a fo , r e n e ra l lin pro g e s , r a m m in g lg o r a to lv e sta e l e t h is ted . m de l