基于节点重要度的城市轨道交通线网换乘协调优化

Transfer Coordination Optimization of Urban Rail Transit Network Based on Node Importance

摘要

随着城市轨道交通规模扩大，车站数量增加，线间关联愈加密切。在网络化运营条件下，网络结构的复杂性、客流需求分布的不均衡性及列车运行组织方式的多样性，均对城市轨道交通运输计划提出更高的要求，在此提出基于节点重要度的城市轨道交通线网换乘优化方法。基于乘客出行选择行为对路径广义出行费用进行计算，建立基于时空出行网络的客流分配模型；依据影响城市轨道交通节点重要度的因素，提出网络内各区间及线路重要度的计算方法，基于线网内各节点、区间及线路的差异，构建基于节点重要度的城市轨道交通换乘协调优化模型；以成都地铁局部网络为例，验证模型的有效性。结果表明：所提出的协调优化模型将网络内站点、区间及线路3个层面的匹配度总共提升了34.58%，有效地提高了线网运输计划的运营效率。

Abstract

With the rapid development of the scale of urban rail transit networks, the number of stations is expanding, and the connection between lines is becoming closer. Under the condition of network operation, higher requirements for urban rail transit transportation plans have been put forward due to the complicated network structure, the imbalanced passenger flow demand distribution, and the diversified train operation organization mode. Therefore, this paper proposed a transfer optimization method for urban rail transit line networks based on node importance. Firstly, based on passengers' travel choice behaviors, the paper calculated the generalized travel cost of the path and built a passenger flow distribution model based on the spatiotemporal travel network. Secondly, based on factors affecting the importance of urban rail transit nodes, the paper established the calculation method for the importance of each section and line within the network. According to the differences between the nodes, sections, and lines in the network, it constructed an optimization model of urban rail transit transfer coordination based on the importance of nodes. Finally, the paper verified the model effectiveness by calculating the data from the local network of Chengdu Metro as an example. The results show that the proposed coordination optimization model improves the matching degree of the three levels of stations, sections, and lines in the network by 34.58% in total, which effectively improves the operation efficiency of the network transportation plan.

Graphical abstract

关键词

城市轨道交通网络 / 节点重要度排序 / 时变客流需求匹配 / 换乘衔接优化 / 遗传算法

Key words

Urban Rail Transit Network / Node Importance Ranking / Time-varying Passenger Flow Demand Matching / Transfer Connection Optimization / Genetic Algorithm

0　引言

伴随各地轨道交通线路的不断蔓延，城市轨道交通网络内各站点、区间及线路的重要度差异逐渐增大，而在运输计划的针对性研究中，基于节点重要度的城市轨道交通模型设计研究是提升网络整体效益的关键。因此，从网络内不同层面出发，提出基于重要度排序的线网运输计划优化方法对时变客流需求进行匹配具有重要意义。

针对此类问题，国内外学者进行了诸多研究。现有关于线网运输计划的优化目标通常为最大限度地减少乘客的延误时间或等待时间^[1]和最小化运营成本及列车能源消耗^[2-3] 2方面，优化方向包括换乘衔接优化及首末班车衔接优化^[4-6]。Eva等^[7]以最小化乘客平均等待时间为目标，提出分支切割算法对模型进行求解。Yuan等^[8]分析容量约束对列车运行的影响，建立混合ILP (MILP)模型最小化乘客的总等待时间。Wang等^[9]对时变客流需求下的列车调度及车辆周转进行一体化优化，提出迭代非线性规划(INP)方法求解。Mo等^[10]从服务质量及运营成本2方面出发构建混合整数非线性模型优化列车运行过程。Wandelt等^[11]的实验表明，现有的基于复杂网络的简化往往低估了节点重要度的影响，并且存在显著的排名不匹配。Zhu等^[12]的实验表明了节点重要度对于线网预测的重要性。Xu等^[13]提出在地铁站客流需求不确定条件下的优化模型，通过遗传算法控制高峰时段的客流。胡映月等^[14]基于客流传播模型得到的数据对节点进行评价；叶营仓^[15]研究站点在遭受破坏后的运输能力的降低来评估节点重要度。胡钢等^[16]综合节点局部重要度和全局属性指标评价节点重要度。况瑢^[17]在考虑列车容量约束的情况下，设计列车与客流的匹配算法。孙梦霞等^[18]以企业运营成本及乘客出行费用之和最小为目标，对列车的发车间隔及时刻进行优化。史丰收等^[19]通过建立换乘衔接方案编排优化模型，在网络层面实现基于线网整体换乘等待时间动态最优的换乘站衔接时刻优化。

整体而言，在现有网络换乘协调优化研究中，鲜有研究对网络中换乘站、区间及线路的重要度进行区分，忽略了优化对象的优先级处理，容易出现关键节点处衔接结果不佳的现象。因此，提出线网运输计划优化方法，从节点、区间及线路3个层面实现定量评价，同时，以评价结果为依据从节点、区间及线路各个层面出发建立基于不同层面内各元素重要度排序的线网运输计划优化模型。该方法充分考虑线网内各节点、区间及线路的重要度差异，优化时提高关键节点协调优先级，构建基于关键换乘站、关键区间及关键线路的线网运输计划优化模型，并设计遗传算法进行求解。最后，以成都地铁为例构建局部网络，对提出的模型进行实例验证。

1　换乘协调优化模型建立

1.1　模型假设

为了便于问题研究，对网络条件提出以下假设。

（1）线路换乘站在各方向的换乘客流量已知。

（2）在研究时段内，客流需求总量不变且服从均匀到达。

（3）在研究时段内，各线路列车采取均衡发车方式运行。

（4）换乘客流呈脉冲性到达，不考虑乘客走行速度的差异，取平均换乘走行时间。

（5）列车容量充足，不存在因列车容量不足而导致乘客滞留站台的情况。

1.2　符号说明

符号及定义如表1所示。

1.3　目标函数

当\mathrm{\S }{(i)}_{lh(x)}^{pq(y)}=1时，线路l在h方向的x列车与线路p在q方向的y列车接续成功；当\mathrm{\S }{(i)}_{lh(x)}^{pq(y)}=0，线路l在h方向的x列车与线路p在q方向的y列车接续失败。

⑴

1.3.1　节点层面

节点层面的优化以时段内各班次列车在不同换乘站各衔接方向的整体换乘候车时间匹配度最佳为目标。线路l在h方向的x列车在换乘站i换乘到线路p在q方向的y列车的换乘站候车时间为

T{(i)}_{lh(x)}^{pq(y)}=D{(i)}_{pq}^{(y)}-\left(A{(i)}_{lh}^{(x)}+t{(i)}_{lh}^{pq}\right)⑵

采用降半梯度分布函数对换乘候车时间进行模糊处理，即

⑶

式中：W_a 为乘客的理想换乘候车时间；W_b 为乘客可容忍的最大换乘候车时间；\theta {(i)}_{lh(x)}^{pq(y)}为线路l在h方向上的x列车在换乘站i内接续线路p在q方向的y列车时车站i的站点匹配度。

换乘站i所有换乘方向对应的节点匹配度值为

T\text{'}\left(i\right)=\sum _{p\in L} \sum _{l\in L} {\displaystyle \sum _{q=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{h=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{y=\mathrm{1}}^{n_{pq}}} {\displaystyle \sum _{x=\mathrm{1}}^{n_{lh}}} \theta {(i)}_{lh(x)}^{pq(y)}·\mathrm{\S }{(i)}_{lh(x)}^{pq(y)}⑷

以换乘站重要度排序结果作为权重，以网络内所有换乘站的加权匹配度最优为节点优化目标，即

F\mathrm{1}=\mathrm{m}\mathrm{a}\mathrm{x}\sum _{i\in U} T\text{'}\left(i\right)·\partial \left(i\right)⑸

1.3.2　区间层面

区间层面以研究时段内网络上各班次列车经过各个区间的运力供给与客流需求的匹配度最佳为目标。

（1）列车区间运力水平。

线路l在h方向的x次列车在区间e的运力水平N_{lh(x)}^e为

N_{lh(x)}^e=C_{lh}\left({\alpha }_{\mathrm{m}\mathrm{a}\mathrm{x}}-{\alpha }_{lh(x)}^e\right)+G_{lh(x)}^e⑹

线路l在h方向的x次列车到达区间e时的下车人数为

G_{ij(x)}^e=\sum _{p\in L} {\displaystyle \sum _{q=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{y=\mathrm{1}}^{n_{pq}}} \mathrm{Q}{\left(i\right)}_{lh\left(x\right)}^{pq\left(y\right)}+O_{lh(x)}^e⑺

（2）区间客流需求。

假设列车容量无限，在t_a至t_b时段内的进站客流量为

U_{lh(x)}^{\left(t_a,t_b\right)}={\lambda }^{lh}\left(t_b-t_a\right)⑻

线路l在h方向的x次列车在区间e的换入客流V_{lh(x)}^{\mathrm{e}}为网络内各线的换入客流量之和

V_{lh(x)}^{\mathrm{e}}=\sum _{p\in L} {\displaystyle \sum _{q=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{y=\mathrm{1}}^{n_{pq}}} \mathrm{Q}{\left(i\right)}_{lh\left(x\right)}^{pq\left(y\right)}\mathrm{\S }{\left(i\right)}_{lh\left(x\right)}^{pq\left(y\right)}⑼

线路l在h方向的x次列车在区间e客流需求为

W_{lh(x)}^e=\left\{\begin{array}{c}{U}_{lh\left(x\right)}^{\left(t_{start},D_{ij(\mathrm{1})}^e\right)}+V_{lh(x)}^{\mathrm{e}}x=\mathrm{1}\\ U_{lh\left(x\right)}^{\left(D_{lh\left(x-\mathrm{1}\right)}^e,D_{lh\left(x\right)}^e\right)}+V_{lh\left(x\right)}^{\mathrm{e}}x=\mathrm{2,3},\dots ,n_{lh}\end{array}\right.⑽

则线路l在h方向的x次列车在区间e的匹配度为

{\theta }_{lh(x)}^{\mathrm{e}}=\frac{N_{lh(x)}^e}{W_{lh(x)}^e}⑾

线路l在h方向的区间匹配度为研究时段内该线路方向上所有班次列车在换乘区间的匹配度之和，即

F_{lh}^{\mathrm{e}}={\displaystyle \sum _{x=\mathrm{1}}^{n_{lh}}} \left|{\theta }_{lh(x)}^{\mathrm{e}}-\mathrm{1}\right|⑿

以优化区间对应的重要度设置区间权重，以网络内整体区间的加权匹配度最优为区间优化目标，即

F\mathrm{2}=\mathrm{m}\mathrm{i}\mathrm{n}\sum _{l\in L} {\displaystyle \sum _{h=\mathrm{1}}^{\mathrm{2}}} F_{lh}^{\mathrm{e}}·l\left(e\right)=\sum _{l\in L} {\displaystyle \sum _{h=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{x=\mathrm{1}}^{n_{lh}}} \left|{\theta }_{lh(x)}^{\mathrm{e}}-\mathrm{1}\right|·l\left(e\right)⒀

1.3.3　线路层面

线路层面的优化以线路评价指标为基础，即研究时段内各线路上各列车的整体运力利用度最佳作为线路层面的优化目标。

线路l在h方向的x列车的跨线客流K_{lh}^{(x)}为网络内各线的换入客流量之和

K_{lh}^{(x)}=\sum _{p\in L} {\displaystyle \sum _{q=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{y=\mathrm{1}}^{n_{pq}}} Q{\left(i\right)}_{lh\left(x\right)}^{pq\left(y\right)}\mathrm{\S }{\left(i\right)}_{lh\left(x\right)}^{pq\left(y\right)}⒁

线路l在h方向的x列车的运力利用度计算公式为

M_{lh}^{(x)}=\frac{K_{lh}^{(x)}+B_{lh}^{(x)}}{d_l}⒂

采用升半梯度分布函数对线路运力利用度进行模糊处理，线路l在h方向的x列车的线路匹配度{\theta }_{lh(x)}^l为

⒃

式中：M_a为可容忍的最低线路列车客流密度；M_b为期待的理想线路列车客流密度。

线路l上下行方向的所有列车对应的运力匹配度M\left(l\right)为

M\left(l\right)={\displaystyle \sum _{h=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{x=\mathrm{1}}^{n_{lh}}} {\theta }_{lh(x)}^l⒄

以网络内各线路对应的重要度设置线路权重，网络内各线路的加权匹配度最优为线路优化目标，即

F\mathrm{3}=\mathrm{m}\mathrm{a}\mathrm{x}\sum _{l\in L} M\left(l\right)·\zeta \left(l\right)=\sum _{l\in L} {\displaystyle \sum _{h=\mathrm{1}}^{\mathrm{2}}} {\displaystyle \sum _{x=\mathrm{1}}^{n_{lh}}} {\theta }_{lh(x)}^l·\zeta \left(l\right)⒅

从节点、区间及线路3个层面的优化目标出发对线网运输计划协调优化的总目标为

F=F\mathrm{1}+F\mathrm{2}+F\mathrm{3}⒆

1.4　约束条件

（1）列车到发时间关系。同一线路的相邻两列车应满足到发时间限制，线路p在q方向的列车在各换乘站的停站约束为

D{(i)}_{pq}^{(x)}-A{\left(i\right)}_{pq}^{\left(x\right)}=W{\left(i\right)}_{pq}^{\left(x\right)}p=\mathrm{1}，\mathrm{2}，\dots ，L;q=\mathrm{1}，\mathrm{2}⒇

（2）各线路列车离站时间关系。线路上同一方向的任意列车在各换乘站的离站时刻可根据协调时段内第一班列车离站时刻D{(i)}_{pq}^{(\mathrm{1})}确定。

D{(i)}_{pq}^n=D{(i)}_{pq}^{(\mathrm{1})}+(n-\mathrm{1})h_{pq}

（3）协调时段约束。线路首班车在各个换乘站的离站时刻应大于t_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}，线路最后一班车的离站时刻应小于t_{\mathrm{e}\mathrm{n}\mathrm{d}}，最后一班车的离站时刻与结束时刻的差不能大于线路列车发车间隔。

t_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}\le D{(i)}_{pq}^{(\mathrm{1})}\le t_{\mathrm{s}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{t}}+h_{pq}

D{(i)}_{pq}^{(\mathrm{1})}+\left(n_{pq}-\mathrm{1}\right)·h_{pq}\le t_{\mathrm{e}\mathrm{n}\mathrm{d}}

D{(i)}_{pq}^{(\mathrm{1})}+n_{pq}·h_{pq}>t_{\mathrm{e}\mathrm{n}\mathrm{d}}

（4）发车间隔约束。各线路上两相邻列车在换乘站的出发及到达时刻应该满足安全发车间隔的要求。

h_{pq}^{\mathrm{m}\mathrm{i}\mathrm{n}}\le D{\left(i\right)}_{pq}^{\left(x+\mathrm{1}\right)}-D{\left(i\right)}_{pq}^{\left(x\right)}\le h_{pq}^{\mathrm{m}\mathrm{a}\mathrm{x}}

D{(i)}_{pq}^{(\mathrm{1})}+\left(n_{pq}-\mathrm{1}\right)·h_{pq}\le t_{\mathrm{e}\mathrm{n}\mathrm{d}}

D{(i)}_{pq}^{(\mathrm{1})}+n_{pq}·h_{pq}>t_{\mathrm{e}\mathrm{n}\mathrm{d}}

（5）列车在相邻换乘站间的到发关系。属于同一线路的其余换乘站b的首班列车发车时刻可由下式得出，同时，根据发车间隔可计算各列车在该换乘站的发车时刻。

D{\left(b\right)}_{pq}^{\left(\mathrm{1}\right)}=\left(D{\left(i\right)}_{pq}^{\left(\mathrm{1}\right)}+R_{ib}\right)\mathrm{m}\mathrm{o}\mathrm{d}{h}_{pq}

D{\left(b\right)}_{pq}^{\left(x\right)}=D{\left(b\right)}_{pq}^{\left(\mathrm{1}\right)}+(x-\mathrm{1})h_{pq}

（6）换乘站列车衔接关系。为了保证不同线路方向的列车在换乘站i衔接成功，有

式中：M为无穷大的正数。

2　算法设计

根据线网不同层面内各个元素的重要度排序设置权重。考虑到遗传算法计算过程简便、求解精确，在迭代过程中更有可能出现全局最优解，故采用遗传算法进行求解。

2.1　重要度排序

（1）城市轨道交通节点重要度排序。

①最优路径指研究时段内乘客出行成本最小的路径，即广义出行费用最低的路径，广义出行费用C_k^{rs}计算公式为

C_k^{rs}=\sum _{u\in U} T_{t_{\mathrm{1}},t_{\mathrm{2}}}^{l^j,u}·{\delta }_{u,k}^{rs}+\sum _{v\in V} \epsilon ·T_{t_{\mathrm{1}},t_{\mathrm{2}}}^{v,l_{\mathrm{1}}^i,l_{\mathrm{2}}^j}·{\delta }_{v,k}^{rs}{t}_{\mathrm{1}},t_{\mathrm{2}}\in T；k\in K_{rs}

式中：T_{t_{\mathrm{1}},t_{\mathrm{2}}}^{l^j,u}为运行弧u\left(v_{t_{\mathrm{1}}}^{l^j},s_{t_{\mathrm{2}}}^{l^j}\right)上消耗的时间；{\delta }_{u,k}^{rs}为时空弧u与时空路径k的关联系数；K_{rs}为时空节点r-s间有效路径集合；\epsilon为换乘惩罚系数； T_{t_{\mathrm{1}},t_{\mathrm{2}}}^{v,l_{\mathrm{1}}^i,l_{\mathrm{2}}^j}为换乘弧u\left(v_{t_{\mathrm{1}}}^{l_{\mathrm{1}}^i},v_{t_{\mathrm{2}}}^{l_{\mathrm{2}}^j}\right)上消耗的时间；{\delta }_{v,k}^{rs}为时空节点v与时空路径k的关联系数。

②节点间信息传播阻抗值为节点间最优路径对应的出行时间费用，节点I_i与I_j间的信息传播阻抗值B_{ij}为

B_{ij}=C_{k\mathrm{\text{'}}}^{ij}i,j\in I；k\mathrm{\text{'}}\in K_{ij}

式中：C_{k\mathrm{\text{'}}}^{ij}为节点I_i与I_j间最优路径k\mathrm{\text{'}}对应的出行费用。

③信息传输能力从两节点间有效路径数目、传播阻抗、客流量3方面定义。节点I_i与I_j间信息传播效率值P_{ij}为

P_{ij}=\frac{q_{ij}}{B_{ij}}·N_{ij}\hspace{0.25em}i,j\in I

式中：q_{ij}为节点I_i与I_j间的客流量；N_{ij}为节点I_i与I_j间有效路径数目。

选取度(k_i)、连接强度(c_i)、节点介数(s_i)及加权节点介数(x_i)4个评价指标衡量二维节点属性，对所有属性指标进行归一化处理，得到节点指标矩阵T_c^{\mathrm{\text{'}}}，网络节点I_i的重要度S_i的计算模型如下。

S_i=F_c^{\mathrm{T}}{T}_c^{\mathrm{\text{'}}}w=\left[\begin{array}{cccc}\mathrm{1}& P_{\mathrm{21}}& \cdots & P_{n\mathrm{1}}\\ P_{\mathrm{12}}& \mathrm{1}& \cdots & P_{n\mathrm{2}}\\ ⋮& ⋮& & ⋮\\ P_{\mathrm{1}n}& P_{\mathrm{2}n}& \cdots & \mathrm{1}\end{array}\right]\times \left[\begin{array}{cccc}k{\mathrm{\text{'}}}_{\mathrm{1}}& c{\mathrm{\text{'}}}_{\mathrm{1}}& s{\mathrm{\text{'}}}_{\mathrm{1}}& x_{\mathrm{1}}^{\mathrm{\text{'}}}\\ k{\mathrm{\text{'}}}_{\mathrm{2}}& c{\mathrm{\text{'}}}_{\mathrm{2}}& s{\mathrm{\text{'}}}_{\mathrm{2}}& x_{\mathrm{2}}^{\mathrm{\text{'}}}\\ ⋮& & & ⋮\\ k{\mathrm{\text{'}}}_n& c{\mathrm{\text{'}}}_n& s{\mathrm{\text{'}}}_n& x_n^{\mathrm{\text{'}}}\end{array}\right]\times \left[\begin{array}{c}{\omega }_{\mathrm{1}}\\ {\omega }_{\mathrm{2}}\\ {\omega }_{\mathrm{3}}\\ {\omega }_{\mathrm{4}}\end{array}\right]=\left[\begin{array}{c}{s}_{\mathrm{1}}\\ s_{\mathrm{2}}\\ ⋮\\ s_n\end{array}\right]

式中：F_c为节点间的传输效率矩阵；T{\mathrm{\text{'}}}_c表示归一化节点属性指标矩阵；w=[{\omega }_{\mathrm{1}},{\omega }_{\mathrm{2}},{\omega }_{\mathrm{3}},{\omega }_{\mathrm{4}}{]}^{\mathrm{T}}表示上述4个特征属性的权重值，{\displaystyle \sum _j^{}}{w}_j=\mathrm{1}。

（2）城市轨道交通区间重要度排序。提出区间客流介数及节点影响指数来衡量影响区间重要度的因素。

①区间客流介数(L_e)。定义区间客流介数L_e表示网络中经过二维物理区间E_e的最优路径所对应的路径客流量与所有最优路径上客流总量的比值，即

L_e=\frac{\sum _{r\ne \mathrm{s}} (f_{k^{\mathrm{\text{'}}}}^{rs}·{\delta }_{e,k^{\mathrm{\text{'}}}}^{rs})}{\sum _{r\ne \mathrm{s}} f_{rs}^k\mathrm{\text{'}}}r,s,v\in I;e\in E

式中：f_{rs}^{k\mathrm{\text{'}}}为节点I_r与节点I_s间最优路径k\mathrm{\text{'}}分配的路径客流量。

②节点影响指数(I_e)。定义节点影响指数I_e表示二维物理区间E_e所连接节点的重要度均值，即

I_e=\frac{\sum _i (S_i·{\delta }_{ie})}{\sum _i {\delta }_{ie}}i\in I;e\in E

式中：S_i为节点I_i的重要度值；{\delta }_{ie}为节点I_i与区间E_e间的关联系数，节点I_i与区间E_e相连时，{\delta }_{ie}的值为1，否则为0。

③区间重要度指数(S_e)的计算公式为

S_e={\omega }_{L_e}·L_e^{\mathrm{\text{'}}}+{\omega }_{S_e}·I_e^{\mathrm{\text{'}}}

式中：{\omega }_{L_e}为区间客流介数L_e的指标权重；L_e^{\mathrm{\text{'}}}为区间客流介数指标的归一化值；{\omega }_{S_e}为节点影响指数I_e的指标权重；I_e^{\mathrm{\text{'}}}为节点影响指数的归一化值。

（3）城市轨道交通线路重要度排序。

以属于同一线路上的节点及区间重要度均值作为衡量线路重要度的依据。线路重要度S_l的计算公式为

S_l={\omega }_{S_i}·\frac{\sum _i (S_i·{\delta }_{il})}{\sum _i {\delta }_{il}}+{\omega }_{S_e}·\frac{\sum _e (S_e·{\delta }_{el})}{\sum _e {\delta }_{el}}

式中：{\omega }_{S_i}为节点重要度权重；{\omega }_{S_e}为区间重要度权重；{\delta }_{il}为节点I_i与线路L_l间的关联系数；{\delta }_{el}为区间E_e与线路L_l间的关联系数。

2.2　遗传算法设计

（1）个体编码设计。染色体编码示意如表2所示。

（2）初始种群的生成。

\mathrm{步骤}\mathrm{1}：在[\mathrm{0},H_{\mathrm{m}\mathrm{a}\mathrm{x}}]间产生随机数D{(a)}_{pq}^{(\mathrm{1})}。

\mathrm{步骤}\mathrm{2}：列车在第2个换乘站发车时刻D{(b)}_{pq}^{(\mathrm{1})}的取值范围为[D{(a)}_{pq}^{(\mathrm{1})}+R_{ab}-\mathrm{\Delta }T,D{\left(a\right)}_{pq}^{\left(\mathrm{1}\right)}+R_{ab}+\mathrm{\Delta }T]。

\mathrm{步骤}\mathrm{3}：重复第2步。直到生成初始列车在换乘站的发车时刻。

\mathrm{步骤}\mathrm{4}：线路发车间隔h_{ij}应该在[H_{\mathrm{m}\mathrm{i}\mathrm{n},}{H}_{\mathrm{m}\mathrm{a}\mathrm{x}}]之间随机产生。

\mathrm{步骤}\mathrm{5}：重复以上4步，直至线网内所有列车均生成在各换乘站的发车时刻及发车间隔，重复上述步骤，当个体数量到达种群规模，完成初始化过程。

（3）交叉。

\mathrm{步骤}\mathrm{1}:在第g代种群中随机选取父代个体T_A^g和T_B^g，随机选取染色体中的第p(\mathrm{1}\le g\le n_q)个基因位进行交叉。

\mathrm{步骤}\mathrm{2}：产生一个范围在[0，1]之间的随机数\kappa，其中\kappa \in [\mathrm{0,1}]。

\mathrm{步骤}\mathrm{3}：以p_c的交叉概率对父体的第p个交叉点进行算术交叉操作，得到g+\mathrm{1}代个体在第p个交叉点的基因。

S_l={\omega }_{S_i}·\frac{\sum _i (S_i·{\delta }_{il})}{\sum _i {\delta }_{il}}+{\omega }_{S_e}·\frac{\sum _e (S_e·{\delta }_{el})}{\sum _e {\delta }_{el}}

（4）变异。

\mathrm{步骤}\mathrm{1}：在种群中随机选取父代个体T_C：[t_{i\mathrm{1}}，t_{i\mathrm{2}},t_{i\mathrm{3}},\cdots ,t_{i(p-\mathrm{1})},t_{ip},\cdots ,t_{in}]，选取一个基因位进行变异，如选择T_C中的t_{ip}(\mathrm{1}\le p\le n_q)作为变异点，根据基因位置确定变异范围，若该变异点为线路发车间隔点，则t_{ip}的变异范围为[H_{\mathrm{m}\mathrm{i}\mathrm{n},}{H}_{\mathrm{m}\mathrm{a}\mathrm{x}}]；若该变异点为换乘站的发车时刻点，则t_{ip}的变异范围为[\mathrm{0}，H_{pq}]。

\mathrm{步骤}\mathrm{2}：产生一个范围在[\mathrm{0,1}]之间的随机数r，其中r\in [\mathrm{0,1}]。

\mathrm{步骤}\mathrm{3}：以p_m的概率对父体变异点t_{ip}进行均匀变异操作。

（5）算法终止。当种群迭代次数达到P时，输出计算结果。线网运行图优化模型算法示意图如图1所示。

3　线网换乘优化模型应用

3.1　线网数据输入

（1）线网基础数据。考虑到信息搜集及数据处理的难度，在此选取成都地铁1号线、3号线及4号线构成局部线网进行分析研究，前文提出的模型及算法同样适用于整体线网的评价与研究。根据选取的局部线网，构建网络拓扑结构图如图2所示，简化交通网络图如图3所示，图3显示了研究时段(14：00—15：00)内各线路上下行方向列车在各换乘站间的运行时间，研究时段内涉及的线网重点区间运行时间及停站时间均从成都地铁实际运行图中提取，线路运行参数如表3所示。

（2）节点换乘客流及重要度数据。根据线网时段配流结果，将同一方向的换乘客流在各车次均衡分配，得到各换乘站在不同接续方向的车次换乘客流量。研究时段内换乘站各接续方向换乘客流如图4所示。

根据重要度排序可得到换乘站权重如表4所示。

（3）区间进出站客流及重要度数据。区间层面数据根据AFC刷卡记录得到，进出站客流量如表5所示。

（4）线路客流及重要度数据。根据AFC刷卡数据得到研究时段内各线路上下行方向的客流量，线路客流量如表6所示。

（5）遗传算法参数及变量设置。在参数取值范围内对交叉及变异的概率取值进行不同情况的组合试验，发现当将交叉取值为 0.8，变异概率取值为 0.15时，可使对应的目标函数达到最佳取值，个体染色体编码如表7所示。

3.2　线网换乘协调优化结果

根据构建的模型和算法，对线网协调优化模型求解，得到计算迭代图如图5所示。

保证研究时段内列车数量不变的前提下，得到调整后各线路列车在首个换乘站的发车时刻表。优化后线网列车时刻表如表8所示。

3.3　优化结果对比分析

（1）节点层面。

省体育馆列车到发时刻表如表9所示。

骡马市列车到发时刻表如表10所示。

市二医院列车发车时刻表如表11所示。

调整后的网络换乘总时间由原来3 710 531 s减少到2 782 810 s，其中省体育馆减少73 h；骡马市减少34 h；市二医院减少151 h，总共节省258 h，提出的线网协调优化模型将网络内所有乘客的换乘候车总时间减少25.01%，节点层面的加权匹配度提升17.51%。

（2）区间层面。区间层面的优化结果显示优化后的综合加权区间匹配度提升了5.10%，区间层面优化结果如表12所示。

（3）线路层面。线路层面的优化结果显示各条线路的加权匹配度均有不同程度的提升，线路层面的综合加权匹配度提高了11.97%，线路层面优化结果如表13所示。

优化后的线网运输计划在各层面的匹配度均有不同程度的提高，在考虑节点、区间及线路重要度的情况下，各层面的匹配度分别提高了17.51%，5.10%及11.97%，调整后的线网运输计划将网络内所有层面的运力供给与客流需求的总匹配度提升了34.58%，具有一定的优化效果。

4　结束语

考虑网络内各车站、区间及线路的重要度差异，基于节点客流信息传输效率矩阵构建线网节点、区间及线路重要度排序模型。在保证运营成本不变的条件下，以列车到发时间、线路运行衔接及协调时段等为约束，以网络内节点、区间及线路3个层面的匹配度最佳为优化目标，提出网络换乘协调优化模型对线网内所有线路在不同方向的发车时刻及发车间隔进行优化。并在模型中引入关键线路、区间及换乘站的重要度权重配比，设计遗传算法进行求解。最后，以成都地铁局部线网为例，验证了模型在协调优化网络内各线路衔接状态的有效性。不足之处，一是构建时空出行网络的换乘弧时仅考虑了乘客在换乘站内的平均走行时间，而在实际出行过程中，乘客在换乘站内走行时间存在差异，导致从同一列车下车的乘客对应着不同的接驳列车，因此，在同一时空节点处换乘弧并非唯一固定的；二是对网络内各线路列车进行衔接优化时仅针对换乘衔接进行优化，没有考虑首末班车间的衔接等优化方向，后续研究应当充分考虑运行衔接优化的多种情形。

参考文献

[1] NIU H， ZHOU X， GAO R. Train Scheduling for Minimizing Passenger Waiting Time with Time-Dependent Demand and Skip-Stop Patterns：Nonlinear Integer Programming Models with Linear Constraints[J]. Transportation Research Part B，2015，76(6)：117-135.

[2] SUN H， WU J， MA H，et al. A Bi-Objective Timetable Optimization Model for Urban Rail Transit Based on the Time-Dependent Passenger Volume[J]. IEEE Transactions on Intelligent Transportation Systems，2018(2)：1-12.

[3] YIN J， YANG L， TANG T，et al. Dynamic Passenger Demand Oriented Metro Train Scheduling with Energy-Efficiency and Waiting Time Minimization：Mixed-integer Linear Programming Approaches[J]. Transportation Research Part B：Methodological，2017，97(3)：182-213.

[4] KANG L， WU J， SUN H，et al. A Case Study on the Coordination of Last Trains for the Beijing Subway Network[J]. Transportation Research Part B，2015，72(2)：112-127.

[5] GUO X， WU J， SUN H，et al. Timetable Coordination of First Trains in Urban Railway Network：A Case Study of Beijing[J]. Applied Mathematical Modelling，2016，40：17-18.

[6] LI X， LU L， ZHENG P，et al. Timetable Coordination of the First Trains for Subway Network with Maximum Passenger Perceived Transfer Quality[J]. IEEE Access，2019(99)：1.

[7] EVA B， DAVID C， COELHO L，et al. Exact Formulations and Algorithm for the Train Timetabling Problem with Dynamic Demand[J]. Computers & Operations Research，2014，44(4)：66-74.

[8] YUAN F， SUN H， KANG L，et al. Passenger Flow Control Strategies for Urban Rail Transit Networks[J]. Applied Mathematical Modelling，2020，82：168-188.

[9] WANG Y， ANDREA D'ARIANO， YIN J，et al. Passenger Demand Oriented Train Scheduling and Rolling Stock Circulation Planning for an Urban Rail Transit Line[J]. Transportation Research Part B：Methodological，2018，118(12)：193-227.

[10] MO P， ANDREA D， YANG L，et al. An Exact Method for The Integrated Optimization of Subway Lines Operation Strategies with Asymmetric Passenger Demand and Operating Costs[J]. Transportation Research Part B：Methodological，2021，149：283-321.

[11] WANDELT S， XU Y F， SUN X Q. Measuring Node Importance in Air Transportation Systems：on the Quality of Complex Network Estimations[J]. Reliability Engineering and System Safety，2023，240：109596.

[12] ZHU J， DAI F， ZHAO F，et al. Integrating Node Importance and Network Topological Properties for Link Prediction in Complex Network[J]. Symmetry，2023，15(8)：1492.

[13] XU X， LIU J， LI H，et al. Capacity-oriented Passenger Flow Control under Uncertain Demand：Algorithm Development and Real-World Case Study[J]. Transportation Research Part E：Logistics and Transportation Review，2016，87：130-148.

[14] 胡映月，陈 峰，陈培文，等.基于网络客流传播的轨道交通关键站点识别[J].西南交通大学学报，2017，52(6)：1193-1200，1215.

[15] HU Yingyue， CHEN Feng， CHEN Peiwen，et al. Critical Station Identification Based on Passenger Propagation in Urban Mass Transit Network[J]. Journal of Southwest Jiaotong University，2017，52(6)：1193-1200，1215.

[16] 叶营仓.有向加权下城市轨道交通车站重要度排名研究[J].齐齐哈尔大学学报(自然科学版)，2017，33(4)：35-39.

[17] YE Yingcang. Study on the Importance Rank of Stations Under the Directed and Weighted Urban Rail Transit Network[J]. Journal of Qiqihar University (Natural Science Edition)，2017，33(4)：35-39.

[18] 胡 钢，高 浩，徐 翔，等. 基于重要度传输矩阵的复杂网络节点重要性辨识方法[J]. 电子学报，2020，48(12)：2402-2408.

[19] HU Gang， GAO Hao， XU Xiang，et al. Importance Identification Method of Complex Network Nodes Based on Importance Transfer Matrix[J]. Acta Electronica Sinica，2020，48(12)：2402-2408.

[20] 况 瑢. 基于客流分配的城市轨道交通列车开行方案优化研究[D]. 成都：西南交通大学，2019.

[21] 孙梦霞，倪少权，吕红霞. 网络条件下轨道交通开行方案协调优化研究[J]. 交通运输工程与信息学报，2020，18(1)：26-33，60.

[22] SUN Mengxia， NI Shaoquan， Hongxia LYU. Rail Transit Optimization for Train Operation Plan under Network Operation[J].Journal of Transportation Engineering and Information， 2020， 18(1)：26-33，60.

[23] 史丰收，黄 俊，邓连波，等. 基于动态优化的城轨网络列车运行计划换乘衔接研究[J].铁路计算机应用，2019，28(7)：66-70.

[24] SHI Fengshou， HUANG Jun， DENG Lianbo，et al. Transfer and Connection of train Operation Plan in Urban Rail Network Based on Dynamic Optimization[J]. Urban Rail Transit Information Technology，2019，28(7)：66-70.

基金资助

国家重点研发计划项目(2022YFB4300502)

国家自然科学基金项目(52102391)

广州市重点研发计划项目(202206030007)

成都市软科学项目(2023-RK00-00036-ZF)

北京经纬信息技术有限公司科研项目(DZYF23-41)