列流图中列流线生成与排序优化算法

耿敬春，武建平，聂英杰，倪少权

（1.西南交通大学 交通运输与物流学院，四川 成都 610031；2.中国国家铁路集团有限公司 工程设计鉴定中心，北京 100844；3.中国铁路经济规划研究院有限公司 线路站场咨询部，北京 100844；4.中国铁路设计集团有限公司 交通运输规划研究院，天津 300308；5.西南交通大学 综合交通运输智能化国家地方联合工程实验室，四川 成都 610031；6.西南交通大学 综合交通大数据应用技术国家工程实验室，四川 成都 610031）

列流图是在铁路新建、改造项目设计中展示枢纽内各种客货列车流的种类、数量和路径的技术文件。列流图绘制主要包括图形布局和列流线铺画。其中：图形布局是枢纽内车站的空间布置，与枢纽内车站的相对位置及数量、铁路线走向和列车流走向等因素相关；列流线铺画是反映列车流（列车种类、数量）在枢纽内走向（路径）的静态指标，其铺画过程中最为关键的2 个步骤是确定列流线的走向和列流线的相对位置。

针对该问题，史峰［1］提出了列流线铺画的左右、紧凑、分层、对称和分类5 种排列原则及其遵循的先后顺序；程学庆［2-5］设计了列流路径寻找标号、列流线折点搜索、列流线偏移描绘、节点集合及边集合自动生成等算法。此外，在计算机自动绘制列流图方面［6-10］，主要从自动绘图算法的提出、计算机程序化实现等方面进行了研究探讨。这些研究成果为实现列流图计算机自动铺画提供了相关技术支持。

列流图分为客运列流图、货运列流图和客货运列流图3 种。列流图铺画的前提是根据客流分配［11］、货运量等确定列车开行方案，其中货物列车开行方案的确定过程还需先将货流折算为车流，再结合编组计划的制定将车流转化为列流。以上内容与列流图铺画工作相对独立且专业性强，需专门研究，本文不涉及。

本文针对大型枢纽内车站数量多、车站衔接方向多、列车种类多等新特点，将衔接方向的车站按经纬向进行分割，在此基础上提出列流线生成与排序优化算法，实现列流线的快速生成以及自动优化排序；基于该算法开发列流图优化编制辅助设计系统；以金华铁路枢纽为例，对算法的合理性与有效性进行验证。

1 列流图的布局与分解

为直观明了地展示枢纽内的列车种类、数量和走向，列流图中所有线条都由水平和竖直线段来描绘［1］。列流图的图形布局经过计算机程序开发后，可以很好地实现并通过人机交互随时进行修改［12］；但大型枢纽内车站衔接铁路线多，用矩形框表述车站时，同一车站的同一边可能会衔接多条线路，会给列流线的计算机自动铺画增加难度。以如图1 所示的某枢纽列流图为例进行说明（图中字母表示车站）。车站B 的左侧边衔接了车站A 和车站D，车站E 的上侧边衔接了车站B 和车站D。

为有效简化该问题，根据列流图“横平竖直”的表现形式，理论上可将整个图幅按经纬向进行分割，经纬分割线的位置和数量随铁路线的布局确定，即互相平行的2 条线路间按平行线路方向设置1 根经纬分割线。对图1 所示的列流图，按经纬向进行分割后如图2 所示。图中：红色虚线表示经纬分割线；B'，B″和E'，E″分别表示经纬向切割后，车站B 和车站E 随铁路线布局分割后得到的虚拟车站；虚线框为原车站位置。

图2 列流图经纬分割后示意图

按此方法不断分割，使得同一矩形同一边上最多只衔接1 条线路，每个矩形（虚拟车站）最多衔接4 条线路。这样一来，车站分割会大幅降低列流线铺画所涉及的处理难度；所有列流线铺画完成后，再将之前分割的车站进行合并。根据列流线表现形式，车站内一般用虚线表示，车站间一般用实线表示，而且任意相邻车站间的列流线均为平行线，故车站合并时只需将车站间的列流线由实线变为虚线。需要指出的是，以上车站的分割与合并均为算法逻辑，在应用到计算机程序开发时并不显示在用户界面上。

2 列流线生成与排序优化算法

2.1 列流线生成算法

人工梳理列流线径路时效率较低且容易出错，对于规模较大枢纽则更为不易，鉴于此种情况，提出列流线生成算法。该算法的总体思路为：列流图按经纬向分割后，生成目标车站对（某条线路两端的2 个车站组成1 个车站对）间的列车径路备选集合，继而通过人机交互方式由用户确定径路上1～2 个节点车站来最终确定列流线径路，并将其添加到列流线待铺画集合中，待下一步铺画。在进行系统开发时，还需要通过人机交互确定列流线的属性（如用不同颜色和线型表示不同的列车种类）。

列流线生成算法中最关键的步骤是目标车站对间列车径路备选集合的生成。一般来说，最简单的方式是在枢纽路网图上基于广度搜索思路进行全枚举生成，但其算法复杂度会随着枢纽规模的扩大呈指数增加。经研究发现，除个别列车会在枢纽内选择指定径路，绝大部分列车一般都会选择最短径路或者相近径路走行。由此可借鉴双重扫除算法（Double-Sweep Algorithm）［13］生成任意车站对间列车备选径路集合［14］，具体步骤如下。

步骤1：将按经纬向分割后的枢纽网络结合图论［15］进行数学抽象，将所有车站视为节点，将所有线路视为连接节点的边，形成有向网络拓扑结构，并为每条边赋权值为1，为每1 个节点编号。

步骤2：确定目标车站对间列车径路备选集合规模，即备选径路条数，记为N。

步骤3：按有向拓扑网络的邻接矩阵构造以N条径路长度为元素的目标车站对的初始向量，即

步骤4：根据步骤（3）中目标车站对的初始向量，构建初始计算矩阵V0，V0中的元素为向量并根据矩阵V0生成下三角矩阵L 和上三角矩阵U，上、下三角矩阵中的空缺元素用维度相同且元素均为极大数的向量填充。

步骤5：计算车站i 至枢纽内除该站之外所有车站的N 条最短径路长度，分别生成初始向量令其元素与矩阵V0元素一致。

步骤6：按式（2）和式（3）进行计算。

式中：r 为迭代次数。

根据式（4），可确定车站i 至车站j 的第n(n

步骤9：循环调用车站对间列车备选径路集合生成算法，得到每一车站对间的N 条备选径路，最终得到所有列车径路备选集合。

根据生成的列车径路备选集合，再结合人机交互，可确定各车站对间的列车径路，并形成列流线待铺画集合。在列流图辅助设计开发时，为减少计算机自动化编制时的无效工作，目标车站对间列车径路备选集的规模（N 值）可由用户根据实际需要提前设定。

2.2 列流线排序优化算法

列流线待铺画集合确定后，就可着手列流线的铺画工作。由于列流图是以“横平竖直”的方式进行展示，同一经纬线上不同区间内列流线的排列顺序会相互影响，不同的排列顺序就会形成不同的交叉形式，即不同的列流线布置形式，最终影响到列流图的整体布局。这是列流图绘制过程中最为关键的问题，也是难点。为有效解决这一难题，可将列流线的排序问题分解为以下2 步解决。第1 步，遍历所有区间（相邻车站构成的区间），对途径的列流线进行相对位置排序；第2 步，根据同一经纬线上各区间的相对位置排序再进行二次排序，最终确定列流线空间位置。

2.2.1 各区间内列流线相对位置排序

1）算法步骤

列流线进入区间的形式有直向进入、左转进入、右转进入、区间始发以及右向后转返回区间5 种，列流线离开区间的形式同样有直向离开、左转离开、右转离开、区间终到以及右向后转返回区间5 种，其中右向后转返回区间形式较为特殊，无论是进入区间还是离开区间都应紧贴铁路线布置，无须再与其他列流线形式进行位置排序，则任意区间内参与位置排序的列流线存在形式共计16 种，如图3 所示。图中：蓝色箭头线条表示列流线形式；G 和H 分别为某枢纽内的2 个相邻车站；黑色线条表示连接2 个车站的铁路线；水平虚线表示2 个车站的边界；橙色数字为该区间内参与位置排序的列流线存在形式编号。

图3 任意车站区间内须排序的列流线形式

在这16 种列流线存在形式中，只有区间始发且终到形式的列流线位置不会对其他区间的排序产生影响，故而在研究时可先将该种形式列流线设为自由位置，待其他列流线排序确定后，再将其按离线路及列车属性由近及远的方式进行插空，因此以下先对其余15 种列流线形式的排序问题进行研究。

针对任一区间，从列流线待铺画集合中筛选经过该区间的待铺画列流线，即将列流线径路中带有目标区间的列流线选出，并确定其在目标区间内的相对位置排序，具体步骤如下。

步骤1：初始化权重。根据列流图的绘制思路，列流线间的交叉是由于列流线在车站进行方向转变而形成，为了减少或避免交叉，当列流线向靠近线路方向转向时，列流线在区间内的相对位置排序应靠近线路；当列流线向远离线路方向转向时，列流线在区间内的相对位置排序应远离线路。据此思想以及铁路左侧行车规则，可根据进入区间和离开区间的方式，为列流线赋予一定的权重，即对右转进入区间和右转离开区间方式赋予较大权重，对左转进入区间和左转离开区间方式赋予较小权重，直向进入和直向离开方式赋予中间大小权重。

步骤2：权重值更新。列流线在目标区间的位置排序还会受到列流线途径各区间相对位置排序的影响。考虑这一影响因素，延续上述思路，沿着列流线径路向前追踪和向后追踪更新权重，具体如下。

（1）顺着列流线方向到达下一区间，根据上述方法对列流线进行权重值更新。若其他区间权重与目标区间权重为同等数量级，则会严重干扰目标区间内的排序；因此，在对下一区间权重赋值时可降1 个数量级。如目标区间权重为5，则下一区间同样形式列流线权重可赋为0.5，此时列流线在目标区间的权重更新为5.5。同理，继续顺向到再下一个区间，再降1 个数量级更新权重，直到列流线终止。

（2）逆着列流线方向回溯到达上一个区间，直到回溯到起点时终止，其权重赋值原则与顺向一致。但逆向回溯时，其方向与顺向相反，则权重的大小也应左右互换。

（3）按照上述（1）和（2）步完成目标区间每一列流线的权值更新。

步骤3：按照权重排序。将目标区间内各列流线最终权重按照降序排列，排序后权重越大的列流线越靠近线路，这样就得到了目标区间内所有列流线距离线路由近及远的相对位置。

步骤4：按步骤1—步骤3 历遍图中所有区间，确定各区间内列流线相对位置排序。

2）算法示例

为更清楚地理解上述算法，以图4 所示列流线（蓝色）所在区间DB″的权重更新为例进行说明。

图4 列流线

如图4 所示，列流线在各区间涉及进入或离开区间的方式有：区间始发、左转离开、左转进入、右转离开、右转进入以及区间终到共6 种方式。令6 种方式的权重分别为0，-4，-5，4，5和0，列流线在区间DB″的权重更新具体过程如下。

（1）在区间DB″内，列流线为右转离开区间，初始化权重为4。

（2）进行顺向追踪。追踪到下一区间B″E″，列流线离开区间方式为左转离开，降1 个数量级更新权重4.0+（-0.4）=3.6；继续顺向追踪到区间E″F，列流线终止权重为0，顺向追踪后权重更新为3.6。

（3）进行逆向回溯。回溯到上一区间DA，列流线右转进入区间，降1 个数量级且反向，权重更新为3.6+0.5=4.1，列流线在区间DA 回溯终止，逆向追踪后权重更新为4.1。

（4）在区间DB″内，列流线以权重4.1 进行相对位置排序。

同理，图4 所示列流线在区间B″E″内的权重为-3.55，在区间E″F 内的权重为-0.455。

2.2.2 同一经纬线上列流线排序

1）算法步骤

根据第1 步中得到的各区间内所有列流线的相对位置排序，进行同一经纬线上所有列流线的二次排序，即实际位置排序，具体流程如下。

步骤1：确定排序标准。将同一经纬线上各区间列流线及其相对位置排序取出，并将各区间内的相对位置作为同一经纬线上列流线2 次排序的标准。

步骤2：初始化排序方案。筛选同一经纬线上各区间所取出的列流线，删除相同列流线，并随机生成初始位置排序方案。

步骤3：排序调整。根据从左至右顺序，按照各区间内列流线相对位置顺序对同一经纬线上所涉及的列流线位置排序进行检查，若不一致则按各区间内的相对位置排序进行调换；循环往复，直到同一经纬线上的列流线位置顺序与各区间内的相对位置顺序全部一致时停止，并更新相关区间列流线实际位置。

步骤4：对同一经纬线上列流线位置进行检查，若同一根列流线靠近线路一侧的相邻位置均为空闲位置，则将该列流线整体向空闲位置移动，并循环往复，直到不存在此种情况。

步骤5：检查该经纬线上各区间是否存在区间内始发终到的列流线；如存在，则按照相对线路由近及远的顺序进行插空，并更新相关区间内列流线实际位置。

步骤6：按步骤1—步骤5 历遍所有经纬线，得到各车站区间列流线的实际位置排序。

2）算法示例

为更清楚说明，以1 个简单例子进行说明。根据列流图图形布局，同一经纬线上有2 个区间AB 和BC，区间AB 内有列流线a，b 和c，其相对位置顺序为“bac”；区间BC 内有列流线b，c，其相对位置顺序为“bc”，列流线d 在区间BC 内始发且终到，其位置为自由位置，具体如图5所示。

图5 列流线经纬向排序的初始位置

该经纬线上列流线位置排序具体步骤如下。

（1）将所有相关列流线取出进行归并、生成初始顺序，如“abc”，此时列流线d 作为自由位置不参与排序。

（2）用区间AB 内的列流线顺序对初始位置进行检查并调整，发现位置顺序一致，为“bac”，再用区间BC 内的列流线顺序对上述顺序进行检查并调整，得到“bac”。

（3）循环检查发现，该顺序与各区间的相对位置都一致，更新各区间位置，即区间AB 内的顺序为“bac”，区间BC 内的顺序为“bc”（b 与c 之间为空闲位置）。

（4）检查发现区间BC 内存在始发且终到列流线，按照相对线路由近及远顺序进行插空，得到“bdc”。

（5）最终得到区间AB 和区间BC 内的列流线排序“bac”和“bdc”，如图6 所示。

图6 列流线经纬向排序后的位置

2.3 列流图合并与调整

1）车站合并与调整

通过上述列流图的布局与分解、列流线生成算法和列流线排序优化算法，即可得到各车站区间内的列流线位置排序，但此时的列流图是按照前述“列流图的布局与分解”方法分解后的图形，因此还需要进一步合并调整。调整方法只需按照对前述的车站分割进行逆向合并即可。合并后，相应区间列流线就变成车站内列流线，但其位置排序仍保持不变。

2）列流线合并

在列流图的绘制实践中，为节省图幅空间，会将具有相同起点且初始径路区段相同的列流线，或具有相同终点且尾部径路区段相同的列流线进行合并处理，且在汇合点或分叉点予以突出显示，该需求可通过开发人机交互功能来实现。用户在绘图界面点击任一列流线时，系统需自动识别并推送具有相同起点或终点、具有相同径路区段以及相同属性的列流线并按相同径路区段长度由长至短排列；然后由用户在推送的径路中选择要合并的径路。径路合并后，对合并区段的列车数进行求和显示。

3 算法实现与案例应用

以金华铁路枢纽客运列流图铺画对前述算法进行实例应用及验证。根据规划［16］，金华铁路枢纽连接沪昆高铁、杭温铁路、金温铁路、金甬铁路、金建铁路、金台城际、金龙城际、金衢城际、沪昆铁路、金千铁路、金温货线、金台铁路，共计12 条线路；衔接杭州（东、西）、衢州、温州、建德、台州、宁波、龙泉、天台共9 个方向。随着规划线路的引入，枢纽客运系统将形成以金华站、义乌站为主要客站，金义站、金华南站为辅助客站的“2 主2 辅”客站格局。根据衔接线路所承担客流以及金华铁路枢纽客运需求［11］，金华铁路枢纽规划年度始发客车对数详见表1，枢纽衔接16 个方向间通过客车详见表2，规划年度远期客站分工及作业量［11］见表3 和表4。

表1 规划年度始发客车对数 对·日-1

表2 规划年度通过客车对数 对·日-1

表3 规划年度远期始发客车主要客站分工及作业量 对·日-1

表4 规划年度远期通过客车主要客站分工及作业量 对·日-1

根据表1—表4 中的数据，利用前述算法完成列流图的铺画，最终得到的列流图如图7 所示。

对图7 所示的列流图经人工检查，无列流径路以及数据标识错误，说明了算法的合理性；在列流图的生成过程中，列流线备选集合生成以及列流线的优化排序时间消耗均小于1 s，在实际应用中可以忽略不计，表明列流线生成与排序优化算法具有较强的高效性。

图7 规划年度客运列流图

4 结 语

随着近年来铁路的快速发展，枢纽内车站作业分工以及列流分配日益复杂，为提高列流图的铺画效率和质量，基于列流图“横平竖直”的表现形式，提出了列流线生成与排序优化算法。通过运用经纬分割线，将1 个方向上衔接多条铁路线的车站转化为1 个方向上衔接单条铁路线的多个车站，将列流线的整体排序转化为经纬向上的排序，从而化繁为简，大大提高了列流线生成与排序的效率。下一步，需要结合列车编组计划以及人工智能等新兴技术对列流图铺画进行协调联动研究。