假设主动衔接方向为由线路换向线路,换乘路径的示意图如图1.

图1 主动衔接示意图
Fig.1 Active coordination of transfer connection direction

t^{(P, A)}_i,r=t⁽⁰⁾_i,l+sH_i,l+t^(T)_i,l→r(1)

其中, t⁽⁰⁾_i,l为在时间段T内,线路l上第1列列车到达车站的时间; t^(T)_i,l→r为乘客在车站i由线路l换向线路r所花费的步行时间.

同时,可得线路r上列车在车站的发车时间为

t^(D)_i,r=t⁽⁰⁾_i,r+uH_i,r+t^(S)_i,r(2)

其中, t⁽⁰⁾_i,r为在时间段T内,线路r上第1列列车到达车站i的时间; H_i,r为线路r上列车在车站i的开行间隔(发车间隔); t^(S)_i,r为线路r上列车在车站i的停站时间; u表示到达后的第几列列车, u≤T/(H_i,r)」.

乘客若要乘坐线路r上的衔接列车,则线路r上列车在车站i的发车时间需至少大于乘客经由线路l换乘到达线路r的时间, t^(P,A)_i,r≥t^(D)_i,r,即

t⁽⁰⁾_i,r+uH_i,r+t^(S)_i,r≥t⁽⁰⁾_i,l+sH_i,l+t^(T)_i,l→r(3)

整理可得

u≥(t⁽⁰⁾_i,l+sH_i,l+t^(T)_i,l→r-t⁽⁰⁾_i,r-t^(S)_i,r)/(H_i,r)(4)

考虑到理性乘客首选候车后第1趟到达的列车,则

u=「(t⁽⁰⁾_i,l+sH_i,l+t^(T)_i,l→r-t⁽⁰⁾_i,r-t^(S)_i,r)/(H_i,r)(5)

因此,第s列列车上乘客的换乘等待时间W_l→r(S)为

W_l→r(S)=t⁽⁰⁾_i,r+t^(S)_i,r+u(H_i,r)-

(t⁽⁰⁾_i,l+sH_i,l+t^(T)_i,l→r)(6)

综上,乘客在时间段T内由线路l换向线路r的平均换乘等待时间W^-_l→r为

W^-_l→r=1/(T/(H_i,l)」)∑^{T/(H_i,l)」}_s=1W_l→r(s)(7)

主动衔接方向为由线路l换向线路r, 相应被动衔接方向为线路r换向线路l, 对应的换乘示意图如图2.其平均换乘等待时间的计算方法与主动衔接平均等待时间的计算方法相类似.

图2 被动衔接示意图
Fig.2 Passive coordination of transfer connection direction

t^(P,A)_i,l=t⁽⁰⁾_i,r+s'H_i,r+t^(T)_i,r→l(8)

同时,可得线路l上列车在车站i的发车时间t^(D)_i,l为

t^(D)_i,l=t⁽⁰⁾_i,l+u'H_i,l+t^(S)_i,l(9)

其中, u'表示到达后的第几列列车, u'≤T/(H_i,l)」.

乘客若要乘坐衔接列车,则线路l上列车在车站i的发车时间需至少大于乘客经由线路r换乘到达线路l的时间, t^(P,A)_i,l≥t^(D)_i,l, 即

t⁽⁰⁾_i,l+u'H_i,l+t^(S)_i,l≥t⁽⁰⁾_i,r+s'H_i,r+t^(T)_i,r→l(10)

整理可得

u'≥(t⁽⁰⁾_i,r+s'H_i,r+t^(T)_i,r→l-t⁽⁰⁾_i,l-t^(S)_i,l)/(H_i,l)(11)

考虑到理性乘客第一选择始终是候车后第一趟到达的列车,因此

u'=「(t⁽⁰⁾_i,r+s'H_i,r+t^(T)_i,r→l-t⁽⁰⁾_i,l-t^(S)_i,l)/(H_i,l)(12)

则第s'列列车上乘客的换乘等待时间W_r→l(s')可以表示为

W_r→l(s')=t⁽⁰⁾_i,l+t^(S)_i,l+u'H_i,l-

(t⁽⁰⁾_i,r+s'H_i,r+t^(T)_i,r→l)(13)

乘客在时间段T内由线路r换向线路l的平均换乘等待时间W^-_r→l为

W^-_r→l=1/(T/(H_i,r)」)∑^{T/(H_i,r)」}_s'=1W_r→l(s')(14)

综合主动衔接和被动衔接两个平均换乘等待时间,在车站i的总换乘等待时间F为

F=f_i,l→r(T)W^-_l→r+f_i,r→l(T)W^-_r→l(15)

其中, f_i,l→r(T)为在时间段T内,在车站i中从线路l换向线路r的总客流量; f_i,r→l(T)为在时间段T内,在车站i中从线路r换向线路l的总客流量.

要求换乘车站i的主动衔接方向和被动衔接方向的衔接程度最优,即使得总平均换乘等待时间最小,需满足

minF_i=min{(f_i,l→r(T)W^-_l→r+f_i,r→l(T)W^-_r→l)/(f_i,l→r(T)+f_i,r→l(T))}(16)

s.t. H_min,l≤H_i,l≤H_max,l

H_min,r≤H_i,r≤H_max,r

0≤t⁽⁰⁾_i,l≤H_i,l

0≤t⁽⁰⁾_i,r≤H_i,r

其中, H_min,l和H_min,r表示列车开行间隔能取的最小值,其与线路折返能力、追踪能力有关; H_max,l和H_max,r表示列车开行间隔能取的最大值.

模型求解首先要得到按换乘客流量排序的全网络换乘衔接方向.得益于近来兴起的轨道交通自动售检票系统(automatic fare collection, AFC),我们可以获得大量乘客出行数据,进而获得在微观层面上量化的客流时空分布结果.具体使用方法为利用给出的路径清分比例表,分析计算指定日期和指定时间段的进出站AFC刷卡数据,可得每个时间点和每个车站上的客流量,随即获得该时段内各换乘站各换乘方向的客流量.将排序后的换乘站和换乘方向集合存储供后续步骤调用.

逐步优化目标可描述为:① 制定一个列车行车计划,使所有换乘站的所有换乘方向均能被接上,且网络所有换乘站的总换乘等待时间最小.根据排序好的换乘衔接方向,对换乘客流大的换乘衔接方向优先构建衔接计划,确定该方向列车开行间隔和首列列车到达时刻,并将该换乘方向进行标记; ② 按换乘客流大小依次将网络上所有换乘方向连接上.若该方向列车开行间隔和列车到达时刻已被标记,则无需改变它们; 若该方向列车开行间隔或列车到达时刻有其中一个未标记确定,则求解之.最终形成一个完整的列车行车计划.

换乘衔接求解中存在两种情况,一是主动衔接与被动衔接中4个变量(分别为列车开行间隔与列车到达间隔)均未知,或3个变量未知1个变量已知; 另一种是主动衔接与被动衔接中2个变量未知2个变量已知,或1个变量未知3个变量已知.从建立模型的公式可以看出,模型为弱约束最优化问题,当变量数量过多时(如情况一),将很难求出优化结果,此时通常采取启发式算法,本研究选取模拟退火算法求解; 而当变量数量少时(如情况二),为得到较优结果,可采用最优化理论求解,本研究选取一维线性搜索算法求解.

模拟退火算法源于固体退火原理^[12],将固体加温至足够高的温度,加温时固体内部分子随升温变为无序状呈现随机排列状态,而逐步降温时粒子渐趋有序.最后在常温时达到基态,内部分子以低能状态排列,固体达到某种稳定状态.

具体模拟退火算法步骤如下:

步骤1 设定初始温度值T₀, 初始状态解x, 计算其目标函数值E.

步骤2 内部循环.

1)产生一个随机干扰,得到新解x', 并计算其目标函数值E'.

2)计算内能增量ΔE, 若ΔE<0, 则接受新解x', 设新解为当前解x←x', 跳转步骤4),否则跳转步骤3).

3)若ΔE>0, 计算概率p=e^-ΔE/kT_i, 并随机生成一个0～1的均匀分布变量,用以判断是否接受新解,若接受则设新解为当前解x←x'; 否则保持原解x, 转步骤4).

4)若满足内循环终止条件,跳出内循环; 一般内循环终止条件取为连续若干个新解都没有被接受,即当前解保持不变若干次循环.

步骤3 外部循环.

1)判断当前温度T_i是否满足终止条件,即T_i→T_min, 其中, T_min为目标温度,若达到终止条件,则终止算法,输出当前解为最优解;

2)设置当前温度为T_i→T_i×ε, 其中, ε为温度衰减参数,一般设置为0.99或0.98,跳转步骤2开始内部循环.

本研究采用的一维线性搜索中“改进0.618法”来计算模型求解中未知变量少的情况二.0.618法(又称黄金分割法)是美国数学家KIEFER^[13]于1953年提出,属于分割法函数求极值方法,分割类方法仅需计算函数值,因此使用范围较广,尤其适用于非光滑及导数表达式复杂或写不出等情形.改进0.618法是针对目标函数是单峰函数,也就是目标函数为凸的情形的分割类方法,因其不要求函数可微,且每次迭代只需计算1个函数值,程序简单容易实现而被广泛采用.由于黄金分割法是以等比例0.618分割缩小区间的,因此,针对在实际问题中遇到的目标函数往往不是单峰函数的情况,它是一种近似最优方法.

按照换乘站换乘客流大小进行排序,可得如表1的换乘衔接方向.

表1 平峰时期排序后换乘衔接方向示例
Table 1 Examples of transfer connection direction ordered by passenger flow during flat period

利用C#.Net程序语言对本节提出的模型与算法进行编程求解,按排序后的换乘衔接方向对换乘站换乘方向进行衔接优化,优化后进行标号,并依次处理余下换乘衔接方向,直至所有换乘衔接方向均已优化.优化过程如图4,其表示随程序求解步骤的推进,当前状态下网络平均换乘等待时间的改变程度.图中x轴表示程序求解步骤,即当前计算到排序后换乘衔接方向的顺序; y轴表示当前网络中已确定的模型决策变量数,包括列车开行间隔和首列到达时刻.图中数据散点圆的半径大小表示当前状态下网络平均换乘等待时间.数据点的大小随求解步骤的推移先增后减,说明随着换乘衔接方向的不断优化,乘客的平均换乘等待时间越来越优.

需指出,在图4程序求解步骤的后期,出现较长时间空白,原因在于该迭代时间点,换乘衔接的变量均在前面的求解步骤中被标定过,此步骤中无决策变量可求解,因此出现该数据点上的空白.

图4 求解代数-平均等待时间图
Fig.4 Diagram of solving steps and average passenger waiting time

最终获得所有换乘站换乘方向的衔接方案结果如表2.可见,平峰时段上海轨道交通1、2、4、5及11号线,由于存在换乘客流大的换乘站,其列车开行间隔优先得到衔接满足,而3、12、13及16号线,由于其中的换乘站客流较小,其列车开行计划主要用于衔接其他线路.此外,表2还显示,平峰时段线路上下行的列车开行间隔均保持相同,并且多条线路的开行间隔由于换乘衔接关系的密切,列车开行间隔呈相同或倍数的关系.同理,几个重要的换乘站首列到达时刻如表3.

表2 优化后各线路开行间隔
Table 2 Train interval of metro lines after optimizations

表3 优化后各换乘站首列列车到达时间示例
Table 3 First train arrival time of metro lines after optimizations

本文研究时段为平峰时间段13:00—15:00,共计2 h,经计算共有换乘客流226 726人次,在未衔接优化之前,各线独立运营,未考虑相互之间的衔接关系,乘客的平均换乘等待时间为128.9 s.经优化衔接后,乘客的平均换乘等待时间为93.9 s,较之前平均减少换乘等待时间约27.1%,优化后的网络整体衔接效果较之前有一定提升.由此可见,通过调整线路间的换乘衔接关系,优化城市轨道交通网络整体衔接程度,可使乘客的平均换乘等待时间缩短,提升乘客出行效率,为网络上的出行乘客提供优质的客运服务.