唐金金，杨露萍,周磊山

(1.北京交通大学 交通运输学院，北京　100044；2.中国铁道科学研究院 运输及经济研究所，北京　100081)

铁路车流组织是指确定车流在铁路网络上的运行径路、直达列车开行方案以及车流改编方案等[1]。由于铁路路网规模庞大、车站数量多、OD车流方向众多、车流和列车流繁多，使得运行径路、直达列车开行方案以及车流改编方案均非常庞大，国内外众多专家学者论证了该问题是NP-Hard问题。因此，实际铁路车流组织过程中，将铁路车流组织优化问题分解为2步，第1步是车流径路优化，第2步是货物列车编组计划优化，其中直达列车开行方案优化是其核心。文献[2]研究了铁路路网上车流径路优化的0-1规划模型及其合理径路生成算法。文献[2—11]尝试用精确算法求解列车编组计划优化编制问题，但是难以求解大规模网络问题。文献[12—13]采用模拟退火等启发式算法求解了大规模编组计划优化编制问题。然而既有列车编组计划优化编制模型和求解算法中依然存在2个难点难以克服。一是既有文献假设车流集结参数为固定值，而实际集结参数应为变量；二是在求解大规模路网的编组计划优化编制问题时，算法求解时间依然过长，难以满足铁路运输部门实际应用要求。

为此，本文将编组计划中的直达列车开行方案优化编制问题转化为网络设计中的服务网络动态配流问题。具体方法是根据所有可能的直达开行方案构建服务网络；参考道路交通中车流与能力关系的BPR函数，进一步构建路段旅行费用与车流量的关系函数，从而将车流集结参数函数化；基于服务网络动态配流算法，实现服务网络流的平衡；此时服务网络中存在车流量的方案弧则表示对应编组站间需要开行直达列车，所有需要开行的直达列车即组成优化的直达列车开行方案。以某地区铁路网络为例，验证本方法的可行性和有效性。

1　根据所有可能的直达列车开行方案构建服务网络的方法

根据所有可能的直达列车开行方案构建服务网络的核心思想：①将编组站视为服务网络节点，编组站间可开行的直达去向视为节点间有向弧，并将该有向弧作为方案弧，将该直达去向车流的集结时间和旅行时间之和作为方案弧的旅行费用；②将服务网络节点进一步分解成入流节点和出流节点，其中终到车流到达入流节点则停止，始发车流在出流节点集结，通过车流于入流节点进入并在出流节点集结，从而有效地将车站的终到、始发和通过这3种车流分离；③同一节点的入流节点至出流节点间构造1条有向弧，将该有向弧作为解体弧，供通过车流解体使用，并将车流的解体时间作为解体弧的旅行费用。

为了较好地描述该问题，选取如图1所示的包含4个编组站的铁路线路进行描述。其对应的包含全部可能直达去向的开行方案如图2所示。将这4个编组站作为服务网络的节点，将对应的直达去向作为节点间的方案弧，则可构造出如图3所示的服务网络。

图1包含4个编组站的铁路线路

图2　包含全部可能直达去向的直达列车开行方案

图3　包含所有直达去向的服务网络

将图3中的各节点进一步分为入流节点和出流节点，并在入流节点至出流节点间构造有向弧，将此有向弧作为解体弧，则构建的最终服务网络如图4所示。图4中，入流节点的编号仍采用原节点的编号，出流节点的编号采用在原节点编号的后面加“01”的形式，如铁路网中的编组站1，则其节点编号和入流节点编号均为1，而出流节点编号为101，从而便于表述节点间的关系。

图4　包含方案弧和解体弧的最终服务网络

但是，实际直达列车开行方案中不可能包含所有可能的直达去向，而是依据设定的目标函数，在所有的直达去向中选择某些直达去向，组成优化的直达列车开行方案。

2　服务网络动态配流的优化模型

定义φ(i，k)为0-1变量，表示弧k是否为编组站i对应的解体弧，若是则φ(i，k)=1， 否则φ(i，k)=0。θ(l，k)为0-1变量，表示弧k是否经由区段l，若是则θ(l，k)=1， 否则θ(l，k)=0。

定义xq，k为0-1决策变量，表示货车q是否用弧k运输，若是则xq，k=1， 否则xq，k=0。yi，j为0-1决策变量，表示i至j间是否开行直达列车，若是则yi，j=1，否则yi，j=0。

(1)

以全网络车流总旅行费用最小为目标函数，构建的服务网络动态配流优化模型为

(2)

s.t.

(3)

wi≤Wiφ(i，k)=1， ∀i，∀k

(4)

(5)

约束条件中：式(3)为区段通过能力约束，即经由区段l的所有车流量之和应不大于该区段的通过能力；式(4)为编组站改编能力约束，即需要在编组站i改编的所有车流量之和应不大于该编组站的解体能力；式(5)为编组站的编发去向数总数约束，即经由编组站i需要改编的车流方向总数应不大于该编组站规定的最大去向数。

另外，通常在直达列车开行方案优化编制模型当中，还应有车流组织方案唯一性约束，即保证每支车流都有列车将其送达前方编组站改编约束。但在本文中，由于将直达列车开行方案优化编制问题转化成了服务网络动态配流问题，这2类约束在车流分配过程中可以自动完成，无需再考虑，因此，本文方法更加简洁。

3　动态配流优化模型的求解算法

Wardrop于1952年提出了交通网络配流的2个基本原则[14]，即用户最优和系统最优。用户最优是指根据个体旅行费用最小选择最短径路，再根据最短径路进行配流；系统最优是指根据全体用户旅行费用之和最小进行配流。其他专家在后续的研究中论证了用户最优和系统最优这2个原则的合理性[15]。

本文所构建的服务网络与交通网络类似，求解动态配流优化模型的核心算法是通过仿真的方法，基于用户最优的原则进行服务网络配流，最终实现网络流量的平衡。该方法是：基于单个货车旅行费用最小选择最短径路，当所有货车实现最短径路后就完成了1次配流；由于径路上的车流量直接影响该径路的旅行费用，因此完成1次配流后，需要重新计算路段旅行费用并对所有货车进行最短径路计算，如果本次计算的货车最短径路与上一次配流过程对应的最短径路不一致，那么网络流量没有达到平衡，则以当前网络旅行费用为基础再次进行配流；通过多次迭代仿真计算，使得所有货车在路网上的旅行总费用最少，服务网络中车流量达到平衡，从而完成服务网络配流。设计的求解算法框图如图5所示。

算法过程分为2步：第1步，基于服务网络，计算任意OD车流间的最短径路，依据最短径路将车流分配到服务网络上；第2步，判断服务网络上车流是否达到平衡，如果没有达到，则继续第1步，否则，计算完成，得到最优方案。

定义算法中的参数：ε为平衡性判定参数，ε=0表示网络流量没有达到平衡，ε=1表示网络流量达到平衡；δ为当有向弧容量超出其能力时其旅行费用的提升倍数，通常设其值为δ>3。

图5　算法框图

由此设计的模型求解算法步骤如下。

输入: 铁路网G，全部OD车流量。

输出: 直达列车开行优化方案。

步骤1：初始化。

步骤1.1： 依据铁路网和所有OD车流，生成包含所有可能直达去向的初始直达列车开行方案。

步骤1.2： 依据铁路网和初始直达列车开行方案构造服务网络；设定δ值，令ε=0。

步骤1.3： 以编组站间旅行时间为旅行费用，求解任意OD车流间最短径路，实现初始配流。

步骤1.4： 如果有向弧的流量为0，则设定该有向弧的流量为0.000 1，从而避免计算中产生无穷大数。

步骤2： 动态配流优化过程。

While (ε=1)

步骤2.1： 依据式(1)计算所有有向弧的旅行费用ck。

步骤2.2： 依据式(3)判定所有区段的流量是否超出其通过能力。如果不超出，则步骤2.3；否则提高对应方案弧的旅行费用δ倍，转步骤2.3。

步骤2.3： 依据式(5)判定任意编组站i需要改编的车流方向总数是否超过其规定的最大编组去向数Mi。如果不超出，则转步骤2.4；否则提高对应解体弧的旅行费用δ倍，转步骤2.4。

步骤2.4： 依据式(4)判定所有编组站的改编车流量是否超出其改编能力。如果不超出，则转步骤2.5；否则提高对应解体弧的旅行费用δ倍，转步骤2.5。

步骤2.5： 计算所有货车在服务网络上的最短径路，根据本次最短径路进行配流。

步骤2.6： 判定所有货车在服务网络上的最短径路与上一次配流的最短径路是否全部一致，如果存在不一致，那么服务网络就没有达到平衡，则令ε=0；否则，表明网络流量平衡，令ε=1。

End while

步骤3： 得到服务网络平衡配流的结果后，抽取有流量的方案弧，生成优化的直达列车开行方案。

步骤4： 结束计算，保存数据，输出优化的直达列车开行方案。

4　实例应用

为了验证本文所提出的直达列车开行方案优化编制方法的可行性与先进性，选取文献[12]中的案例进行对比分析，该案例中的铁路网有19个编组站，如图6所示。假设编组站平均解体时间为3 h，OD车流量表与其他参数详见文献[12]。

图6　某区域铁路网

按照本文方法，依据铁路网结构和OD车流量，构建的包含方案弧和解体弧的服务网络如图7所示。

图7　包含方案弧和解体弧的服务网络

将本文提出的方法用C# 2010编程实现。在CPU为Inter Core i7 2.8 GHZ，内存为4.0 GB，操纵系统为Windows Sever 2008条件下，对上述案例进行服务网络动态配流，经过30次迭代达到网络流量的平衡，完成全部配流过程耗时58 s。得到的直达列车开行优化方案为：总旅行费用39 062车小时，共有66个直达去向，见表1和图8。由于直达去向较多，为了直观，图8中仅显示了编组站2开行的直达列车开行方案，包括2-1,2-3,

表1　优化解结果

图8　服务网络动态配流计算结果

2-4,2-5,2-8，宽的线条表示该方案弧存在车流。

文献[12]计算得到的直达列车开行优化方案为：总旅行费用45 421车小时，共有69个直达去向。对比本文的与文献[12]的计算结果可知：本文方案的总旅行费用节省11%，少开行3个直达去向，可见本文的优化效果优于文献[12]。

截止到2014年12月，全路有40个编组站[16]。可见本文选取有19个编组站的网络是有一定代表性的。

5　结　语

本文提出了利用服务网络动态配流方法解决直达列车开行方案优化编制问题。重点研究如何将直达列车开行方案优化编制问题转化为服务网络动态配流优化问题的方法，并构建了全新的服务网络动态配流模型，将直达车流集结车小时消耗与车流在各编组站内改编车小时消耗统一转化为车流在有向弧上的旅行费用。运用动态配流算法实现网络流平衡，从而得出优化的直达列车开行方案。以我国某区域铁路网为例，对比分析了基于服务网络动态配流的直达列车开行方案优化编制方法与既有方法的优劣，计算结果表明，采用本文方法能够快速、准确地得到优化的直达列车开行方案。

[1]杨浩, 何世伟. 铁路运输组织学[M].3版. 北京:中国铁道出版社, 2011: 203-244.

(YANG Hao, HE Shiwei. Transportation Organization of Railway [M].3rd ed.Beijing: China Railway Publishing House， 2011: 203-244. in Chinese)

[2]林柏梁, 朱松年,陈竹生, 等. 路网上车流径路优化的0-1规划模型及其合理径路集生成算法[J]. 铁道学报,1997,19(1): 7-12.

(LIN Boliang, ZHU Songnian, CHEN Zhusheng, et al. The 0-1 Integer Programming Model for Optimal Car Routing Problem and Algorithm for the Available Set in Rail Network [J]. Journal of the China Railway Society, 1997,19(1): 7-12. in Chinese.)

[3]HARRY N Newton，CYNTHIA Barnhart，PAMELA H Vance. Constructing Railroad Blocking Plans to Minimize Handling Costs [J]. Transportation Science, 1998, 32(4): 330-345.

[4]CYNTHIA Barnhart，HONG Jin，PAMELA H Vance. Railroad Blocking: a Network Design Application [J].Operations Research, 2000, 48(4): 603-614.

[5]RAVINDRA K Ahuja，KRISHNA C Jha，JIAN Liu. Solving Real-Life Railroad Blocking Problems [J]. Interfaces, 2007, 37(5): 404-419.

[6]彭其渊, 闫海峰, 周勇. 集装箱班列编组计划相关因素分析[J]. 中国铁道科学, 2003,24(5):120-123.

(PENG Qiyuan, YAN Haifeng, ZHOU Yong. Analysis of Factors Relevant to Formation Plan of Container Blocks [J]. China Railway Science, 2003, 24(5):120-123. in Chinese)

[7]闫海峰, 彭其渊, 谭云江. 结点站间集装箱班列开行方案的优化模型及算法[J]. 中国铁道科学, 2008, 29(1): 97-101.

(YAN Haifeng, PENG Qiyuan, TAN Yunjiang. Optimization Model and Algorithm of Block Container Trains Formation Plan between Railway Network Container Freight Stations [J]. China Railway Science, 2008, 29(1): 97-101. in Chinese)

[8]陈崇双, 王慈光, 薛锋, 等. 货物列车编组计划国内外研究综述[J]. 铁道学报, 2012, 34(2): 8-20.

(CHEN Chongshuang, WANG Ciguang, XUE Feng, et al. Survey of Optimization of Train Formation Plan at Home and Abroad [J]. Journal of the China Railway Society, 2012, 34(2): 8-20. in Chinese)

[9]史峰, 李致中, 孙焰, 等. 列车编组计划网络优化方法[J]. 铁道学报, 1994, 16(2): 74-79.

(SHI Feng, LI Zhizhong, SUN Yan, et al. A Network Optimizing Method for the Train Formation Plan [J]. Journal of the China Railway Society, 1994, 16(2): 74-79. in Chinese)

[10]王志美, 林柏梁, 陈雷, 等. 多点列车编组计划优化模型研究[J]. 中国铁道科学, 2012, 33(6):108-114.

(WANG Zhimei, LIN Boliang, CHEN Lei, et al. Research on the Optimization Model for Multi-Point Train Formation Plan [J]. China Railway Science, 2012, 33(6): 108-114. in Chinese)

[11]陈崇双, 王慈光. 分组列车优化组织理论与方法研究[J]. 中国铁道科学, 2015, 36(2):142-144.

(CHEN Chongshuang, WANG Ciguang. Research on Optimized Organization Theory and Method for Multi-Block Train [J]. China Railway Science, 2015, 36(2): 142-144. in Chinese)

[12]LIN Boliang, WANG Zhimei, JI Lijun, et al. Optimizing the Freight Train Connection Service Network of a Large-Scale Rail System [J]. Transportation Research Part B Methodological, 2012, 46(5):649-667.

[13]林柏梁, 田亚明, 王志美. 基于最远站法则的列车编组计划优化双层规划模型[J]. 中国铁道科学, 2011, 32(5):108-113.

(LIN Boliang, TIAN Yaming, WANG Zhimei. The Bi-Level Programming Model for Optimizing Train Formation Plan and Technical Station Load Distribution Based on the Remote Re-Classification Rule [J]. China Railway Science, 2011, 32(5):108-113. in Chinese)

[14]WARDROP J G. Some Theoretical Aspects of Road Traffic Research [J]. Proceeding of the Institution of Civil Engineering， 1952,1(2): 325-378.

[15]BECKMANN Martin J, MCGUIRE C B, WINSTEN Christopher B, et al. Studies in the Economics of Transportation [J]. Economic Journal, 1955, 26(12):820-821.

[16]彭开宇. 中国铁道年鉴[M]. 北京:中国铁道出版社, 2014：127-129.

(PENG Kaiyu. China Railway Yearbook[M]. Beijing: China Railway Publishing House, 2014：127-129. in Chinese)