基于遗传算法的高铁列车运行图结构优化研究

袁才清

摘 要：本文以2015年京沪高速铁路数据进行实例验证，建立列车运行图结构的优化方案。计算结果表明：原方案开行39列列车最少需628 min，优化方案的开行时间比原方案的开行时间减少了133 min，约21.2%，能更好地满足高峰时段的客流要求以及车站突发性客流增加时需尽快密集发车的要求。

关键词：列车运行图;高速铁路列车;通过能力;遗传算法

1 高速铁路列车运行图参数描述

设高速铁路某线路上的车站集为，为上行方向（或下行方向）列车从线路区段始发站到终到站依次经过的车站，为线路上的车站总数。线路上的列车集为，线路上的列车数为。对于列车在车站只有停与不停两种情况，用0-1变量描述：

表示列车的停站序列。表示高速列车在站的停站时分，表示不停站直达列车的旅行时分，表示起车附加时分，表示停车附加时分。

定义1：对任意两列车和，当为的紧后行列车时，找不到比更小的始发站发车间隔时间，使得这两列车在任意车站均满足相应的车站间隔时间，称为列车和的最小始发间隔时间。

2 高速铁路列车运行图结构优化模型

根据既定的高速铁路停站方案，通过对列车进行合理排序，优化列车运行图结构，可以提高铁路通过能力。优化目标为使紧凑铺画的列车运行图中第一列列车从始发站出发至最后一列列车到达终到站之间的总间隔时间最短。将每条列车运行线视为一个节点，构造节点网络完全图。用表示节点编号（与其对应的运行线编号）。令从节点指向节点的路径的费用等于列车和的最小始发间隔时间，那么根据定义1和定义2，整个网络完全图中所有路径的费用可以根据既定的高速铁路停站方案来确定。

紧凑铺画时列车运行图结构的优化问题可转化为经典的旅行商问题。设G=（V，E）是带正权的完全图，，E表示完全图中所有边的集合，边的费用记为。

节点网络完全图的费用矩阵：

用变量表示边是否存在于总费用最小的巡回路径中，若是=1，否则=0。这里有一种特殊情况，若时，取=0，因为这样的边在节点网络完全图中并不存在。所以待求解的矩阵：

为了优化紧凑铺画列车运行图的结构，确定最优的列车运行线顺序，实现第一列车从始发站出发至最末列车到达终到站的间隔时间最小化的目标，巡回路径总费用最小化的TSP问题表达为：

式中：为巡回路径子图的边的数目。

式（1）和式（2）表示任一节点在巡回路径中只能出现一次，式（3）表示巡回路径必须遍历所有节点。

3 遗传算法参数设计

（1）染色体编码。采用以遍历节点的次序进行编码的方法，如码串123456表示从节点1开始，依次经节点2、3、4、5和6，最后返回节点1的遍历路径，这是针对TSP问题的最自然的编码方式。

（2）适应度函数。适应度函数常取路径长度的倒数，即。结合TSP的约束条件（每个节点经过且只经过一次），适应度函数修正为：，式中：为对TSP路径不合法的度量，这里取为未遍历的节点的个数;为惩罚系数，取值通常为节点之间最长距离的两倍多，这里取2.1。

（3）遗传算子。1）选择算子。用适应度函数对群体中所有个体进行评估，将选择算子作用于群体，选择的目的是把优化的个体直接遗传到下一代，或通过配对交叉产生新的个体再遗传到下一代。采用轮盘赌与精英个体保存的混合策略，选择当前种群中的最优个体直接进入下一代，剩余个体通过轮盘赌随机选择，这种方式能够在一定程度上避免算法过早收敛。2）交叉算子。采用部分匹配交叉策略：随机选择两个交叉点，将两交叉点之间的基因段互换，将互换后的基因段以外的部分中与互换后基因段中冲突的节点用另一父代相应位置的码值代替，直至没有冲突。3）变异算子。对群体中的个体，随机选择染色体中的两点，交换其码值。

（4）遗传算法求解流程。具体步骤如下：1）设定参数，种群大小为，交叉概率为，变异概率为，最大遗传代数为。2）按照染色体编码方式生成初始种群，当前代数。3）计算当前种群中各染色体的适应度，选择最优个体直接进入下一代，剩余个体通过轮盘赌随机选择。4）根据给定的交叉概率，对种群进行一致性交叉操作。5）根据给定的变异概率，对种群进行变异操作，更新代数。6）算法终止条件。若，转步骤3）;否则，输出当前种群中最優染色体，并解码为列车运行图编制方案。

4 实例分析

为了对该优化模型的优化效果进行验证，以2015年京沪高铁列车为案例进行验证。以全路运行图中由北京南始发上海虹桥终到的全部39列速度为300 km/h的下行列车为研究对象。

全路运行图中京沪高铁在各站的停站时间如表1所示，具体停站方案如表1所示。

将表2中各列车依次编码为1至39，增加一个虚拟节点，其编号为40。设定遗传算法参数，种群大小;交叉概率;变异概率;最大遗传代数。

经过300次迭代后，取当代种群中，取当地种群中最优染色体，其编码为1-2-5-6-4-3-7-15-13-38-9-8-26-24-14-31-35-37-10-22-36-25-16-12-20-32-33-30-17-39-19-34-27-21-11-28-23-29-40，去除最末的虚拟节点，解码成列车运行线的铺画顺序。

5 结论

本文以列车通过能力最大为出发点来铺画高速列车的运行图，然后建立关于高速铁路列车运行图结构优化的数学模型，再利用遗传算法及其设计参数对模型进行求解。高速铁路在我国成为人们出行的主要交通工具以及我国的高速铁路逐渐成网，而且条件更加复杂，对列车运行图的结构还需进一步深入研究。

参考文献：

[1]胡思继.列车运行图编制理论与方法[M].北京：中国铁道出版社，2013.

[2]周文梁，史峰，陈彦，等.客运专线网络列车开行方案与运行图综合优化方法[J].铁道学报，2011，33（2）：1-7.