基于车流最佳归属算法的货物列车开行方案集中编制及优化探讨

刘洪亮

（中国铁路济南局集团有限公司 运输部，山东 济南 250001)

0 引言

全路货物列车开行方案是货物列车编组计划的重要组成部分，货物列车编组计划是全路的车流组织计划，它统一安排全路的车流组织方案，是编制列车运行图、运输方案、日班计划及改善站场布局的依据。

全路货物列车开行方案的优化是一个十分复杂的组合优化问题，需要建立对不同方案进行比较的统一计算平台，每个列车开行方案都是一个整体，在这个方案下各支车流都应算出用最少改编时间送达目的地的列车经由，对各支列车去向来讲，形成了车流最合理组合，对于所有车流总时间消耗最小的组合，即车流最佳归属。不同的列车开行方案，最合理的车流组合各不相同，需要根据列车开行方案，对每支车流确定最佳归属，为统一计算平台的系统研发提供指导和支撑。

1 技术站车流最佳归属计算方法

1.1 货物列车开行方案与车流输送的关系

全国铁路网十分复杂，首先要解决如何正确、完整地计算一个列车开行方案的经济指标，以车流组合来建模优化[1-2]。把全路车流划分到各技术站吸引的始发车流，形成几百乃至上千棵车流树[3]，可以采用化整体为分散的思想，把复杂的路网结构化成比较简单的树结构计算，从一个技术站出发，开往全路各技术站的始发车流可以用一棵有序树表示，包含在这棵树里某个开行方案的直达、直通列车作为添加的弧，构成一个无有向回路的有向图[4]。指定了一个开行方案，就能确定车流的最合理组合(称作车流最佳归属)，可结合最短径路算法(Dijkstra算法[5])构建优化模型求解。

车流树中添加弧的长度，用有向弧的箭头所指节点的改编时间t改加上直达、直通列车沿途通过技术站的中转时间t中来表示，有序树中各条弧也用箭头所指节点的t改表示弧长。无有向回路避免了绕路运输反而消耗时间短的问题，保证了计算的正确性。全路各技术站同时计算，把全路所有车流全部计算完，汇总后可以得到一个开行方案的全部技术数据，为集中编制及选优打下基础[4]。

1.2 基于动态路由数值的Dijkstra算法

初始时，记录车流最后发车站序号的路由数组m(i) = 0 (i= 1，2，…，n)，除起始节点外，所有节点到起始节点的通路长度d(vi)都记为足够大的数，d(v1) = 0。p为计算起点，从1开始。

在计算过程中，对于每一个属于待计算顶点集T内的点vi，计算经过vp到达该点的距离为d(vp)+lpi，若小于原有记录的通路长度d(vi)，则更新d(vi)为d(vp)+ lpi并更新m(i)为p。

找到属于待计算顶点集T内的点vi且d(vi)最小，最小值相同时取小的下标i，计算起点变量p更新为新的节点i值，将节点vi从待计算顶点集中剔除。重复上述流程，直到T中没有待计算节点，输出通路长度数组及路由数组，算法结束。

一个技术站始发的车流构成车流树，车流经过和到达的技术站构成树的节点，以图G(V，E)表示，E即边，实边是区段列车，虚边是直达或直通列车，在通过的技术站不改编只进行中转作业。

举一个n为15的车流树示例如图1所示。车流树n=15用实线表示，相邻节点即区段列车。边长的箭头所指车站改编时间，为简化起见，均为3 h。有8支直达、直通列车，用虚线表示。跨1个技术站，改编及中转时间为4 h；跨2个技术站，改编及中转时间为5 h。

图1 车流树示例Fig.1 Example of a traffic tree

对Dijkstra算法加了一个路由数组m，当更新路长数组d(vi)时，把计算起点p计入m(i)，m(i)保存了各支车流最后发车站的序号，本例计算结果 如 下：m(2) =1，m(3) =1，m(4) =1，m(5) =1，m(6) =3，m(7) =1，m(8) = 4，m(9) = 2，m(10) =4，m(11) = 2，m(12) = 9，m(13) = 9，m(14) = 5，m(15) = 9，m(1) = 0无意义。

1.3 车流更新迭代算法

根据路由数组m反推各支车流的输送轨迹，m(i)的值是1→i这支车流最后发车站的序号，如上例中1→15这支车流，先查m(15) = 9，表示有9→15这支列车，再查m(9) = 2，表示有2→9这支列车，查m(2) =1，表示有1→2这支列车，且已查到根节点。1→15这支车流轨迹为1→2→9→15。有了轨迹，不仅可以知道车流在哪些车站改编，还知道各列车(包括区段、直通、直达列车)吸收了哪些车流，在反推的过程中同时更新本技术站临时列车、车流信息，车流树中没有车流的通过节点，不进行迭代计算。由于列车与多棵树关联，需要全路汇总后，才能得到各支列车吸引的车流量和各技术站的改编车数。

2 全路列车开行方案集中编制及优化

车流最佳归属计算奠定全路集中计算的基础，但开行方案十分庞大，直接求解效率低。根据全路70多个路网、区域、地方性编组站的分布以及其他300多个区段站的配合，缩小选择范围，分出必选去向和待选去向[6-7]。抓重点、压任务、多比选、求优化。运用计算机进行集中编制，建立全路车流信息库，直达、直通、区段列车信息库，分“全路总任务”“技术站任务”，大约有几百个任务并行运行，有上千棵车流树同时计算。计算的方案数庞大，只能有限计算，求得较优的开行方案[8-9]。

2.1 数据结构及主要参数

主要技术参数：技术站分上下行直通中转时间t中、改编时间t改、集结车小时cm、车流量n、无改编节省时间t节、各技术站分上下行改编能力设计值N改。

车流信息库是以各技术站来建表，1个技术站吸收的本地区车流按全路技术站划分，1支车流为1条记录，分上下行填记发站、经由技术站、到站及车数，并分本站作业车，上行、下行摘挂车数，以便计算改编工作量。经由技术站按车流径路逐个填记，并设改编标记项，折角车流另加设标记。由于车流长短不一，车流记录是可变长记录。

直达、直通列车库是根据待选列车方案随时建立的，按列车分表，列车代号参照车流代号标记，首字母加“D”“T”表示直达、直通列车。表中记录吸引的车流代号及车数。列车总表记录列车代号，分上下行的发站、经由站、到站、总车数。基地直达列车库和区段列车库应单独建立，作为编组计划的重要组成部分。

通常一个技术站按衔接方向建几棵车流有序树，有的站可以合并成1棵树，为方便操作，可以构建车流编号代码，例如站名除汉字、电报码外，采用数字代号，用3位数标识。有序树以关联矩阵描述，树节点序号是连续的，也作为车流数组的下标。车流代号是发到站代号拼接起来的6位数，相同发到站不同径路的车流加标记区分。

2.2 装车基地直达列车开行方案的确定

基地直达与技术直达不同，它只吸收本基地车流，与其他车流不发生关系，当单支车流在装车基地开行直达额外消耗比沿途技术站上最小的无改编节省还要小，这支车流就可单独确定开行直达。装车基地都在重要的厂矿、港口、储运企业，大多数具备稳定的货源、较强的装车能力，加上整列配空，形成了规律性很强的骨干车流，开行基地直达既保证了国民经济发展的需要，又促进了运输指挥的有序可控，参考文献[10-12]对基地直达列车做了深入研究，这些列车不再参与开行方案的选择。装车基地还有一些车流，可归到前方技术站。基地直达列车中如果有需要中转的车流，归到基地直达列车到达技术站。

2.3 优化方法的实现过程

2.3.1 开行方案的产生及预分

以编组站分工为主，参照上年度的列车开行方案，根据计划年度运量的变化和技术设备的变化以及大型施工情况，车流径路调整以及运输组织创新要求，来确定必选列车去向，铁路局集团公司确定各技术站的待选列车去向。必选列车去向占的比例小，待选列车去向要有较大冗余。先计算一个现行方案作为参照点，得到初始目标值，以便和其他方案比较。按车站等级或能力，有比例地随机从待选列车中抽取列车与必选列车组成开行方案。

一支直达、直通列车包含在多棵车流树中，先建立列车与车流树的关联表，根据该表，把方案中的直达、直通列车预分到各车流树中，归各技术站任务处理。

2.3.2 开行方案的计算及修正

各技术站任务修改树的边长矩阵，构成无有向回路的有向图，进行车流最佳归属计算，全路总任务汇总，根据计算结果进行方案修正。方案修正分去弧计算与加弧计算(区段列车不动)。

去弧计算：判断列车方案中有无某支列车开行不利的情况，即∑nt节＜cm，去除该支列车，向相关技术站任务发送重新进行车流归属计算的信息，去除该支列车后的目标值得到优化，与该支直达列车不相关的技术站不重算。相关技术站任务计算后计算结果返回，修改数据库，全路总任务重新汇总结果。

加弧计算：全路总任务在车流信息库中查找是否存在单支车流满足充分条件而未开行直达列车，即车流表中已标识为改编，改开直达后的节省时间)。若有，取值最大的一支车流，补开直达列车，优化目标值。判定包含所加列车的相关树及技术站，发送重新进行车流归属计算的信息。相关技术站任务进行加弧计算，再返回结果，全路总任务重新汇总。自动修正时，如果加弧的去向不在待选去向中提交人工干预，以后相同问题自动处理。

2.3.3 完成方案的修正和指标计算后进入下一个方案计算

加弧计算引起车流归属的重新分配，因为每支直达列车在网络中的位置及无改编节省的数值不同，与相关的直达、直通列车既协作又竞争，所以加弧以后，原来开行的有些直达列车可能会出现开行不利的情况，于是应该重复去弧过程，进一步优化目标。再检查加弧条件，如果没有加弧的可能，该过程就停止，否则重复这个过程。计算该方案目标值，目标值达到满意指标标准则留存，继续推算其他方案。

2.3.4 技术站改编作业量的计算

在技术指标中，技术站改编作业量十分重要，能决定方案可否采用。改编作业量按到达列车统计(包括区段列车)，列车的到站一般已确定上行或下行，改编工作量不难计算。一般情况下折角车流要计算重复改编作业量，到达本站的摘挂车流中存在折角车。

存在通过不同的进站线路分别到达技术站上行和下行的情况，发站车流分2个去向集结，为了计算方便按1支列车计算车流归属，把吸引的车流分成2部分，车流库的结构已考虑这种情况，可以计算出上行及下行的改编工作量。这种情况无重复改编，发站的集结时间应加倍计算。减少改编作业量可以提高车站通过能力。

2.3.5 最终开行方案的确定

全路总任务规定至少抽取方案数，规定目标值的最大增幅与已抽取方案数相比的阈值，当小于阈值时结束计算。提供目标值较优的若干个方案的经济技术指标，包括目标值(∑nt节- ∑cm)，各技术站上下行改编车数、无调比重，技术直达、直通列车列数及平均通过技术站数，车流平均改编次数等，在经济效益、能力协调和提高、直达水平、车辆运用及可控性等方面进行综合分析比较。要兼顾区段内车流输送，相邻技术站应留足编开中间站重点作业列车的能力，解决区段通过能力因摘挂车流过大而出现的紧张问题。

经过综合比较分析以后，选择一个较优方案，适当调整，作为最终开行方案，遵循最终开行方案编制各铁路局集团公司列车编组计划。

3 货物列车编组计划优化方法有关问题说明

（1）全路总任务分成列车开行方案产生及预分、方案计算及修正、技术指标计算3个任务，有关联地并行运行。方案计算及修正任务与几百个技术站任务交替运行，相互触发，几百个技术站任务并行运行，建立触发机制确保并行任务同步，化解数据库访问冲突。技术站任务又分总任务和几个车流树并行计算任务。

（2）技术站编发能力可以控制，改编能力是否适应则要看计算结果。技术指标详细计算任务，对明显不可行方案立即淘汰。在结束阶段，对各个方案中几百个技术站的能力协调程度作模糊综合评判。货物列车不固定开行，必须考虑车流波动，列车去向吸引的车流支数多、车流量大，好控制；勉强够开行条件的列车去向，难控制。调度人员对可控性更为关切，开行方案包括几千支列车，也采用模糊评判。

（3）全路技术站划分车流进行车流最佳归属计算，可以完成全路车流计算，实现集中编制。为适应车流日常波动，铁路局集团公司编制列车编组计划时，既要保持开行去向不变，又要在编组内容上适当调整，便于实施。同时各铁路局集团公司之间要在总开行方案框架内共同商定分组列车的组织方法，进一步挖掘运输潜力。

（4）本次研究建立的信息系统属于铁路运输管理信息系统，要做好系统整合、信息共享。尤其是十分准确的货票信息对计划车流的推算有较大帮助，本系统提供的信息对全路车流组织有深远影响。

4 结束语

按全路技术站划分车流进行最佳归属计算，实现了列车开行方案的集中编制。优化货物列车开行方案是编制货物列车编组计划的关键，运用计算机进行集中计算，把必选列车去向和随机抽取的待选列车去向，组成大量的开行方案进行比选，以经由节点标识法构建车流及列车数据库，为详细计算提供依据。运用直达列车开行的充分和必要条件检查修正每个方案，实行多目标综合评价，寻找较优方案，尊重经验又不囿于经验，具有可实施性；采用车流树并行计算，当铁路网增加线路、增减技术站、调整重车流径路时，只需要修改相关车流树，具有灵便性。全路集中优化涉及许多方面，这里仅作了初步探讨，还有许多不足之处，有待于不断改进和完善。