高速列车周期性开行方案优化模型与交叉熵算法

付慧伶，胡怀宾，武 鑫

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

0 引 言

铁路旅客周期性列车开行方案确定一个周期时间内(如1 h 或2 h)的列车起讫点、停站、开行频率及编组定员等，相同种类的列车按一定周期时间间隔重复开行，在1 d各个周期内呈现基本相同的停站和运行时分特征.其编制要求是列车起讫点、停站方式种类不能过多，列车运距不能太长.将单周期的方案扩展到全天后，列车具有服务频率高、开行间隔均匀、停站规律的特征.

周期性列车开行方案和运行图，既方便旅客出行又利于运输组织.欧洲很多国家，日本及我国台湾地区都有成功的实践，也有很多理论研究，例如M.T.Claessens[1]，S.Scholl[2]，M.Goerigk[3]，Yu-Hern Chang[4]等学者，在铁路成本或旅客效益最优目标下决策一个周期内的列车组合.国内学者也开始关注列车的周期组织方式：汪波[5]优化了京津城际铁路的周期开行方案；颜颖[6]分析了高速铁路周期化列车开行方案编制过程；肖龙文[7]研究了铁路列车公交化开行，针对广深线两站之间的列车开行对数、停车次数进行优化；W.Zhou[8]，李天琦[9]等研究了周期性列车运行图优化问题.既有周期性列车开行方案的研究特点是：针对较小型线网，列车密度不高、运距短、停站少、容易组织站站停列车，多采用1 h周期；旅客运程较短，优化满足旅客单一方面的需求，如使所有旅客的乘车时间最短[4]或换乘次数最少[2].

我国高速铁路周期性列车开行方案优化更加复杂：一是在旅客直达化目标下，很多高铁线长站多、列车密度大、长车比例高，考虑线路能力，不宜开行旅速低的长距离多站或站站停列车，需要停站次数受限、速差小的多种隔站停列车，相互配合提高站间直达率；二是为了使一个周期容纳增多的列车隔站停方式，要求周期时间长于1 h，如2 h或更长，因此起讫点和停站组合规模变大；三是不同车站旅客的乘车距离、时空分布，对列车频次、旅速、直达与中转等服务水平的接受程度差别明显，旅客需求的异质程度更高，在周期能力制约下，要实现用少量列车更好地匹配多类客流需求.

针对这些复杂特点，除了考虑减少铁路成本和旅客乘车时间目标，研究在一个周期内，以大站停和多种隔站停列车为主优化列车组合，最大程度保证站间直达率、满足旅客异质需求.由此提出一个新模型，并设计可求解大规模实际问题的算法.

1 问题描述与建模

1.1 优化问题及定义

(1)问题描述.

基于高峰客流确定高峰周期方案.为满足旅客的多样需求，一个周期内既开行停站少、旅速高的大站停快车，也开行隔站停的相对中低速列车，站站停列车只考虑在较短区段内开行.在生成列车时，从一个备选列车集合中优选一部分列车方案线(每条方案线是起讫点、停站和编组的一种组合)，决策选出方案线的开行频率，以最低列车开行成本满足旅客需求.

(2)车站、列车、客流的层级划分.

对一条高铁线的车站采取3 级划分：1 级节点为大站，2 级节点为中等车站，3 级节点为小站.大站之间开行的为“1层级列车”(简写为I-列车)，大、中站都停靠的为“2 层级列车”(II-列车)，在小站有停站的为“3 层级列车”(III-列车)，对应定义3 个层级的客流，即I-客流，II-客流和III-客流.

(3)备选列车集合生成规则.

备选列车方案线的停站组合按特定的规则来枚举生成.规则为：按运距，确定列车停站次数上限；考虑停站布点均衡性，起讫点内所有大站区段至少有一次停站；设定列车连续停站次数上限；III-列车要保证一定数量比例的小站停等.

1.2 优化模型

(1)集 合.

U——高铁线网中所有客流OD对集合，每个客流OD记作u；

UH——I-客流OD对集合；

UM——II-客流OD对集合；

UTF——不提供直达列车服务的客流OD对集合；

L——备选列车集合，每条列车方案线记作l；

LH——备选的I-列车集合；

LM——备选的II-列车集合；

Lu——能服务客流OD对u的备选列车集合，集合中lu表示列车l可以服务客流OD对u；

S——其每个元素s(l)为每列车l通过沿途停站能服务的客流OD对集合，⋃s(l)=U；

E——铁路区间集合，每个区间为e，任意客流OD对u必定覆盖一个或多个区间，u覆盖e时记为e∈u；

Le——运行径路覆盖区间e的列车集合，集合中le表示列车l覆盖区间e，Le=⋃{e∈s(le)|le∈L} ；

V——高铁线网的车站集合，每个车站为v；

Vu——客流OD对u之间的1、2级节点车站集合，u的起点站为v′u，终点站为v″u.

(2)参 数.

wl——列车l的开行成本；

T——规划的周期时间长度(h)；

Fu——在T内，客流OD对u的列车服务频率需求；

Qu——在T内，客流OD对u的客流量；

φlu——可服务客流OD 对u的列车lu对于u所在区段内的停站时间损失(min)；

τl——列车方案线l的停站总次数；

——在T内，区间e的列车通过能力；

——在T内，经验下可采用的停站方式总数；

dl——列车l的运行距离(km)；

——列车l的单位运行距离成本(元/km)；

——列车l由于在中间站停站所产生的成本(元)；

——列车l的固定运行成本(元)；clu——可服务客流OD 对u的列车lu对于u所在区间(段)内列车的定员；

θ——列车客座率，一般θ≤1.0.

(3)决策变量.

xs(l)——子集s(列车l)被选择时xs(l)=1，否则xs(l)=0；

fl——在T内，列车l的开行频率，该整数变量决定u被直达列车服务的次数.

(4)模 型.

模型包括两个优化目标，一是总列车开行成本最低，即

式(1)中每列车的成本包括固定成本和变动成本，变动成本与其运行距离、停站次数成正比，即

二是旅客乘车时的停站损失时间最小，即

对于给定高铁线网，旅客运程和列车区间运行速度是固定的，旅客乘车时间长短取决于列车在途经车站的停站时间(包括起停附加时分)和次数.目标函数式(3)使1、2 级节点旅客由列车停站而产生的时间损失最少，缩短总乘车时间.

求解多目标问题时可以统一量级，再根据目标的重要度，设置权重系数λ，将其转化为单目标规划问题.

客流OD 的列车服务频率是衡量服务水平的一个重要指标，生成列车开行方案时应满足各客流OD的服务频率需求下限，即

还需要保证区间(段)列车席位能力不能低于区间(段)客流密度，即

如果加入层级索引，式(4)和式(5)可以共同约束用某种等级的列车服务对应层级的客流，即I-列车、II-列车、III-列车分别服务I-客流、II-客流、III-客流.利用式(4)，针对I-客流，按距离别对Fu设置较大值，意味着向大站旅客提供I-列车的“高速度、高直达频次”服务；针对II-客流，Fu值适当降低，向中等车站旅客提供II-列车的“较高速度、较高直达频次”服务；针对III-客流，Fu设置最低值或为0，向小站旅客保证III-列车的“一定频次的直达或中转”服务.

在规划周期时间T内，要保证经过各区间的总列车数不能超过该区间通过能力上限，即

受周期能力限制，如果III-列车不能保证小站旅客全部直达，则部分需要中转(即部分Fu值为0).要保证这些旅客能够在小站有机会乘坐列车，到某个换乘条件良好的1、2级节点实现一次中转.

考虑到列车方案线之间的异质性(由停站次数不同体现)影响运行图能力，在T内可以限制列车停站方式的总数.当区间通过能力紧张时，通过调节N(T)值，铺画运行图，可以评估停站结构对能力的影响.

决策变量的关系约束为

式中：M为较大正整数.

限制fl为非负整数的约束为

限制xs(l)为0或1的约束为

2 交叉熵算法

上述模型是线性整数规划，当备选列车集合规模很大时求解困难.结合模型特点设计基于交叉熵的算法(Cross Entropy Algorithm，CE算法).

CE 算法基于概率函数产生初始样本，随历次迭代缩小 ||L规模.通过提取每次迭代后解集中重要样本的参数特征，更新概率函数参数，不断迭代收敛得到优化解.基本步骤为：

Step 1样本群初始化.

构造m个初始样本L1,L2,…,Li,…,Lm，每个样本中有n条列车方案线，初始样本群为一个m×n矩阵.决策变量xs(l)服从伯努利分布，第t次迭代时备选集中方案线l对应变量xs(l)的取值概率函数为为概率函数参数.t=1 时，利用Pl(1)为xs(l)随机赋值，xs(l)=1 表示方案线l被选中；验证t=1 时随机产生的样本群，保证满足预设的客流OD直达约束.

Step 2优化模型求解.

基于xs(l)赋值，利用模型求解每组样本中被选中方案线的频率fl，记录目标函数值Zi(1 ≤i≤m).

Step 3精英样本提取.

将模型目标函数值Zi作为每组样本的评价函数，构造评价函数矩阵Z=(Z1,Z2,…,Zm)，并对Zi排序，选取一定比例σ的评价函数值较小样本作为精英样本.

Step 4新样本群生成.

利用精英样本特征更新第t+1次迭代时概率函数，即当时，利用伯努利概率函数继续为新样本赋值，并与第t次迭代时保留的精英样本群合并，作为新样本群进入第t+1次迭代.

Step 5迭代终止.

当样本的评价函数值Zi均相同时，说明收敛到(局部)最优解，可终止迭代；也可设置迭代次数或时间上限.不满足迭代终止条件时转Step 2.

3 案例计算与结果分析

3.1 案例设计

选取车站分布和客流特征区别明显的两条线路，即京沪高铁和沪昆高铁(沪湘段)，优化本线区段的周期性列车开行方案，验证模型与算法.京沪高铁全长1 318 km，途经23 个车站，1、2 级节点客流比重较大；沪昆高铁沪湘段里程1 083 km，途经28个车站，3级节点小站数目多达19个，方案中的III-列车比例要高于京沪高铁.

案例均基于实际客流数据，模型参数设置如表1所示，限于篇幅，省略Fu、Qu及φlu等大矩阵列表，案例中对N(T)暂不做限制.令UTF为空集，验证能力限制下，能否实现所有客流OD之间有直达列车服务；为保证较高直达率，T应长于1 h，通过测试，T=2 h.

表1 模型参数设置Table1 Model parameter setting

3.2 结果分析

(1)方案结果.

对京沪、沪昆高铁两个案例，均先利用CPLEX 12.3 软件直接求解，再利用CE 算法求解，借助以2.00 GHz运行的Intel Xeon E7处理器运算.执行CE 算法时，设置48 个样本群，计算时间上限4 000 s，σ=0.5.

为保证各个区间(段)列车与客流在层级上的精确匹配，求解时针对各层级客流分别生成方案.案例求解指标如表2所示，以京沪案例为例展示结果，如图1所示，线旁数字为频率.

对比表2指标，京沪案例验证了CE 算法的正确性，沪昆案例验证了CE算法在III-列车比例高、大规模变量决策复杂的情形下，方案求解具有可行性.

表2 案例求解指标Table2 Indicators of solutions

图1 京沪高铁高峰周期列车开行方案Fig.1 Peak-hour periodic line plan of Beijing-Shanghai high-speed railway

(2)服务指标.

在案例设置参数Fu、T与τl组合下，列车开行方案均满足区间能力限制，实现了客流OD之间100%的直达率.再以京沪案例为例，统计方案的主要服务指标，如表3所示.

优化方案利用8个起讫点、20种停站方式的列车服务于253 个OD 的旅客.向大站旅客提供的是“高速度、高直达频次”的列车服务，列车频率分布符合中短距离旅客出行频次一般高于长距离旅客的现实.小站列车服务频率最低，但旅客不仅都能乘坐直达列车，并且每隔一个周期时间有相同的列车.总体上，列车服务质量体现差异化，随客流层级的增高而提升.

由于3 个层级列车均满足对应层级的客流需求，各区间的总列车席位有富余，占用了较高的区间能力20(列/2 h).本文也对全部层级客流整体生成方案进行了测试，区间能力最高占用为17，且列车开行成本降低14.8%.但节省线路能力和成本是以牺牲服务质量为代价的，部分大站客流由II-列车或III-列车输送，将增加乘车时间.若希望继续节省能力和成本，可让部分小站客流中转(令UTF不为空集)，或同时减小τl值；更多能力、成本与服务水平之间的博弈关系，本文不再详细分析.

表3 京沪案例服务指标Table3 Line plan performance of Beijing-Shanghai high-speed railway

将图1方案扩展到全天(平峰时段适当减少列车)，与实际非周期列车开行方案对比，两方面指标有明显改进.一是优化方案中，各区间I-列车比例都在40%以上，而实际方案平均约为21%；大站停快车比例提升有利于增强京沪高铁竞争力；二是中小站之间列车频率普遍提高，例如定远—丹阳北实际方案1 d只有2趟列车，且相隔近8 h，优化方案每2 h有1～3趟列车，列车开行间隔缩短且规律，相对于非周期列车不规律开行更易于吸引客流.

4 结 论

针对我国高铁周期性列车开行方案问题的复杂性，建立优化模型，决策周期时间内大站停和多种隔站停列车组合.设计CE算法，通过实例求解，验证了算法有效性.京沪高铁优化方案在2 h时周期内利用3个服务水平层级、8个起讫点之间20种停站方式的列车，实现253个客流OD之间100%直达，满足了多样化客流需求；列车旅速、节点与OD列车服务频率等指标均较优，与实际方案对比也取得良好优化效果.

本文模型针对高铁本线列车开行方案优化，如果结合跨线列车将涉及本线外其他衔接线路上的列车结构、客流、能力等约束，是一个联动多线、多流的网络化复杂问题，将在后续展开研究.