一种城区交通管制条件下的新型择径方法

摘要

本发明涉及一种城区交通管制条件下的新型择径方法，其技术特点是：用二极管截止特性支路模型表示公路交通网络中受到交通管制的公路；并将二极管超越指数型V-A特性函数进行逐区间线性化，在此基础上，以二极管截止特性支路模型建立超越模拟电路网络,并采用改进型迭代法求解上述超越模拟电路网络模型的各个节点电压，进而得到从择径起点至择径终点的最优路径。本发明通过对非线性电子器件二极管的伏安特性进行分段线性化处理，并且改进迭代过程中的控制策略，使得路径规划方法的计算效率得到提高，并且复杂性分析与仿真实验证明了本方法的有效性与可行性。

说明书

技术领域

本发明涉及一种新型择径方法，特别涉及一种城区交通管制条件下的新 型择径方法。

背景技术

随着北京、天津、上海、广州等一线重大城市的快速发展，道路交通网日 趋复杂。现代城市复杂交通环境包含路段长度、车道数目、路面质量、实时 车流密度、实时拥挤程度、单行道、禁止左转弯等属性。面对庞大的公路交 通网络及日益增加的机动车保有量，交通管理部门多措并举治理交通拥堵， 其中疏导车流、限路限行是其中一种有效措施。复杂交通网智能导航系统的 最优路径规划是在满足基本道路约束(单行道)与响应实时道路信息的条件 下，综合全交通网各路段属性，优化出满足用户要求的最佳路径。

在智能交通导航系统的最优路径算法中，城市交通网络被映射为线性纯电 阻电路网络。该电路网络与交通网络具有相同的拓扑结构，并且电路网络的 支路电阻值表达路况信息，畅通、长度短、路况好的路段电阻小。电路网中 小电阻支路有大电流通过的性质与交通网中短、宽路径较优的性质相互对应

但现有技术中的非超越模拟电路没有对电气量-电流走向约束，故只可使 用于无交通管制的中小城市简单公路网络。而现代城市城区交通管制下的方 向限制条件无法用非超越模拟电路表达。

而且，现有技术中针对非超越模拟电路常用的最优路径规划算法有改进型 Dijkstra算法、遗传算法、神经网络算法、电路地图算法等。而在面对交通 网中单行道的局部约束问题(即超越模拟电路)时，上述方法无法解决。或 是理论上通过广义牛顿-拉弗逊迭代方法、广义阻尼牛顿-拉弗逊方法虽可得 出上述超越模拟电路网络的各个模拟电位。但此类连续型超越模拟电路方程 组是非线性方程组，上述算法在计算求解过程中普遍存在对初始值设定敏感、 收敛域较小、复杂性过高、收敛速度慢等问题。

发明内容

本发明的目的在于克服现有技术的不足，提供一种设计合理、可行有效 且计算求解过程简易的城区交通管制条件下的新型择径方法。

本发明解决其技术问题是采取以下技术方案实现的：

一种城区交通管制条件下的新型择径方法，包括以下步骤：

步骤1、用二极管截止特性支路模型表示公路交通网络中受到交通管制的 公路；并将二极管超越指数型V-A特性函数进行逐区间线性化，在此基础上， 以二极管截止特性支路模型建立超越模拟电路网络,转化后的二极管截止特 性支路模型的逻辑判断非超越方程为：

$\left(\begin{array}{cc}\mathrm{if}(v>0)& G=f(a,b,c···)\\ \mathrm{else}& G=0\end{array}\right)$

其中,v为模拟电路中该段电压，G为模拟电路中该段电导，f为电导函数， a、b、c为决定此路段所花费时间的因素；

步骤2、求解上述超越模拟电路网络模型的节点电压,具体方法包括以下 步骤：

(1)判断整个公路交通网络中受到交通管制而限行的公路的数量；

(2)若整个公路交通网络中只有一条公路受到交通管制而限行，则首先 将该交通管制而限行的公路以外的公路交通网络转化为具有若干内部节点和 对外接口的非超越模拟电路；通过解决纯电阻电路的方法求得该非超越模拟 电路中各个节点电压；并根据戴维南等效原理进一步确定从该条因受到交通 管制而限行公路向整个公路交通网络观察的设有外部激励的非超越模拟电路 网络的等效电路；然后，在上述等效电路基础上，判断是否将二极管截止特 性支路加进上述非超越模拟电路,进而构造新的非超越模拟电路网络；最后， 应用解决纯电导电路的方法，得到新的非超越模拟电路网络节点电压；

(3)若整个公路交通网络中有多条公路受到交通管制而限行，则超越模拟 电路网络中包含有多个二极管截止特性支路，采用改进型迭代法求解超越模 拟电路节点电压。

而且，所述改进型迭代法求解超越模拟电路节点电压的具体步骤包括：

步骤(1)求解初始内外节点电压；

步骤(2)确定方程初始状态；

步骤(3)系统电压状态迭代求解节点电压；

步骤(4)判断二极管截止特性支路电流是否存在误差，若存在误差， 则返回步骤(3)继续迭代；若不存在误差，则输出结果。

而且，所述求解初始内外节点电压的具体方法包括以下步骤：

(1)将因受交通管制而限行的d条公路移除，则剩余的非超越模拟电路 网络变为具有d个端口的设有外部激励并且具有若干内部节点和对外接口非 超越模拟电路网络。

(2)编制该具有外部激励的非超越模拟电路网络的非超越模拟电路方 程，求解出该设有外部激励的非超越模拟电路网络内部电位与外部端口电位；

而且，所述确定方程初始状态的具体步骤为：

检验外部端口电位与所有二极管截止特性支路的适配情况，将正极端口 要接高电位的二极管截止特性支路全部以纯电导支路的形式加进到d端口， 其他二极管截止特性支路不加进，进而构造新的非超越模拟电路网络，并确 定方程的初始状态。

定义向量N＝[N_i]_d×1，描述d个二极管截止特性支路的状态：

而且，所述系统电压状态迭代求解节点电压的具体步骤为：

定义并计算二极管截止特性支路误差电流列向量E＝[E_i]_d×1：则 进而得出E的最小元素E_m和其所在支路号 m；

其中，E_i为第i条支路的误差电流、N_i为第i条支路的状态量、为d 个二极管截止特性支路中第i条支路的电导、为第i条支路正极电压、为第i条支路负极电压；

若E_m＜0，则存在二极管截止特性支路不满足二极管约束条件的情况， 改变第m条二极管截止特性支路的状态；

若E_m≥0，则所有二极管截止特性支路满足二极管截止特性支路的约束条 件，从而确定等效线性电路的拓扑结构；确定电路的拓扑结构后，将含多条 二极管截止特性支路的电路网络转化成为线性纯电导电路网络，应用解决纯 电导电路的方法，得到新的非超越模拟电路网络的节点电压。

而且，所述改变第m条二极管截止特性支路的状态的具体方法为：若 N_m＝1，则将其从d端口中切除；若N_m＝-1，说明电流存在误差，则将其投 入d端口，继续迭代。

而且，判断是否将二极管截止特性支路加进上述非超越模拟电路的具体 步骤是：判断将二极管截止特性支路加进前的两端电压的电压关系，若二极 管截止特性支路正极接高电位，则将含相同电导的线性支路加进非超越模拟 电路网络中，若二极管截止特性支路负极接高电位，则不将其加进非超越模 拟电路网络。

本发明的优点和积极效果是：

1、本发明比较了因交通管制而限行公路与非线性二极管单向导电之间的 类似特性，在电路地图基础上建立了城市交通网的电路网络模型，并提出一 种基于二极管截止特性支路模型的车辆最优路径规划方法；该方法通过对二 极管截止特性电子器件二极管的伏安特性进行分段线性化处理，并且改进迭 代过程中的控制策略，使得路径规划方法的计算效率得到提高，并且复杂性 分析与仿真实验证明了本方法的有效性与可行性。

2、本发明提出基于二极管截止特性电路的最优路径规划算法，通过对线 性电路在特殊局部进行以二极管截止特性电子元件为基础的建模与变构，解 决了因交通管制而限行公路的最优路径规划问题。本发明在分析了因交通管 制而限行的公路局部最优化的基础上，将二极管截止特性电路求解过程离散 线性化，克服了由传统泰勒级数建立的二极管截止特性方程迭代过程过于繁 琐的缺陷，并且运算过程更广泛适用计算机控制，在保证精度的前提下简化 了规划方法，对快速发展的复杂交通智能导航系统具有重要意义。

附图说明

图1是本发明的二极管截止特性支路电路模型图；

图2是本发明的二极管截止特性支路正极接高电位的戴维宁等效电路 模型图；

图3是本发明的二极管截止特性支路负极接高电位的戴维宁等效电路 模型图；

图4是本发明的d端口及其二极管截止特性支路模型图；

图5是本发明的改进型迭代法求解节点电压的计算流程图；

图6是本发明交通管制条件下的超越电路网络模型图

具体实施方式

以下结合附图对本发明实施例做进一步详述：

一种城区交通管制条件下的新型择径方法，包括以下步骤：

步骤1、用图1所示的二极管截止特性支路模型表示公路交通网络中受到 交通管制的公路；并将二极管超越指数型V-A特性函数进行逐区间线性化， 在此基础上，以图1所示的二极管截止特性支路模型建立超越模拟电路网络 模型；

转化后的二极管截止特性支路的逻辑判断非超越方程变为：

$\left(\begin{array}{cc}\mathrm{if}(v>0)& G=f(a,b,c···)\\ \mathrm{else}& G=0\end{array}\right)$

其中v为模拟电路中该段电压，G为模拟电路中该段电导，f为电导函数， a、b、c为决定此路段所花费时间的因素，例如：公路长度、车道数量、车流 密度等。

步骤2、求解上述超越模拟电路网络模型

其中，步骤2的具体步骤为：

(1)判断整个公路交通网络中受到交通管制而限行的公路的数量；

(2)若整个公路交通网络中只有一条公路K受到交通管制而限行， 则首先将该K公路以外的公路交通网络转化为非超越模拟电路，通过解决 纯电阻电路的方法求得该非超越模拟电路中各个节点电压；并根据戴维南 等效原理进一步确定从K公路向整个公路交通网络观察的设有外部激励的 非超越模拟电路网络的等效电路，所述等效电路，如图2、图3所示；然 后，在上述等效电路基础上，判断是否将表示因受交通管制而限行的公路 的二极管截止特性支路模型加入上述非超越模拟电路网络中，其具体判断 方法为：首先、判断将二极管截止特性支路加进前的i、j两端节点电压的 电压关系，如图2所示，若二极管截止特性支路正极接高电位，则二极管 导通且影响整个网络电流分布。但此时i、j节点电压依然满足投入前的关 系，与仅含电导的线性支路形式投入网络一样，不会影响k支路的局部约 束条件，因此，将含相同电导的线性支路加进非超越模拟电路网络中；若 二极管截止特性支路负极接高电位，如图3所示，则二极管截止特性支路 截止而不影响原网络电流分布，因此不将其加进非超越模拟电路网络，进 而构造新的非超越模拟电路网络；最后，应用解决纯电导电路的方法，得 到新的非超越模拟电路网络节点电压；

(3)若整个公路交通网络中有d条(多条)公路受到交通管制而限行， 投入(或切除)一条二极管截止特性支路会影响其他端口电压而改变其他 二极管导通情况和网络拓扑结构，因此，采用改进型迭代法求解超越模拟 电路节点电压，其具体步骤如图5所示：

①求解初始内外节点电压

如图6所示，将因受交通管制而限行的公路4移除，则除去d条二极管 截止特性支路的超越模拟电路网络视为具有d个端口的设有外部激励8的非 超越模拟电路网络，简称d端口。列写d端口内部非超越模拟电路的方程式， 解得上述非超越模拟电路的内节点2电压列向量U与d端口5的电压。

②确定方程初始状态

检验d个端口电压与所有二极管截止特性支路的适配情况，如图4中 虚线所示，将阳极端口要接高电位的二极管支路全部以纯电导支路1的形 式投入到d端口，其他二极管截止特性支路不投入，构造如图6所示的新 的非超越模拟网络，其中设定择径起点6、择径终点7以及交通网络的等 效拓扑连接3；

定义向量N＝[N_i]_d×1，描述d个二极管截止特性支路的状态：

③系统电压状态迭代求解节点电压

定义并计算非超越模拟电路的误差电流列向量E＝[E_i]_d×1：则 进而得出E的最小元素E_m和其所在支路号 m；

其中，E_i为第i条支路的误差电流、N_i为第i条支路的状态量、为d 个二极管截止特性支路中第i条支路的电导、为第i条支路正极电压、为第i条支路负极电压。

④判断二极管截止特性支路电流是否存在误差，若存在误差，则返回 步骤③继续迭代；若不存在误差，则输出结果。

若E_m＜0，则存在二极管截止特性支路不满足二极管约束条件的情况 (E的负值元素所对应的二极管截止特性支路均不满足约束条件)。改变第 m条二极管截止特性支路的状态，即若第m条支路状态为N_m＝1，则将其 从d端口中切除；若N_m＝-1，说明电流存在误差，则将其投入d端口，继 续迭代。

若E_m≥0，则E所有元素非负，即所有二极管截止特性支路满足二极管约 束条件的情况，此时的N描述了d条二极管截止特性支路的状态，从而确定 了等效线性电路的拓扑结构，输出结果；再将含d条二极管截止特性支路的 电路网络转化成为线性纯电导电路网络，应用解决纯电导电路的方法，得到 新的非超越模拟电路网络节点电压。

需要说明的是：因为一条支路电流的改变对整个网络其他支路电流的影 响程度，与投入(或切除)该支路前后电流的变化量正相关，所以每次迭代 时都是对投入(或切除)前后电流变化最大的支路进行处理。随着迭代过程 的进行，不满足二极管截止特性支路电压电流约束条件的程度越来越小，结 果不断接近于真值。并且所有二极管通断状态组合的有限性和真值的存在性， 所以迭代结果一定收敛并使所有二极管截止特性支路同时满足约束条件。上 述改进型迭代算法的复杂性分析。

设计以下三点前提以消除执行方法下机器速率与示例特殊性的影响：

1.定义执行该方法进行一次加减乘除及比较等基本验算均需要相同时 间，该时间为单位时间；

2.方法的复杂性定义为该择径方案的效果，即将固定规模的实例需要被 执行基本验算次数的上限；

3.定义F₁(x)与F₂(x)为正整数集上的两个正实数函数，若有一个大于零的 常数D，使得当x足够大时有F₁(x)≤DF₂(x)，记F₁(x)＝O[F₂(x)]。

以节点数为x，支路数为b的复杂交通网为例，研究分析该方法的复杂性。 该x-1阶非超越模拟电路网络并搜索最大电流通路的验算次数最多为：

$F_1=\frac{1}{2}{(x-1)}^2[2{(x-2)}^2-1]+2{(x-1)}^2+D_1(x-1)=O\left(x^4\right)$

其次，假设在最坏情况时所有b个方向限制模型需要全部进行迭代。由 于该方法的优化性，每次调整最大电流变化的方向限制模型极性，出现一个、 两个或多于两个的方向限制模型极性由符合条件变为不符合条件情况的概 率，会随着电路网络规模的增大而趋于0。略去两个或多于两个的情况，并按 一个方向限制模型的最坏情况分析。迭代方向限制模型支路的验算次数：

F₂＝[b²+(b-1)²+…+2²+1²]＝O(b³)

最后，整个方法的复杂性为F＝F₁F₂＝O(x⁴b³)，故该方法有多项式界，即该 方法是有效的。

本发明所提出的路径规划方法还可以扩展应用于有特殊行为要求的机器 人控制系统，只要对行为约束条件建立二极管截止特性电子元件模型，应用 离散线性化的迭代方法即可求解。

需要强调的是，本发明所述的实施例是说明性的，而不是限定性的，因 此本发明包括并不限于具体实施方式中所述的实施例，凡是由本领域技术人 员根据本发明的技术方案得出的其他实施方式，同样属于本发明保护的范围。