史 峰，李彦霖，胡心磊，徐光明，单杏花

(1.中南大学 交通运输工程学院，湖南 长沙 410075；2.中国铁道科学研究院 电子计算技术研究所，北京 100081)

在列车运输组织中，列车开行方案将客流转化成列车流，为编制列车运行图提供依据。由于高速铁路列车高密度开行，使旅客出行的时变出行需求得以满足，为了保证发车时间分布与时变需求相吻合，有必要在传统列车开行方案内涵的基础上进行扩展，引入列车始发时间，形成高速铁路列车开行方案的新概念。高速铁路列车开行方案的服务水平同样是一个重要的关注内容，包括关键O-D对之间的服务列车数下限、每个车站在需求稀疏时段的发车时间间隔上限等。随着高速铁路网络的快速发展，面向服务水平的高速铁路列车开行方案优化问题成为提高运输组织品质的重要研究问题。

很多学者对列车开行方案优化问题、列车停站方案优化子问题和列车上的客流分配子问题等展开了深入研究。其中，对于列车开行方案优化问题，史峰等[1]建立了开行方案的双层规划优化模型，上层规划是铁路企业对开行方案的优化，下层规划是旅客对列车开行方案的反应，即换乘网络上的客流分配，客流分配的结果作为铁路企业评价开行方案的重要依据，并设计了求解模型的模拟退火算法。Kaspi等[2]在不考虑列车能力约束的情况下，对列车开行方案和时刻表进行综合优化。FU等[3]建立了开行方案的混合整数规划模型，并根据模型结构特点设计拉格朗日松弛算法。苏焕银等[4]建立了开行方案的双层规划优化模型，下层规划将客流分配到列车上，设计了求解模型的模拟退火算法。FU等[3]和苏焕银等[4]都基于包括停站方案的列车运行区段备选集生成列车开行方案。徐光明[5]首先将客流分配到路网上，然后在每一个区段上开行若干列车单元，进而将相邻列车单元拼接成列车，形成列车开行方案；还设计了模拟退火算法优化拼接方案。在上述研究中，Kaspi等[2]、苏焕银等[4]和徐光明[5]均是针对时变需求优化列车开行方案的。

对于列车停站方案优化子问题，邓连波等[6]建立了列车停站方案的双层规划模型，上层规划优化了列车停站方案，下层规划针对给定的停站方案进行多类用户均衡的客流分配，并设计了模拟退火优化算法。李得伟等[7]以方案总停站次数最少为目标，考虑节点的列车服务频率、站间的列车可达性、单趟列车停站次数等约束，构建非线性规划模型，将其转化为连续优化模型，运用Matlab工具包求解。YUE等[8]考虑O-D对的服务列车数下限约束，基于给定列车开行方案优化停站方案和列车时刻表，使用拉格朗日松弛方法将数学模型转化为线性约束问题来求解。YANG等[9]粗略地考虑各车站发送能力分布与旅客发送量的吻合程度，并考虑车站服务列车数的下限约束，基于给定列车开行方案优化列车时刻表和停站方案，建立了混合整数线性规划模型，采用GAMS工具软件求解。史峰等[10]分析了位于省(直辖市)、地、县各级政府所在城市的高速铁路车站的出行需求集聚效应，建立了高速铁路线路上各级车站的列车经停比优化模型，发现高速铁路列车在省级站经停比几乎为1，不同线路上各级车站的最优经停比存在差异，这种差异与线路上各级车站的数量比率相关。

对于列车上的客流分配子问题，史峰等[1]针对日需求设计了客流分配的换乘网络，使旅客出行方案与网络路径一一对应，出行费用与路径长度相等，利用换乘网络上的客流分配求解旅客的出行方案，大幅提升了旅客出行方案求解的效率。Kaspi等[2]在客流分配时设计了1个规模很小的旅客换乘网络，2趟列车在1个车站的换乘过程只需要1条换乘弧和若干等待弧。Douglas等[11]在只考虑旅客直达情况下，对于城市轨道交通中的任意点对，设计了时变需求旅客选择列车的屋顶算法，将全天划分为多个区间，每1个区间内计划到达的旅客具有相同的最优乘车方案。Su等[12]采用了与Kaspi等[2]相同的换乘网络，注意到旅客在购票的瞬间占用列车能力，模拟旅客的购票过程设计列车上的客流分配过程，将屋顶模型扩展为多阶段屋顶模型，并扩展到旅客出行全过程。

本文在上述研究成果基础上，面向服务水平研究高速铁路列车开行方案优化问题。以高速铁路线路为研究对象，考虑旅客出行的时变需求、高速铁路线路条件、动车组小时数和服务水平，借助于列车在省级站经停比几乎为1的特征，将相关O-D对的服务列车数转化为各级车站服务列车数，建立高速铁路列车开行方案优化模型，并设计模拟退火优化算法。

1 问题描述

记高速铁路列车开行方案为Ω={T=(LT，VT，BT，DT)}， 其中LT，VT，BT，DT分别为列车T的运行区段、停站方案、编组和始发时刻估计值。1个合理的高速铁路列车开行方案，必须具有较小的旅客出行费用和铁路运输成本，还需为旅客提供一定水平的服务。因此，高速铁路列车开行方案优化问题可描述如下：

给定各O-D对的时变客流需求、高速铁路线路条件、动车组小时数，在一定服务水平和各项能力约束下，优化高速铁路列车开行方案Ω，使得旅客出行费用和铁路运输成本均最小化。

2 问题分析

1) 列车运行区段及备选集

列车运行区段LT包括列车始发站、终点站和列车径路，由于高速铁路上的列车径路是唯一确定的，所以列车运行区段只包括列车的始发站和终点站。

列车运行区段备选集L是由若干个备选运行区段构成的集合。备选运行区段是指任意2个具有始发终到能力的车站之间的区段，其中具有始发终到能力的车站通常是指具有动车所(段)或动车组存车线的车站。在优化列车开行方案时，全部列车运行区段都限制于备选集L中，即LT∈L，T∈Ω，从而缩小了优化搜索空间。

列车运行区段备选集的构建：设定客流量下限值，对于具有始发终到能力的2个车站，若这2个车站之间的客流需求达到设定的客流量下限值，则将其加入备选集；在一个省属地域范围内，线路上具有始发终到能力的2个端头站，无论客流需求大小，均将其加入备选集，多用于“早晚三角区”开行短途列车。

2) 列车停站方案

给定所有列车运行区段{LT|T∈Ω}，依据各O-D对的服务列车数和各站的服务列车数，确定列车停站方案{VT|T∈Ω}。通常规定所有列车在省级站全停，由此便可确定列车在地级站和县级站停站数的下限。同为地级站或县级站，到发客流量大小的差异，停车数的下限也存在差异。

3) 列车编组

列车编组BT分为16辆和8辆编组2种，通常根据线路通过能力和服务水平等确定采用哪种编组。

4) 列车始发时刻估计值

为了满足旅客时变需求，若掌握了列车在各站的发车时刻信息，则可能评价列车发车时刻与旅客时变需求的吻合程度。参照列车运行方案图的理念，在不考虑列车运行线冲突的情况下，在传统列车开行方案中引入列车始发时刻估计值，便可推导出列车在各站的发车时刻信息，实现列车发车时刻与旅客时变需求吻合程度的评价。

对于任意始发站，在时长为Δt的时段内，按照发车时刻呈均匀分布的原则排列列车始发时刻，便可估计出所有列车的始发时刻{DT|T∈Ω}。

5) 服务水平

高速铁路列车开行方案的服务水平包括以下2个方面，一方面是对关键O-D对的服务水平，另一方面是对车站的服务水平。

列车开行方案对于车站的服务水平，是指对于给定车站v、时段k=1，2，…，(t2-t1)/Δτ的停站列车数Tv(k)需要达到的下限规定标准Sv(Δτ)，以此保证稀疏需求时段内(比如早晚时段)车站的服务列车数。

6) 动车组小时数

列车开行方案需要以一定数量的动车组为保障，注意到开行方案优化期间并没有确定列车运行时刻表，进而没有确定动车组周转方案，也就没有确定所需要的动车组数量。我们转而以可支配动车组小时数作为列车开行方案实际使用的动车组小时数的上限约束，这是一种退而求其次的处理办法。

3 模型构建

3.1 约束条件

综上所述，列车开行方案Ω必须满足相关的约束条件，具体描述如下。

(1) 列车运行区段备选集约束。构造列车运行区段备选集L={lk|k=1，2，…，m}，列车T∈Ω的运行区段LT仅限于列车运行区段备选集L中产生，即

LT∈L={lk|k=1，2，…，m}T∈Ω

(1)

(2) 列车T∈Ω的编组BT约束。列车T的编组分为8辆编组和16辆编组，即

BT∈{8辆编组，16辆编组}T∈Ω

(2)

(3)

(4)

(5)

(4) 各时段和全天的区间通过能力约束。根据各列车在各站的出发或通过时间，可以统计出时段k内进入区间e的列车数Te(k)，进而统计出全天进入区间e的列车数为Te(D)。Te(k)和Te(D)分别受相应的通过能力限制，即

Te(k)≤Ce(Δt)

e∈E，k=1，2，…，(t2-t1)/Δt

(6)

Te(D)≤Ce(D)e∈E

(7)

(5) 每个车站始发和终到的列车总数约束。车站的始发和终到列车数不能超过车站始发终到能力限制，即

(8)

(9)

(6) 可支配动车组小时数作为上限约束。记列车T∈Ω的旅行时间为tT，列车开行方案使用的动车组小时数不超过可支配动车组小时数D，即

(10)

(11)

(8) 各车站各时段内停站列车数约束。记时段k在车站v∈V停站的列车数为Tv(k)，Tv(k)不得低于规定的下限列车数Sv(Δτ)，即

Tv(k)≥Sv(Δτ)

k=1，2，…，(t2-t1)/Δτ，v∈V

(12)

(9) 动车组周转约束。在任意车站，始发列车编组总数等于终到列车编组总数，使得动车组得以周转运行，即

(13)

(10) 剩余客流总人数为0。这是列车开行方案完成全部出行旅客运输任务的保障，要求开行列车数、停站数及其分布提供足够的运输能力，并通过客流分配进行验证。记客流分配的剩余客流总人数为P，此约束可表示为

P=0

(14)

3.2 优化模型

minZ=λ(wrτr+whτh+wcτc)+

(15)

s.t.

式(1)—式(14)

该双层规划模型描述了一个主从博弈，博弈的主体方为铁路运输企业，根据旅客的反应优化列车开行方案(上层规划)；从属方为旅客，针对铁路运输企业制定的列车开行方案，以旅客的集体选择行为作为反应，即产生旅客出行时间τr，τh，τc和剩余客流总量P等，作为铁路企业决策的依据(下层规划)。求解下层规划的客流分配方法见文献[12]。

4 模拟退火算法关键技术

列车开行方案优化是NP难问题[13]，通常采用智能算法求解。比如史峰等[14]基于模拟退火算法优化求解普通列车开行方案。WANG等[15]采用遗传算法优化列车停站方案。考虑到模拟退火算法具有较强的鲁棒性和适用性，下面设计模拟退火算法求解模型。

在模拟退火算法框架中，需要根据问题特点设计初始解的生成方法和邻域解的搜索方法，并要求初始解和新的邻域解满足全部约束条件。在所有约束条件中：式(1)—式(5)比较独立，是容易满足的；对于能力约束式(6)—式(10)，若增加太多列车必然导致该约束条件遭到破坏，这时可以通过提高列车客座率和增加16辆编组列车数的方法，力图在满足能力约束式(6)—式(10)的情况下满足服务水平约束式(11)、式(12)和剩余客流量约束式(14)；在构造初始方案时，通过尽可能地多开列车、多设停站，使服务水平约束式(11)、式(12)和剩余客流量约束式(14)得以满足；在邻域搜索时，一旦服务水平约束式(11)、式(12)或剩余客流量约束式(14)遭到破坏，立即以增加列车或增加停站的方式恢复这些约束条件的可行性；对于动车组周转约束式(13)，可通过限制双向列车成对运行使其得以满足。

在下面的算法设计中，将忽略模拟退火算法的一般性框架叙述，重点介绍模拟退火算法设计的关键技术，包括列车停站方案的确定方法、初始解的生成方法和邻域解的搜索方法。

4.1 停站方案的确定方法

列车停站方案受到服务水平约束式(11)和式(12)，以及剩余客流量约束式(14)的制约，下面依据式(11)、式(12)和式(14)的满足情况讨论列车停站方案的确定方法。

在任意车站，将停站列车和通过列车统称为经过列车，并将停站列车数与经过列车数的比值称为经停比。文献[10]研究表明，高速铁路列车在省级车站的合理经停比接近于1。对于2个省级车站r和s，若Trs

若O-D对(r，s)∈W之间存在剩余客流，即不满足式(14)，则可以增加列车在车站r和s或(r，s)之间途中车站的停站次数，甚至增开服务于点对(r，s)的列车，直至满足式(14)为止。

若列车开行稀疏的时空区域不满足式(12)，则适当增加停站密度。若仍然不满足式(12)，则适当增加列车，直至满足式(12)为止。之所以要先增加停站密度，再增加列车密度，是因为在客流较稀疏的时空区域，多停站少开车是合理的开行法则。

4.2 初始开行方案的生成

根据模拟退火算法框架和停站方案的确定方法，按照如下步骤生成初始列车开行方案。

步骤1：确定无能力约束的列车开行方案。

对于备选集L中全部运行区段，在可行时段k=1，2，…，(t2-t1)/Δt内开行1趟列车；将各个时段k内开行的列车均匀排列始发时间，确定列车的停站方案，推导列车在沿途各站的到达和出发时刻，全部列车无能力约束。

步骤2：按照列车定员分解列车。

步骤3：调整列车开行数量与停站。

在列车网络上进行客流分配，获得所有列车的客座率，分别按照如下情形调整列车开行数量与停站方案。

若不满足服务水平约束式(12)，则增加相应时空区域的列车停站和开行列车数，直至满足式(12)为止；

若不满足能力约束式(6)—式(10)，则在保持式(12)的基础上，按照客座率从低到高的顺序删除列车，直至满足式(6)—式(10)为止；

若不满足服务水平约束式(11)或剩余客流量约束式(14)，则在保持能力约束式(6)—式(10)的基础上，增加列车或停站，直至满足式(11)和式(14)为止。

为了保证式(13)得到满足，上述增加或删除列车的操作都得成对进行。

4.3 邻域解的搜索策略

在模拟退火算法中，需要在满足开行方案所有约束条件下，采用下列搜索策略依次搜索邻域解。

策略1：删除列车。以给定概率删除客座率小于下限标准的8辆编组列车，同时在反方向区段删除1列客座率最低的8辆编组列车。

策略2：增加列车。在始发能力允许的车站和时段内，选择现行列车客座率最高的列车运行区段增开1趟8辆编组列车，同时在反方向区段按照相同原则增开1趟8辆编组列车。

策略3：改变列车编组。若2个方向都存在8辆编组列车的客座率高于上限标准，则以给定概率将这2列相向列车都调整为16辆编组；若2个方向都存在16辆编组列车的客座率低于下限标准，则以给定概率将这2列相向列车都调整为8辆编组。

策略4：拼接列车。若1个方向上存在接续车站相同、接续时间相近的2趟相同编组列车，并且反方向存在2趟相同运行区段和编组的列车，分别将2个方向的列车拼接起来，形成更长距离的列车。

策略5：删除列车后增加停站。若不满足服务水平约束式(11)、式(12)和剩余客流约束式(14)，则相应地增加停站，直至满足式(11)、式(12)和式(14)，并在停站稀疏的时空区域适当增加停站。

策略6：增加列车后调整停站。对于新增加的列车，相应地确定停站，与其它列车经停比相适应。在保持满足式(11)、式(12)和式(14)的情况下，选择停站密集的时空区域删除停站，使得旅客出行时间下降。

5 算例分析

5.1 算例数据

以杭福深高速铁路线为例，该线路共有53个车站，其中省级站5个，地级站10个，县级站38个，线路上车站等级和区间里程如图1所示。

图1 杭福深高速铁路线图(单位：km)

5.2 算例结果

运用本文提出的模型和算法，求解得到杭福深高速铁路线双向列车运行方案图，如图2所示。图中纵坐标只显示了具有始发终到能力的车站站名，实心菱形点表示列车的始发终到车站和时间，空心圆点表示列车的中途停靠车站和时间。优化后的列车开行方案评价指标见表1。从表1可知，旅客的平均出行时间偏差较小(20 min)，列车平均客座率较高(72%)。

图2 杭州—福州—深圳间列车运行方案

折射动车组小时旅客出行费用/元列车总数/对出发时间偏差/min平均客座率/%1 1306.12×1071002072

每个车站的经过列车数、停站列车数和经停比分别按上、下行表示在图3中，图中横坐标为在线路上顺序排列的车站，并以数字1,2,3分别表示车站的省地县级的等级，图中左侧纵坐标为列车数，用于表示车站的经过列车数和停站列车数，右侧纵坐标为比例值，用于表示车站的经停比。

结合图1和图3可知：杭福深高速铁路中段的经过列车较多，但厦门至饶平的列车较少，这是因为厦门至饶平这段线路位于福建省与广东省的交界区域，客流较少；不同等级车站的经停比具有显著层次性：省级站的经停比为1，地级站的经停比分布于0.7～0.9之间，县级站的经停比分布于0.2～0.5之间，地级站的经停比显著高于县级站的经停比，是因为杭福深高速铁路上的县级站很多，地级站对同地区县级站具有出行集聚效应。

图3 杭州—福州—深圳间各车站列车服务情况

采用C#语言编程，该算例的运行时间为20 min，收敛曲线如图4所示，可见，运算收敛速度较快，收敛趋势较为稳定，表明本文提出的优化方法具有较高的运行效率。

图4 算法迭代收敛趋势示意图

6 结 语

本文对传统列车开行方案增加了列车始发时间估计值，综合考虑旅客出行时变O-D需求、高速铁路线路运输能力、列车定员、可支配动车组小时数等因素，面对关键O-D对的服务列车数和稀疏时空区域的服务列车间隔等服务水平，构建了优化高速铁路列车开行方案的双层规划模型，上层规划优化列车开行方案，下层规划根据给定的开行方案进行时变需求客流分配。设计了列车停站方案确定方法、初始开行方案生成方法和邻域解的搜索方法，进而设计了求解模型的模拟退火算法。算例分析表明，采用该模型和算法求解的列车开行方案在时空区域上较好地吻合了旅客出行的时变需求，其服务水平达到规定下限，该模型和算法具有良好的优化效率和实用性。