一种用于缓解轨道交通拥挤的最小成本路径和混合路径分配方法

摘要

本发明公开了一种用于缓解轨道交通拥挤的最小成本路径和混合路径分配方法，以乘客出行时间为基础，综合考虑拥挤带来的拥挤成本，通过将出行成本进行转换，基于Frank-Wolfe算法能够用于求解轨道区间分配流量，实现对客流的集聚和分散。该方法通过改变少部分出行者的路径，仅轻微增加少量出行者出行时间，就可有效缓解轨道交通拥挤。混合路径分配方法通过找到最短路径方法和最小成本方法的路径发生变化的节点，使得整个轨道交通网络中的平均额外乘客数和平均出行成本都得到较大的降低，然后通过信息发布等交通流诱导方式引导乘客选择最小成本路径，实现从最短路径状态转变到最小成本路径状态。

说明书

技术领域

本发明涉及一种用于缓解轨道交通拥挤的最小成本路径和混合路径分配方法。

背景技术

交通运输网络在现代社会拥有着举足轻重的地位，然而，由于需求的不平衡分配，交通 网络经常出现拥挤的现象，极大地影响了网络的效率。为了提高交通运输网络的使用效率， 越来越多的研究者开始从路由的角度思考缓解网络拥挤的方法。然而，这些方法目前仍存在 以下问题：

1)在采用最短路径分配的方法中，任一出行选择路径的原则是总距离最短，导致网络中 心节点拥挤，极大降低了网络的效率；

2)故意避开了中心节点，使得中心节点没有得到有效利用；

3)采用启发式算法得到的是次优解，并不是最优解；

4)选用线性目标函数，而现实生活中的阻抗函数通常都是非线性的，与实际情况相差较 大；

5)在现有的缓解网络拥挤方法中，极大地增加了乘客的出行时间；

6)有些路由方法以各网络节点为研究对象，建立固定的路径，而没有考虑客流之间的相 互影响；不同起终点的出行者在部分的站间区间可能重叠，从而使得这些区间可能产生拥挤。 有些缓堵模型针对各网络节点建立拥挤最小的路径，然后再把OD分配到各确定的路径上， 而没有考虑它们之间的相互影响。

综上所述，现行的网络缓解拥挤模型要么没有考虑乘客路径选择博弈，要么算法采用启 发式算法，得到的是次优解；要么算法的目标函数不符合实际，要么优化过程复杂，实际应 用难度大。

发明内容

本发明提出了一种用于缓解轨道交通拥挤的最小成本路径和混合路径分配方法，从乘客 出行路径的角度出发，提出新的路径分配方法，实现对客流的集聚与分散，通过改变少部分 出行者的路径，仅轻微增加少量出行者出行时间，就可有效缓解网络。

一种用于缓解轨道交通拥挤的最小成本路径分配方法，通过构建轨道交通网络，利用乘 客的出行起点和终点信息，计算乘客在轨道交通网络中每段轨道区间上的出行成本，以所有 轨道区间的出行成本之和构成轨道交通网络总出行成本达到最小，来分配轨道交通网络中每 段轨道上的交通流量，缓解轨道交通拥挤；

其中，所述轨道交通网络由节点和节点之间连接边构成，所述节点是指轨道交通网络中 的车站，所述节点与节点之间的连接边是指轨道交通网络的站间区间；

所述乘客在轨道交通网络中每段轨道区间上的出行成本c_ij(f_ij)是指i站到相邻的j站的出 行时间成本和拥挤成本之和：

$c_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)=(1+\alpha ·{\left(\frac{f_{\mathrm{ij}}}{M_{\mathrm{ij}}}\right)}^{\beta })·t_{\mathrm{ij}}=t_{\mathrm{ij}}+\alpha ·{\left(\frac{f_{\mathrm{ij}}}{M_{\mathrm{ij}}}\right)}^{\beta }·t_{\mathrm{ij}}$

其中，f_ij和M_ij分别表示在从车站i到相邻的车站j一小时内的客流量和额定容量，t_ij表 示i站到相邻的j站的出行时间，α表示拥挤成本线性参数，取值范围为0.15～0.45，β表 示拥挤成本指数参数，取值范围为1～10；

受BPR方程的启发，用α(f/M)^βt_ij来表示i站到j站客流拥挤所带来的成本；这个表达式 可以很好地表征出行者在i站和j站间的拥挤感受，原因如下：

①这个方程将难以测量的出行者的感受转换成可测量的时间；

②这个方程与i站到j站的出行时间成正比，因此拥挤带来的成本和出行时间成正比， 这和出行者日常感受是一致的，即拥挤时间越长，出行者对拥挤的容忍度越低；

③合适的α和β值能够合理地定量化乘客的拥挤感受。

在现实感受中，客流量f/M越大，出行者的拥挤感受越强烈，这就决定了β值必须大于1。 同时，考虑到每个出行者都能够忍受一定的拥挤水平，因此β值又不能太大。参数α表征的 是当f＝M时拥挤所带来的成本，即出行者在满员的车辆上乘坐时间t所带来的出行成本等同 于出行者在非满员的车辆上乘坐时间(1+α)t所带来的出行成本。

所述轨道交通网络总出行成本为C_MC，C_MC＝∑f_ijc_ij(f_ij)。

所述以所有轨道区间的出行成本之和构成轨道交通网络总出行成本达到最小，来分配轨 道交通网络中每段轨道上的交通流量，具体步骤如下：

步骤1：令迭代次数n＝1，基于出行时间t_ij，利用Dijkstra算法分配各轨道区间的交通流 量，得到各轨道区间的客流量f_ij；

步骤2：基于各轨道区间的客流量，计算每段轨道区间的出行成本，并按照以下公式获取 每段轨道区间的出行成本转换值${\tilde{c}}_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)=c_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)+f_{\mathrm{ij}}\frac{{\mathrm{dc}}_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)}{{\mathrm{df}}_{\mathrm{ij}}};$

将出行成本进行转换是为了能够使得出行成本转换值与纳什平衡的目标函数具有同样的 表达形式，从而，运用Frank-Wolfe算法能够用于求解轨道区间分配流量。

步骤3：以步骤2获得的每段轨道区间的出行成本转换值，采用Dijkstra算法分配轨道交 通流量，得到每段轨道区间的客流量中间状态值g_ij；

步骤4：确定迭代步长λ，λ满足公式$\Sigma ({g_{\mathrm{ij}}}^n-{f_{\mathrm{ij}}}^n)\times {\tilde{c}}_{\mathrm{ij}}({f_{\mathrm{ij}}}^n+\lambda ({g_{\mathrm{ij}}}^n-{f_{\mathrm{ij}}}^n))\times t_{\mathrm{ij}}=0,$g_ijⁿ和f_ijⁿ分别表示在第n次迭过程中得到轨道区间的客流量中间状态值和迭代值；

步骤5：确定新的迭代起点：f_ijⁿ⁺¹＝f_ijⁿ+λ(g_ijⁿ-f_ijⁿ)；

步骤6：收敛性检验，判断每段轨道区间在第n次分配的客流量和第n+1次分配的客流量 是否没变化，即是否满足公式ε为判断因子，ε<10^-3，若满足 公式，则停止迭代，以当前的每段轨道区间上的客流量迭代值分配路径；否则，返回步骤2， 以f_ijⁿ⁺¹重新计算每段轨道区间的出行成本。

最短路径法也称为Dijkstra算法，常用于计算从某一指定点(起点)到另一指定点(终点) 之间的最小距离，它是交通流分配中最基本也最重要的算法，几乎所有交通流分配方法都是 以它作为一个基本子过程反复调用。

一种用于缓解轨道交通拥挤的混合路径分配方法，通过少量增加部分乘客的出行时间， 首先对需要出行的乘客按照乘客在轨道交通网络中的出行成本按照从大到小的顺序进行排 序，划分使用最小成本路径的乘客和使用最短路径的乘客；接着，将最小成本路径的乘客按 照所述的一种用于缓解轨道交通拥挤的最小成本路径分配方法，对使用最短路径的乘客按照 最短路径方法分配乘客的出行路径；实现对乘客的出行路径进行分配，从而缓解轨道交通拥 挤；

所述使用最小成本路径的乘客占所有乘客的比例为P，使用最短路径的乘客占所有乘客的 比例为1-P；

其中，P由平均额外乘客数F确定；首先，当P＝1时，得到的平均额外乘客数为F₀；将 P从0逐渐增大，当满足1.02F₀<F(P)<1.05F₀时，P为可取值；

所述平均额外乘客数是指所有轨道区间的额外乘客数除以轨道区间总数，所述额外乘客 数是指超过车辆额定载客量的乘客数量；

所述乘客在轨道交通网络中的出行成本是利用最短路径方法分配得到乘客的出行路径， 基于乘客所经过的路径中包含的每段轨道区间上的出行成本之和。

通过定位少部分的出行者，将这部分出行者用最小成本方法分配路径，其余大部分出行 者仍用最短路径分配路径，达到类似于全部用最小成本方法分配路径的缓堵效果。

在现实交通中，通过信号控制等交通流诱导方式引导乘客选择混合路径，实现从最短路 径状态转变到最小成本路径状态。

有益效果

本发明提供了一种用于缓解轨道交通拥挤的最小成本路径和混合路径分配方法，以乘客出 行时间为基础，综合考虑拥挤带来的拥挤成本，通过将出行成本进行转换，基于Frank-Wolfe 算法能够用于求解轨道区间分配流量，实现对客流的集聚和分散。该方法通过改变少部分出 行者的路径，仅轻微增加少量出行者出行时间，就可有效缓解网络(特别是客流高峰时段) 拥挤。此路径模型可以通过信息发布等现实交通流诱导方式来实现，方法易于操作，简单有 效，现实应用性强。混合路径分配方法通过找到最短路径方法和最小成本方法的路径发生变 化的节点，使得整个轨道交通网络中的平均额外乘客数和平均出行成本都得到较大的降低， 然后通过信息发布等交通流诱导方式引导乘客选择最小成本路径，实现从最短路径状态转变 到最小成本路径状态。

附图说明

图1本发明所述的最小成本路径方法流程图；

图2应用本发明所述的混合路径分配结果展示图，其中，(a)为平均出行时间随P的增 长变化曲线，(b)为平均额外乘客数随P的增长变化曲线，(c)为平均出行成本随P的增长 变化曲线；

图3为应用最短路径和最小成本路径展示图，其中，(a)为不同换乘次数下两种路径分 配示意图，(b)为同换乘次数下两种路径分配示意图。

具体实施方式

下面结合附图和具体实施例对本发明作进一步详细描述，但不作为对本发明的限定。

如图1所示，一种用于缓解轨道交通拥挤的最小成本路径分配方法，通过构建轨道交通 网络，利用乘客的出行起点和终点信息，计算乘客在轨道交通网络中每段轨道区间上的出行 成本，以所有轨道区间的出行成本之和构成轨道交通网络总出行成本达到最小，来分配轨道 交通网络中每段轨道上的交通流量，缓解轨道交通拥挤；

其中，所述轨道交通网络由节点和节点之间连接边构成，所述节点是指轨道交通网络中 的车站，所述节点与节点之间的连接边是指轨道交通网络的站间区间；

所述乘客在轨道交通网络中每段轨道区间上的出行成本c_ij(f_ij)是指i站到相邻的j站的出 行时间成本和拥挤成本之和：(PW:拥挤成本更恰当)

$c_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)=(1+\alpha ·{\left(\frac{f_{\mathrm{ij}}}{M_{\mathrm{ij}}}\right)}^{\beta })·t_{\mathrm{ij}}=t_{\mathrm{ij}}+\alpha ·{\left(\frac{f_{\mathrm{ij}}}{M_{\mathrm{ij}}}\right)}^{\beta }·t_{\mathrm{ij}}$

其中，f_ij和M_ij分别表示在从车站i到相邻的车站j一小时内的客流量和额定容量，t_ij表 示i站到相邻的j站的出行时间，α表示拥挤成本线性参数，取值范围为0.15～0.45，β表 示拥挤成本指数参数，取值范围为1～10；

在本实例中α取值为0.15，β取值为4。

所述轨道交通网络总出行成本为C_MC，C_MC＝∑f_ijc_ij(f_ij)。

所述以所有轨道区间的出行成本之和构成轨道交通网络总出行成本达到最小，来分配轨 道交通网络中每段轨道上的交通流量，具体步骤如下：

步骤1：令迭代次数n＝1，基于出行时间t_ij，利用Dijkstra算法分配各轨道区间的交通流 量，得到各轨道区间的客流量f_ij；

步骤2：基于各轨道区间的客流量，计算每段轨道区间的出行成本，并按照以下公式获取 每段轨道区间的出行成本转换值${\tilde{c}}_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)=c_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)+f_{\mathrm{ij}}\frac{{\mathrm{dc}}_{\mathrm{ij}}\left(f_{\mathrm{ij}}\right)}{{\mathrm{df}}_{\mathrm{ij}}};$

将出行成本进行转换是为了能够使得出行成本转换值与纳什平衡的目标函数具有同样的 表达形式，从而，运用Frank-Wolfe算法能够用于求解轨道区间分配流量。

步骤3：以步骤2获得的每段轨道区间的出行成本转换值，采用Dijkstra算法分配轨道交 通流量，得到每段轨道区间的客流量中间状态值g_ij；

步骤4：确定迭代步长λ，λ满足公式$\Sigma ({g_{\mathrm{ij}}}^n-{f_{\mathrm{ij}}}^n)\times {\tilde{c}}_{\mathrm{ij}}({f_{\mathrm{ij}}}^n+\lambda ({g_{\mathrm{ij}}}^n-{f_{\mathrm{ij}}}^n))\times t_{\mathrm{ij}}=0,$g_ijⁿ和f_ijⁿ分别表示在第n次迭过程中得到轨道区间的客流量中间状态值和迭代值；

步骤5：确定新的迭代起点：f_ijⁿ⁺¹＝f_ijⁿ+λ(g_ijⁿ-f_ijⁿ)；

步骤6：收敛性检验，判断每段轨道区间在第n次分配的客流量和第n+1次分配的客流量 是否没变化，即是否满足公式ε为判断因子，ε<10^-3，若满足 公式，则停止迭代，以当前的每段轨道区间上的客流量迭代值分配路径；否则，返回步骤2， 以f_ijⁿ⁺¹重新计算每段轨道区间的出行成本。

本发明基于轨道交通刷卡数据预测高峰小时OD量。刷卡数据记录了每个乘客进站和出 站的时间，因此可以根据刷卡数据得到交通量随时间的分布图，从而得到早高峰和晚高峰的 时间区间，进而截取出早高峰和晚高峰的OD。

第一步：构建北京地铁网络并预测北京地铁高峰小时OD；

从北京地铁官方网站找到北京地铁站点及其连接关系，然后用google earth记录各车站地 理坐标(包括经度和纬度)；收集各站间区间信息，包括起点、终点、出行时间和方向；将节 点及站间区间信息转化为shape文件，从而创建了北京地铁网络。

基于北京地铁刷卡数据，预测北京地铁早高峰和晚高峰的出行量，分别为2,028,440出行 /小时和1,692,770出行/小时。

第二步：北京地铁高峰小时客流分配；

①分别按照最短路径方法和最小成本路径方法分配路径。

和最短路径方法相比，最小成本路径方法的缓解拥挤效果如下：在早高峰，增加2.18％ 的平均出行时间，平均额外乘客数降低了16.34％，而平均出行成本也降低了8.57％；在晚高 峰，增加1.37％的平均出行时间，平均额外乘客数降低了16.78％，平均出行成本也降低了 5.72％。

②对所有出行者按照出行成本排序，应用混合路径方法分配路径。

图2是平均出行时间、平均额外乘客数和平均出行成本随P值的变化情况，其中P值对 应用最小成本路径分配路径的出行比例。P＝0.2即出行成本排在前20％的出行者用最小成本 路径分配路径，剩余80％的出行者用最短路径分配路径。由图2可知，当P＝0.2时，混合路 径方法能够实现类似于整体用最小成本路径方法的缓解拥挤的效果。

为了进一步验证混合路径方法的有效性，对出行成本排在前20％的出行者进行研究，单 独分析其用混合路径方法分配路径比最短路径方法分配路径增加的出行时间。研究结果显示， 这部分目标出行者，用混合路径方法分配路径仅比最短路径方法分配路径增加5.11％的出行 时间，而其平均出行成本降低了13.55％。

第三步：从最短路径状态转变到最小成本路径状态

对最短路径方法的路径和混合路径方法的路径进行比较，得到出行者从最短路径到混合 路径的替代线路。

图3以早高峰为例，图(a)、图(b)分别表示两种不同的路径变换类型。图(a)表示 从最短路径分配的路径(虚线)到最小成本分配的路径(实线)需增加一次换乘。比如，从 霍营到知春路，出行者可以选择最短路径13号线直达，出行时间为25分钟，总换算出行成 本为87.60分钟；也可以选择最小成本路径，先乘8号线到北土城然后换乘10号线到知春路， 出行时间增加7.78分钟，总换算出行成本减少34.47分钟。图(b)表示两种路由方法具有相 同的换乘次数。如，从东大桥到西直门，出行者可以选择最短路径，先乘6号线到平安里然 后换乘4号线到西直门，出行时间为16.69分钟，总换算出行成本为15.65分钟；也可以选择 最小成本路径，先乘6号线到朝阳门然后换乘2号线到西直门，出行时间增加1.14分钟，总 换算出行成本为16.70分钟。

图(a)和图(b)都表示乘客的两种选择，图(b)因为是表示相同换乘次数，所以其出 行时间和出行成本比较相近，而(a)中两种路径下出行时间增加少量，出行成本降低很大。

因此，该发明可以先找到最短路径方法和最小成本方法的路径发生变化的节点，然后通 过信息发布等交通流诱导方式引导乘客选择最小成本路径，实现从最短路径状态转变到最小 成本路径状态。