第 18 卷 第 6 期 2010 年 12 月
中国管理科学 Chinese Jour nal of M anagement Science
文章编号: 1003- 207( 2010) 06- 0051- 08
V ol. 18, No . 6 December , 2010
高速铁路客运网络列车开行方案优化模型
旅客列车开行方案设计是指从一个可行方案的 集合中选出既能满足运营约束又能实现运营目标的 开行方案组合, 总的目标是以客运量为基础( 即 按 流开车 ) , 在相关条件允许的情况下, 经济、合理、充 分地使用客运机车车辆和各种客运技术设备, 最大 限度地满足旅客出行需求, 方便旅客出行( 尽可能地 减少旅客换乘次数的旅行时间) , 同时要尽量减少运 营成本, 使铁路运营商收益最大化。列车开行方案 设计是铁路运输的战略计划层的重要任务, 好的旅 客列车开行方案能够提高铁路旅客运输的经营效果 和效益。
每次列车具体的承运和坐席分配数据。 本模型利用一个 OD 客流的虚拟换乘矩阵, 精
确计算 OD 客流在各个可能的换乘站的换乘情况, 同时构造了几个关联矩阵, 把每个 OD 客流在各条 换乘弧上的客流与每列可以运送该 OD 客流的列车 相关联, 不仅能够优化列车开行方案, 还能同时优化 各列车的坐席分配和中转客流, 并使客流分配与列 车开行方案相互匹配, 统一优化。
本研究和现有研究相比的主要特点和 区别如 下: ( 1) 本文提出的模型将列车开行方案、OD 客流 分配与列车坐席分配统一在一个模型中优化; ( 2) 着 眼于复杂路网的全局最优, 而不是单条线路; ( 3) 从 复杂网络多种不同始发- 到达组合、不同停站方式、 不同类型的发车备选方案集中选出最优发车方案组 合。对上述创新点还会在本文的第 2 和第 3 小节中 进一步展开论述。
我国对旅客列车开行方案的研究起步较晚, 且 定性研究多, 定量研究少; 研究单条线路开行方案的 多, 研究整个路网开行方案的少; 采用启发式搜索方 法的多, 采用数学规划模型的少。
查伟雄和符卓( 2000) [ 11] 采用定量和定 性分析 相结合的办法, 根据路网 O- D 流量, 以方便旅客出 行为目标, 将直达列车开行方案问题归结为二分图 的最大权匹配问题, 通过对初始优化方案的评价与 调整形成较为满意的结果。冯枫( 2006) [ 12] 设计了 以最大化直达运输和最小化列车虚糜为目标, 求解 旅客列车开行方案的多目标数学规划模型, 但是没 有考虑旅客换乘的影响。邓连波( 2007) [ 13] 构造了 客运专线旅客列车开行方案的双层规划模型, 在上 层规划中考虑企业收益和旅客需求, 在下层规划中 处理客流换乘选择问题, 并设计了基于模拟退火方 法的优化算法。
管理学院教授, 博士生导师, 研究方向: 大系统优化理 论与算法、收益管理优化模型
以多条客运专线为主体的 四纵四横 快速客运网。 在我国高速铁路客运大发展的今天, 凭经验制定开 行方案已经无法适应高铁客运的需求, 铁路运营和 管理的效率急待提高, 对开行方案优化的研究非常 急迫和重要。
以德国、荷兰、法国为代表的欧洲国家铁路客运 网络发达, 研究旅客列车开行方案问题起步较早, 通 常是针对旅客列车开行方案的成本、收益、直达旅客 人数、换乘次数等目标建立数学规划模型。
从模型优化的目标函数上看, 已有模型通常以 成本最小、直达旅客数最大和旅行时间最短为目标 进行优化。单一目标模型存在以下问题:
成本最小化模型虽然可以减少运营成本, 但缺 点也很明显: ( 1) 增加旅客的换乘次数造成旅客出行 不便; ( 2) 选择成本便宜但服务质量差的列车降低对 旅客的吸引力; ( 3) 可能为缩减成本而降低运能, 导 致部分旅客需求未被满足。
( 1) 模型下标 s: 车站( st at ion) , s ∀ S , S 为全部车站的集合。 e: 物理路段( edge) , 路网上相邻两车站间的轨 道, e ∀ E= { ( i , j ) | i, j ∀ S} 。 k: 列车, k ∀ K , K 为全部备选列车的集合。 l: 运输路段( leg ) , 列车每两次停车之间行走的 路径, l = ( i , j ) , i , j ∀ S。 p : O- D 需求对, p = ( o, d) , o, d ∀ S。 ( 2) 参数定义 A p : mp # np 维矩阵, p O D 需求换乘网络 的节 点( 可能的换乘站点) - 运输弧关联矩阵, 表示可以 满足该 O- D 需求的运输方式( 直达或中转) ; mp 是 p OD 需求换乘矩阵的节点数, np 是反映各种可能 换乘方案的运输弧数, 图 1 给出一个具体 OD 的例 子来演示该换乘网络网络。 该网络表示在 1- 4 节点间的 OD 运输需求, 接 点 2、3 是中转换乘节点。运输需求可通过不同运输
Schobel 等人( 2005) [ 9] 提出了一个考虑换乘成
! 52 !
中国管理科学
2010 年
本, 以乘客旅行时间最小化为目标的开行方案优化 模型, 并 用 Dant zig Wolf e 分 解 算法 求解 该 模型。 Bor ndorf e 等人( 2008) [ 10] 提出两个多目标网络流模 型, 以运营成本最小化和旅客旅行时间最小化为目 标。这两个模型中旅客可以根据旅行时间而改变旅 行路径。
图 1 实现 OD 运输的换乘网络
途径满足, 可以从 1 直达 4( 变量 x 1 4 表示直达运输
旅客数量) , 可以在 3 中转( 变量 x 13 , x 34 表示在 3 中 转量) , 也可以在 2 中转( 变量 x 12 , x 24 表示在 2 中转 量) , 最极端是分别在 2 和 3 中转两次。
Bussieck 等人( 1997) [ 1] 提出了一个以直达旅客 数最大化为目标的混合整数规划模型, 考虑的主要 约束是全部运送旅客和运能上限。
Claessens 等人( 1998, 2004, 2004, 2006) [ 2- 5] 提 出了一个在给定路网结构、客流量、开行成本、运能 约束的条件下, 以成本最小为目标的开行方案优化 模型。模型优化发车频率和所需的列车数量, 是一 个整数非线性规划模型, 给出了 5 个来自荷兰铁路 的真实算例。研究了 3 种不同停站模式下列车开行 方案的优化模型与算法。
基于上面的分析, 结合我国高速铁路及客运专 线网络的发展情况, 综合考虑客票收入、运营成本、
第6期
蓝伯雄等: 高速铁路 客运网络列车开行方案优化模型
! 53 !
直达旅客数、以及总运送旅客数, 本小节将提出运营 商收益最大化列车开行方案模型。 3 1 模型基本假设
铁路客运网络由若干车站和连接车站 的路段 ( 铁路轨道) 组成。其中车站按 照客流量分为 三个 ( 或更多) 等级, 比如: I 类站为大的始发- 终到站或 中转枢纽站, 客流量最大; II 类站客流量中等; III 类 站客流量最小。列车按照其停站情况和运行速度等 也可分为多种类型, 比如分为三类: 直达车, 中途不 停站; 快速车, 中途只停 I 类站或 II 类站; 普快车, 每 站停车或者错站停 车。列车可 以按不同的频 率发 车, 以提供和客流相符合的运能。客运网络中存在 中转客流, 即部分旅客不是通过直达客车运送, 而需 要中转换乘。
2 对已有模型的进一步分析
通过文献研究可知, 已有的列车开行方案优化 方法通常将开行方案制定和客 流分配与换乘 分离 开, 分别作为单独的问题加以研究与优化, 将客流分 配和换乘方案的结果作为开行方案优化问题的输入 数据, 两个分离问题的最优结果不一定是统一优化 问题的最优结果。
此外, 已有研究在考虑列车开行数量时通常将 客流与列车运能分别和路段相关联, 分别考虑每条 路段上必须满足的客流和每条路段上至少需要通过 的列车数量, 求解结果只能得到列车的运行频率和 路段的分段总客流流量, 无法获得具体的 OD 客流 是通过哪些列车运送的客流分配数据, 也无法得到
Chang 等人( 2000) [ 6] 建立了基于台湾高速铁路 结构的多目标( 铁路运营费用, 旅客等待时间) 整数 规划模型, 用于优化周期运行的列车开行方案。
Borndor fe 等人( 2004) [ 7] 提出了一个多货物流 模型, 能够动态的生成备选开行方案和旅客径路, 讨 论了该模 型的特点 和算法复 杂度。Bussieck 等人 ( 2004) [ 8] 提出了求解成本最小化列车开行方案模型 的整数规划和 非线性整数规划相结合 的启发式算 法。
最后, 西方国家由于人口较少, 运能充分, 所以 往往把满足全部的旅客需求作为硬性约束条件。这 类约束可能导致运能浪费, 无法适用于我国旅客需 求大, 铁路运能紧张的实际情况。在本模型中, 满足 旅客需求不作为硬性约束, 允许在运能不足或运输 不经济的情况下流失部分旅客。
3 收益最大化列车开行方案模型介绍
本模型着眼于整个客运网络中的列车开行方案 制定。可行发车方案( 即列车的型号、径路、停站) 集 合已知, 需要从中选出最优方案集合, 并确定其发车 频率。主要考虑的约束有: 客流约束、运能 分配约 束、成对发车约束、各路段通过能力约束等。
本模型优化的目标是运营商的收益最大, 包括 经济收益和公共服务效益。运营商的收益为客票收 入和成本之差, 其中成本又包括列车开行成本、运能 不足而流失旅客的惩罚成本、旅客换乘成本。模型 通过引入流失成本和换乘成本来体现铁路旅客运输 的公共服务性质, 避免出现为了降低成本而造成运 能不足或中转过多的情况。 3 2 模型参数及变量描述
蓝伯雄, 吴李知
( 清华大学经济管理学院, 北京 100084)
摘 要: 本文在分析铁路旅客列车开行方案优化 研究进展的 基础上, 提出 了一个 适合我 国铁路客 运网络 的开行 方
案优化模型。本模型综合考虑客票收入、运营成本、直达旅客数和总运送旅客数, 在保证铁 路旅客运 输公共服务 性
质的 基础上以运营商收益最大化为目标, 对全网列车的开 行方案的进行优化。利用随机生 成数据进 行的模型试 验