基于区域阈值的铁路空车调配算法研究

金福才

（中国铁道科学研究院集团有限公司电子计算技术研究所 北京100081）

基金项目：中国铁路总公司科技研究开发计划课题（2017X009-B，2017X009-C）。

摘要：空车调配是铁路运输调度中的重要工作内容，良好的空车调配计划不仅能提高车辆使用效率，而且对增加货运量、保障货物运输时限具有重要影响。调度工作中的空车调配是一个动态的工作过程，存在多种不确定因素。本文将路网划分为若干调空区域，设计基于区域阈值的空车调配模型与求解算法。基于该方法开发的空车调配系统支持定时计算和实时计算，能有效支撑调度工作中的空车调配计算需求。

关键词：铁路运输；空车调配；模型；阈值；算法

Study on Railway Empty Wagon Distribution Algorithm Based on the Demand Threshold of Regions

Jin Fucai

(Institute of Computing Technologies， China Academy of Railway Sciences Corporation Limited， Beijing 100081)

Abstract: The empty wagon distribution is an important working content of railway dispatchers， a good empty car distribution plan can not only improve the working efficiency of wagons， but also have important influence on increasing the volume of freight and insuring cargos＇ shipping time. The empty wagon distribution calculation of railway dispatching is a dynamic working process for existing some uncertain factors . The railway network is divided into several regions， and the model and the algorithm for empty car distribution are designed based on the demand threshold of regions. The empty car distribution system has developed based on the algorithm. the system can calculate empty car distribution plan at an appointed time or at any time， which can effectively meet needs of railway dispatchers when they make empty car distribution plan.

Keywords: Railway Transport， Empty Wagon Distribution， Model， Threshold， Algorithm

1 引言

铁路是国家重要的基础设施，是国民经济的大动脉。铁路在合同约定时间内将货物送达至目的地，既是对货主的承诺，也是铁路内部调度管理的要求。要提升铁路货运物流服务质量、提高路网车流周转效率，离不开高效的空车调配。

空车调配问题历来被研究铁路运输的学者所关注。现有研究铁路空车调配问题基本从两个层面进行：第一个层面是不考虑具体空车需求，满足远期的预期货运需求的空车调配计划的制定方法；第二个层面是考虑具体的空车需求，满足近期的特定货物装车时间窗限制的空车调配计划的制定方法。国外在第一个层面的研究如文献[1][2]等，在第二个层面的研究如文献[3～5]等。国内在第一个层面的研究如文献[6][7]等，在第二个层面的研究有代表性的为文献[8][9]等。国外铁路运输能力一般富裕，空车通常根据货主需求的时间和车型进行调配，空车调配目标是节约空车走行距离成本。国内空车调配问题的研究侧重于假设一些确定的因素，如有确定的空车需求和供给站，有确定的装车时间范围等，这些因素很难获取，使得研究的方法很难在现场得到应用。铁路运输是一个持续的过程，车辆是不断运行的，状态也是不断变化的。为消除路网车流持续变化的影响，本文设计了基于区域阈值的空车调配算法，该方法既考虑了路网状况变化情况，又兼顾了路网车流变动情况。

2 空车调配问题分析

2.1 调配过程分析

铁路运输货物时，先要将货物装在车辆上，编成列车后进行运输，货物到站后卸车，然后将货物移交给收货人。当车站的装车数小于到达卸空车数时，就会出现从卸空车站向装车站之间的空车转移运输，这就是空车调配。

现有空车调配为总公司级和铁路局级两级调度员配合完成。总公司负责铁路局间空车调配，铁路局负责局管内空车调配。空车调配时先进行局内调配，方法是将空车分为本局卸空车和外局调入空车，根据局间车流交换数据，确定铁路局分界口接入的空车数量，结合本局内的卸车情况和请车情况得到本局空车需求，然后将分界站的空车向该装车地输送，如果铁路局的空车有富余，则沿排空方向将空车调配给邻局分界口。确定好分界口空车后，将该方案作为初始方案上报总公司，总公司根据近期全路货源情况在初始方案上进行调整，以保证未来一段时间重点地区装车任务的完成。调整配空计划制定后下达给路局，此时铁路局再新的分界口交接计划，重新编制本局内的空车调配计划。

空车调配与重车运输不同，空车在没有明确装车站和装运货物时，并没有固定到站，只是按照预期的排空方向输送。由于真实的货物运输需求很难提前掌握，铁路须预测需求并提前管理空车。空车调配虽不直接产生运输收益，但对及时满足客户的货物运输需求、均衡路网运力具有重要意义。

2.2 调配过程的不确定性

空车调配受货运需求变化、重车分布、机车运用情况等因素影响，这些因素很难被准确预测，原因是它们存在很强的不确定性。

（1）空车装车需求的不确定性

空车调配的主要原因是空车需求（货物运输需求）和空车供应之间的不平衡。因此，空车需求和供应的不确定性就决定了空车调配的不确定性。主要表现在：①空车需求和供应产生地点的不确定性；②空车需求和供应数量的不确定性；③空车需求和供应时间的不确定性。

（2）有效空车数据的不确定性

空车来源既有分界站调配的空车，也有本局内的卸空空车，而本局内的空车如果能在当日装车，通常称为有效空车。有效空车数的确定需要卸车计划执行完美，卸车受到天气、器械、作业人员的影响，这些都是不确定因素。

（3）空车走行所需时间的不确定性

在实际空车调配过程中，为保证货主运输需求的顺利实现，不仅需要满足空车数量上的需求，而且还要满足空车准时到达的需求，空车走行时间与铁路运输组织过程相关。如果原计划的空车不能按时到达，则需要就近调剂空车，调整原来的空车调配计划。

3 基于区域阈值的空车调配模型

3.1 基本思想

货车使用周期是从货主发出请求开始，铁路必须预测货运需求才能提前管理空车，而空车需求难以确定，可以设置一定的阈值范围来消除此不确定性。

首先将全路路网划分为若干空车集结区，划分依据可以根据管辖范围，也可以根据具体车流组织需要。以划定的集结区为单位，结合历史和近期的运输需求变化情况，计算未来时间内每个车种的空车需求的上限值和下限值。这个数值范围就是区域空车阈值，阈值可以根据经验设定，也可以从历史数据分析中得到。

每个集结区要选出一个代表车站，空车区域阈值以空车代表站参加计算。当供给超过阈值上限时，就要向其他缺少空车的区域调配；反之，则就要从多余空车的区域补入。利用此方法，不仅可以减少空车需求不确定性的影响，也可以避免基于当前列车或车辆追踪位置推算出空车供给数量实时变化的影响。

3.2 调配模型

按照上述思想，依据追踪列车的当前位置数据和车站上板的车辆站存数据可以追踪到车辆当前位置，从而计算出未来时间段内该区域某车种的空车供给，并与区域空车设置阈值进行比较。低于阈值下限表明本区域需调入空车，高于阈值上限表明本区域需调出空车，如果正好在阈值范围内，则表示本区域不参与空车调配。当空车区域间结束调配后，需判断每个区域内空车分布是否合理，并且根据重车分布状况以及卸空车状况进行区域内 调整。

基于区域阈值的空车调配算法模型可以用图 1 表示。每次空车计算时都要按此流程图计算一次，区域间调整数据可以计算铁路局间分界口的空车调配计划。区域内调整可以计算铁路局内的空车调配计划。

4 空车调配算法实现

4.1 空车调配计算步骤

基于区域阈值的调配方法主要包括以下6个计算步骤。

第1步：确定调配时间内的空车需求。

计算方法是根据最近一段时间的历史数据计算得出本区域的空车需求上限和下限，得到区域的阈值。

第2步：确定调配时间内的空车来源。

依据追踪车辆当前位置，计算得到未来车辆的所在位置和空重状态[10]，从而确定调配时间段内的有效空车数量。

第3步：优先计算特殊需求空车调配方案。

以下三类空车按以下方法优先计算：

① 空车自备车：如有回空货票数据，则按重车处理，否则按普通空车对待。

② 调配时间段内卸后可以在本站装车的空车：优先直接在本站装车，不参加计算。

③ 对于回空有特殊需求的空车，按指定到站和指定径路回空进行计算。

对于上述空车的调配结果，依次核减第 1 步内的空车需求，如果空车经过分界口则计入分界口通过空车数量。调配时间段内的剩余空车继续计算。

第4步：得到参加计算的空车数，步骤如下。

① 依据空车管理需求设定空车区域，此区域要小于铁路局管辖范围，通过设定更细致的区域和空车集结站，才能使分界站计算结果更准确。

② 依据当前重车推算结果，计算调配时间段空车分布和数量，作为空车的供给量。

③ 根据各区域修正后的阈值，确定空车的需求数量。

④ 进行调配数处理，将各区域的供给量和需求数量进行比较，超过阈值上限的作为空车供给点，小于阈值下限的则作为空车需求点。将有效卸车数与空车需求阈值进行比较：当有效卸车数大于阈值上限，则该区域应该调配出空车，空车调出数=有效卸车数-阈值上限；当有效卸车数小于阈值下限，则该区域应该调配进空车，空车调入数=阈值下限-有效卸车数；当有效空车数小于等于阈值上限，大于等于阈值下限，则此区域不参加调配。

第5步：铁路局间空车调配计算。

第6步：铁路局内空车调配计算。

4.2 运输问题模型与求解算法

由于求解运输问题的单纯型算法[11]具有优化效果好、计算迅速的特点，因此采用此方法计算上述第5步和第6步。由于第1步和第2步已经确定了区域内的空车供给与需求，因此假设：有m个空车供给点和n个空车需求点，空车供给点Ai的可供给空车数量为ai(i=1，2，…，m)，空车需求点Bj的需要空车数量bj(j=1，2，…，n)，从第i个空车供给点向第 j个空车需求点运输每单位物资的运价为Cij。此时成为由多个供给点供应多个需求点的空车调配运输问题，建立数学模型如下：

模型的目标是使总运费达到最小。

a i和bj满足：当时，表示供需平衡条件；当时，表示供给小于需求的运输问题；当时，表示供给大于需求的运输问题。求解供需不平衡运输问题时可以考虑增加虚拟供给点或需求点将其转换为产销平衡的运输问题。

空车调配运输问题在供需平衡时可以采用表上作业法求解，步骤如下。

（1）找到初始解

在计算过程中，用表上作业法确定初始解时，可以采用最小元素法，即以就近供应的思想，从单位运价表的最小运价开始确定产销关系，直到给出基本方案为止。

（2）判断解是否为优

在得到初始可行解之后就要用检验数判断其是否满足最优，计算非基变量的检验数采用伏格尔法，即对于特定的调运方案的每一行给出一个因子u（i 称为行位势），每一列给出一个因子vj（称为列位势），使对于目前解的每一个基变量xij有cij =ui+vj，这里的ui和vj可正、可负，也可以为 0。那么任一非基变量xij的检验数就是σij =cij-(ui+vj)，如果检验数均大于0则满足最优条件，算法停止，如果存在某非基变量检验数σij ＜0，则进行迭代调整。

（3）解的持续优化改进

在负检验数中找出最小的检验数，该检验数所对应的变量即为入基变量。寻找入基变量对应位置的闭回路，即在已给出的调运方案的运输表上从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有遇到代表基变量的填入数字的格才能向左或右转90度（也可以不改变方向）继续前进，这样继续下去，直至回到出发时的空格，由此形成的封闭折线称为闭合回路。

一个空格存在唯一的闭回路。在入基变量所处的闭合回路上，赋予入基变量最大的增量，同时将闭回路上的其他运量进行相应的调整，即可完成方案迭代，对迭代的方案继续验证是否满足最优，执行上述步骤直到得到最优解。

4.3 铁路局间空车调配计算

计算步骤如下。

① 判定各铁路局分界口剩余通过能力，如果剩余通过能力为0，则关闭这些铁路局分界口，设置该分界口距离为无穷大，重新进行运输距离计算。

② 运用4.2节的方法计算区域间调配的最优解。

③ 将区域内调配结果以铁路局为单位进行汇总，作为路局间的空车调配数量，将调配结果写入路局间空车调配结果表。

④ 将调配方案中解析运输径路中通过的铁路局分界站，然后将分界站通过的空车数进行累加，得到分界站空车调配数值。

⑤ 如果空车调配值超过分界站通过能力，则分出超过分界站通过能力数值的OD（起始-终到）对，返回1步。对于未超过分界站通过能力的OD对，直接记录在调配表中；当所有分界站能力都满足时，进行下一步。

⑥ 统计局间分界站的调配数及来源OD对，算法结束。

4.4 铁路局内空车调配计算

计算步骤如下。

① 根据区域间分界口推算结果，将空车推算结果累计在区域间分界口上。如果是接入空车，则增加分界口车站空车供给；如果是排出空车，则增加分界口车站空车需求。

② 运用4.2节的方法进行空车调配的计算，计算得到区域内空车最优调配方案。

③ 将运算结果写入路局内空车调配结果表。

④ 根据OD对，统计局内各站间的调配数，算法结束。

5. 结语

为解决空车调配时所出现的各种不确定性，在将路网划分若干调空区域的基础上，设计了基于区域阈值的空车调配算法，开发了相应的空车调配系统。该系统可以每日定时计算次日铁路局间空车调配方案，也可以实时计算局管内空车调配方案。该算法计算效率高，可以结合当前路网的车辆分布情况，有效消除空车需求的不确定性，支持频繁计算并能不断优化计算结果。

参考文献：

［1］MISRA S C. Linear Programming of Empty Wagon Disposition［J］.Rail Internat. 3，151-158（1972）.

［2］AVI-ITZHAK B，BENN B A，POWELL B A. Car Pool Systems in Railroad Transportation：Mathematical Models［J］. Management Sci， 1967， 13：694-711.

［3］RATCLIFFE L L，VINOD B，SPARROW F T.Optimal Prepositioning of Empty Freight Cars［J］.Simulation，1984， 42：269-275（1984）.

［4］SPIECKERMANN S，VOSS S.A Case Study in Empty Railcar Distribution［J］.Eur. J. Operational Res，1995，87：586-598.

［5］HOLMBERG K，JOBORN M，LUNDGREN J T. Improved Empty Freight Car Distribution［J］.Transp. Sci，1998，32：163-173.

［6］果鹏文，林柏梁，余洋.大规模路网上空车调配的区段中心优化法［J］.中国铁道科学，2001，4：122-128.

［7］金福才，王长群，张强，王启东. 路网空车调整系统的设计与实现［J］.铁路计算机应用，2008，11：1-3.

［8］王龙，马建军，林柏梁，等. 全路空车动态调配及路网分界口排空流量测算方法［J］.铁道学报.2015，06：1-9.

［9］张红斌，董宝田，孙远运. 基于能力约束的多车种空车动态调整方法［J］.北京交通大学学报，2016，6：50-56.

［10］金福才，朱涛.铁路运输数据集中下的重车推算方法分析. 第十届中国智能运输学会论文集［M］.北京：电子工业出版社，2015.

［11］胡运权.运筹学教程［M］.北京：清华大学出版社，2012.