面向O-D时变需求的城轨列车运行计划优化方法

史 峰，涂 纤，赵 烁

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

城市轨道交通(简称城轨)线路的运行效率与服务水平在很大程度上取决于列车运行计划。高品质的列车运行计划通常需要权衡乘客和企业两方面的利益，一方面为乘客提供较优质的服务，另一方面为企业降低运行成本[1]。

列车运行计划包括列车时刻表与列车周转方案。现有列车时刻表的研究更多地关注降低乘客出行费用，如减少乘客的候车时间[2]、换乘时间[3]和总旅行时间[4],以及优化周期性列车时刻表[5]，文献[6]综合考虑了乘客出行费用和企业运行成本，但这些研究均假定全天出行需求为固定常数或是均匀到达车站的理想客流。实际上，旅客出行需求具有随时间的波动性，这种具有时间波动性的出行需求称为时变需求[7]。文献[8]基于客流O-D时变需求，考虑列车对数与上座率，设计了优化列车发车时间间隔的遗传算法，降低了乘客的等待时间。文献[9]以德国市郊铁路为背景，强调指出需确定灵活的列车间隔以适应客流的时变性。文献[10]和文献[11]建立了基于弹性需求的乘客列车开行方案的双层规划模型，并设计了基于模拟退火算法求解的优化算法。列车时刻表的实施必须由列车周转方案来保障[12]。文献[13]基于给定的车辆运行时刻表，针对单车场研究了车辆调度问题。综合优化列车运行计划的问题非常复杂，研究成果较少。文献[14]针对城轨线路时变断面需求，提出了满足服务水平的列车时刻表和列车周转方案的两阶段优化方法。同时，文献[15]对城轨列车运行计划的优化具有一定的参考价值。以上文献虽然未能有效解决面向O-D时变需求的城轨线路列车运行计划优化问题，但是在优化思想、优化方法上有一定的启发作用。

本文在上述文献研究成果的基础上，针对城轨线路的O-D时变需求，以具有单一尽头车场的城轨线路为研究背景，提出基于列车时刻表的客流分配方法，在给定乘客服务水平的限制下，实现O-D时变需求与列车时刻表的耦合，进而以列车对数和列车车底数最小化为目标，构建了列车时刻表和列车周转的2阶段优化模型，并提出了2阶段求解算法。

1 列车运行计划优化问题

城轨线路具有m个车站s1,s2,…,sm，记全体车站集为S。车站s1至sm为线路的下行方向D，车站sm至s1为上行方向U。列车从车站su至sv的旅行时间与车站sv的停站时间之和为τ(su,sv)。端点站s1和sm的列车停放能力分别为N1和Nm(含立即折返列车)，折返作业时间分别为r1和rm。全天运营时段为[T1,T2]。

1.1 列车运行计划

列车周转方案主要受车场布局的影响，城轨线路上有很多种车场布局形式，每种布局形式对应不同类型的列车周转方案。本文以单一尽头车场为背景，讨论列车时刻表与列车接续的优化问题。具有单一尽头车场的城市轨道线路及列车运行组织形式特征如下：

线路仅有1个车场p且与端点站s1邻接，且车场p无能力限制；若车站s1达到饱和，则新到达列车必须停放至车场p；若车站sm达到饱和，则只能等待车站sm有列车驶离后才能到达列车。

由此可见，所有早班列车均由车场p提供给车站s1，列车从车站s1出发，到达车站sm，或折返回车站s1，或停留于车站sm；列车到达车站s1后，可折返回车站sm，也可停放在车站，还可返回车场；所有晚班列车均返回车场p。

1.2 乘客服务水平

从以下3个方面来考虑乘客服务水平。

(2)发车时间间隔限制：最小发车时间间隔为τmin，最大发车时间间隔为τmax。

(3)列车载客量限制：列车载客能力为C，常规载客系数为α(0<α<1)。列车断面载客量一般不超过αC，除非列车按最小发车时间间隔发车。当列车按最小发车时间间隔发车时，列车最大断面载客量达到αC，但不超过列车载客能力C，超过载客能力C的需求作为车站滞留客流。

1.3 列车运行计划优化

2 基于列车时刻表的客流分配

基于列车时刻表的客流分配就是模拟乘客的上车行为，根据每趟列车到达每个车站时列车上的客流量、下车人数和列车容量，计算列车在每一站的剩余能力，确定可以上车的乘客数。超过上车数量的乘客作为滞留客流，各站的滞留客流量按终点分别记录。当需求量超过上车数量时，各终点的需求量按照等比例原则上车，以便适度体现“先到先走”的原则。

基于给定的列车时刻表，分别计算双向各站滞留客流量和客流量。

1)下行方向

按照k=1,2,…,n;u=1,2,…,m-1;v=u+1,u+2,…,m的顺序，依次递推求解滞留客流量和客流量如下。

首先，求解滞留客流总量，即

(1)

(2)

(3)

(4)

2)上行方向

按照k=1,2,…,n;u=m,m-1,…,2;v=u-1,u-2,…,1的顺序，依次递推求解滞留客流量和客流量如下。

首先，求解滞留客流总量，即

(5)

(6)

(7)

(8)

3 列车时刻表优化模型

列车发车时刻相关的约束条件如下。

(9)

(10)

综合考虑以上2部分内容，获得首班车发车时间约束为

(11)

(12)

(2)末班车的最早发车时间约束。表示为

(13)

(14)

(3)最小发车时间间隔约束。同一方向发车时间间隔不得小于最小发车时间间隔，即

(15)

(16)

(4)最大发车时间间隔约束。同一方向发车时间间隔不得大于最大发车时间间隔，即

(17)

(18)

(5)列车在各站发车时间与始发时间的关系

由于τ(s1,su),τ(sm,su)分别表示列车在区段(s1,su),(sm,su)的旅行时间与车站su的停站时间之和，所以满足如下关系。

(19)

(20)

(6)无车场端车站sm列车接续约束。第i趟上行列车出发前，第i趟下行列车必须到达车站sm。由于τ(s1,sm)表示列车在区段(s1,sm)的旅行时间与车站sm的停站时间之和，rm为车站sm的折返作业时间，所以

(21)

(7)无车场端车站sm停车能力约束。第i趟下行列车到达车站sm之前，第i-Nm趟上行列车必须离开车站sm。由于τ(s1,sm)表示列车在区段(s1,sm)的旅行时间与车站sm的停站时间之和，rm为车站sm的折返作业时间，所以

(22)

(8)出行需求与列车始发时间的耦合。若按最小发车时间间隔发车，则列车最大断面载客量达到常规载客能力αC，但不超过最大载客能力C；否则，列车断面载客量不超过常规载客能力αC。即

(23)

(24)

(25)

(26)

以列车对数n最小化为优化目标函数，以上述关系式为约束条件，构建列车时刻表的优化模型为

minZ=n

(27)

s.t.

约束条件式(1)—式(26)。

4 列车时刻表优化算法

4.1 算法思想

将求解步骤分为3步：最大化首班车发车时间、最大化中间列车发车时间、终止条件。

(28)

(29)

对于下行方向，分别考虑以下3种情形。

3)终止条件

根据上述算法思想和相应步骤，设计模型式(1)—式(27)的求解算法。

4.2 列车最晚发车时间的双向关联序列化优化算法

开始

i←2,j←2；

开始1

i←i+1,j←j+1}；

j←j+1}；

返回1

i←i-1,j←j-1；

n←i；

结束。

5 列车周转方案优化方法

5.1 列车周转方案优化模型

车站s1始发的下行列车车次序集为{i|i=1,2,…,n}，终到的上行列车车次序集为{j|j=1,2,…,n}，列车周转问题就是要确定这2个方向列车车次的衔接关系。每1趟始发的下行列车，或者由此前到达的上行列车来担当，或者由来自车场p的列车来担当。我们采用指派问题描述列车周转问题。

借助于指派问题优化求解列车周转问题，就是优化{j|j=1,2,…,n}与{i|i=1,2,…,n}之间的指派M。指派满足以下限制：M⊂{(j,i)|j,i=1,2,…,n}， 对于任何(j,i), (j′,i′)∈M，满足若j=j′，则i≠i′；若i=i′，则j≠j′。对于任何j=1,2,…,n,i=1,2,…,n,定义指派费用cji如下。

(30)

式中：K为充分大的数，通常取K=24nh。

定义指派变量

(31)

可建立列车周转问题的指派模型为

(32)

s.t.

(33)

(34)

xji=0, 1j，i=1,2,…,n

(35)

指派模型的式(30)—式(35)以接续时间最小化为优化目标，等价于不可接续车次数量最小，全部列车运用小时数最小，进而列车车底数最小。

(36)

5.2 列车周转方案优化算法

匈牙利算法可以用来求解指派问题的最优解。采用匈牙利算法对建立的指派模型进行求解，算法分为以下2步。

第1步：用匈牙利算法求解指派问题最优解的方法求解最优指派方案M*。

6 算例分析

以北京市地铁5号线为例，对本文的方法进行验证。该线路上共23个车站，如图1所示，天通苑北—宋家庄为下行方向，天通苑北站有太平庄车辆段。列车在立水桥、大屯路东、惠新西街南口、雍和宫、东四、东单、磁器口、蒲黄榆站的停站时间为45 s，其它车站停站时间为30 s。区间运行时间参考首班列车各站发车时间与停站时间推算出，

图1 车站及区间运行时间(单位：s)

采用该线2014年某天的实际乘车O-D客流数据作为时变需求，篇幅所限，不详细列举。为了增加客流需求强度，将该O-D客流需求放大2倍作为算例的O-D客流需求。

利用优化方法求出列车运行计划如图2所示，图中车站s1与车站sm之间的线段为列车运行线，简略起见，没有标记沿途停站的时间信息。车站s1与车站sm外侧的折线表示列车的接续关系。车站s1外侧的实心箭头表示列车来自或返回车场，空心箭头表示列车在车场接续，以解决车站s1不满足停放能力N1的困难。D与数字的组合表示下行方向列车车次，U与数字的组合表示上行方向列车车次，为避免车次标记过于密集，车次标记间隔大约为10趟列车。

优化产生的列车运行计划，开行列车194对，需要列车62列，列车接续时间为850.36 min，往返车场124次。

从图2可以看出，在早晚高峰具有较密集的列车开行频率，发车时间间隔随着客流需求变化而变化，具有较平滑的变化规律。下面分别对折返站列车接续状态、发车时间间隔、主导方向成因分析如下。

1)折返站列车接续状态

为了分析折返站sm的列车接续状态，从图2可以看出：列车接续状态大体可分为3个阶段，第1阶段为立即折返，第2阶段为停车能力持续饱和，第3阶段为立即折返。

比较双向列车在折返站sm的始发终到时刻发现：

下行列车1至36与上行列车1至36均由立即折返的方式接续，即接续时间均为折返作业时间rm=2 min。下行列车37与上行列车37的接续时间超过折返作业时间rm，此后，接续时间不断增加，折返站sm开始停放暂时不需要的列车，停车能力饱和率越来越大。

图2 城轨线路列车运行计划示意图

上行列车44的发车，释放了折返站sm处于饱和的停车能力，保证下行列车46能够终到车站sm(依据如下：下行列车46的终到时间等于上行列车44的始发时间，但下行列车45的终到时间大于上行列车43的始发时间)。此后，折返站sm进入了停车能力持续饱和状态。

下行列车104的终到，终止了停车能力持续饱和状态(依据如下：下行列车104的终到时间略小于上行列车102的始发时间，但下行列车103的终到时间等于上行列车101的始发时间)。此后，车站sm的停车能力饱和率越来越小，进而变得完全不饱和，折返时间越来越短，直至下行列车112与上行列车112仍然不是按照立即折返的方式接续。下行列车113至194与上行列车113至194均由立即折返的方式接续。

立即折返与停车能力持续饱和分别表示不同方向的需求主导。立即折返意味着上行方向为主导方向，即上行方向按上行需求开行列车，下行方向为上行方向及时提供列车。折返站停车能力持续饱和意味着下行方向为主导方向，即下行方向按下行需求开行列车，上行方向为下行终到折返站而及时释放停车能力。

2)发车间隔时间

为了分析发车间隔时间，将上下行2个方向相邻列车发车间隔时间变化规律如图3所示。图中第i个蓝色菱形标记下行列车i与下行列车i+1的发车间隔时间，第j个红色加号标记上行列车j与上行列车j+1的发车间隔时间。

图3 列车运行间隔时间示意图

从图3可以看出：对于列车i=1,2,…,36，与列车i+1的发车间隔时间曲线，上下行方向的变化规律完全一致，只是下行方向提前了τ(s1,sm)+rm=53 min 5 s，这是由上行方向主导的原因所致。

上行方向在这一阶段的主导地位结束于下行列车37的终到，下行方向需求加大，发车间隔时间变小，下行列车发车间隔时间曲线出现了1个折点，但上行列车的发车间隔时间仍然在增加。直至上行列车43的终到，上下行分别按照各自需求确定发车间隔时间，密集到达、暂不需要的下行列车可以停放在折返站sm备用。

上行列车43与44的发车间隔时间有1个突变，就是图3中被圆圈所包围加号对应的孤立点，此时上行列车44必须发车，以释放折返站sm处于饱和的停车能力，保证下行列车46能够终到车站sm。此后上行列车i的发车时刻与下行列车i+2在折返站sm的终到时刻保持相等，体现了下行方向的主导地位，致使上行列车的发车间隔时间与下行列车的发车时间间隔保持一致。

下行方向在这一阶段的主导地位结束于下行列车104的终到，上行方向需求加大，发车间隔时间大幅下降，但下行列车的发车间隔时间仍然缓慢下降。直至下行列车112的终到，上下行分别按照各自需求确定发车间隔时间，上行列车出发较下行列车到达的列车缺额，由折返站sm停放的列车填补。

下行列车112与113的发车间隔时间有1个突变，就是图3中被圆圈所包围菱形符号对应的孤立点，此时下行列车113必须到达折返站sm，以立即折返的接续方式担当上行列车113，保证上行列车113能够准时始发。此后下行列车的发车间隔时间与上行列车的发车间隔时间保持一致，体现了上行方向的主导地位。

3)主导方向成因

各个阶段主导方向的成因与需求大小相关，与折返站没有车场也相关。折返站没有车场导致上行列车k比下行列车k的需求滞后约1 h，使得上下行需求大小必须进行错位比较。由此分析3个阶段的主导方向成因如下。

在第1阶段，下行列车更接近于早班低谷，上行列车更接近于早高峰，可见上行列车的需求更大一些，所以上行方向为主导方向。

在第2阶段，下行列车更接近于早高峰，上行列车更接近于中午低谷，可见下行列车的需求更大一些，所以下行方向为主导方向。

在第3阶段，阶段前期，下行列车更接近于中午低谷，上行列车更接近于晚高峰，可见上行列车的需求更大一些，所以上行方向为主导方向。阶段后期，由于上行方向晚高峰持续时间更长一些，所以一直保持上行方向为主导方向。在晚班期间，上下行列车都按照最大间隔时间τmax=15 min发车，自然也都是立即折返了。

综上所述，折返站列车接续状态、发车间隔时间和各阶段的主导方向成因都反映了列车运行计划具有显著的合理性，这得归功于结合客流分配和服务水平优化列车运行计划，使得列车运行计划与乘客出行需求的吻合度高，列车开行趟数和车底数量最小化。

7 结 论

(1)城轨线路列车运行计划优化问题可以描述为基于服务水平的列车时刻表和列车周转2阶段优化问题，最小化开行列车对数和列车车底数，优化有车场端列车接续关系。对于给定的列车时刻表，关于O-D时变需求的客流分配可以通过递推公式获得，由此可实现客流需求与列车时刻表的耦合。

(2)针对具有单一尽头车场的城轨线路，在无车场端的列车接续和停车能力约束下，结合O-D时变需求的客流分配，可采用序列化优化方法，分步实施最大化列车发车时间，实现双向列车时刻表关联优化。

(3)基于最优列车时刻表，将有车场端的列车周转问题描述为指派问题，一个指派模型可同时确定端点站的列车最优接续关系、往返于车场的列车。

(4)具有单一尽头车场的城轨线路的列车运行计划，上行方向发车间隔时间比下行方向发车间隔时间的变化规律滞后。在上行方向为主导的时间段，滞后稍大；在下行方向为主导的时间段，滞后稍小。