基于快速通勤需求的地铁列车跨站停车方案优化

摘要

AB跨站停车方案可以满足高峰时段地铁通勤线路场景下的乘客快速出行需求。在充分考虑乘客换乘便利性和候车安全性的基础上，以最小化乘客总旅行时间并兼顾换乘乘客的公平性影响为目标，基于出行过程和换乘类别建立了地铁AB跨站停车0-1整数规划模型，并设计了高效的变邻域搜索算法，最后以上海地铁11号线为例验证了模型和算法的有效性。结果表明：变邻域搜索算法相较于遗传算法可在短时间内搜索得到较优解，能够很好地适用于AB跨站停车优化模型；AB跨站停车方案人均旅行时间可节省2.91 min，考虑人工经验策略的AB跨站停车方案人均旅行时间可节省2.12 min，且换乘乘客数量可减少41.18%；通过灵敏度分析可以得出，换乘站候车时间惩罚系数、列车始发间隔时间和最大AB类车站间隔是影响优化结果的关键因素。

关键词

城市轨道交通; 列车停站方案; 0-1整数规划; 变邻域搜索算法; 快速通勤需求; AB跨站停车

城市轨道交通（简称地铁）网络的扩张过程中逐步形成了连接市中心与市郊的超长地铁线路，此类线路往往在高峰时段具有明显的向心或离心通勤特征。传统的站站停车模式下，高峰时段大部分通勤乘客的长距离、快速出行需求难以得到满足，且超高的车内拥挤度经常导致停站时间延长并引发列车运行延误现象。以上海地铁11号线为例，该线路两端连接市郊并贯穿中心城区，早高峰上行方向去往市中心的约55%的乘客其乘距在10 km以上，中长距离出行需求非常突出，中途的站站停车效率较低。为了提升超长线路上高峰通勤客流的出行效率，运营部门会考虑实施跨站停车方案，其中快慢车方案受既有线路配置限制难以实施，灵活跳停方案严重影响乘客的乘车体验和运输组织的节奏性，因此分别开行A、B 2种列车的AB跨站停车方案成为了一种值得尝试的策略。

目前国内外关于列车跨站停车方案的研究和应用多集中于快慢车方案^［1-3］和灵活跳停方案^［4-7］，而关于AB跨站停车方案的探讨较少。在模型构建方面，Vukan等^［8］对AB跨站停车模式的特征和潜力进行分析并建立了该停站模式下的运行效果评价方法，Freyss等^［9］采用连续逼近方法基于连续参数构建了适用于单线轨道的AB跨站停车模型，Gu等^［10］基于出行需求和线路对称的理想化假设对已有的跨 站停车连续模型进行了扩展，但以上研究与实际运营场景和精细化客流需求的结合不紧密；另有学者基于出行类别描述了不同类型乘客的换乘行为^［11-14］，但未深入考虑停站方案对换乘乘客公平性的影响。在模型求解方面，AB跨站停车优化是一类典型的0-1整数规划问题，也是大规模组合优化问题，以遍历迭代为基本特征的精确算法难以在运营单位可接受的时间内给出最优解或满意解，同时以遗传算法^［12-14］、禁忌搜索算法^［11］等为代表的启发式算法得到了广泛的应用，其中变邻域搜索算法作为一种基于单点搜索的启发式算法，具有效率高、鲁棒性好的优势^［15］，但该算法对AB跨站停车模型的求解效果还有待论证。在案例应用方面，既有的研究多采用模拟客流或模拟线路作为测试输入^［11-14］，而超长地铁线路场景下AB跨站停车方案的适用性还需进一步分析。

基于以上研究现状，本文从超长地铁线路乘客的快速通勤需求出发，充分考虑乘客换乘便利性和候车安全性，基于出行过程和换乘类别建立地铁AB跨站停车0-1整数规划模型，最小化乘客总旅行时间并设计高效的变邻域搜索算法求解，最后以上海地铁11号线为背景，论证在该线路上开行AB跨站停车方案的适用性，并验证模型和算法的有效性。

1 问题描述及模型建立

1.1　问题描述

地铁AB跨站停车方案优化问题，是指在一定的约束条件下，以乘客总旅行时间最小为目标，确定A类列车和B类列车的停站方案，等同于确定A类车站（A类车停）、B类车站（B类车停）和AB类车站（A、B类车均可停）的选择问题（图1）。

图1  AB跨站停车方案示意图

Fig. 1  Diagrammatic drawing of AB skip-stop operation

该问题基于以下假设：① 线路不具备越行条件。② A类列车和B类列车轮流发车。③ 乘客总是可以登上最先到达且可以乘坐的列车。④ 乘客优先选择不需要换乘就可以到达目的地的列车，如果不能直达，则优先选择起讫点（OD）方向上距离到达车站最近的AB类车站进行换乘。⑤ 考虑到车站服务间隔、列车追踪间隔等因素的制约，因此A类列车和B类列车的停站数要相同，同时需引入参数$\alpha$，表示每趟列车连续跨站不超过$\alpha$站。⑥ 结合现场的客流组织要求，AB类车站可以由人工来指定。为此引入指定AB类车站集合$S_{\mathrm{A}\mathrm{B}}$，可基于人工经验策略将具有换乘线路、大客流等特征的特殊车站指定为AB类车站。⑦ 为了避免部分乘客额外换乘成本过大，2个AB类车站之间的距离不能过长。为此引入参数$\delta$，表示每$\delta$个连续车站中至少有一个AB类车站。⑧ 运行图中列车的行车间隔大于跨站停车条件下的最小列车追踪间隔。⑨ 计划图中列车的车底接续方案不改变。

由于AB跨站停车模式下，部分从A或B车站出

发，到达B或A车站的客流需要在A、B这2类列车间进行换乘，则乘客存在多种“A或B列车→AB车站→B或A列车”路径可能性，考虑到乘客的出行习惯，可以将乘客路径选择行为划归为假设（4），而这一假设对起讫点在2个相邻AB类车站之间的需要反向换乘的乘客同样适用，不影响模型的结果。

1.2　AB跨站停车模型建立

1.2.1　目标函数

考虑到AB跨站停车模式在缩短乘客旅行时间方面的显著效益，选取乘客总旅行时间最小作为优化的目标，以提升高峰时期远距离通勤客流的乘客服务水平。借鉴文献［14］的思路，按照乘坐的列车类型对乘客出行进行分类（图2），分别计算每一类乘客的旅行时间，然后对所有出行类别和所有OD的旅行时间求和即得乘客总旅行时间。

图2  跨站停车模式下基于乘车类型的乘客出行分类

Fig. 2  Passenger travel classification based on train types in AB skip-stop operation

乘客的出行过程分为候车和乘车2个阶段，因此乘客旅行时间可表示为客流量与候车、乘车时间之和的乘积。某一OD客流在某出行类别下的乘客旅行时间可用式（1）的通式表示：

$$T_{i,j,c}=q_{i,j}{P}_{i,j,c}\left(W_{i,j,c}+I_{i,j,c}\right)$$

（1）

式中：$T_{i,j,c}$为$i\mathrm{到}j$的客流在出行类别$c$下的候车时间；$q_{i,j}$为$i\mathrm{到}j$的客流量；$P_{i,j,c}$为$i\mathrm{到}j$的客流属于出行类别$c$的选择概率；$W_{i,j,c}$和$I_{i,j,c}$分别为$i\mathrm{到}j$的客流在出行类别$c$下的候车时间和乘车时间。

各种出行类别下乘客旅行时间计算方法如下。

（1）类别1：乘坐A类列车或B类列车。

$$\left\{\begin{array}{c}{P}_{i,j,\mathrm{1}}=x_i^{\mathrm{A}}{x}_i^{\mathrm{B}}{x}_j^{\mathrm{A}}{x}_j^{\mathrm{B}}\\ W_{i,j,\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{A}\mathrm{B}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{0}}\\ I_{i,j,\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{2}}{\sum }_{k\in \{\mathrm{A},\mathrm{B}\}}\left({\sum }_{r=i+\mathrm{1}}^{j-\mathrm{1}}{x}_r^k{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\right)\end{array}\right.$$

（2）

式中：$x_i^k(k\in \{\mathrm{A},\mathrm{B}\})$为$k$类列车在车站$i$是否停站，停站为1，否则为0；$h_{\mathrm{A}\mathrm{B}}$为相邻开行的A类列车和B类列车之间的时间间隔；$h_{\mathrm{0}}$为列车始发间隔时间；$t_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}$为列车在车站$r$的停站时间与起停附加时间之和；$t_r^{\mathrm{r}\mathrm{u}\mathrm{n}}$为列车在车站$r$的前方区间的纯运行时间。需要注意，在A类列车和B类列车的停站数相同的条件下，$h_{\mathrm{A}\mathrm{B}}$可采用列车始发间隔时间$h_{\mathrm{0}}$作为估计值，即$W_{i,j,\mathrm{1}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{0}}$。而$I_{i,j,\mathrm{1}}$则取为A类列车和B类列车乘车时间的算术平均值。

（2）类别2：乘坐A类列车。

$$\left\{\begin{array}{c}{P}_{i,j,\mathrm{2}}=x_i^{\mathrm{A}}{x}_j^{\mathrm{A}}(\mathrm{1}-x_i^{\mathrm{B}}{x}_j^{\mathrm{B}})\\ W_{i,j,\mathrm{2}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{A}/\mathrm{B}}=h_{\mathrm{0}}\\ I_{i,j,\mathrm{2}}={\sum }_{r=i+\mathrm{1}}^{j-\mathrm{1}}{x}_r^{\mathrm{A}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\end{array}\right.$$

（3）

式中：$h_{\mathrm{A}/\mathrm{B}}$为A或者B类列车与下一列A或者B类列车之间的时间间隔。

（3）类别3：乘坐B类列车。

$$\left\{\begin{array}{c}{P}_{i,j,\mathrm{3}}=x_i^{\mathrm{B}}{x}_j^{\mathrm{B}}(\mathrm{1}-x_i^{\mathrm{A}}{x}_j^{\mathrm{A}})\\ W_{i,j,\mathrm{3}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{A}/\mathrm{B}}=h_{\mathrm{0}}\\ I_{i,j,\mathrm{3}}={\sum }_{r=i+\mathrm{1}}^{j-\mathrm{1}}{x}_r^{\mathrm{B}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\end{array}\right.$$

（4）

（4）类别4：先乘坐A类列车，再换乘B类列车。

$$\left\{\begin{array}{c}{P}_{i,j,\mathrm{4}}=x_i^{\mathrm{A}}\left(\mathrm{1}-x_i^{\mathrm{B}}\right)x_j^{\mathrm{B}}\left(\mathrm{1}-x_j^{\mathrm{A}}\right)\\ W_{i,j,\mathrm{4}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{A}/\mathrm{B}}+\beta h_{\mathrm{A}\mathrm{B}}=(\mathrm{1}+\beta )h_{\mathrm{0}}\\ I_{i,j,\mathrm{4}}={\sum }_{n=\mathrm{1}}^{\mathrm{m}\mathrm{i}\mathrm{n}\left\{\delta -\mathrm{1},m-i\right\}}{p}_{i+n}\left[\left({\sum }_{r=i+\mathrm{1}}^{i+n-\mathrm{1}}{x}_r^{\mathrm{A}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{i+n-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\right)+I_{i,j,\mathrm{4}}^{\mathrm{B}}\right]\\ p_{i+n}=x_{i+n}^{\mathrm{A}}{x}_{i+n}^{\mathrm{B}}{\prod }_{r=i+\mathrm{1}}^{i+n-\mathrm{1}}\left(\mathrm{1}-x_r^{\mathrm{A}}{x}_r^{\mathrm{B}}\right)\\ I_{i,j,\mathrm{4}}^{\mathrm{B}}=\left\{\begin{array}{c}{\sum }_{r=i+n+\mathrm{1}}^{j-\mathrm{1}}{x}_r^{\mathrm{B}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i+n}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}},i+n\le j\\ {\sum }_{r=j+\mathrm{1}}^{i+n-\mathrm{1}}{x}_r^{\mathrm{B}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=j}^{i+n-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}},i+n>j\end{array}\right.\end{array}\right.$$

（5）

考虑到换乘乘客的出行时间成本增加，对换乘站候车时间施以惩罚系数$\beta$，从而$W_{i,j,\mathrm{4}}$表示为$(\mathrm{1}+\beta )h_{\mathrm{0}}$。$I_{i,j,\mathrm{4}}$由起点站$i$到换乘站$i+n$的A类车乘车时间，以及换乘站$i+n$到终点站$j$的B类车乘车时间$I_{i,j,\mathrm{4}}^{\mathrm{B}}$组成，其中$I_{i,j,\mathrm{4}}^{\mathrm{B}}$需要根据$i+n$与$j$的相对位置分别讨论。由于不同OD的乘客对应的换乘站$i+n$不同，需要引入$p_{i+n}$表示换乘站选择概率。

（5）类别5：先乘坐B类列车，再换乘A类列车。

$$\left\{\begin{array}{c}{P}_{i,j,\mathrm{5}}=x_i^{\mathrm{B}}\left(\mathrm{1}-x_i^{\mathrm{A}}\right)x_j^{\mathrm{A}}\left(\mathrm{1}-x_j^{\mathrm{B}}\right)\\ W_{i,j,\mathrm{5}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{A}/\mathrm{B}}+\beta h_{\mathrm{A}\mathrm{B}}=(\mathrm{1}+\beta )h_{\mathrm{0}}\\ I_{i,j,\mathrm{5}}={\sum }_{n=\mathrm{1}}^{\mathrm{m}\mathrm{i}\mathrm{n}\left\{\delta -\mathrm{1},m-i\right\}}{p}_{i+n}\left[\left({\sum }_{r=i+\mathrm{1}}^{i+n-\mathrm{1}}{x}_r^{\mathrm{B}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{i+n-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\right)+I_{i,j,\mathrm{5}}^{\mathrm{A}}\right]\\ p_{i+n}=x_{i+n}^{\mathrm{A}}{x}_{i+n}^{\mathrm{B}}{\prod }_{r=i+\mathrm{1}}^{i+n-\mathrm{1}}\left(\mathrm{1}-x_r^{\mathrm{A}}{x}_r^{\mathrm{B}}\right)\\ I_{i,j,\mathrm{5}}^{\mathrm{A}}=\left\{\begin{array}{c}{\sum }_{r=i+n+\mathrm{1}}^{j-\mathrm{1}}{x}_r^{\mathrm{A}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i+n}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}},i+n\le j\\ {\sum }_{r=j+\mathrm{1}}^{i+n-\mathrm{1}}{x}_r^{\mathrm{A}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=j}^{i+n-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}},i+n>j\end{array}\right.\end{array}\right.$$

（6）

将不同OD、不同出行类别下的乘客旅行时间求和，即可得到最小化乘客总旅行时间$T$的目标函数，为

$$\mathrm{m}\mathrm{i}\mathrm{n}T={\sum }_{i=\mathrm{1}}^{m-\mathrm{1}}{\sum }_{j=i+\mathrm{1}}^m{\sum }_{c\in C}{T}_{i,j,c}$$

（7）

为了与站站停车方案进行对比，参照上述分析可给出站站停车方案下的乘客总旅行时间$T^{\mathrm{i}\mathrm{n}\mathrm{i}}$，以及跨站停车相较于站站停车的总旅行时间节省量$\left(\mathrm{\Delta }T\right)\mathrm{。}$

$$\left\{\begin{array}{c}{T}^{\mathrm{i}\mathrm{n}\mathrm{i}}={\sum }_{i=\mathrm{1}}^{m-\mathrm{1}}{\sum }_{j=i+\mathrm{1}}^m{q}_{i,j}\left(W_{i,j}^{\mathrm{i}\mathrm{n}\mathrm{i}}+I_{i,j}^{\mathrm{i}\mathrm{n}\mathrm{i}}\right)\\ W_{i,j}^{\mathrm{i}\mathrm{n}\mathrm{i}}=\frac{\mathrm{1}}{\mathrm{2}}{h}_{\mathrm{0}}\\ I_{i,j}^{\mathrm{i}\mathrm{n}\mathrm{i}}={\sum }_{r=i+\mathrm{1}}^{j-\mathrm{1}}{t}_r^{\mathrm{s}\mathrm{t}\mathrm{o}\mathrm{p}}+{\sum }_{r=i}^{j-\mathrm{1}}{t}_r^{\mathrm{r}\mathrm{u}\mathrm{n}}\end{array}\right.$$

（8）

$$\Delta T=T^{\mathrm{i}\mathrm{n}\mathrm{i}}-T$$

（9）

1.2.2　约束条件

模型的约束条件为

$${\sum }_{k\in \{A,B\}}{x}_i^k⩾\mathrm{1}\forall i\in S$$

（10）

$$x_i^{\mathrm{A}}{x}_i^{\mathrm{B}}=\mathrm{1}\forall i\in S_{\mathrm{A}\mathrm{B}}$$

（11）

$${\sum }_{i=\mathrm{1}}^m{x}_i^{\mathrm{A}}-{\sum }_{i=\mathrm{1}}^m{x}_i^{\mathrm{B}}=\mathrm{0}$$

（12）

$${\sum }_{r=i}^{i+\alpha }{x}_r^k>\mathrm{0}\forall k\in \{\mathrm{A},\mathrm{B}\},\forall i\in \{\mathrm{1,2},\dots ,m-\alpha \}$$

（13）

$${\sum }_{r=i}^{i+\delta -\mathrm{1}}{x}_r^{\mathrm{A}}{x}_r^{\mathrm{B}}⩾\mathrm{1}\forall i\in \left\{\mathrm{1,2},\dots ,m-\delta +\mathrm{1}\right\}$$

（14）

$$x_i^k\in \left\{\mathrm{0,1}\right\}\forall k\in \{\mathrm{A},\mathrm{B}\},\forall i\in S$$

（15）

约束（10）表示每一个车站都至少有一类列车停站；约束（11）表示人工经验策略下可指定AB类车站；约束（12）表示A、B类列车的停站数量相等；约束（13）表示列车连续跨站数量不超过$\alpha$；约束（14）表示每$\delta$个连续车站中至少有一个AB类车站；约束（15）表示$x_i^k$为0、1变量。

2 算法设计

式（1）—（15）为0-1整数非线性规划模型，属于大规模组合优化问题，以遍历迭代为基本特征的精确算法难以在可接受的时间内给出最优解或满意解，因此采用变邻域搜索算法（variable neighborhood search，VNS）对模型进行求解。VNS算法从当前解的最小邻域开始，在搜索过程中系统地改变邻域结构，扩展搜索范围，获得局部最优解；然后基于该局部最优解重新从最小邻域开始搜索找到下一局部最优解。VNS算法框架如图3所示，该算法包含3个主要部分：初始解的生成、邻域和邻解生成和局部最优解搜索。其主要步骤如下：

图3  VNS算法流程

Fig. 3  Flowchart of the VNS algorithm

（1）初始解的生成。首先定义解的结构：$\mathit{x}={\left[x_{\mathrm{1}}^{\mathrm{A}},x_{\mathrm{2}}^{\mathrm{A}},\dots ,x_m^{\mathrm{A}},x_{\mathrm{1}}^{\mathrm{B}},x_{\mathrm{2}}^{\mathrm{B}},\dots ,x_m^{\mathrm{B}}\right]}^{\mathrm{T}}$，即停站决策变量$x_i^k$组成的列向量。通过在$\{\mathrm{0,1}\}$中重复随机抽取，得到只有0、1编码的列向量${\mathit{x}}_{\mathrm{0}}$，然后判断${\mathit{x}}_{\mathrm{0}}$是否满足约束条件，如果满足则输出可行的初始解$\mathit{x}={\mathit{x}}_{\mathrm{0}}$，否则继续重复上述步骤。

（2）邻域和邻解生成。该过程的目的是通过抖动（shaking）当前解$\mathit{x}$来逃避局部最优。通过将$\mathit{x}$的点位随机两两互换$i$次，即可得到邻域$N_i$上的邻解${\mathit{x}}^{\text{'}}$。该算法在邻域$N_i$上生成的邻解${\mathit{x}}^{\mathit{\text{'}}}$与当前解$\mathit{x}$之间的相似性随着$i$的增加而降低，从而其逃避局部最优的机会随之上升。

（3）局部最优解搜索。该过程称为变邻域深度搜索（variable neighborhood descent，VND），其框架和VNS类似，并采用了另一种邻域结构$\{{\mathrm{𝒩}}_{\mathrm{1}},{\mathrm{𝒩}}_{\mathrm{2}},\dots ,{\mathrm{𝒩}}_l,\dots ,{\mathrm{𝒩}}_L\}$。算法中，邻域搜索采用了最佳改进移动策略^［14］（move at best improvement，MABI），即找到${\mathrm{𝒩}}_l({\mathit{x}}^{\text{'}})$中的最优解之后，再判断是否替换当前最优解$\mathit{x}\text{'}$。

邻域结构${\mathrm{𝒩}}_l$的设计是算法的核心部分，原则是尽量保证算法的全局性。一般来说，VND需要多个邻域结构进行局部搜索，因此基于取反（reverse）、交换（swap）和移位（shift）等基本动作^［16］，设计4种邻域结构$\{{\mathrm{𝒩}}_{\mathrm{1}},{\mathrm{𝒩}}_{\mathrm{2}},{\mathrm{𝒩}}_{\mathrm{3}},{\mathrm{𝒩}}_{\mathrm{4}}\}$，如表1所示。通常以解向量间不同元素的个数来定义邻域间的距离，而邻域结构一般按照距离从小到大排序，以便首先搜索最小或最快的邻域，然后搜索更复杂的邻域。因此，邻域搜索即按照${\mathrm{𝒩}}_{\mathrm{1}}\mathrm{至}{\mathrm{𝒩}}_{\mathrm{4}}$的顺序。

表1  VND算法的邻域结构

Tab. 1  Neighborhood structure of the VND algorithm

邻域结构	邻域动作
${\mathcal{N}}_1$	将$\mathit{x}$的第$i$位取反，$i=\mathrm{1,2},\dots ,2m$
${\mathcal{N}}_2$	将$\mathit{x}$的第$i$位取反后，再将第$j$位取反，$i=\mathrm{1,2},\dots ,2m-1$，$j=i+1,i+2,\dots ,2m$
${\mathcal{N}}_3$	将$\mathit{x}$的第$i$位和第$j$位交换，$i=\mathrm{1,2},\dots ,2m-1$，$j=i+1,i+2,\dots ,2m$
${\mathcal{N}}_4$	将$\mathit{x}$的第$j$位前移到第$i$位，$i=\mathrm{1,2},\dots ,2m-1$，$j=i+1,i+2,\dots ,2m$

3 案例分析

3.1　案例背景

以上海地铁11号线为例，客流为2021年7月某工作日的OD数据。各车站早高峰（6：45—9：45）上行方向（由北段向市中心方向）的进出站客流及断面客流分布如图4所示，图中嘉定北、嘉定西、白银路、嘉定新城等4个车站位于支线，其断面客流从零累计。为方便观察趋势，将其平移至虚线所示位置。从图中可以发现，11号线北段的大部分车站在早高峰进市区方向上以进站客流为主，而中心城区的车站则以出站客流为主。进一步分析断面客流可知，嘉定新城至曹杨路区间（图4中点划线所框选的范围）的断面客流持续快速增长且出站客流较少，观察该区间OD客流弦图（图5）可以发现，由嘉定新城（及以北）、南翔、上海西站等车站去往曹杨路（及以南）车站的客流需求较为集中，符合长距离的通勤特征。因此，选取早高峰时段（6：45—9：45）进市区方向的嘉定新城至曹杨路区间作为研究对象。

图4  上海地铁11号线早高峰时段上行方向各站进出站客流及断面客流量分布

Fig. 4  Distribution of inbound/outbound passenger flow and section passenger flow in upward direction during morning peak hours of Shanghai Metro Line 11

图5  上海地铁11号线早高峰时段上行方向嘉定新城至曹杨路区间OD客流弦图

Fig. 5  Chord diagram of OD passenger flow from Jiading Xincheng Station to Caoyang Road Station in upward direction during morning peak hours of Shanghai Metro Line 11

3.2　数据输入

11号线相关运营参数如图6所示，早高峰时段上行方向嘉定新城至曹杨路区间的OD客流数据如表2所示，结合实际运营情况，相应的参数设定如下：假设$\delta =\mathrm{6}\mathrm{、}{h}_{\mathrm{0}}=\mathrm{3}\mathrm{m}\mathrm{i}\mathrm{n}\mathrm{、}\beta =\mathrm{1}\mathrm{、}\alpha =\mathrm{1}$。

图6  上海地铁11号线相关运行参数

Fig. 6  Operation parameters of Shanghai Metro Line 11

表2  上海地铁11号线早高峰时段上行方向嘉定新城至曹杨路区间的OD客流

Tab. 2  OD passenger flow from Jiading Xincheng Station to Caoyang Road Station in upward direction during morning peak hours of Shanghai Metro Line 11

车站	客流量/人次
	马陆	陈翔公路	南翔	桃浦新村	武威路	祁连山路	李子园	上海西站	真如	枫桥路	曹杨路（及以南）
嘉定新城（及以北）	439	761	1 901	312	56	1 101	908	4 128	346	560	40 939
马陆		94	255	66	8	261	167	966	86	139	7 504
陈翔公路			25	16	5	126	90	559	59	80	5 355
南翔				41	10	230	180	1 231	120	196	11 031
桃浦新村					6	121	169	1 212	91	217	10 500
武威路						2	0	11	4	6	99
祁连山路							17	176	10	33	2 293
李子园								299	18	47	3 266
上海西站									91	402	22 073
真如										5	4 658
枫桥路											3 688

3.3　应用场景设计及结果分析

为对比不同运营方案条件下的开行效果，共设计3种应用场景，如表3所示。其中，场景1是站站停车方案，作为AB跨站停车方案的原始对照方案；场景2是AB跨站停车方案，其各类车站的选择都包含在模型的优化空间中；场景3在场景2的基础上考虑乘客的便利性，将某些有特殊要求的车站$S_{\mathrm{A}\mathrm{B}}$指定为AB类车站。

表3  案例分析的应用场景设计

Tab. 3  Application scenarios of the case study

场景编号	场景类型	场景说明
1	站站停车方案	不考虑AB跨站停车的原始对照方案
2	AB跨站停车方案（不指定AB类车站）	$S_{\mathrm{A}\mathrm{B}}=\mathrm{\varnothing }$
3	AB跨站停车方案（指定AB类车站）	$S_{\mathrm{A}\mathrm{B}}=\left\{\mathrm{4,5},\mathrm{9,10,12}\right\}$

基于场景2对VNS算法参数和性能进行分析。测试所用的软硬件环境为：Intel Core i9-14900HX CPU （2.20 GHz）、32 GB内存、64位Windows 11操作系统，MATLAB R2022a。为了确定VNS算法中抖动邻域数量最大值S_max的合理取值，3种选择参数（200、300、400）下的目标函数收敛曲线如图7所示。从图中可以看出，当S_max = 300时，目标函数乘客总旅行时间可以较快地收敛于2 143 452.20 min，其结果比S_max = 200时的目标函数值更小，比S_max = 400时的收敛时间更短。因此本次案例测试中，选取S_max = 300。为了检验VNS算法的性能，采用遗传算法（GA）与VNS算法对场景2同时进行求解，前者参数选取如下：群体大小为200，交叉概率为0.9，变异概率为0.1，进化代数为300。分别使用2种算法运行50次，目标函数值和求解时间分布如图8所示。运行结果表明：VNS算法的目标函数值均值为2 143 452.20 min，求解时间均值为4.17 s，相比GA算法分别降低0.19%和30.03%；VNS算法目标函数值标准差为零，远低于GA算法的7 765.01 min；VNS算法的求解时间标准差为0.22 s，略大于GA算法的0.17 s。由此可以看出，相比于GA算法，VNS算法在此问题上的收敛速度更快、全局寻优能力更强，且具有良好的鲁棒性。

图7  VNS算法在不同算法参数下的收敛过程

Fig. 7  Convergence process of the VNS algorithm with different parameters

图8  VNS和GA算法的目标函数值与求解时间箱线图

Fig. 8  Box plot of optimized objective function values and solution time obtained by the VNS algorithm and the GA algorithm

经VNS算法计算，各场景的停站方案及乘客总旅行时间如表4所示。

表4  各场景的停站方案及乘客总旅行时间

Tab. 4  Stop plan and passenger total travel time in each scenario

场景类型	列车类型	停站方案												乘客总旅行时间/ min
		嘉定新城（及以北）	马陆	陈翔公路	南翔	桃浦新村	武威路	祁连山路	李子园	上海西站	真如	枫桥路	曹杨路（及以南）
场景1	A	停	停	停	停	停	停	停	停	停	停	停	停	2 522 267.95
	B	停	停	停	停	停	停	停	停	停	停	停	停
场景2	A	停	停	通	停	停	通	停	通	停	通	停	停	2 143 452.20
	B	停	通	停	停	通	停	通	停	停	停	通	停
场景3	A	停	停	通	停	停	通	停	通	停	停	停	停	2 247 129.42
	B	停	通	停	停	停	停	通	停	停	停	通	停

针对场景2，跨站停车方案相比站站停车方案（场景1）可节省378 815.75 min（平均每位乘客2.91 min）的旅行时间，基于2021年上海平均收入推算人均小时工资为65.5元，可节省人工成本约41万元。为了进一步观察跨站停车方案在各车站的表现，计算场景2和场景1下各车站进站乘客的平均旅行时间如图9所示，可以看出11个车站中有10个车站的人均旅行时间与原来相比有明显缩短或基本持平，而枫桥路车站的人均旅时有所增加，但总体控制在5 min以内。

图9  跨站停车和站站停车方案下各车站进站乘客的平均旅行时间

Fig. 9  Average inbound passenger travel time of each station in skip-stop operation and all-stop operation

针对场景3，指定上海西站、真如、曹杨路等3个换乘站以及南翔、桃浦新村等2个进站量较大的车站为AB类车站，即$S_{\mathrm{A}\mathrm{B}}=\{\mathrm{4,5},\mathrm{9,10,12}\}$。在该场景下，跨站停车方案相比站站停车方案（场景1）可节省275 138.53 min（平均每位乘客2.12 min）的旅行时间，约合节省人工成本30万元。场景3与场景2的直达客流与换乘客流如表5所示，其中“同一场景下的比例”是对同一场景下2种客流类型而言的，两者之和为100%；“同一客流类型下的变化率”是对同一客流类型下2种场景而言的，是后者相对前者的变化率从表中可以看出，相较于场景2，考虑人工经验策略的场景3可将需要换乘的乘客数量大幅压缩41.18%。

表5  指定AB类车站与否的2种场景下直达客流与换乘客流情况

Tab. 5  Direct passenger flow and transfer passenger flow in the two scenarios of specifying AB stations or not

客流类型	跨站停车方案	客流量/人次	同一场景下的比例/%	同一客流类型下的变化率/%
直达客流	场景2	128 935	99.28	0.30
	场景3	129 318	99.58
换乘客流	场景2	930	0.72	-41.18
	场景3	547	0.42

为分析不同输入参数对模型结果的影响程度，对模型参数进行灵敏度分析。首先改变换乘乘客在换乘站候车时间的惩罚系数$(\beta )$，观察换乘乘客总旅行时间增加量和所有乘客总旅行时间的变化，结果如图10所示。从图中可以看出，随着$\beta$的增加，一方面换乘乘客的额外时间成本得到了压缩，另一方面乘客总旅行时间有所提升，这显示出$\beta$对于服务效率和公平性的权衡效果。基于此，可以通过方案实施后的现场反馈情况对$\beta$进行调节，进而提升跨站停车方案的适用性。

图10  换乘站候车时间惩罚系数的灵敏度分析

Fig. 10  Sensitivity analysis of transfer station waiting time penalty coefficient

改变列车始发间隔时间$h_{\mathrm{0}}$和最大AB类车站间隔$\delta$的取值，观察乘客总旅行时间节省量的变化，结果如图11所示。

图11  列车始发间隔时间和最大AB类车站间隔的灵敏度分析

Fig. 11  Sensitivity analysis of train original departure interval and maximum AB station interval

从图11中可以看出，总旅行时间节省量随着$h_{\mathrm{0}}$的增加而减少，因而跨站停车方案在$h_{\mathrm{0}}$较小的情况下可以获得显著效益。与此同时，总旅行时间节省量随着$\delta$的增加而增加，考虑到AB类车站（也即换乘站）较少会对部分乘客的出行便利性造成不利影响，因此$\delta$数值不宜过大。

4 结语

以AB跨站停车方案为研究对象，基于出行过程和换乘类别，考虑服务水平和管理需求，构建了地铁AB跨站停车0-1整数规划模型，通过变邻域搜索算法进行求解，并以上海地铁11号线为案例进行验证，分析结果表明：

（1）相比于GA算法，VNS算法的收敛速度更快、全局寻优能力更强，且具有良好的鲁棒性，可以很好地适用于AB跨站停车优化模型。本次案例中，VNS算法的目标函数值均值和求解时间均值比GA算法降低了0.19%和30.03%，VNS算法的目标函数值标准差为零，远低于GA算法的7 765.01 min。

（2）在特定的客流需求条件下，AB跨站停车方案可以有效节省乘客的旅行时间，具有一定的适用性。本次案例中，不考虑人工经验策略的跨站停车方案下乘客总旅行时间节省378 815.75 min（人均节省2.91 min），11个车站中有10个车站的人均旅行时间有明显缩短或基本持平；考虑人工经验策略的跨站停车方案下乘客总旅行时间节省275 138.53 min（人均节省2.12 min），需要换乘的乘客数量也可大幅压缩41.18%。

（3）通过灵敏度分析可以得出，换乘站候车时间惩罚系数、列车始发间隔时间和最大AB类车站间隔对求解目标影响较大。

考虑到模型的复杂度和求解难度，本文未考虑时变客流需求下列车容量限制以及运行间隔约束在开行密度较大情况下对AB跨站停车模式有效性的影响，下一步工作中将纳入时变的客流需求，量化AB跨站停车的追踪运行间隔下列车的满载率和站台的候车人数，从而评估线路能力对AB跨站停车方案的弹性以及滞留乘客对站台安全性的威胁，并实现停站方案和时刻表的联合优化。另外，受限于案例场景的求解规模，本文未深入讨论VNS算法在更大规模的开行方案优化问题中的适用性，后续可将其加入算法性能分析当中。

作者贡献声明

江志彬：确定研究内容，指导论文撰写，修改论文。

王炳勋：整理数据，建模与分析，撰写论文。

李洪运：协助整理数据。

赵 源：协助整理数据。

金晓琴：协助整理数据。