考虑运营费用和线性化树形改编策略的货物列车开行方案研究

王志美，林柏梁

(北京交通大学 交通运输学院，北京100044)

考虑运营费用和线性化树形改编策略的货物列车开行方案研究

王志美*，林柏梁

(北京交通大学 交通运输学院，北京100044)

国外货物列车开行方案的制定通常以车流和车列的综合费用最小为目标，而我国大多以车流的集结和改编车小时消耗最小为目标，很少考虑每个车列的运营费用，造成理论开行费用偏小，其方案未必最优.此外，我国现有开行方案模型将车流树形改编策略递归表示，不利于对不可行流的处理.鉴于此，本文对现有模型进行改造，在总目标中增加车列运营费用；在约束中引入新的决策变量，实现线性化的车流树形改编策略.设计并行禁忌搜索算法实现对模型的求解.结果表明，单位列车运营费用中的固定费用对开行方案有着重要的影响，其费用越高，总开行列数越少，列车平均运距越长，但总改编车流量增加；线性化的改编策略直观展现车流的改编路径，便于对不可行流的运输方案进行调整.

铁路运输；运营费用；并行禁忌；开行方案；树形改编策略

1 引 言

国外[1]对货物列车开行方案研究时，首先编制车组计划，而后再编制车组到车列计划，两步骤共同确立了货物列车开行方案，其开行费用包含了车流运输费用和车列运输费用.由于我国货物列车大多数为单组列车，学者和管理人员通常将货物列车编组计划等同于货物列车开行方案.而我国货物列车编组计划目标函数[2,3]通常仅考虑车流集结费用和改编费用.但实际上，车列运营费用占据了货物列车开行费用很大比例，并在客运列车开行方案优化模型中[4]有所体现.因而在货物列车开行方案的优化过程中，除需考虑上述费用外，还需考虑车组被列车牵引时的固定成本和变动成本.由文献[5]的分析可知，列车运营费用占据列车开行费用的比例很大.因此在对列车开行方案进行建模分析时，应充分考虑每一列车的运营费用，可使建立模型的计算结果更加合理，生成的列车开行方案更加符合实际.

此外，既有研究[2]的树形改编策略对并入同一个开行去向的车流递推叠加，使得约束条件和目标函数中含有高次项，增加了模型求解复杂度；同时递推表达使相同到站车流融为一体，造成并入同一去向车流的OD构成不易细分.当运输需求超出线路或站点能力时，车流的递归表达不利于对不可行流改编链的二次调整.本文借鉴文献[6]将车流的树形改编特性线性化表达的思想，应用在约束中，可直观表达每股车流的改编路径，便于对不可行流的运输方案进行调整，增强了模型求解过程中人机交互的灵活性和模型求解的可行性.

因而，本文在文献[2]的基础上，除对模型目标函数重新考虑外，也对树形改编策略的约束表达进行了改造，使得模型的求解结果更符合实际，应对不可行流等复杂问题更灵活.

2 模型的构建

2.1 模型参数

G=(N,A)——直达去向网络，N为技术站集合，A为可能的去向弧集合；

vst——发站为s到站为t的OD的车流量（车）；

u——单位列车的固定费用，为单位列车牵引机车的折旧费用和随车司乘人员及维修人员的工资费用（元）；

σ——单位列车单位公里的燃油费（元）；

dij——i→j之间的里程数（公里）；

θ——车小时与人民币的转换系数；

flowij——i→j直达去向吸引的车流量（车）；

mij——（i,j）弧上运行的单位直达列车最大编成辆数（车）；

Ti——i站开行一个直达去向的集结参数；

τi——单位车辆在技术站i进行改编的作业时间（车小时）；

η——单位车辆单位公里的磨损费用（元）；

Ci——技术站i拥有的分类线数（条）；

Ri——i站能承受的最大改编车数（车）；

ctij——区段i→j最大通过能力（车）.

2.2 决策变量

（1）车流运送方案.

（2）直达去向开行方案.

（3）列车开行频度决策变量yij≥0且为整数.当xij=1时，yij≥1；当xij=0时，yij=0.

（4）相同到站车流的树形运输决策.

（5）弧路关联变量.

2.3 约束条件

（1）改编径路唯一性约束.

式（1）表示到站为t的OD，在i站改编后，后续改编站只能选择i→t径路上其中一个技术站进行改编.

（2）车流改编站选择约束.对于i→t的车流，若在其径路上 j站改编，则必须有i→j的直达去向存在

（3）相同到站车流的树形改编链约束.

具有相同到站的车流若同时在途中某个技术站改编，那么他们的后续改编站序列应完全相同

式（1）～式（3）称之为树形改编链约束.相比文献[2]中递归表达式，其优点在于降低了模型计算的复杂度；可通过变量直接追踪车流改编链.

（4）车流改编链接续约束.即对于同一股流，其可选择的运输方案是唯一的，且改编链是连续的，保证车流能够从始发站送往终到站.

（5）直达去向吸引的车流量与列车开行频度的关联关系约束，保证所有吸引到某去向的车流必须能被全部运走.

（6）列车去向开行方案与开行频度变量的关联关系约束，在有列车去向时，列车开行频度才能大于等于1，否则为0.

（7）编组站能力约束.包括最大解编车数约束和列车去向数约束.

式（12）中左边表示i→j去向占用的股道数是该去向吸引的车流量 flowij分段函数，具体表达可参照文献[7]中5.1.3节内容.

（8）线路通过能力约束.表示区段i→j方向通过车数约束.

2.4 模型的目标函数

本文模型目标函数在文献[2]的基础上，增加了列车开行的运营费用（固定和变动费用），具体如下.

式（14）共有三部分组成，第一部分和第二部分分别为集结费用和改编费用，由于本文将车流的树形改编策略线性化表达，则模型目标函数的第二项相比于文献[2]降低了维度，即由高次项表达式变为一次项表达式，降低了模型求解的复杂度.第三部分为所有开行列车的固定费用和变动费用之和.

由于每个直达去向吸引的车流量不一定是编成辆数的整倍数，故列车变动费用用开行列数与mij的乘积表达较实际值偏大.因而可将第三项改为

2.5 不可行流的约束及求解方法

我国铁路一般在制定列车开行方案之前，提前给定车流的物理径路范围，致使需求能力大于某线路或者站点能力现象的产生，进而导致模型无解.为解决这一问题，本文引入虚拟开行方案U.形成新的目标函数.在求得的虚拟方案和利用构建的线性化树形改编策略获知每股流的运输链基础上，进一步调整不可行车流的物理径路，再次优化开行方案.该部分车流的调整策略如下：

（1）首先找出所有u＞0的去向；

（3）再次，优先将经由多个uij运送的OD流挑选出；

（4）综合考虑步骤（2）和步骤（3），将满足uij运送量OD流物理径路调整，再进一步优化计算.

3 基于并行禁忌搜索算法的模型求解

禁忌搜索算法是一种亚启发式优化算法，简称TS.它以其灵活的存储结构和相应的禁忌准则来避免迂回搜索，并通过藐视准则来赦免一些被禁忌的优良状态，进而保证多样化的有效探索以最终实现全局优化，在优化算法中独树一帜.但传统的串行禁忌算法存在求解速度慢、计算结果不稳定等缺点，本文引入并行禁忌搜索算法对问题进行了求解，获得了较优的计算结果.

3.1 算法设计

基于并行禁忌搜索算法的计算流程如图1所示.

图1 基于并行禁忌搜索算法模型求解的计算流程图Fig.1 Flowchart of Parallel tabu algorithm optimization

（1）模型编码.

本文在进行模型求解时，将列车开行频度和树形改编变量各用1位整数表示.当列车开行频度大于0时，表示存在直达去向；否则，只有改编方案，这种编码方式省略了对直达去向决策变量的编码.通过对约束分析，可知变量xisjt和 wijt有很强的关联性，当i=s，且 j在s→t的径路上，必定有，故给出变量w的解码后，不需再对x进一步解码.

对N个点构造的路网N（N-1）股OD流的运送方案编码，形成一个长度为2N（N-1）的一维整形数组，格式为

式中 yij为开行频度；wij为i→j物理径路上除i站以外的所有可能的改编站.

（2）扰动法则.

本文定义的领域结构为在给定的当前开行方案解U0基础上，任意改变一个OD对的开行频度y和变更车流可能的改编站w，其余点之间的开行状态不变.根据当前模型特点，本文设计了如下扰动策略：

（a）i,j相邻，随机取数，更改其开行频度值，需保证开行频度值始终大于等于1，并将其赋值到，此时=0；

基于初始方案和邻域结构，通过上述扰动原则生成邻域解.

（3）禁忌表.

本文设计的禁忌表如下：

(a)禁忌对象，列车开行方案；

(b)禁忌长度，3*个体数；

(c)禁忌表中禁忌对象的替换，采用先进先出的方式.

本文采用基于多禁忌搜索任务并行策略的禁忌搜索算法进行处理，禁忌表的设计考虑了多任务协作的要求，各个个体共用一个禁忌表，且实时更新禁忌表的禁忌对象，实现个体之间不重复搜索.

（4）适配置函数.

由模型的目标函数和不满足约束条件的惩罚函数值构成.

（5）终止条件.

连续100次全局最佳开行方案不更新.

3.2 算例参数设置

本文以14个技术站构成的路网作为算例路网，如图2所示.路网中技术站的相关参数取值如表1所示，各区段之间的里程如表2所示，各OD间的日均货流数据随机生成，因篇幅有限，不再罗列.

图2 以14个技术站构成的路网图Fig.2 A railway network with 14 yards

表1 14个技术站参数列表Table 1 The list of parameter values of 14 yards

表2 区段里程数据Table 2 The distances of sections between adjacent nodes

在模型的求解中，模型的其它参数取值如下：θ= 50元/车小时；mij全部取值为50车；u=3 000元/列；σ=3元/车公里；η=2元/车公里.

4 优化结果分析

以VC++6.0平台，开发适用于列车开行方案优化问题的并行禁忌搜索算法，在CPU为双核2.40GHz、内存为2GB的硬件配置的PC机上运行，获得优化方案.

为了分析固定费用变化对列车开行方案各项指标的影响，在保持其它参数值不变的前提下，分别将固定开行费用设置为0、1 000、3 000、5 000元/列进行求解，优化结果如表3所示.

表3 不同固定开行费用下开行方案的指标分析Table 3 Freight delivering stategy analysis base on different fix cost

由表3可知，随着单位列车固定开行费用增加，直达去向数逐渐增加，而总开行频度值逐渐减少.同时，由于长程直达去向数的增加，使得部分长距离车流由中转运送变为直达运送，减少了全路的改编车数.第4行数据表明单位列车的平均运距随着固定费用的增加而逐渐增加，这说明长程直达列车的开行列数占总开行列数的比例有所提高.在实际运输中，运距较短的列车在首末站的机车连挂、整备时间和费用占据其运输过程的比例相比于长距离列车较高，因而，尽可能开行长距离直达列车可增大货物在途时间所占总运输时间的比例，提高货物的运输效率.总之，考虑列车固定费用既可减少总开行列数，节省机车运用台数，又可提高货物的运输效率，提高铁路运输竞争力.

为验证本文引入的线性化树形改编策略的求解效果，将其分别在14个点和37个点构成的算例路网上求解，并与文献[2]递归表达的求解结果进行对比，如表4所示.

表4 基于ILOG的线性化树形约束与递归树形约束求解效果对比Table 4 Solution effect comparison between linearize and recursive constraint of car flow shipping strategy on ILOG platform

从表4中可看出，将树形约束线性化后，其求解速度和目标值接近最优值的程度都明显提高.进而表明，将树形约束线性化具有理论和实际意义.

为验证线性化树形改编策略在模型出行不可行流情况下的调整优势，这里进行举例说明.仍以14个点构成的路网算例为例，假定1→2线路能力不足.即运用考虑不可行流的目标函数进行求解时，发现u12＞0.所有经由1→2去向的所有OD流有：1→2、1→3、1→4、1→5，它们的流量分别为249、174、58、153；求得的 y12=10；则剩余了134车经由u12运送.1→5的车流量与134接近，可选择将1→5的车流绕道运输.由此可看出，将车流的树形改编方案线性化表达，便于因不可行流导致模型无解时，进行人工交互的解决路径调整问题，使得开行方案优化问题的求解更加灵活.

为验证本文设计的并行禁忌算法对该问题求解的可行性和高效性，分别将并行禁忌算法应用在14个点和37个点构成的算例网络上求解，它的求解效果如图3所示.

图3 基于14个点和37个点算例路网的并行禁忌搜索算法求解效率图Fig.3 The solution efficiency of parallel tabu search algorithm base on networks with 14 and 37 nodes

将图3两个算例路网的求解时间和目标分别与表4对比可看出，在小规模算例网络下，并行禁忌搜索算法能同商业软件一样很快求得全局最优解；对于较大规模算例，并行禁忌算法的求解速度明显快于ILOG，在22秒时得到的局部最优解已经比较接近全局最优解；而ILOG在连续运算3 600秒时，才求出可行解，且运算到7 200秒时，仍未找到全局最优解.因而，对于大规模问题，ILOG无法在限定的时间内给出可行解，且随着规模增加，其约束变量数指数增长，无法求得全局最优解，进而突显禁忌搜索算法在对该问题求解的高效性.

5 研究结论

本文指出固定费用是列车开行费用的重要组成部分，且对列车开行方案制定有着重要的影响.传统的列车编组计划模型未考虑单位列车的固定开行费用，使得单位列车的理论开行费用在总费用构成中所占比例相对较低，导致理论方案开行列车数、机车和人员数量较实际多；本文在模型中考虑固定开行费用，使得优化方案较之前方案延长了列车平均运距，节省了机车和人员费用开支，与实际更符.此外，将模型中的树形改编约束线性化表示，相比于递归表达式，可加快模型求解速度，并为不可行流的调整优化带来便利.本文设计的并行禁忌算法在求解速度和求解效果上优于商业求解软件，验证了求解算法的可行性和有效性.

[1] AHUJA R K,CUNHA C B,SAHIN G.Network models in railroad planning and scheduling[J].Tutorials in Operations Research,2005,1:54-101.

[2] LIN B L,WANG Z M.Optimizing the freight train connection service network of a large-scale rail system[J]. Transportation Research Part B: Methodological,2012,46(5):649-667.

[3] 陈崇双，王慈光，薛峰.货物列车编组计划国内外研究综述[J].铁道学报，2012,34(2):8-20.[CHEN C S, WANG C G,XUE F,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.]

[4] 陶思宇.客运专线网络旅客列车开行方案优化设计与调整研究[D].成都：西南交通大学,2012. [TAO S Y.Optimization and adjustment of passenger train operation scheme in passenger dedicated line network[D].Chengdu:Southwest Jiaotong University, 2012.]

[5] M H Keaton.Designing railroad operating plans:a dual adjustment method for implementing lagrangian relaxation[J].Transp.Sci.,1992,26,433-452.

[6] Armin Fugenschuh,Stefan Vigerske.Mixed-integer nonlinear problems in transportation applications[C]∕∕2nd International Conference on Engineering Optimization:2010:1-10.

[7] 牛惠民.铁路枢纽编组站作业分工整体优化的研究 [D].北京:北京交通大学.1999.[NIU H M. Optimization work division of railway hub marshalling yard[D].Beijing:Beijing Jiaotong University,1999.]

Freight Train Service Design Problem with Operation Cost and Linearization Constraints for Carflow’s Tree-shaped Classification Strategy

WANG Zhi-mei,LIN Bo-liang
（school of traffic&Transportation,Beijing jiaotong University,Beijing 100044,China）

With regard to formulating freight train operation plan,foreign countries generally take minimizing the integrated cost of traffic flow and train set as the objective.However,our country mainly focuses on minimizing the total train service accumulation cost and classification cost,rarely considering the operation cost of train set,which results that the theoretical operation cost is less than normal level and the operation plan may not be the best.Furthermore,the existing train formation plan models in our country recursively represent the traffic flow’s tree-shaped classification strategy,which is not conducive to deal with infeasible flow.In view of this situation,this paper modifies the existing models as follows:train set operation cost is added to the overall objective function and new decision variables are introduced into constraints to realize linearly representing the traffic flow’s tree-shaped classification strategy.Then,the parallel tabu search algorithm is designed to solve the proposed model.The results demonstrate that the fixed cost in unit train operation cost has a significant impact on train operation plan.The higher the fixed cost is, the smaller the total number of opening train is,the longer the average transport distance is,but the greater the total classification traffic flow is.Linearized classification strategy makes classification route of traffic flow much more intuitive so that it is easier to adjust the operation plan of infeasible traffic flow.

railway transportation;operation cost;parallel tabu search algorithm;operation plan; carflow’s tree-shaped classification strategy

2014-06-18

2014-08-20录用日期：2014-09-23

国家自然基金资助项目（U1361114）.

王志美（1984-），河南民权人，博士后. *

wzm_sxhd@163.com

1009-6744（2014）06-0126-07

U294.1

A