0.   引言

近30年来, 随着中国国民经济和城镇化进程的进一步加快, 城市规模不断扩张, 城市居民交通需求激增, 由此导致交通拥堵问题已经成为中国大中城市普遍存在的“城市病”, 严重制约了城市的可持续发展, 影响了城市居民的日常出行。其主要原因是交通流量在城市路网中分配的不均衡性, 这种不均衡性是由交通需求引起的, 是一种流量分布状态, 而出行者的路径选择行为是改变这种流量分布状态的关键, 因此, 城市交通拥堵问题的实质在于出行者的路径选择行为, 只有深入了解此行为, 制定调控路段流量的有效措施, 才能快速、有效地缓解交通拥堵问题。Friesz等研究了出行者的路径选择行为, 提出了动态用户均衡(Dynamic User Equilibrium, DUE) 模型^{[1, 2, 3, 4]}, 前提条件是假定所有的出行者均熟悉路网中各条路径的拥挤状况和路径阻抗, 且能够独立地做出令自己的出行阻抗最小的决策。由于实际路网中的交通情况是实时变化的, 路网中的交通流分配也会随着时间发生变化, 出行者并不能完全了解某一时刻路网的交通流分布情况, 对路径阻抗的预测与实际阻抗存在一定的误差。Daganzo等放松了DUE模型的假设条件, 降低了出行者对路径阻抗的敏感程度, 提出了随机用户均衡(Stochastic User Equilibrium, SUE) 模型^{[5, 6, 7, 8]}, 允许出行者预测的路径阻抗与路径实际阻抗之间存在误差, 并将该误差视为随机变量, 同时还允许出行者利用路径感知阻抗选择路径, 使交通分配状况更加接近实际的车流分布情况。为了有效缓解交通拥堵问题, 更准确地模拟出行者的路径选择行为, 国内外学者均致力于基于离散路径选择的SUE模型研究, 因此, 更准确地运用基于离散选择的SUE模型进行交通分配具有重要的理论和现实意义。

针对SUE模型的研究及其求解算法, 国内外已经取得了一些成果。鉴于直接求解SUE模型比较困难, Daganzo等首先提出了一个间接求解SUE模型的方法, 即无约束数学规划模型^[5], 其与SUE模型条件等价; Maher提出SUE模型在弹性需求条件下的交通分配^[9]; Kuang等又将Maher提出的SUE模型扩展成多用户条件下的交通分配, 同时提出了求解该模型的一种算法, 即平衡需求算法(Balanced Demand Algorithm, BDA)^[10]; Meng等提出了一种在固定需求下含有路段容量约束的SUE模型^[11]; 基于广义旅行负效应, Kuang等提出了一种混合SUE模型, 并基于连续平均算法(Method of Successive Averages, MSA) 对其进行求解^[12]; 针对道路出行成本为非对称情况, 运用变分不等式理论, Meng等提出了弹性需求条件下的SUE模型^[13]; 周晶在固定需求和弹性需求下, 假定路段出行成本只与自身流量有关, 首次证明了Logit型SUE模型可表示成一个变分不等式问题^[14]; 况爱武等提出了多用户类弹性需求的SUE模型及其求解算法, 即无环简单路径搜索^[15]; 陈群等通过将理解阻抗的正态分布形式变换为与流量无关的随机变量的正态分布形式, 利用Monte-Carlo仿真将为服从预定概率分布的SUE配流简化为多次求解的确定性用户均衡配流问题^[16]; 周博见等将Logit随机用户均衡模型转化为一个无约束的最优化问题, 再运用截断牛顿算法求解该最优化问题, 并在Sioux Falls网络上比较了梯度投影法与改进的截断牛顿法^[17]; 徐兵等运用变分不等式理论构建了多用户多准则随机交通分配模型, 并设计了一种求解该模型的MSA算法^[18]。MSA算法在求解SUE模型上应用较为广泛, 计算简单, 主要是通过不断迭代来调整各路段的流量分配, 使路段的均方根误差较小, 尽可能地使流量均衡分布到各路段。MSA算法是一种最接近平衡分配法的分配方法, 但仍存在均衡性较低的现象。

蚁群优化(Ant Colony Optimization, ACO) 算法是近年来受到广泛关注的一种自然计算方法, 具有正反馈、鲁棒性强和启发式搜索等特点, 已成功地应用于求解旅行商问题、车辆调度及机器人路径规划等问题^{[19, 20]}。国内外许多研究者将ACO算法应用于用户均衡问题, Matteucci等研究了ACO算法内部参数(如信息素参数、启发因子等) 对其性能的影响^[21]; D’Acierno等提出了一种SUE模型道路交通分配问题的求解算法, 即带有MSA算法框架的ACO算法^[22]; Matteucci等利用ACO算法求解DUE和SUE模型的交通分配问题, 结果表明相比传统算法, ACO算法的随机性可更快地求解SUE交通分配模型, 有更好的应用前景^[23]; 徐勋倩等使用蚂蚁算法求解DUE问题, 验证了ACO算法的可行性, 并提出ACO算法可进一步应用到弹性需求交通分配等问题上^[24]; 安毅生等为了合理分配交通流量, 模拟出行者的行为, 在伪随机状态转移规则的基础上实现了动态路径选择的优化, 结果表明, 相比增量分配法和平衡分配法在路段上的流量分配, 动态路径选择优化方法的分配结果更加均衡^[25]。

现有的信息素更新策略, 主要考虑了使用信息素和OD对间最短路径阻抗的倒数, 这使得OD对间最短路径阻抗的倒数在路径概率选择上作用过大, 易导致最短路径上分配的流量过多, 并造成重叠路段上的流量较大。为此, 本文将同时考虑信息素和启发函数对出行者进行路径选择的影响, 提出基于指数效用函数信息素更新规则的SUE问题求解算法, 并与MSA算法的路段流量分配结果进行比较, 分析这2种算法的敏感性。

1.   随机用户均衡模型

给定一个有向交通网络G= (N, A), N是有向图中全部节点的集合, A是有向图中全部路段的集合。

1.1   约束条件

在对路网中的流量进行分配时, 需要满足流量守恒约束条件, 即OD对的交通需求量等于该OD间所有路径的流量和, 且每条路径上的流量均为非负

式中: f_rs^k为OD对(r, s) 间第k条路径上的流量; q_rs为OD对(r, s) 间的交通需求。

路段流量与路径流量之间的关系为

式中: v_a为路段a上的流量; δ_rs^ak为路段a是否属于OD对(r, s) 间的第k条路径, 是为1, 否则为0。

路段阻抗函数t_a (v_a) 为

式中: t_a⁰为车辆通过路段a的初始自由阻抗; p、q分别为2个校正参数, 取值分别为0.15、4;C_a为单位时间内通过路段a的车辆数。

路段阻抗与路径阻抗之间的关系为

式中: c_rs^k (v_a) 为OD对(r, s) 间根据路段流量v_a计算得到的第k条路径上的实际阻抗。

1.2   问题描述

本文研究的主要内容是SUE模型交通流分配问题, 合理有效的交通分配对于缓解道路拥堵至关重要。SUE模型是从出行者的角度出发, 通过对用户进行交通分配缓解道路交通拥堵问题。在拥挤的城市路网中, 由于出行者对路网的了解程度不一, 对路径的感觉状况也不相同, 因而出行者在进行路径选择时, 均会选择自己认为的阻抗最小的路径, 即感知阻抗最小的路径, 而路径的感知阻抗与实际阻抗之间存在误差, 这个误差是一个随机变量, 即存在路径感知误差项, 则路径感知阻抗是路径实际阻抗与路径误差阻抗之和, 为

式中: C_rs^k (v) 为OD对(r, s) 间根据流量v计算得到的第k条路径上的感知阻抗; c_rs^k (v)、ξ_rs^k (v) 分别为OD对(r, s) 间根据流量v计算得到的第k条路径上的实际阻抗和误差阻抗。

SUE条件除式(1) 外, 还有以下条件

式中: p_rs^k (v) 为根据流量v计算得到的OD对(r, s) 间第k条路径被选择的概率。

根据SUE原理, Sheffi等提出的无约束数学规划模型为^[26]

式中: Z (v) 为目标函数; 为随机变量 的条件期望; b_rs (v) 为OD对(r, s) 间的实际路径时间向量。

根据式(8) 的一阶最优条件, 可得出该无约束数学规划模型的解满足SUE条件和流量守恒约束条件。虽然目标函数的Hessian矩阵一般不是正定的, 但在SUE节点处是正定的, 且在极小值点附近存在一个局部极小值点, 由于目标函数是凸函数, 因此, 该局部极小值点也是全局极小值点, 求解式(8), 即可得到符合SUE条件的流量分布结果。

1.3   SUE模型的求解算法

SUE交通分配是将OD交通量分配到路网中, 通过不断调整路网中各路段的交通量, 使路网最终处于均衡状态。各路段的流量分配是路段与路径流量、阻抗循环作用的结果, 循环流程见图 1。

随着对交通分配的深入研究, 有关SUE模型的求解算法相继被提出, 最初提出的算法是全有全无分配法, 又称0-1分配法, 随后是增量分配法和MSA算法等。MSA算法是一种循环分配方法, 其求解SUE模型的主要思想是: 加载离散选择模型初始化路网, 更新路段实际阻抗; 再次加载离散选择模型, 获取路段附加流量, 将路段已有的流量与获取的附加流量进行加权平均, 得到各路段的流量, 在下一循环中即可使用这些路段流量再次进行交通分配; 计算各路段流量的均方根误差(RMSE), 若RMSE小于规定值时停止循环, 否则继续迭代; 循环完成后, 最后一次循环所获得的流量即为路网均衡时各路段上的交通量。采用增量分配法求解SUE模型, 会引起交通分配问题, 而MSA算法克服了该交通分配问题, 它介于增量分配法和用户均衡分配法之间, 是求解SUE模型中使用最多的算法。

图  1  SUE模型交通分配动态循环流程

Figure  1.  Dynamic cycle flow of traffic assignment of SUE model

下载: 全尺寸图片 幻灯片

ACO算法是一种新型启发式算法, 其求解SUE模型的基本原理是: 在一个有固定OD需求的路网中, 依次将OD对放置在路网规定的起点上, 根据路径选择规则确定车辆路径; 当所有车辆到达路径终点时, 再根据信息素更新规则, 更新所有路径上的信息素; 如此循环, 直至所有OD对均完成路径访问; 再对各路段流量的RSME进行判断, 若RSME小于规定值, 则停止迭代, 否则继续循环。由于ACO算法具有启发式搜索和正反馈特点, 因此, 后续蚂蚁能够快速找到最优路径。

2.   基于ACO的SUE模型求解算法

在对SUE模型进行求解时, 为了模拟出行者的路径选择行为, 根据SUE模型中路径阻抗感知误差项服从的分布情况, 可加载不同的离散选择模型, 如Logit模型、Weibit模型等, 对出行者进行路径选择。本文将在加载Logit模型的基础上, 采用ACO算法求解SUE模型交通分配问题。

2.1   Logit模型

Logit模型假定所有可选对象的效用随机项均独立且服从Gumbel分布, 由随机效用理论、效用最大化假说及路径阻抗与总效用间的反比关系可推导出Logit模型的路径选择概率为

式中: θ为度量出行者对路网熟悉程度的参数, 与误差阻抗成反比。

θ越大, 出行者对路径的感知阻抗误差越小, 即出行者对路网越熟悉, 反之亦然。Logit模型直观易懂, 在实际交通分析中使用较广, 但该模型存在2个缺陷: IIA特性, 即同一个路网中, 路径与路径之间没有关联, 相互独立, 且由于假定了误差阻抗间相互独立, 使得任意2条路径选择概率与其他选择路径的状态无关; 路径的选择概率只与路径之间的实际阻抗绝对差有关。这2个缺陷导致路径与路径之间的重叠路段上分配较多的流量, 而MSA算法在求解时可以避开Logit模型的上述缺陷。

2.2   基于ACO算法的SUE模型实现

根据1.3节中ACO算法求解SUE模型的基本原理可知, 在求解过程中涉及到2个规则: 路径选择规则和信息素更新规则。

2.2.1   路径选择规则

个体车辆从起始节点r移动到终端节点s的路径选择规则为

式中: ψ_rs^k为OD对(r, s) 间选择路径k移动的概率; τ_rs^k为OD对(r, s) 间第k条路径上的信息素量; η_rs^k为OD对(r, s) 间第k条路径上的启发函数; x为信息素的作用强度; y为启发式函数在车辆路径选择上的重要程度。

x值越大, 车辆越倾向于选择其他车辆走过的路径, 车辆之间的协作性越强。启发函数则由路径上的阻抗决定。

2.2.2   信息素更新规则

由于路径上的信息素随着时间的推移存在挥发现象, 通过信息素更新规则可对路径上信息素进行更新, 因此, 信息素更新规则为

式中: Δτ_rs^k为OD对(r, s) 间第k条路径上的信息素增量; ρ为第k条路径上的信息素衰减系数, ρ∈ (0, 1)。

2.2.3   求解算法

根据信息素更新策略的不同, Dorigo等提出了蚁密、蚁量和蚁周3种蚂蚁算法^[19]。基于该思想, 本文借鉴Logit模型的路径选择概率公式, 采用指数形式, 当θ不变时, 路径阻抗与选择第k条路径的概率成反比关系, 建立了基于指数效用函数的如下信息素更新规则, 考虑了路径阻抗感知误差项的影响, 为

基于上述讨论, 图 2为基于ACO的SUE问题求解算法的流程。

图  2  SUE模型求解流程

Figure  2.  Solved flow of SUE model

下载: 全尺寸图片 幻灯片

3.   算例分析

本文采用Nguyen-Dupuis路网模型验证本文方法的正确性和有效性, 该路网模型包括13个节点和19个路段, 见图 3。Nguyen-Dupuis路网中各路段的基本属性与文献[26]中的参数设置一致, 包括路段容量、路段自由阻抗等, 每条路段的基本属性见表 1。在Nguyen-Dupuis路网中定义了(1, 2)、(1, 3)、(4, 2)、(4, 3) 共4个OD对, OD对需求与路径信息见表 2。

图  3  Nguyen-Dupuis路网模型

Figure  3.  Nguyen-Dupuis road network model

下载: 全尺寸图片 幻灯片

表  1  路段的基本属性

Table  1.  Basic properties of roads

下载: 导出CSV 

| 显示表格

3.1   基于ACO算法的流量分配结果

在2.2节中采用ACO算法求解SUE模型的基础上, 本节采用基于式(12) 的信息素更新策略的ACO算法求解SUE模型, 19个路段的流量与阻抗分配结果分别见图 4、5, 其中, θ取值为0.1。

表  2  路网中的有效路径

Table  2.  Effective paths in road network

下载: 导出CSV 

| 显示表格

从图 4、5可以看出: 19个路段的流量分布在40~230pcu, 其中路段2的流量分配最小, 为40pcu, 路段15的流量分配最大, 为230pcu, 分配的流量在150pcu左右的路段的实际阻抗与其自由阻抗相差较大, 而路段9、17最为明显, 主要原因在于路段9、17的路段容量为150pcu·h^-1, 路段容量较小, 且流量较大。

3.2   ACO与MSA算法的结果比较

将2种算法针对19个路段计算的流量和阻抗进行比较, 结果分别见图 6、7。MSA算法计算的路段流量分布为20~280pcu, 而ACO算法计算的路段流量分布为40~230pcu, 将流量的分布区间降低了15.4%, 将路段上流量的最大值降低了7.1%。ACO算法较MSA算法的主要区别在于: 路段2是ACO算法和MSA算法流量分配最小的路段, 但相比MSA算法, ACO算法在路段2上分配的流量较大, 增大了路段流量的最小值; 路段15是ACO算法和MSA算法流量分配最大的路段, 而ACO算法在该路段上分配的流量小于MSA算法, 降低了路段流量的最大值, 同时, 该路段上的阻抗也有所减小; MSA算法在路段9、17上分配的流量相对较小, ACO算法在这2个路段上分配的流量大于MSA算法, 主要原因在于路段9、17的路段容量较小, 因此, 路段阻抗相差较为明显; 采用MSA算法进行流量分配, 在流量分配较多的路段(如路段3、5、6、7、16、18) 上, ACO算法分配的流量均有所减小, 同时, 这些路段的阻抗也有所降低。

图  4  ACO算法流量分配结果

Figure  4.  Traffic flow assignment result of ACO algorithm

下载: 全尺寸图片 幻灯片

图  5  ACO算法阻抗分配结果

Figure  5.  Impedance assignment result of ACO algorithm

下载: 全尺寸图片 幻灯片

图  6  路段流量比较

Figure  6.  Comparison of road section flows

下载: 全尺寸图片 幻灯片

图  7  路段阻抗比较

Figure  7.  Comparison of road section impedances

下载: 全尺寸图片 幻灯片

综上, ACO算法虽然容易受信息素作用强度、启发函数的重要程度与信息素衰减系数等参数的影响, 但是一旦确定了最佳参数组合后, 在求解LogitSUE模型时ACO算法仍优于MSA算法, 采用MSA算法分配在各路段上的交通量变化较大, 而ACO算法分配在各路段上的流量较为均衡, 在流量较大的路段更有利于减小交通拥堵现象。

MSA算法和ACO算法在对Logit-SUE模型进行求解时, 迭代完成后, 2种算法求解的各路段流量标准差相差较大, 分别为65、48pcu, ACO算法较MSA算法分配在各路段上的交通流量更接近19个路段上的平均值, 离散程度较小。根据图 6、7各路段的流量和阻抗分配情况, 2种算法在25条路径上的阻抗比较见图 8, MSA算法阻抗分布较为分散, 而ACO算法计算的88%的路径阻抗分布在61~64, 分布相对集中, 且在84%的路径上, ACO算法计算的路径阻抗低于MSA算法, 因此, 在进行SUE模型交通分配时, ACO算法减少了用户出行时间。

图  8  路径阻抗比较

Figure  8.  Comparison of path impedances

下载: 全尺寸图片 幻灯片

3.3   敏感性分析

采用MSA算法和ACO算法求解Logit-SUE模型时有一个共同的参数θ, 本文针对不同的θ取值, 对2种算法的敏感性进行探讨。图 9(a)~(f) 为不同θ条件下采用2种算法求解的各路段流量, 图 10为不同θ条件下采用2种算法求解的各路段流量标准差, 其中θ分别取0.01、0.1、1、2、7、11。

由图 9、10可知: 采用MSA算法计算的路段流量标准差分别为75、65、50、47、45、45pcu, 采用ACO算法计算的路段流量标准差则分别为48、48、48、47、43、43pcu, 随着θ的逐渐增大, 其分配在各路段上的流量范围逐渐减小, 标准差趋于稳定。总体来看, 2种算法的敏感度在θ=2时最为接近, 流量标准差均为47pcu, 随着θ的增大, 由于信息素更新策略对出行者的路径选择概率的影响较明显, 出行者选择阻抗小的路径的概率变大, 因此, ACO算法在路段上分配的流量更为均衡。与此同时, 调节基于ACO算法的信息素更新规则中存在的3个可变参数x、y、ρ, 可调整信息素更新规则的作用强度, 进一步提高ACO算法性能, 这表明ACO算法比MSA算法具有更强的灵活性。

图  9  求解结果比较

Figure  9.  Comparison of solved results

下载: 全尺寸图片 幻灯片

图  10  流量标准差比较

Figure  10.  Comparison of traffic flow standard deviations

下载: 全尺寸图片 幻灯片

4.   结语

(1) 针对交通流量在路网中分配的不均衡性进行系统研究, 在Logit离散路径选择模型基础上, 提出了基于蚁群优化的随机用户均衡模型求解算法, 其核心思想是在传统的基于路径的选择方法上引入了蚁群优化中特有的节点转移概率公式, 客观地描述了出行者路径选择的行为。同时, 提出了基于指数效用函数的信息素更新规则, 考虑了路径阻抗感知误差项的影响, 有利于实现各路段上流量分布的均衡性。

(2) 以Nguyen-Dupuis路网模型为算例, 采用ACO算法计算各路段上的流量、阻抗及路径阻抗, 并与传统的MSA算法进行了比较, 结果表明: ACO算法对流量的分配更加均衡, 有利于用户出行。此外, 为了更准确地分析ACO算法和MSA算法的交通流分配性能, 讨论了在不同θ条件下, 2种算法的敏感性, 结果表明: 在一定条件下, ACO算法优于MSA算法, 特别是在出行者对路网不熟悉时, 优越性更加明显, 同时, ACO算法比MSA算法具有更强的灵活性。

(3) ACO算法主要针对Logit离散路径选择模型, 除Logit模型外还有Weibit模型、边缘指数模型等扩展路径选择模型, 如何将基于ACO的求解算法应用于这些扩展路径选择模型的SUE问题, 是下一步要研究的内容。