最优路径的诱导是路径诱导系统的重要理论研究部分，其目的就是在已知出行者出行需求的情况下，实时动态地规划出一条最合理的路径，通过诱导出行者的路径选择来改善交通状态，减少车辆在路网上停留时间，能够有效防止交通拥堵，提高整个路面交通系统的运行效率。

国内外学者在有关交通诱导的路网建模、路径寻优算法等方面进行了很多的研究。Yuhong Yang等^[1]建立了动静态广义路网模型，实现了对交通行为的有效描述。Demir等^[2]建立了集群超图模型来描述道路网络，减少了路网的存储空间并提高查询处理速度。Feng Yuqin^[3]运用博弈理论建立了考虑广义出行费用的路径诱导模型。曹政才、郭耕辰等^{[4, 5]}构建了新型的RBM 路网模型以及自适应分层路网模型，提高了路网的信息存储能力。Luca D’Acierno ，Pavel Krmer^{[6, 7]}等人针对蚁群算法的停滞行为和过早收敛的问题进行了改进，将并将其应用于最短路径求解中，有效地实现了路径搜索。李士勇等^[8]将量子计算与蚁群计算相融合提出了适用于连续空间的CQACA算法，提高了算法的寻优效率。贾瑞昱、赵俊生等^{[9, 10]}将量子蚁群算法应用到车辆路径与旅行商问题中，具有很好的全局搜索能力。由以上研究可以看出，在路网模型研究方面，交叉口处的动态信息往往被忽略掉，而作为路网的枢纽道路交叉口往往决定了路网的运行效率；而在算法方面，现有的算法在路径寻优方面往往存在局部最优解以及搜索效率的问题。

本文首先建立了动态路网模型以及基于时间的最优路径模型，然后在量子蚁群算法的基础上对其进行改进，并将其应用到时间最优路径诱导问题中，解决动态路径诱导问题。

1 动态路网模型 1.1 动态交通路网模型与动态最优路径模型

根据交通路网的直观结构，可以将路网用图论的赋权图表示。赋权图中的节点即表示路网交叉口，赋权图中的边表示路网中的路段。路网中的路权这里统称为耗费。在动态路网模型中，将耗费T分成交叉口耗费和路段耗费两部分，是随着时间t的函数，如下描述：

在动态最优路径中，时间最优路径是出行者和管理者最关注的问题，它关系着整个交通路网的运行效率。时间最优路径一个组合优化问题，设t_min为车辆行驶的最优时间，r_ij、r_i、r_j为所经过的路段和交叉口，t_ij为经过连接交叉口i、j的路段所用的时间，t_i、t_j为经过交叉口i、j所用的时间。结合上文，时间最优路径模型如下所示，若最优路径经过节点或路段，则r_ij、r_i、r_j取值为1；反之，取0。

1.2 交叉口时间延误与路段行驶时间计算

实际路网中，影响交通网络通行能力的交通因素分别发生在交叉口和路段上。下面分别对交叉口和路段相关信息进行描述。

信号交叉口延误是由于交叉口处信号控制引起交通流间断而损失的车辆行驶时间，本文以十字交叉路口为例。将排队车辆看做是质点，不考虑其长度。

本文参考排队延误的计算方法，基本公式如下：

t_cp=t₁f+t₂

交叉口排队延误的计算如下：

1)当交叉口处的饱和度X≤1.0时

2)当交叉口处饱和度X>1.0时

路段上的动态信息最重要的就是路段行驶时间。为了减少计算量，本文采用一种改进的BPR函数计算路段行驶时间。

BPR函数形式如下：

由于交通路网的动态性，车辆的交通量不能直接应用，需要转换成交通负荷。则BPR函数变为如下形式：

2 改进的量子蚁群算法

2.1 量子蚁群算法

针对蚁群算法收敛速度慢、易陷入局部最优解的问题，量子蚁群算法(quantum ant colony algorithm,QACA)将量子计算的优点融入到蚁群算法中，可以有效地实现对连续空间的寻优问题。量子蚁群算法的基本思想表现为3个方面：1)将蚂蚁释放的信息素采用位置点更新方式，也就是说将信息素集中到驻留的位置上；2)蚂蚁所在的位置用一组量子比特表示，用量子旋转门移动蚂蚁的位置；3)用量子非门实现当前位置的变异。

量子蚁群算法的主要步骤：

1)根据状态转移规则确定蚂蚁移动的位置；

2)量子旋转门实现蚂蚁的位置移动；

3)量子与非门实现空间位置的变异；

4)将蚂蚁搜索单位空间的位置映射到优化解空间；

5)信息素局部更新与全局更新。

2.2 改进的量子蚁群算法

本文借鉴量子蚁群算法的寻优策略，在其基础上针对量子比特编码以及其变异机制，提出了改进的量子蚁群算法(improved quantum ant colony algorithm,IQACA)。

2.2.1 蚂蚁量子比特编码的改进

在量子蚁群算法QACA中，蚂蚁k在空间中携带一组量子比特，蚂蚁初始位置为

当种群规模不变时，搜索空间增加一倍。在QACA中量子比特编码空间范围为[0,2π]，在概率幅的取值范围内，尽管增加了搜索空间，但是编码空间也会过大，则相角搜索范围过大，从而影响算法的收敛速度。

IQACA算法通过将量子比特相位取值范围缩小的方法，对编码空间进行了改进，将量子比特编码的初始相位角φ_kn限定在[π/2,3π/2]范围内，则φ′_kn=π/2+π×rand，概率幅取值范围仍在(-1,1)，这样就可以提高概率幅的密度。本文在编码时引入一个调整因子k，来弥补缩小编码空间会减小最优解的搜索概率的缺陷。改进的编码方式为

其中引入的调整因子k为大于等于1的常数，本文取k=2。

2.2.2 Hadamard门变异机制

在量子蚁群算法中，当完成蚂蚁位置的量子比特编码，并实现位置移动后，引入了变异机制。在QACA中是利用量子非门实现的变异过程，式(1)描述了其过程。这种变异方式实际是实现了量子位的概率幅互换，其中与非门操作就是使得量子位的幅角实现了π/2的正向旋转，但是其量子位的幅值并没有发生变化，而实际上这种操作也容易造成局部最优的现象。

因此，改进的量子蚁群算法将采用Hadamard门变异机制，Hadamard门表述如下所示：

则Hadamard门变异操作如下：

根据式(2)可以看出，Hadamard门变异策略也是一种相位角旋转，这种旋转不会影响目前搜索到的种群最优位置。Hadamard门变异策略不仅实现了量子比特两个概率幅值的位置互换，也改变了量子位的幅值，扩大了种群多样性，增加了全局最优解搜索的概率。

2.3 改进的量子蚁群算法在路径诱导中的应用

在路径诱导系统中，出行者倾向于选择时间最优的路径，即在交通路网上的行驶时间最短的路径。以时间为评价标准求得时间最优路径时，要根据时间最优路径模型，确定适应度函数，即

在时间最优路径诱导中，将适应度函数引入其中作为权值。根据上述的改进量子蚁群算法，算法流程如图 1所示。

图 1 IQACA算法流程

图选项

3 仿真实验

本文选取了哈尔滨市某区域主干道路网，将其作为城市道路网络的抽象对象，采用本文改进算法进行时间最优路径搜索测试。选取的路网示意图如图 2所示，图 3为其模拟路网赋权图。

图 2 哈尔滨市某区域路网

图选项

图 3 模拟赋权

图选项

初始设置：实验路网路段自由流速V_af为11 m/s。车辆起始点为1，目标点为21。在t时刻路段交通负荷可设置为：连接交叉口13~17以及8~13的路段交通负荷为50 veh，其他路段上的交通负荷取值在5~35 veh，区间内任意可调；t时刻交叉口交通负荷如表 1所示；表 2为3种对比算法的参数设置。

在仿真软件平台下，采用本文的IQACA算法进行距离最优路径的搜索，得到距离最优路径。车辆起始点选定华山北路与先锋路交叉口(即节点1)，目标点选择长江路与红旗大街交叉口处(即节点21)进行相关测试，并与基本蚁群算法、量子蚁群算进行对比分析。运用本文的IQACA算法所得的时间最优路径为：1-2-7-12-16-17-21，仿真图如图 4所示。

图 4 时间最优路径仿真

图选项

由图 5为3种不同算法下，求解时间最优路径时最优解与迭代次数的变化规律。可以看出，IQACA算法在3种算法中的求解效率最高，寻优结果也最好；QACA算法总体表现良好，虽然也搜索到了时间最优解，但效果不如IQACA算法。

图 5 3种算法行驶时间与迭代次数对比

图选项

4 结束语

本文构建了动态路网模型，并描述了时间最优路径模型；提出的改进量子蚁群算法不仅可以提高算法的搜索空间，而且增加了全局最优解搜索的概率；适用于求解时间最优路径问题，具有很好的收敛性能，为今后研究交通诱导系统的最优问题提供了理论基础，具有很好的实用意义。