基于候选列车集与弹性需求的城际铁路列车开行方案优化

周文梁，刘晓航，姜 敏，薛利娟

(中南大学 交通运输工程学院， 湖南 长沙 410075)

列车开行方案是城际铁路列车开行计划的重要组成部分，其优化通常是基于客流出行需求在路网上的时空分布，在线路运输能力、车站列车始发与终到能力等限制下，从降低企业运营成本、提高企业运营效率或旅客出行服务水平等角度确定列车开行数量、径路以及沿途停站等。高质量的城际列车开行方案有助于提高旅客出行服务水平与列车运营效益，同时对缩短城市间时空距离、促进城市群一体化等具有重要现实意义。

在网络化运营条件下，根据客流时空分布整体性优化列车开行方案各组成部分，因问题规模庞大、组合方案众多，故其求解难度较大。为了在保证列车开行方案合理性的基础上尽可能提高求解效率，不少学者基于候选列车集优化列车开行方案，即首先根据出行需求在轨道网络上的时空分布，按一定条件生成较多候选列车，然后从其中组合选择部分候选列车开行。文献[1]提出将列车服务频率、列车编组与运行径路等结合形成候选列车集；文献[2]首先根据一定原则生成候选列车集，并以此作为列车开行方案优化的解空间，进而建立基于候选列车集生成列车开行方案的混合整数规划模型，采用拉格朗日松弛启发算法求解；文献[3]分析了候选列车集对列车开行方案优化的影响，并提出了候选列车集生成算法，在此基础上优化列车开行方案。

目前，国内外研究通常基于固定客流需求优化列车开行方案，缺乏考虑竞争条件下列车开行方案优化质量对出行需求的影响。文献[4]基于不同时段客流需求量，以列车开行的最大效益和旅客的最大方便度为目标，建立列车开行方案优化的多目标双层规划模型。文献[5]将列车开行方案与客流换乘方案相结合，建立旅客列车开行方案的双层规划模型。实际上，随着城市群旅客需求与运输供给的多样化发展，客流出行方式选择与各交通方式服务水平之间的相互影响越来越明显。近年来，基于弹性需求的列车开行方案优化引起了不少研究人员的兴趣，文献[6]建立了客流动态调整的列车开行方案的综合优化模型，以实现列车开行方案的动态优化；文献[7-9]通过分析开行方案、旅客出行费用、旅客出行需求三者之间的影响关系，构造旅客运输弹性需求函数，将旅客换乘方案的选择归结为弹性需求下的用户平衡分配问题，通过利用铁路企业与旅客之间的主从博弈关系，建立了基于弹性需求的旅客列车开行方案的双层规划模型，并设计了基于模拟退火算法求解的优化算法。

虽然已有少量研究对弹性需求下旅客列车开行方案进行优化，但因其未涉及列车车站到发时刻信息而不能准确描述旅客上车等待时间、换乘时间等出行费用，进而难以确定OD出行需求量以及出行列车选择。本文试图将列车车站到发时刻优化融入到传统列车开行方案优化中，延伸至对列车运行图的优化。通过在准确描述旅客出行的各项费用、构建描述出行需求与出行费用之间变化关系的弹性出行需求函数、以及构建基于给定候选列车的弹性客流出行网络的基础上，结合弹性需求客流出行列车选择，构建一种基于候选列车集与弹性出行需求的城际列车开行方案优化模型，并基于模拟退火算法，通过设计列车运行图邻域解搜索策略实现对模型的求解。

1 候选列车及其开行成本与收益分析

1.1 候选列车集

基于给定城际铁路网络上客流出行的时空分布，以提供旅客较低的出发等待时间、旅行时间与无缝换乘等良好的出行服务为原则，预先生成可能开行的各候选列车，并确定每列候选列车的开行径路、开行时间范围、速度等级以及编组等部分开行方案内容，形成城际铁路网络的候选开行列车集，并将其作为输入。需指出的是城际铁路通常各开行列车的速度等级、编组均相同，故本文假定各候选列车具有相同的速度等级与编组大小。城际铁路网Wnet为

Wnet=(S,E)

E={e=(k,k′)|k,k′∈S}

式中：S为城际网络的车站集合；k,k′为车站；E为城际网络的区间集合；e为城际网络的区间。

Wnet上可能开行的候选列车集合Ω为

Ef为候选列车f经由区间集；Zcap为各候选列车最大载客能力，人；R(k,k′)为所有候选列车在区间(k,k′)∈E统一的纯运行时间，min；W(k)为各候选列车若在车站k停车所需要的停站时间，包括停留时间与起停附加时分，min。

因城际铁路候选列车集是以提供旅客良好的出行服务条件为原则确定，显然，若最终将所有候选列车开行，则旅客必具有良好的出行服务，但相应地列车客座率、开行效率等将较差。因此，最终所确定的实际开行列车不应多于候选列车。本文基于给定候选列车集优化城际列车开行方案，实质上是从预先确定的候选列车集合Ω中合理选择部分候选列车组织开行，同时进一步确定各开行列车的停站方案、以及车站到发时刻。

综上所述，便可为每列候选列车f定义以下决策内容：

(1)xf为候选列车开行决策变量，决定候选列车f是否开行，若开行，为1；否则为0。

(2)yf(k)为候选列车停站决策变量，决定候选列车f在其经由站k∈Sf{rf,sf}是否停车，若停车，则为1；否则为0。

(3)af(k)为候选列车车站到达时刻变量，表示候选列车f在其经由站k∈Sf{rf}的到达时刻。

(4)df(k)为候选列车车站出发时刻变量，表示候选列车f在其经由站k∈Sf{sf}的出发时刻。

本文虽已将列车到发时刻融入到列车开行方案中，扩展至对列车运行方案图的优化，但因不考虑列车车站到发作业间安全时间间隔要求，故本文所确定的列车车站到发时刻并不一定满足实际运营要求，而需要在此基础上进一步采用定序优化思想[13]，通过小幅度调整列车车站到发时间使其满足作业安全时间间隔，即生成可行列车运行图。显然，列车到发时刻的小幅度调整不会导致列车运行方案图质量的明显恶化。

1.2 列车开行成本与收益分析

列车开行成本分为列车开行组织成本、列车运行成本。列车开行组织成本为列车开行所需要的固定成本，包括乘务人员相关费用、机车车辆购置分摊费用等，该项成本与列车旅行时间无关；列车运行成本与开行列车旅行时间成正比，主要包括线路使用费、机车车辆折旧费等。列车开行的总组织成本CZ与总运行成本CT分别为

( 1 )

( 2 )

本文仅考虑列车开行收益的主要部分列车票价收益，而其他收益因受列车开行影响较小，故可视为常数。则列车f的票价收益Pf为

Pf=Df×μ

( 3 )

式中：Df为乘坐列车f的旅客人公里数，该值将在稍后模型中给以明确计算方法；因所有列车采用统一类型的动车组，假定所有列车单位人公里票价率均为μ。

2 客流出行网络构建与弹性需求分析

2.1 客流出行网络构建

基于给定城际铁路网络及其候选出行列车，构建描述弹性客流出行选择及其出行费用的网络，是获取各开行列车乘车客流量、评价列车开行方案的关键。弹性客流出行网络为由3类节点与5类有向弧构成的有向图，记为

G=(N,A)

N=NS∪NA∪ND

A=AS∪AQ∪AC∪AH∪AX

式中：N为节点集合；NS为车站节点子集；NA为列车车站到达节点子集；ND为列车车站出发节点子集；A为有向弧集合；AS为上车弧子集；AQ为区间乘车弧子集；AC为车站停留弧子集；AH为换乘弧子集；AX为下车弧子集。

基于以上3类节点，在它们之间构造以下5类有向弧：

在以上构建的客流出行网络上，旅客途经每条有向弧均存在一定的运输能力限制。

(1) 上、下车弧运输能力均有两种可能：当列车开行且在车站停车时，对应的上下车弧的运输能力为无穷大，记为M；当列车不开行或者列车不在车站停车时，对应的上下车弧运输能力只能为0，即不允许旅客上下车。

(2) 区间乘车弧运输能力取值为列车运输能力或0，即当列车开行时，对应该列车在所有经由区间的区间弧运输能力均为列车运输能力；否则均为0。

(3) 车站停留弧运输能力取决于对应列车是否开行以及在车站停车，若列车开行且停车，则车站弧的运输能力为列车运输能力，否则为0。

(4) 换乘弧运输能力取决于两个关键因素：两列列车是否均开行且在车站停车；两列车在车站的到达与出发时刻是否达到最低换乘时间要求。只有满足这两项条件，换乘弧运输能力可设为无穷大M；否则为0。

此外，旅客经由各有向弧时需承担一定的出行成本，其中，在上车弧的出行成本主要为旅客出行等待时间，在区间乘车弧的出行成本包括票价与乘车时间，在车站停留弧的出行成本为停留时间(不停车时为0)，在换乘弧的出行成本为换乘时间，为了尽可避免换乘，可在换乘弧上增加额外的换乘惩罚费用；而下车弧上出行成本均视为0。

值得说明的是，以上出行网络节点与弧集均是固定不变的，并不随实际开行列车变化而改变。开行列车的选择只能影响着相关弧上的费用与能力变化。

2.2 弹性出行需求分析

城际铁路旅客出行需求受列车开行服务、竞争交通出行方式服务等影响，而弹性出行需求反映了旅客出行需求量与其影响因素之间的变化关系。假设在其它竞争交通出行方式服务不变前提下，因不同列车开行方案使得OD具有不同出行服务水平，故OD出行需求量也存在差异。本文将通过优化列车开行方案、确定各OD出行服务水平，使得其对应的出行需求量能够产生最大的票价收益。

弹性出行需求函数用于定量化描述OD出行需求量与列车服务水平(采用旅客出行成本体现)之间的变化关系。本文基于铁路预售票系统中所具有的海量售票数据、以及列车时刻表信息，首先，根据列车时刻表确定每个OD出行服务水平，统计售票数据获得每个OD出行量；然后，以此服务水平作为OD基准出行服务水平、以此出行统计量作为OD基准出行需求量，进而通过引入弹性系数λ构造弹性出行需求函数为

( 4 )

通常弹性需求系数取值取决于旅客需求的刚性水平、竞争交通出行方式服务水平等。对于以通勤客流为主的OD，该系数取值相对较小；但对于以旅游与购物客流为主OD，其取值相对较大。

某OD出行需求量与其出行费用之间的变化函数曲线见图2，3条曲线均经过坐标点(c0,q0)，意味着当OD客流出行费用为c0时，其出行需求量均为q0。

针对每支时段弹性客流，本文需要为其确定以下决策内容：

3 优化模型建立

通常列车开行方案优化一方面应提高铁路企业列车开行效益，另一方面应保证旅客出行服务水平。在固定出行需求下，因出行需求量不会因列车服务水平的改变而变化，为避免因减少列车开行成本而导致旅客出行服务质量下降，应选择两者作为优化目标。但在弹性需求下，若要最大化列车开行效益，既要降低列车开行成本，又需通过提高列车服务水平留住甚至吸引更多客流。因此，列车开行效益的最大化实质上就应降低旅客出行成本来提高票价收益，故本文以此作为模型优化目标。

( 5 )

( 6 )

式中：Df为乘坐列车f的旅客人公里数，为其各经由区间乘车人数与里程之乘积；L(k,k′)为区间(k,k′)的里程数。

模型同时满足以下6类约束条件：

(1) 列车停站约束

( 7 )

yf(rf)=xf∀f∈Ω

( 8 )

yf(sf)=xf∀f∈Ω

( 9 )

式( 7 )确保了任意列车f∈Ω在不开行，即xf=0时，其在中间车站均应不停车，否则开行(xf=1)时，其在中间停站不受限制；式( 8 )、式( 9 )则分别确保了列车f在开行时，在起、终点站必停，而不开行时，在两车站均不停车。

(2) 列车始发时间范围约束

(10)

式(10)使得任意候选列车f在其给定的始发时间范围内始发。

(3) 列车到发时刻约束

af(k′)-df(k)=R(k,k′)×xf

∀(k,k′)∈Ef∀f∈Ω

(11)

df(k)-af(k)=yf(k)×W(k)

k∈Sf/{rf,sf} ∀f∈Ω

(12)

式(11)、式(12)分别使得任意候选列车f在其开行时，在经由区间的运行时间、在经由中间站的停留时间分别等于给定的时间值，而在不开行时，两者均为0。

(4) 区间运输能力约束

∀(k,k′)∈E∀h∈H

(13)

该约束确保了任意区间(k,k′)在任意时段h内运行的列车数量不超过该区间的运输能力。

(5) 客流平衡约束

∀k∈S∀h∈H

(14)

∀k∈S∀h∈H∀j∈N{nk′:k′∈S}

(15)

∀k∈S∀h∈H∀k′≠k

(16)

(6) 客流出行弧能力约束

① 上车弧能力限制

∀f∈Ωk∈Sf/{sf}

(17)

② 区间乘车弧与车站停留弧能力限制

∀(k′,k″)∈Ef∀f∈Ω

(18)

∀k′∈Sf{rf,sf} ∀f∈Ω

(19)

③ 换乘弧能力限制

(20)

两列列车都在相应车站停车。

(21)

两列车在车站的衔接时间达到最低换乘时间要求。

(22)

式中：Ψk为换乘所需要的最大换乘时间。

④ 下车弧能力限制

∀k∈Sf{rf} ∀f∈Ω

(23)

4 算法设计

鉴于列车开行方案优化问题的复杂性与求解难度，该问题通常采用启发式算法进行迭代求解。作为现代启发式算法之一的模拟退火算法具有较强的适用性与鲁棒性等优良特性，较多文献已将其有效用于求解列车开行方案优化问题。如文献[10]采用模拟退火算法解决时变需求下的高铁列车开行方案优化问题，文献[11]通过模拟退火算法解决城际铁路开行频率的优化问题。为此，本文将结合以上模型特点，基于模拟退火算法框架设计其求解算法。

4.1 算法优化思想

模拟退火算法优化列车开行方案的思路是在生成初始列车开行方案的基础上，通过邻域解搜索方法不断搜索当前解的邻域解，若产生的邻域解优于当前解，则直接将前者替换后者；否则，按给定的概率随机替换后者。由此逐步改进当前列车开行方案，直至触发某一给定的算法终止条件而停止。

因算法只考虑从给定候选列车集中选择开行列车，并且各候选列车的经由车站与发车时段均已给定，故可首先将所有候选列车均设为开行列车，同一发车时段内开行列车以等时间间隔出发，并针对任意开行列车途经站以一定概率随机确定是否停车，由此形成初始列车开行方案，并将其设为当前解，其中，用于确定列车是否停站的概率可分别针对省级车站、地级车站以及县级车站等设不同值[12]。

基于当前获得的列车开行方案，更新旅客出行网络费用与能力参数，进而采用最小费用流将各OD客流分配至开行列车上，由此获得各开行列车车站上下车客流量、区间载客量以及车站列车间换乘客流量等。在此基础上，依据计算获得的各列车开行收益、停站比例以及车站旅客服务水平等对开行列车、列车停站与始发时刻进行调整，进而搜索当前列车开行方案的邻域解，具体如下。

4.2 列车开行方案邻域解搜索策略

列车开行方案邻域解的搜索策略包括停开列车、增开列车、取消列车停站、新增列车停站、调整列车始发时间。

(1) 停开列车

(2) 增开列车

(3) 取消列车停站

计算当前各开行列车f在其停站k的上下车客流量Qf,k、及其在车站k停车的前一列与后一列列车在该站发车时间差值Tf,k，选取按RCf,k=Qf,k×Tf,k值由小到大排序在前的固定比例列车停站，记其集合与数量分别为Ωc与nc；按给定概率关闭Ωc中一定数量的列车停站，即首先随机生成一个0至nc间的整数σc，并计算各列车停站的关闭概率

其中，RCmax为最大值；其次，以此概率采用轮盘赌方式选择σc个列车停站将其关闭。此外，若某列车停站无旅客上下车，则直接关闭。

(4) 新增列车停站

其中,RAmax为最大值；其次，以此概率采用轮盘赌的方式选择σa个列车通过站停车。

(5) 调整列车始发时刻

4.3 基于模拟退火的算法步骤

模拟退火算法相关参数设置为：初始温度Ψ0设为一较大的固定值；温度下降规则采用比例下降法，比例值θ随着温度下降而逐步提高；同一温度的迭代次数采用迭代次数下限、上限和接受频率来综合控制；算法终止规则采用温度下降至接近0或目标函数在λend次迭代无改变来综合控制。在此基础上，设计城际铁路列车开行方案优化的模拟退火算法如下：

城际铁路列车开行方案优化的模拟退火算法

输入：城际铁路网络，候选列车集，弹性需求、算法相关参数；

开始

初始化温度值Ψ0，设置温度下降比例θ，终止温度Ψend，同一温度下迭代上、下限，最大连续不改进迭代次数λend，允许的接受频率ϑ；

令当前温度Ψ=Ψ0，最优解连续保持迭代次数λn=1;

开始1

令当前温度下迭代次数K=1；

当K小于温度Ψ下的迭代下限，或者小于迭代上限且接受频率ϑ/K小于给定值

开始2

K=K+1；

返回2

温度下降，即令Ψ=Ψ×θ，并重置迭代次数K=1；

返回1

结束

5 算例分析

本节以昌九城际铁路为例分析所建模型与算法的有效性。昌九城际铁路全长约131 km，共设九江、庐山、德安、共青城、永修、南昌北6个车站，区间里程分别为18、35、8、25、45 km。考虑九江至南昌方向全天列车开行问题，该线路列车运营时间范围为06:00—23:00，以1 h为时长，将全天运营时间划分为17个时段，每个时段设置候选列车5列，故全天共85列候选列车从九江站始发、终到南昌站。

列车运营相关参数设置如下：列车人公里票价率为0.6元/km，列车旅行速度为250 km/h，定员为800人，开行固定组织成本为4 000元/列，单位时间运营成本为9 000元/h。列车在车站的停站时间统一设为2 min，列车区间起、停附加时分分别设为2、1 min。此外，旅客单位时间价值取37.8元/h，需求弹性系数统一设为0.05，暂不考虑OD需求弹性的差异性。

模拟退火算法相关参数包括：初始温度设为10 000 ℃，终止温度为低于5 ℃，各温度下的迭代次数的下限为10次、上限为20次，降温速率在整个迭代过程中保持0.7不变，目标函数若100次迭代无改变则终止算法。

5.1 不同分布特征客流下的列车开行方案优化结果

列车在全天各时段开行数量分布应与客流分布相吻合，以满足客流出行需求的同时提高列车开行效率。为检验列车开行方案与客流需求时间分布的吻合性，以下针对双峰型、平峰型两种分布特征客流，分别采用模拟退火算法优化获得相应的列车开行方案。

针对双峰型与平峰型分布特征客流的模拟退火算法迭代收敛分别见图3。从两图中可以看到，随着迭代次数的增加，列车总收益总体呈现上升趋势，最后收敛于某稳定值，故算法具有较好的收敛性。此外，在列车总收益上升过程中，列车票价收益并不一定保持上升趋势，如图3(b)中，列车票价收益在迭代过程中是有所下降的，但是因其减少量比列车开行成本增加量要少得多，故列车总收益仍然上升。值得说明的是因模拟退火算法允许以较小概率接受差解，故列车总收益收敛过程中是有小幅度的波动，并不是完全一直上升。

针对双峰型与平峰型客流分别优化获得如图4与图5所示的列车运行方案图，其相对应的指标见表1。由图4可知：在客流双峰时段内列车开行数量明显高于其他时段列车数；由图5可见，平峰型客流的列车运行方案图中，各列车在各时段开行数量基本相近。这较好地说明了所获得列车开行方案能够使得各时段开行列车数量有效适应时段客流量。

表1 基于弹性需求下不同分布类型客流的开行方案指标

图6、图7与图8分别给出了庐山—德安、德安—共青城、共青城—永修3个区间列车开行方案所提供的各时段运输能力与客流输送量对比曲线；通过比较发现，列车开行方案的运输能力和客流输送量的时段变化趋势是吻合的，各时段列车平均客座率在52%左右，避免出现在高峰时段运输能力不够，在非高峰时段运能过剩的情况发生，即在高峰时段能提供充足的运输能力，同时在非高峰期间也能提供良好的服务水平。

5.2 弹性系数对优化结果分析

弹性出行需求量不仅与旅客出行费用相关，而且与弹性系数有关。弹性系数决定了旅客对出行费用的敏感性，其值越小，说明需求弹性越小、刚性越大；反之，需求弹性越大、刚性越小。下面分析弹性系数的变化对于列车开行方案优化的影响，弹性系数从0增加至0.3时，所获得的列车开行方案各项指标的变化趋势见图9。

由图9可知，随着弹性系数的增加，旅客出行成本的变化更容易影响客流需求量的波动幅度，此时，因降低旅客出行成本所导致的列车开行成本的增加量相对较少，而导致客流出行需求的增加量相对较多，虽然列车开行成本有所增加，但客流增加所导致的票价收益增加量明显大于列车开行成本的增加量，故随着弹性系数的增加，列车总收益增加，人均单位里程费用减少，表明旅客服务质量不断提升。值得说明的是，在弹性系数为0，即出行需求量不会因出行成本变化而变化时，为了追求总收益最大化，通过减少开行列车数即降低列车开行成本，但因出行需求量不变故列车票价收益基本不变，这种情况下列车客座率相对较大，达到73.42%，人均单位里程费用也达到最高。随着弹性系数的增加，需求量对于服务质量的灵敏度增加，列车客座率逐渐下降，但基本在60%左右。

6 结论

本文考虑城际铁路各时段出行客流量与列车开行方案所提供出行服务水平之间的变化关系，在建立不同时段出行需求量与出行费用之间的弹性需求函数、基于城际铁路候选列车集构造弹性客流出行网络的基础上，结合弹性需求客流在出行网络上的出行选择决策，以候选列车是否开行0-1决策、是否停站0-1决策以及始发时间等为开行方案优化决策变量，以最大化列车开行收益为优化目标，构建列车开行方案优化模型。在生成初始列车开行方案的基础上，通过构建其邻域解生成策略，包括候选列车停开与增开策略、列车停站取消与新增策略以及列车始发时刻调整策略等，形成基于模拟退火思想的模型求解算法。基于昌九城际铁路的算例分析表明优化获得的列车开行方案能够有效使得各时段开行列车与旅客运输需求相适应，从而产生更大的社会与经济效益。

因列车开行方案没有列车到发时刻信息，而不能准确确定出旅客出行服务水平，因此，后续研究应面向弹性需求将列车开行方案与时刻表结合起来进行整体优化。此外，城际铁路与高速公路等交通方式市场竞争大，随着铁路“一日一价”票价理念的推出，在计划阶段将票价与列车开行方案优化结合起来进行优化也为本文需进一步研究的内容。