在城市路网中, 交通需求一般会受到网络服务水平的影响, 当网络比较拥挤时, 用户可能改变出行时间或者选择其他出行方式, 甚至放弃出行计划, 即弹性需求更加符合现实网络^[1-3].在弹性需求模型中常有部分路段的流量高于路段容量, 这不符合实际情形, 虽然可以采用内罚函数法、外罚函数法或广义拉格朗日乘子法将路段容量约束问题转化为为一系列无容量约束子问题^[4-6], 并通过对惩罚因子的不断调节, 反复采用Frank-Wolfe算法求解, 但由于Frank-Wolfe算法在弹性需求情况下收敛速度特别慢^[7], 因而妨碍了容量约束模型在大型路网上的应用.因此, 在弹性需求情况下设计一种带路段容量约束的有效算法可以加快分配速度, 提高分配效率.

本文首先分析了无容量约束和容量约束弹性需求交通分配模型在路段行驶时间和需求方面的差异, 指出在无容量约束情况下, 函数近似路段行驶时间低估了真实行驶时间, 进而高估了真实需求.基于这种思想, 提出了一种带路段容量约束的弹性需求UE交通分配近似算法, 该方法采用超需求模型将弹性需求转化为固定需求, 然后设计带路段容量约束的UE近似算法求解.基本思想是基于O-D对间最短路的动态生成, 不需要路径枚举, 在每轮迭代中, 按全有全无方法进行流量分配, 与前一轮迭代所得到的流量进行加权得到新一轮的路径流量, 而各O-D对的加权系数则依据Logit模型来确定, 通过不断自适应调节排队延误因子、误差因子来逼近真实路段行驶时间和O-D需求, 从而使路段流量逐步满足约束条件, 最终达到广义用户均衡.该算法不需要在每轮迭代中采用Frank-Wolfe算法求解无约束交通分配模型, 从而改进了分配效率.随后证明了算法的收敛性.最后通过一个算例, 说明了算法的可行性.

给定一个交通网络 $G=(N, A)$, $N$为节点集, $A$为路段集, $R$为起点集, $S$为终点集, $R$与 $S$可以有公共元素; 网络中共有 $|A|$条路段; $(r, s)$是以 $r$为起点, $s$为终点的O-D对; $P_{rs}$为O-D对 $(r, s)$间所有路径集合.容量约束弹性需求交通分配问题考虑了路段的容量, 使该问题更加符合实际路网情形, 容量约束交通均衡模型具有形式:

$ \begin{eqnarray*} \min\limits_{x\in\Omega}\sum\limits_{a\in A}\int_{0}^{x_{a}}t_{a}(\omega)d\omega-\sum\limits_{r\in R}\sum\limits_{s\in S}\int_{0}^{q_{rs}}B(\omega)d\omega, \end{eqnarray*} $

(2.1)

其中

$ \begin{eqnarray*} \Omega=\left\{x|\sum\limits_{p\in P_{rs}}f_{p}^{rs}=q_{rs}, f_{p}^{rs}\geq 0, x_{a}=\sum\limits_{r\in R}\sum\limits_{s\in S}\sum\limits_{p\in P_{rs}}f_{p}^{rs}\delta_{ap}^{rs}, x_{a}\leq C_{a}, \forall a, p, r, s\right\}. \end{eqnarray*} $

(2.2)

式中: $x_{a}$为路段 $a$上的流量, 它们组成的向量为 $x=(\cdots, x_{a}, \cdots)^{T}$; $f_{p}^{rs}$是O-D对 $(r, s)$间路径 $p$上的流量, 组成的向量为 $f=(\cdots, f_{p}^{rs}, \cdots)^{T}$; $t_{a}(x_{a})$为路段 $a$行驶时间函数, 关于 $x_{a}$是严格单调增加且连续可微的, $t(x)=(\cdots, t_{a}(x_{a}), \cdots)^{T}$为路段行驶时间函数向量; $C_{a}$为路段 $a$的容量, $C=(\cdots, C_{a}, \cdots)^{T}$; $q_{rs}$为O-D对 $(r, s)$间的交通需求量; $q_{rs}=D_{rs}(u_{rs})$是O-D对 $(r, s)$间的需求函数, 假定只与 $(r, s)$间的最短行驶时间 $u_{rs}$有关, 关于 $u_{rs}$是严格单调减少且连续可微的, $q=(\cdots, q_{rs}, \cdots)^{T}$; $u_{rs}=B_{rs}(q_{rs})=D^{-1}(q_{rs})$.如果O-D对 $(r, s)$间路径 $p$经过路段 $a$, 则 $\delta_{ap}^{rs}=1$, 否则为0.明显的, 上述模型(2.1)-(2.2) 具有唯一路段流量、需求解 $(x^{*}, q^{*})$.由K-K-T条件知, 模型(2.1)-(2.2) 的均衡条件为

$ \begin{eqnarray} (\sum\limits_{a\in A}\tilde{t}_{a}(x^{*}_{a})\delta_{ap}^{rs}-u_{rs})f_{p}^{rs*}=0, \sum\limits_{a\in A}\tilde{t}_{a}(x^{*}_{a})\delta_{ap}^{rs}-u_{rs}\geq 0, f_{p}^{rs*}\geq 0, \end{eqnarray} $

(2.3)

$ \begin{eqnarray} q_{rs}^{*}(u_{rs}-B_{rs}(q_{rs}^{*}))=0, u_{rs}\geq B_{rs}(q_{rs}^{*}), q_{rs}^{*}\geq 0, \end{eqnarray} $

(2.4)

$ \begin{eqnarray} d_{a}(x_{a}^{*}-C_{a})=0, x_{a}^{*}\leq C_{a}, d_{a}\geq 0, \end{eqnarray} $

(2.5)

其中 $\tilde{t}_{a}(x_{a})=t_{a}(x_{a})+d_{a}$称为广义路段行驶时间, Lagrange乘子 $u_{rs}$, $d_{a}$分别代表O-D对 $(r, s)$间的最小行驶时间与路段 $a$的排队延误时间, 因此上述一阶最优性条件经常称为弹性需求广义用户均衡条件.由于在拥挤网络中, $d_{a}$并不是可以忽略的, 又 $t_{a}(x_{a})$是连续可微的, 因此当路段流量接近其容量时, 无容量约束时间函数近似曲线变化比较平稳, 而实际情况会产生排队, 使路段实际行驶时间快速增加, 即当 $x_{a}>C_{a}$时, 实际延误 $d_{a}$要高于无容量约束下函数近似延误 $d_{a}'$, 其误差因子 $\triangle d_{a}=d_{a}-d_{a}'>0$, 从而实际路径行驶时间也要高于函数近似时间, 又需求是关于最短路径行驶时间是严格递减的, 因此无路段容量约束弹性需求UE高估了实际交通需求量.需要注意的是虽然在实际弹性需求路网均衡条件下, 排队延误是唯一的, 但Lagrange乘子 $d_{a}$并不唯一^[1].

Sheffi等在无容量约束下提出一种超需求模型将弹性需求UE模型转化为固定需求模型^[7], 可以采用Frank-Wolfe算法求解.带路段容量约束弹性需求UE模型也可以基于该思想进行转化:在模型(2.1) 中

$ \begin{equation} \int_{0}^{q_{rs}}B(\omega)d\omega=\int_{0}^{D_{rs}(u_{rs}^{0})}B(\omega)d\omega-\int_{q_{rs}}^{D_{rs}(u_{rs}^{0})}B(\omega)d\omega, \end{equation} $

(3.1)

(3.1) 式右边第一项为常数, 在优化模型中可以省略, $u_{rs}^{0}$为自由流时 $(r, s)$间最小行驶时间.令 $e_{rs}=D_{rs}(u_{rs}^{0})-q_{rs}$, 则

$ \begin{equation*} -\int_{q_{rs}}^{D_{rs}(u_{rs}^{0})}B_{rs}(\omega)d\omega=\int_{D_{rs}(u_{rs}^{0})-q_{rs}}^{0}B_{rs}(D_{rs}(u_{rs}^{0})-\omega)d\omega=-\int_{0}^{e_{rs}}W_{rs}(\omega)d\omega, \end{equation*} $

其中 $W_{rs}(\omega)=B_{rs}(D_{rs}(u_{rs}^{0})-\omega)$是单调增加且连续可微的.若在O-D对 $(r, s)$间添加一条虚拟路段, $e_{rs}$为虚拟路段流量, $W_{rs}(e_{rs})$为路段流量函数, 则路段容量约束弹性需求UE模型可转化为如下固定需求模型:

$ \begin{eqnarray*} \min\limits_{(x, e)\in\overline{\Omega}}\sum\limits_{a\in A}\int_{0}^{x_{a}}t_{a}(\omega)d\omega+\sum\limits_{r\in R}\sum\limits_{s\in S}\int_{0}^{e_{rs}}W_{rs}(\omega)d\omega, \end{eqnarray*} $

(3.2)

其中

$ \begin{eqnarray*} \overline{\Omega}=\left\{(x, e)|\sum\limits_{p\in P_{rs}}f_{p}^{rs}+e_{rs}=D_{rs}(u_{rs}^{0}), e_{rs}\geq 0, x\in \Omega, \forall r, s\right\}. \end{eqnarray*} $

(3.3)

设路网中有 $N$个O-D对, 首先置各路段初始流量为零, 进行全有全无交通分配并将产生的最短路归入各O-D对的最短路径集 $A_{i}$ ( $i$表示第 $i$个O-D对, $i=1, 2, \cdots, N$)中, 然后自适应校正排队延误因子 $d_{a}$和误差因子 $\triangle d_{a}$, 再根据各路段上的当前流量重新计算路段行驶时间 $\tilde{t}_{a}(x_{a})=t_{a}(x_{a})+d_{a}$, 并利用最短路算法产生与之对应的新的最短路 $p_{i}$ ( $i=1, 2, \cdots, N$).如果 $p_{i}$不属于 $A_{i}$, 将其归入 $A_{i}$中; 否则 $A_{i}$中所含路径不发生变化, 但须将路径 $p_{i}$的重复出现次数由 $m_{p_{i}}$更新为 $m_{p_{i}}+1$.对第 $i$个O-D对, 选取流量加权组合系数 $\alpha_{i}^{2}$, 将本次按全有全无分配的流量与前一步迭代各路径相应流量进行加权平均, 得到第二次迭代的路径分配流量, 据此计算新的路段流量.重复上述过程直至迭代终止.

由于现实路网中各个O-D对的路径集和交通需求量存在一定差异性, 不同于Frank-Wolfe算法中各O-D对共用一个加权系数, 本算法在迭代过程中各O-D对可选取不同的加权组合系数.选取方式如下:计算第 $k$次迭代时新产生的路径 $p_{i}^{k}$的初始行驶时间 $t_{p_{i}^{k}}$及 $A_{i}^{k}$中各条路径的初始行驶时间, 取

$ \begin{equation} \alpha_{i}^{k}=\max\left\{\frac{\exp(-\theta t_{p_{i}^{k}})}{\sum\limits_{p_{i}\in A_{i}^{k}}m_{p_{i}}\exp(-\theta t_{p_{i}})}, \zeta_{i}\right\}, \end{equation} $

(3.4)

其中 $\theta\geq 0$为Logit模型中的分布参数, $A_{i}^{k}$为迭代到第 $k$次时, 已经求出的第 $i$个O-D对的最短路集合(包括路径 $p_{i}^{k}$), $t_{p_{i}}$是路径 $p_{i}$的初始行驶时间, $m_{p_{i}}$表示到目前为止, 在每次最短路算法中, 路径 $p_{i}$作为最短路而被重复选中的次数.因此对第 $i$个O-D对显然有 $\sum_{p_{i}\in A_{i}^{k}}m_{p_{i}}=k$.式(3.4) 中 $\zeta_{i}$是一个与算法迭代误差 $\varepsilon$有关的充分小正数, 其作用是既要保证算法能够收敛, 又要使每一步迭代路径流量都有适当调整.

步骤0  输入O-D表及网络几何信息, 设O-D对个数为 $N$, 令 $i$表示第 $i$个O-D对, 连接各O-D对添加虚拟路段, 取容量为无穷大; 置各路段初始流量为0, 迭代次数 $k=1$, 第 $i$个O-D对最短路径集 $A_{i}=\varnothing$; 取允许误差 $\varepsilon>0$, 按全有全无分配各O-D对流量, 得路段流量 $x^{k}$和行驶时间 $t^{k}$, 计算 $d_{a}^{k}= \begin{cases} t_{a}^{k}-t_{a}(C_{a}), & \text{如果}~x_{a}>C_{a}, \\ 0,&\text{否则}, \end{cases}$随机产生 $\Delta d_{a}^{k}\geq 0$, $\forall a\in A$; 将产生的最短路归入各O-D对的最短路径集 $A_{i}$( $A_{i}$表示第 $i$个O-D对, $i=1, 2, \cdots, N$)中, 置 $m_{p_{i}^{k}}=1$.

步骤1  确定各路段行驶时间 $t^{k+1}_{a}=t^{k}_{a}+d_{a}^{k}$, 并利用最短路算法计算各个O-D对最短路 $p_{i}^{k+1}$; 如果 $p_{i}^{k+1}\not \in A_{i}$, 置 $A_{i}:=A_{i}\cup p_{i}^{k+1}$, 路径 $p_{i}^{k+1}$的出现次数 $m_{p_{i}^{k+1}}=1$, 否则 $A_{i}$中路径不发生变化, 置 $m_{p_{i}^{k+1}}=m_{p_{i}^{k}}+1$.将每个O-D对的需求量进行全有全无分配, 将所得到的各路径上的流量向量记为 $\tilde{f}_{i}^{k}$, $\tilde{e}_{i}^{k}$.按规则(3.4) 选取流量加权组合系数 $\alpha_{i}^{k+1}$, 对第 $i$个O-D对, 按如下方式在其最短路径集 $A_{i}$中分配流量: $f_{i}^{k+1}=\alpha_{i}^{k+1}\tilde{f}_{i}^{k}+(1-\alpha_{i}^{k+1})f_{i}^{k}$, $e_{i}^{k+1}=\alpha_{i}^{k+1}\tilde{e}_{i}^{k}+(1-\alpha_{i}^{k+1})e_{i}^{k}$.

步骤2  计算并输出路段分配流量 $x^{k+1}$, $e^{k+1}$及路段行驶时间 $t^{k+1}$, 如果

$ \max\limits_{a\in A}|x_{a}^{k+1}-x_{a}^{k}|+\max\limits_{i=1, 2, \cdots, N}|e_{i}^{k+1}-e_{i}^{k+1}|+\max\limits_{a\in A}|x_{a}^{k+1}-C_{a}|<\varepsilon, $

停止; 否则转步骤3.

步骤3  令 $d_{a}^{k+1}= \begin{cases} d_{a}^{k}+\triangle d_{a}^{k},&\text{如果}~x_{a}^{k+1}\geq C_{a}, \\ 0,&\text{否则}, \end{cases}$并令

$ \triangle d_{a}^{k+1}=\max \{0, \triangle d_{a}^{k}+\frac{1}{k+1}(x_{a}^{k+1}-C_{a})\}, $

$\forall a \in A$, 置 $k:=k+1$, 转步骤1.

定理  当 $\Omega \neq \varnothing$且 $D_{i}(u_{i}^{0})<\infty~(i=1, 2, \cdots, N)$时, 则对任意给定的迭代误差 $\varepsilon>0$, 适当选取 $\zeta_{i}$, 算法能有限终止.

证  由于路网中只有有限条路段, 要证明上述定理, 只需证明对路网中任意一条路段 $a$, 有

$ |x_{a}^{k+1}-x_{a}^{k}|<\frac{\varepsilon}{3}, |e_{i}^{k+1}-e_{i}^{k}|<\frac{\varepsilon}{3}, \max\{0, x_{a}^{k+1}-C_{a}\}<\frac{\varepsilon}{3}, k \rightarrow \infty, $

即可.

先证 $|x_{a}^{k+1}-x_{a}^{k}|<\frac{\varepsilon}{3}$, $k\rightarrow\infty$.

考察第 $i$个O-D对, 取

$ M=\max\limits_{p \in P}\{\exp(-\theta t_{p})\}, \ m=\min\limits_{p \in P}\{\exp(-\theta t_{p})\}, $

其中 $P$为各O-D对所有生成路径的集合, 有

$ \frac{\exp(-\theta t_{p_{i}^{k}})}{\sum\limits_{p_{i}\in A_{i}^{k}}m_{p_{i}}\exp(-\theta t_{p_{i}})}\leq \frac{M}{\sum\limits_{p_{i} \in A_{i}}m\cdot m_{i}^{k}}\leq \frac{M}{m}\cdot \frac{1}{k}\rightarrow 0, \ k\rightarrow \infty. $

因此 $k$当充分大时, 总有 $\alpha_{i}^{k}=\zeta_{i}$, 若取 $\zeta_{i}=\frac{\varepsilon}{3N|A_{i}|q_{i}}$, 那么对 $A_{i}$中任一条路径 $p_{i}$, 由

$ f_{p_{i}}^{k+1}=\alpha_{i}^{k+1}\tilde{f}_{p_{i}^{k}}+(1-\alpha_{i}^{k+1})f_{p_{i}}^{k}=f_{p_{i}}^{k}+\alpha_{i}^{k+1}(\tilde{f}_{p_{i}}^{k}-f_{p_{i}}^{k}), $

知

$ |f^{k+1}_{p_{i}}-f^{k}_{p_{i}}|=\alpha_{i}^{k+1}|\tilde{f}_{p_{i}^{k}}-f_{p_{i}}^{k}|\leq q_{i}\alpha_{i}^{k+1}=q_{i}\zeta_{i}, \ k\rightarrow\infty, $

其中 $q_{i}$为第 $i$个O-D对的交通需求量.由于交通网络中每个O-D对路径是有限的, 即当 $k\rightarrow\infty$时 $A_{i}$中路径不再产生变化, 从而对路网中任意一条路段 $a$, 其路段流量为 $x_{a}=\sum\limits_{i}\sum\limits_{p\in A_{i}}\delta_{ap}f_{p}^{k+1}$, 即有

$\begin{eqnarray*} |x^{k+1}_{a}-x^{k}_{a}|\leq \sum\limits_{i}\sum\limits_{p\in A_{i}}\delta_{ap}|f_{p}^{k+1}-f_{p}^{k}|\leq \sum\limits_{i}|A_{i}|q_{i}\zeta_{i}\leq \frac{\varepsilon}{3}, \ k\rightarrow\infty.\end{eqnarray*} $

再证 $|e_{i}^{k+1}-e_{i}^{k+1}|\leq \frac{\varepsilon}{3}, \ k\rightarrow \infty$.

因为 $e_{i}^{k}$是对应第 $i$个O-D的路径流量, 由算法迭代过程 $e_{i}^{k+1}=\alpha_{i}^{k+1}\tilde{e}_{i}^{k}+(1-\alpha_{i}^{k+1})e_{i}^{k}$, 可知

$ |e^{k+1}_{i}-e^{k}_{i}|=\alpha_{i}^{k+1}|\tilde{e}_{i}^{k}-e_{i}^{k}|\leq \alpha_{i}^{k+1}q_{i}=q_{i}\zeta_{i}\leq \frac{\varepsilon}{3}, \ k\rightarrow\infty. $

最后证 $\max\{0, x_{a}^{k+1}-C_{a}\}<\frac{\varepsilon}{3}, k \rightarrow \infty $.

假设当 $k\rightarrow \infty$时有 $\max\{0, x_{a}^{k+1}-C_{a}\}>\frac{\varepsilon}{3}$, 则存在一条路段 $a$, 当 $k$充分大时有 $x_{a}^{k}-C_{a}>\frac{\varepsilon}{3}>0$, 根据 $d_{a}^{k}$, $\triangle d_{a}^{k}$的取法可知 $d_{a}^{k}\rightarrow \infty$, 即有路段行驶时间 $t_{a}^{k}\rightarrow \infty$, 因而可得当 $k$充分大时, 与路段 $a$关联的路径 $p$均有 $\tilde{f}_{p}^{k}=0$, 从而

$ f_{p}^{k+1}=\alpha_{i}^{k+1}\tilde{f}_{p}^{k}+(1-\alpha_{i}^{k+1})f_{p}^{k}=(1-\alpha_{i}^{k+1})f_{p}^{k}=(1-\zeta_{i})f_{p}^{k}\rightarrow 0, \ k\rightarrow \infty. $

既有 $x_{a}^{k+1}=\sum_{p \in P}\delta_{ap}f_{p}^{k+1}\rightarrow 0, \ k\rightarrow \infty$, 这与 $x_{a}^{k+1}-C_{a}>\frac{\varepsilon}{3}$矛盾, 得证.

本文算法通过不断生成最短路来产生新路径, 且总是在最短路上进行流量分配, 而一些较差路径不会被选择, 这符合均衡分配原则.随着迭代次数的增加, 算法将不会产生新路径, 由前后两次路段流量的差异逐渐变小可知流量在不断调节过程中达到广义用户均衡.由于该算法在迭代过程中不断来近似实际路段行驶时间, 所以称为近似算法.虽然算法步骤3中误差因子更新方式与Lagrange乘子法更新方式相似, 但本文算法不需要在每次迭代中进行无约束交通分配运算, 而且每次迭代都更新已产生的所有路径流量, 因此提高了迭代效率.

下面通过一个实例来检验本文提出的分配算法, 考虑下图所示的道路交通网络:

网络中有4个O-D对: 1-12、9-4、12-1、4-9, O-D需求函数为 $d_{rs}=\bar{D}_{rs}\exp(0.5(1-\frac{u_{rs}}{u_{rs}^{0}}))$, 其中 $u_{rs}^{0}$为自由流时O-D对 $(r, s)$间的最短行驶时间; 分别取 $\bar{D}_{1, 12}=460$, $\bar{D}_{9, 4}=400$, $\bar{D}_{12, 1}=440$, $\bar{D}_{4, 9}=420$; 共有34条路段, 路段旁数字表示自由流路段行驶时间, 设每条路段容量300, 采用BPR路阻函数: $t_{a}(x_{a})=t_{a}(0)(1+0.5(\frac{x_{a}}{C_{a}})^{4})$, $C_{a}$为路段 $a$的容量.图中虚线表示算法各O-D对间添加的虚拟路段, 初始行驶时间 $W_{rs}(0)=B_{rs}(D_{rs}(u_{rs}^{0}))=u_{rs}^{0}$.

令 $x_{a}$表示算法得到的路段流量, 分配结果如表 1所示(取 $\varepsilon=1$, 保留小数点后两位).

从表 1可以发现, 在弹性需求情况下, 即使路网比较拥挤, 路段分配流量也不会高于其容量, 本文算法所得的结果中, 最高路段(6, 7) 流量仅为299.78, 意味着在现实情况下该路段达到饱和.虚拟路段流量为 $e_{1, 12}=59.86$, $e_{9, 4}=59.99$, $e_{12, 1}=55.39$, $e_{4, 9}=64.86$表示未出发需求.

图 2给出了算法收敛曲线, 可以看出算法收敛速度非常快, 迭代528次达到收敛标准, 图 3给出了路段(1, 2) 在算法迭代过程中流量的变化趋势, 在100次迭代以后路段流量趋于稳定.

本文提出了一种带路段容量约束的弹性需求用户均衡交通分配近似算法, 这种方法不需要在每轮迭代中采用Frank-Wolfe算法求解无约束交通分配模型, 从而改进了分配效率.本文算法所得分配结果均不超过路段容量, 因此更符合实际路网交通流分布情况.由于分配流量的路径均是各O-D当前迭代下的最优路径, 而未被选中的路径(相对较差的路径)不分配流量, 这恰好符合均衡交通分配原则.本算法不需要路径枚举, 因而它是有效的容量约束弹性需求交通分配算法.后续工作我们将考虑在非对称网络中交通分配问题^[8]中应用.