孙琦，袁才鸿

（214072 江苏省 无锡市 无锡市政设计研究院有限公司）

0 引言

随着经济发展和城市化的推进，交通拥堵日益加剧。发达国家研究的智能交通系统（ITS）的核心之一就是动态交通分配（DTA）。1978 年，Merchant 和Nemhauser[1]首次提出了动态交通分配模型，为交通管控和诱导提供了新方法和思路。经过长期的研究，其体系已较为完备，其中又以最优控制模型最为成熟。最优控制模型根据不同的目标可分为动态系统最优（DSO）和动态用户最优（DUO）。它们最大的差别在于DSO 不必对出行者的路径选择行为进行假设，虽然更简单但不符合实际，因此，DUO 更具有实际应用价值。

学者们大都使用Frank-Wolf、连续平均法等数值算法求解动态分配模型，虽然能降低计算复杂度，但却无法适用于实际大规模网络。为了解决这一问题，学者们开始使用启发式算法求解DTA 模型，例如神经网络、遗传算法等。其中，蚁群算法（Ant Colony Optimization，ACO）由于其分布式并行计算的特性，在动态交通分配领域得到了广泛应用。学者们也提出了许多ACO 的改进算法，但这些改进算法的主要目标是改进算法求解质量和效率，而忽略了时变的出行状况在算法中的体现，例如，实际出行中出行者易于通过手机地图、车载导航、道路状况播报屏等获得较为准确的实时道路情况，根据所得信息动态调整出行路线。因此，蚁群算法在保证算法效率的同时，在增加实际性方面还有很大的改进空间。

1 动态用户最优配流模型

DSO 是从管理者的角度力求路网的流量分布达到均衡，使整个系统的阻抗最低。但是出行者作为独立的个体，他们的择路行为具有不确定性，在大规模路网中DSO 往往不能体现出这一复杂性。而DUO 是从用户角度出发，每个出行者都能选择自身感知最小阻抗的路径，达到个体的阻抗最优，进而促成系统的动态平衡。魏秋月[2]认为，DUO 假定每个出行者都能了解路网并选择感知阻抗最小路径的说法不太符合实际，她认为，出行者并不能完全了解路网实时状态。但是在智能交通设施日益完善的今天，一些手机导航软件、车载导航设备都能够提供较为准确的实时路况信息，路口、路段安装的智能视频监控设备也能将检测的实时流量在电子显示屏实时播报，出行者可从多方渠道获取较为准确的实时路况信息，从而合理规划、调整出行路线。由此看来，DUO 更符合现代智能化出行条件下出行者的择路行为。

将DUO 模型的[0，T]时段分成K+1 个部分进行离散化，表达式具体如下：目标函数：

式中：xa(t)，ua(t)，va(t)——t 时刻路段 a 上的流量、流入率、流出率；时刻进入路段a 要到终点s 去的流量、流入率、流出率；ca(t)（瞬时阻抗）=g1a[xa（t），ua（t）]（运行时间）+g2a[xa（t），va（t）]（等待延误时间）；gls（t）——节点l 新产生的流量。

2 基于阻抗动态反馈的蚁群系统算法

蚁群算法由Dorigo[3]于1991 年提出，在DTA领域得到了长足发展，许多改进蚁群算法也相继被提出，如带精英策略的蚂蚁系统、基于排序的蚂蚁系统、最大-最小蚂蚁系统等，其中以蚁群系统的综合性能最佳，但是蚁群系统在大规模问题的计算中仍然存在全局搜索能力差的缺点。

2.1 蚁群系统（ACS）模型

蚁群系统由Dorigo[4]于1996 年提出，在ACO 的基础上进行了如下改进。

（1）ACS 在状态转移规则中添加了伪随机比例规则，能够利用以信息素形式存储的信息等先验知识，进行更有倾向性的探索

（2）ACS 重新定义了信息素更新规则。规定每次循环后更新局部信息素，避免蚂蚁收敛到同一路径；蚂蚁全部到达终点后，只在最优蚂蚁路径上更新全局信息素，这种改进使得最优路径和其他路径间信息素的差异越来越大，使得搜索能很快地集中于最优和次优路径的解集范围内，极大提高了搜索效率。

局部信息素更新规则：

全局信息素更新规则：

式中：λ——挥发参数（0<λ<1）；ρ——信息素挥发系数（0<ρ<1）；Lgb——当前全局最优路径。

2.2 基于阻抗动态反馈的改进ACS 模型

国内外学者对ACS 进行了很多研究。曹继英[5]考虑道路容量限制，使用ACS求解DUO模型，并与MSA 算法比较证明其优越性；Alaya[6]等对ACS 的蚂蚁数和信息素路径进行参数化改进，并与其它算法进行了比较；常玉林[7]等考虑交叉口延误因素对信息素更新机制进行调整，取得了很好的效果。可见，现有ACS 的改进大都是为了提高局部搜索效率，适用范围仅限于小规模问题，却没有考虑到求解大规模搜索问题时，算法的全局搜索能力是和解的质量直接挂钩的，所以，提高ACS 的全局搜索能力对求解大规模分配问题具有决定性的重要意义。

本文考虑通过在ACS 中加入实际因素的指导来改进算法的固有机制，从而增加算法的全局搜索能力。其原理为：根据蚂蚁寻路的结果计算出路段实际阻抗，再反作用于蚂蚁寻路，指引蚂蚁去往阻抗更低的路段。如上节所述，全局信息素更新保证了局部搜索的效率，加入实际阻抗因素可以保证增加最优路段的周边路段的竞争力，保证算法的全局搜索能力且更加符合实际出行情况。主要改进3 部分：

（1）基于元胞传输的实际阻抗计算

现有DUO 模型中计算阻抗的方法大都采用BPR 函数，虽然简单但是精确度不高。本文基于一种宏观交通流理论-元胞传输理论提出一种实际阻抗计算方法，保证实际阻抗计算的精确性。元胞传输理论顾名思义就是将路段划分为一个个首尾相连元胞组，将车辆通过路段的过程离散化为车辆通过一个个元胞的过程，从而得到较为准确的路段实时的流量和密度[8]，进而可以计算出路段实际阻抗。方法具体如下：

以求解t 时刻流入路段a 的交通量ua(t)的实际阻抗为例，将这部分交通量看作车队，车队在将来t+x 个时段完全流出路段。对路段首尾元胞提取数据可以得到路段累计流入、流出量Ua(t)，Oa(t) 和路段车辆数Ca(t)，进而对t～t+x 的数据处理可得Ua(t)的实际阻抗，基础关系式如下：

把ua(t)的行驶状态分为3 种（如图1 所示）。状态1 和状态3 分别为ua(t)的车头和尾部开始流入和流出路段，这2 个状态会有上、下一时刻的车辆混合流出路段，故对这两个状态离散化计算。状态2 为ua(t)的主体连续流出路段，因此，考虑根据放行流率曲线进行积分计算，保证解的准确性，具体如下：

式中：ca（t）——ua（t）的平均实际阻抗；ca（t）'——状态1 的实际阻抗，依此类推。根据状态1，2，3 的分界时刻和式（9），分别计算如下：

图1 流入量行驶状态图Fig.1 Traffic inflow driving state diagram

（2）对信息素更新机制的改进

全局信息素更新机制是为了使蚂蚁很快集中到最优路径范围内，但在提高局部搜索效率的同时，却丧失了全局搜索能力，因此，本文以路段实际阻抗作为决策因子动态调整路段信息素浓度，在进行信息素更新时，不光扩大最优路径的信息素浓度，同时使周围路段的信息素浓度小幅减小，保证周围路段的吸引力，增加全局搜索能力，具体如下：

式（14）为信息素挥发系数自适应调整公式，ρmax和ρmin取经验值分别为0.9 和0.1；cf——自由阻抗。

式（14）可以根据实际阻抗调整信息素挥发系数，从而改变路段信息素浓度，指导蚂蚁选路。例如：假设某路段很拥堵，则实际阻抗就很大，根据式（14），该路段信息素挥发系数会变大，路段信息素快速挥发，浓度会骤降，对蚂蚁的吸引力会变弱，蚂蚁会更倾向于其他路段；反之，路段很畅通就会对应很小的信息素挥发系数，蚂蚁不断选择该路段的同时，路段信息素小幅挥发，信息素浓度整体呈现增长趋势，能够持续吸引蚂蚁直至路段变得拥堵。

（3）对状态转移概率公式的改进

状态转移概率公式的参数主要有路段信息素量和路段信息启发程度，信息素量取决于信息素更新机制。曹继英在文献[9]中对ACS 的信息素启发程度进行了改进，使用阻抗替换原有路段长度，即把ηij=1/lij替换为ηij=1/τij。但是出行者择路时，会综合考虑路段拥堵状况和路段长度双重因素，因此，本文考虑在信息素启发程度中加入阻抗和路段长度的权重系数作为择路依据，定义为ηij=1/（x·τij+y·lij），其中，x 和y 为阻抗和路段长度的权重，根据经验分别取6 和4。综合考虑阻抗和路段长度因素更符合实际情况。

总体来说，本节对ACS 的改进是为了实现实际阻抗指导蚂蚁选路，算法中蚂蚁代表实际的流量，通过实际阻抗这一因子，实现蚂蚁选路结果（即流量分布）和选路过程的循环相互作用，保留算法原有优势机制的同时增强了全局搜索能力和实际性。

3 算法具体实现流程

使用上节提出的改进ACS 求解动态用户最优分配模型，具体流程如下：

我姨妈是从她的嗓音里辨认出她的。姨妈挤在法庭外面的人群里，从悬在电线杆上的高音喇叭里听见了她的证词，尽管她用的是另一个名字。

Step1：初始化。确定参数：路网坐标（禁忌表）；OD 交通量；自由流速度vf；阻塞密度kjam；蚂蚁数m；迭代次数NC；信息和期望启发因子α、β；初始信息素挥发系数ρ0。

Step2：初始流量置0，初始信息素浓度Δτij（0，1）。将初始时段所有OD 对蚂蚁放在起点，起点禁忌表值置为1。

Step3：寻路开始，根据禁忌表确定下一步的节点，判断路段容量是否达到限制，进而根据式（6）确定下一个节点，并将所选节点对应禁忌表值置1。

Step4：根据式（7）局部更新信息素，并按式（10）—式（13）更新各路段流量和实际阻抗，将计算值存入阻抗矩阵。

Step5：根据阻抗矩阵中各路段的实际阻抗，对式（6）进行更新。

Step6：重复Step3，4，5 直到所有蚂蚁都到达终点。

4 算例测试与分析

为了验证上述提出算法的有效性，本文引用Nguyen-Dupius 经典路网模型[10]。路网算例如图2 所示，共由13 个节点和19 条路段组成，共有2 组起点和终点：节点1 与4、节点2 与3，易知OD 对一共为4 对，可组合成25 条路径。路段容量限制和自由阻抗采用陆化普[11]设置的属性。

图2 Nguyen-Dupius 路网Fig.2 Nguyen-Dupius network

分别使用ACS 和改进ACS 求解DUO 模型，将改进ACS 和基本ACS 对案例路网流量的分配结果如表1、图3 所示。一般，ACS 与本文改进ACS 求解所得流量均具有路段2 最少和路段15最多的共同特征，且均未超过路段容量限制，基本ACS 流量分布在41-233 之间，改进ACS 流量分布在54-185 之间。

如表1 所示，除了路段1，2，9，17，19，改进ACS 的阻抗值比基本ACS 略高外，改进ACS 计算其余路段的阻抗均优于基本ACS，这是因为节点分岔处另一路段吸引大量车辆，改进算法自动将车辆分流至长度虽然较长但是阻抗较低的路段。通过比较各路段阻抗值比较可以明显看出，改进ACS比基本ACS的分配结果更均衡合理。基本ACS 各路段分配流量标准差为49.2，阻抗标准差为15.0，改进ACS 各路段流量标准差为37.7，阻抗标准差为14.8，改进ACS 计算结果的各路段流量和阻抗更接近平均值，离散程度较小。将两种算法计算阻抗结果按25 条路径生成路径阻抗散点图，如图4 所示。基本ACS 路径阻抗差异大，改进ACS 计算阻抗相对集中，路网利用率更高。

表1 案例路网分配结果分析Tab.1 Analysis of assignment results of case network

图3 路段分配流量图Fig.3 Road assignment flow chart

图4 路径分配阻抗图Fig.4 Path assignment impedance graph

5 结论

本文针对现有蚁群系统算法全局搜索能力差、无法计算大规模分配问题的缺点，基于ACS的固有机制，采用阻抗动态反馈的方法，通过每步蚂蚁寻路结果动态调整信息素更新公式与状态转移概率公式，在保证ACS 局部搜索优势的前提下，增加算法的全局搜索能力。通过使用改进前后的算法对案例路网进行求解，输出路段流量和目标函数阻抗值，结果表明，改进算法分配结果更均衡，结果离散程度小，在最短路径通行能力不佳的情况下能有效利用次优路径，并根据路段阻抗保持路径选择的动态平衡，实现系统的阻抗最优，路网利用率高。下一步工作为使用改进算法和其他启发式算法对实际大规模路网进行求解，验证算法的有效性。