城市轨道交通过轨开行方案编制技术

于 剑 张星臣 徐 彬 陈载朝

（1.中国铁路经济规划研究院，100038，北京；2.北京交通交通运输学院，100044，北京；3.武汉铁路局宜昌车务段，443000，宜昌∥第一作者，研究实习员）

“过轨运营”，是指在相互衔接的两条或多条轨道交通线路上，列车从一条线路跨越到另一条归属于另一个运营实体的线路，从而与该线路上的原有列车共用某一区段的运营组织方式［1］。随着路网规模的扩大，线路间的影响越来越多，客流总生成量和换乘客流量均显著增加，这都使以往仅着眼于匹配一条线路客流的单线独立开行模式逐渐不能满足日益精细化的运营需求。针对此，本文对过轨运营城市轨道交通网络上的开行方案编制算法进行了研究。

相关研究中，文献［2］建立了使列车满载率达到最大的优化模型，考虑了车底衔接问题，求算了合理的列车开行频率。文献［3］详细阐述了共线运营、多交路运营、快慢车结合组织方式的具体内容和相关条件，并以乘客旅行时间最小化为目标建立了快慢车开行方案优化模型。文献［4］主要从客流、交路、停站、开行密度、运行图协调等方面进行了研究，其中对停站方案和开行密度进行了定量分析。文献［5］同时考虑地铁运营方和乘客两方面效益，应用动态规划方法研究了跨线列车开行方案编制问题。文献［6］研究了城市轨道交通运行计划编制方法，开行方案方面重点研究了开行频率的确定方法。文献［7］通过引入备选交路集，利用双层规划模型优化了城轨网络交路方案和发车间隔；同时注意到，铁路领域对于开行方案的研究更为成熟。文献［8］利用多目标规划模型和模糊数学规划方法研究了城际无支路高速铁路的停站方案、开行频率和编组长度三个方面的开行方案优化问题。文献［9－10］研究了具备不同停站特征的铁路开行方案优化问题，以最小化运营成本为目标，利用多个模型对交路、频率、停站方案进行了优化。文献［11－12］均衡考虑企业和旅客的需求，建立了多目标规划模型、双层规划模型等优化模型，并设计了开行方案评价方法、列车吸流原则、启发式优化算法。文献［13］运用双层规划模型和模拟退火算法对大规模路网上铁路列车交路及开行频率问题进行了研究。

可见，城市轨道交通领域已有的研究成果大多都只定性介绍了不同类型交路的特点和运用条件，同时对给定交路的开行频率的计算方法、运行图铺画模型及协调方法进行了较为深入的研究，但对交路方案本身的优化方法的相关研究较少，更鲜见过轨条件下的相关研究。

本文要探讨的是，如何在一个过轨运营的城市轨道交通网络上，根据已知的OD（起讫点）客流量，计算合理的交路方案和开行频率，使其既可降低乘客整体旅行成本，又具备较低运营成本。考虑到优化难度和实际中大多数车站无越行条件、可变编组又增加作业复杂度等的情况，本文采用站站停车、固定编组远行模式。

1 开行方案优化目标

开行方案的优化目标是算法的优化方向，是合理编制开行方案的基础，应综合考虑运营成本和乘客旅行成本两个方面。

1.1 条件假设

（1）所有网络化过轨运营条件均已具备。不同于单线运营，过轨运营需要具备一定的线路基础条件和运营组织条件，本文认为所分析的城市轨道交通系统已具备诸如轨道、通信、信号、调度、旅客服务等一系列条件。

（2）各交路列车均成对开行，每对列车的途经站点集合完全相同。

1.2 符号约定

设城市轨道交通网络（P，Q）上有n个车站、m条路段、o个不同的运营线路。相关符号说明见表1。

1.3 优化目标

1）总旅客周转量：是计算各项成本的基础，是旅客人数与运送距离的乘积。满足同样的运输需求量，产生的周转量越少，行驶的里程数就越少，运营成本就越低。

总旅客周转量Z＝所有乘客的乘车距离之和：

表1 相关符号表示

其中，n为路网中站点数量，下同。

2）列车运行能源成本、车辆维修成本、设备维修成本：列车总质量越大、行驶距离越长，所需的能源就越多，车辆、设备维修成本就越大，所以列车运行能源成本、车辆维修成本、设备维修成本可以用质量和周转量的乘积来计算。其中周转量包括旅客总周转量和列车总周转量，质量包括旅客质量和列车自重。令：

式中：

λ1——列车运行每t·km所需的能源成本；

λ2——列车运行每t·km所需的车辆维修成本；

λ3——列车运行每t·km所需的设备维修成本。

3）旅客旅行时间成本：旅客主要旅行时间有乘车时间、换乘时间两项。

（1）乘车时间成本。旅客总乘车时间为所有旅客乘车时间之和，所以总乘车时间成本为：

（2）换乘时间成本。旅客总换乘时间为所有旅客在各换乘站所经历的换乘时间之和，故换乘时间成本为：

4）综合优化目标：根据前述各指标建立的城市轨道交通开行方案综合优化目标如下：

其中，ω1，ω2（ω1＋ω2＝1）分别为运营成本和旅客旅行成本的权重系数，此指标值越小表示开行方案越优秀。

2 基于遗传算法的开行方案编制方法

算法的主要思路是，首先生成一个包含多条染色体的初始种群，每条染色体均代表一套可行的交路方案（包含多条交路）；之后针对每套交路方案进行客流分配和各交路开行对数的求算（以输送能力刚好超过最大客流区段客流量为准），并计算、记录此开行方案的优化目标值、适应度；完成一代计算后，经过选择、杂交和变异产生新一代种群，重复上述步骤，直至一定代数后终止，选择最优染色体（和相应开行频率）作为最终开行方案。

在一个已确定的路网上，发车站和折返站是确定的。本文认为，列车可从发车站发出，在另一发车站或折返站折返。算法流程图如图1所示。

其中，选择算子采用轮盘赌选择法，设式（8）的上限估计值为M，则适应度为M－C。杂交算子采用单点杂交，变异算子采用单点随机变异，下面对关键步骤进行阐述。

2.1 确定备选交路集

图1 列车开行方案算法流程图

首先定义全交路集，它是指路网上所有可能开行交路的集合，本文将各发车站和发车站、发车站和折返站之间的最短路径的集合作为全交路集的主要组成部分，再通过人工增加部分环线、绕行线等最短路径算法无法算得的线路共同构成全交路集。备选交路集通过对全交路集进行筛选得出，是指路网上可开行的、较为合理的所有交路的集合，最终的交路方案是备选交路集的一个子集。由于城市轨道交通系统主要吸引中远途客流，为减少换乘次数，筛选应遵循：①排除过短交路；②排除本线客流（能通过该线路直达的客流）较小的交路。

其中，第一个原则可作为计算机自动筛选交路的依据。对于第二个原则，由于难以在计算前对本线客流量设定科学的下限，且还需考虑线路走向等因素，故通过人工筛选更合理。

2.2 染色体描述方法和初始种群

一个种群有多条染色体，每个染色体代表一套交路方案，染色体的长度等于备选交路集中交路的数量。染色体采用二进制编码方法，各基因与备选交路集中各交路一一对应：若某基因对应的交路开行，此基因值为1，否则为0。确定初始种群就是确定种群内各染色体的初始编码。例如某路网经过计算、筛选得出的备选交路集中交路数量为8，种群数量为4，那么初始种群可能为：

设备选交路集中交路的数量为Nz。本文计算初始种群的方法是，事先凭经验指定拟开行的交路数量Nk，之后以Nk／Nz为开行概率对各基因随机赋1。

2.3 构建服务网络和有效路径搜索

本文以途经站数和换乘次数为考虑因素构建服务网络［14］。例如，在图2 中，一个十字形线路上有用虚线表示的l1，l2，l3号3条交路开行，构建的服务网络示意图如图3所示。

图2 服务网络构建示例

图3 服务网络示意图

其中，空心圆点代表对应于不同线路停站点的虚拟点，实心圆点代表对应于实际车站的虚拟点，各路段权值标注如图。其中定义途经1 站的成本为1，旅客认为的换乘一次的平均成本为R。服务网络与染色体一一对应，不断进行重构。

令换乘路径阻抗为其所包含的所有路段的阻抗权值之和。本文利用删边法求算了服务网络中任意两点间的前两条最短路径作为旅客的有效路径，具体算法如下：

（1）步骤1：初始化，i＝1，利用Floyd算法求算路网所有点对间的最短路。记m、n两点间的最短路径阻抗为Fmn，0，记目前求得的m、n两点间的次短路径阻抗为Smn，令Smn＝∞，∀m，n∈［1，N］，其中N为服务网络中点的数量。

（2）步骤2：恢复路段i－1的原始权值（若算法首次执行至此则无此步），检查服务网络的路段i，若其权值非0且不为无穷，则将其权值置为无穷产生新的服务网络，转步骤3；否则i＝i＋1，继续检查路段i。

（3）步骤3：利用Floyd算法在新产生的服务网络上求算所有点对间的最短路，记计算所得的m、n两点间的最短路径阻抗为Fmn，1，转步骤4。

（4）步骤4：若Fmn，1≤Fmn，0＋μ（无过远绕行约束，μ为阈值）、Fmn，1＜Smn且Fmn，1对应的路径与Fmn，0对应的最短路径不同，则Smn＝Fmn，1，记录相应的换乘路径；否则变更m、n点对，重新执行步骤4，直到所有点对均已判断。之后i＝i＋1，若i已超过服务网络的路段数，转步骤5，否则转步骤2。

（5）步骤5：若各点对间已求出次短路，则输出最短路、次短路，否则证明该点对间无满足条件的次短路，只输出最短路，所有点对输出后算法结束。

3 算例

利用C#语言开发“网络化条件下城市轨道交通开行方案编制”软件。算例为一个类似“田”字形的中型路网（见图4），站点以字母命名，共计21个，外围一周车站 A1、B1、C1、A5、B5、C5、D1、D2、E1、E2、F1、F2为发车站点，A3、B2、B3、B4、C3 为折返站点。编制该路网1 h内的OD 客流，共运送旅客120 906人次。

以6 km 作为交路长度下限，利用最短路算法求出一个备选交路集，数量恰为100条；为继续缩小规模，将本线OD 客流量在8 140人次以下的交路全部删除，得到有15条交路的备选交路集，如表2所示。

优化参数如图5所示，其中，“换乘一次的当量站数”意为旅客认为的平均每换乘一次的旅行成本相当于乘车途经一个区间旅行成本的倍数，此处定为5，“大致开行的交路数量”Nk定为6。

图4 算例路网

表2 备选交路集

优化耗时43 min 37 s，结果如表3所示。每代种群中最好的优化目标值随着进化代数增加的变化趋势图如图6：部分进化阶段目标值显现出提前成熟、局部收敛的现象，但随着变异率的提高，目标值总体呈现下降的趋势。此外，为与单线运营作对比，将备选交路集中交路确定为直线交路A1－A5、B1－B5、C1－C5、D1－D2、E1－E2、F1－F2并全部开行，在相同参数下算得的优化目标值为300 755元。而利用本文算法得出的优化开行方案目标值为262 424元，相比降低12.7%，证明网络化过轨运营能够比单线运营大幅降低综合成本，提高组织效率。

图5 优化参数设置

表3 优化结果 （最优目标值为262 424元）

4 结语

随着各国大型城市地面轨道交通路网规模的不断扩大，采取过轨运营等运输组织方式，提高客流直达率，减少运营和旅行成本必将是规划建设和运营组织的重点研究方向之一。本文研究了城市轨道交通列车过轨开行方案的计算机编制方法与技术，提出的算法可优化中小型路网的列车过轨开行方案。但是，仍存在很多不足，例如较少考虑编制开行方案的约束条件，如车站、区间能力限制、线路间相互干扰以及车底调度等问题，未考虑停站和编组方案的优化；同时算法效率有待提高，今后应在有关方面进行更加深入的探索。

图6 优化目标值的变化趋势

［1］毛保华，刘明君，黄荣，等.轨道交通网络化运营组织理论与关键技术［M］.北京：北京科学出版社，2011.

［2］孙焰，施其洲，赵源.城市轨道交通列车开行方案的确定［J］.同济大学学报：自然科学版，2004，32（8）：1005.

［3］黄荣.城市轨道交通网络化运营的组织方法及实施技术研究［D］.北京：北京交通大学，2010.

［4］房霄虹.城市轨道交通网络化运输组织协调理论及方法研究［D］.北京：北京交通大学，2010.

［5］陈强，何世伟，宋瑞，等.动态规划方法研究城市轨道交通网状线路跨线列车开行方案［J］.城市轨道交通研究，2010，13（3）：17.

［6］周艳芳.城市轨道交通网络列车运行计划一体化编制理论与方法研究［D］.北京：北京交通大学，2012.

［7］王永亮，张星臣，徐彬，等.城市轨道交通网络化列车开行方案优化方法［J］.中国铁道科学，2012，33（5）：120.

［8］Chang Yuhern，Yeh Chunghsing，Shen Chingcheng.A multiobjective model for passenger train services planning：application to Taiwan＇s high－speed rail line ［J］.Transportation Research Part B：Methodological，2000，34（2），91.

［9］Jan－Willem Goossens，Stan van Hoesel，Leo Kroon.A Branch－and－Cut Approach for Solving Railway Line－Planning Problems［J］.Transportation Science.2004，38（3）：379.

［10］Jan－Willem Goossens，Stan van Hoesel，Leo Kroon.On solving multi－type railway line planning problems［J］.European Journal of Operational Research.2006，168（2）：403.

［11］史峰，邓连波，霍亮.旅客列车开行方案的双层规划模型和算法［J］.中国铁道科学，2007，28（3）：110.

［12］史峰，邓连波，黎新华.客运专线相关旅客列车开行方案研究［J］.铁道学报，2004，26（2）：16.

［13］Lin Boliang，Wang Zhimei，Ji Lijun，et al.Optimizing the freight train connection service network of a large－scale rail system ［J ］.Transportation Research Part B：Methodological.2012，46（5）：649.

［14］陈胜波，何世伟，何必胜.客流波动条件下城市轨道交通列车开行方案研究［J］.城市轨道交通研究，2013（10）：53.

［15］于剑，张星臣，徐彬，等.面向客流分配的城市轨道服务网络构建算法与实现［J］.武汉理工大学学报：交通科学与工程版，2013，37（5）：1036.