迂回限制下城市交通网络最短路径算法优化设计

刘 昊

(南宁学院信息工程学院，广西 南宁 530299)

0 引 言

城市交通网络是城市中所有邮电与运输网组成的交通网，也叫城市运输网络。设施、组织、需求和径路网络是城市交通网络的主要组成[1]。交通节点与交通线路组成了设施网络与径路网络，二者相结合即为组织网络。城市交通网络具有开放性和复杂性[2]，城市交通网络路径分析是城市交通网络的关键，而城市交通网络路径分析重点则是最短路径计算[3]，求解最短路径被广泛应用在城市交通学、地理信息学等各种领域中[4]。而迂回限制是指限制车辆迂回次数，或者避免迂回线路，因此在求解城市交通网络最短路径前，考虑实际交通网络中迂回限制下的分布规律、时间、交通网络容量等问题[5]，可确保城市交通网络最短路径优算法更适用于实际。许多专家学者都对城市交通网络最短路径算法进行了研究，并取得了一定的研究成果。

文献[6]提出了一种基于快速收敛牛顿算法的城市最短路径分析。主要将城市道路交通网络作为研究基础，通过快速收敛牛顿(RCN)算法对城市道路网络最短路径进行规划，根据均衡接近原则以及更新速度获取优化步长以及迭代方向，以几种类型不同的道路交通网络为例，通过RCN算法以及GP(梯度投影)算法对收敛速度进行验证。但是该方法存在耗时较长的问题，难以应用到实际生活中去。文献[7]提出了一种基于双端队列的交通网络最短路径Dijkstra算法。采用标号对改进Dijkstra算法的思路进行分析，从运行以及存储结构出发，对该算法进行改进优化的同时对空间以及时间复杂度进行深入研究，最后在大规模城市交通网络中进行效率测试。但是采用Pallottino算法优化城市交通网络最短路径过程中，未考虑实际路况迂回限制下的交通网络流量，导致优化结果精度低。文献[8]提出了一种基于改进Floyd算法的城市交通网络最短路径规划方法。分析了Floyd算法解决车道的设置问题的有效性，但是由于在设置过程中计算量大且效率较低，所以需要对Floyd算法进行改进。改进的算法在计算最短路径过程中，不相连的节点或通过中间节点相连的路径将在判断是否应当舍弃后在进行计算，降低了计算复杂度，但是改进之后的算法依旧存在迭代次数较高的问题。文献[9]提出了一种基于MapInfo的Dijkstra最短路径算法研究。由于MapInfo平台数据结构简单，但是不具备空间数据拓扑关系，存在无法直接分析最优路径的问题，因此建立了路网模型与道路数据的预处理，使用MapBasic语言编程扩MapInfo的功能。在MapInfo平台上成功地建立了空间数据的拓扑关系，实现基于Dijkstra算法的城市交通网络最优路径分析。但是该方法存在耗时较长与鲁棒性较低的问题。

为了解决上述算法迭代次数高，耗时长，计算复杂且精度较低的问题，本文采用优化Dijkstra算法，其主要原因在于为了保持Dijkstra算法保持通用性强、程序设计简单的优点，克服该算法在进行路径寻优时效率较低与占用空间大，严重浪费计算机的资源的缺点，且与其他算法相比，该算法的应用最为普遍，优化价值较大且算法优化后通用性较强，因此对Dijkstra算法进行改进。本文先计算了迂回限制下城市交通网络容量，以此为基础，利用二叉树方法改进Dijkstra算法，并对最短路径进行搜索，实现迂回限制下城市交通网络最短路径运算，提高最短路径运算效率和精度。

1 城市交通网络最短路径算法优化

1.1 迂回限制下城市交通网络容量计算

城市交通网络在规定时间内大概通过车辆及人流的最大流量即城市交通网络容量[10]，城市交通网络需要划分各个城市交通小区，所有城市交通小区起讫点对之间客流分布相加就是城市交通需求总量。

计算城市交通网络容量需要先调查现状起讫点并划分城市交通小区。城市交通网络双向路段依据图论可简单认为是不同方向的两条弧与将路段相连的端点；城市交通网络单行道依据图论可简单认为是与道路网相连部位的点与一条单向弧。因此，有容量约束的点与弧组成了城市交通网络。为使问题简单化，用弧容量来代表交通网络中的点容量，以交叉口容量情况针对点容量折减各路段容量，这时的弧容量为将交叉口点容量加入与折减后的新容量，因此城市交通网络可以用弧容量表示为D=(V,C)。此公式内，V表示为城市交通网络中节点集合，C表示为城市交通网络中弧的集合。

设划分城市交通小区后，起讫点分布如下：

(1)

设各起讫点对占总城市交通网络分布量比例已知，城市交通网络总容量依据增量加载方法求解步骤为：

(1)求解城市交通网络路段零流阻抗与通行情况。寻找该交通网络中距离最短的起讫点对并将其行驶时间计算出来。交通网络中最短距离城市交通小区j点与城市交通小区s点间行驶时间用T(r,s)表示。

(2)城市交通网络中各起讫点对间交通情况矩阵为：

(2)

设总出行城市交通分布增量用ΔQ(m)表示，ΔQ(m)×p=Δq(m)，则有：

(3)

使m=1。

(3)在城市交通网络中分配交通量，分配次数为m。在城市交通网络中利用交通分配方法分配Δq(m)，城市交通网络中行驶时间阻抗被更新[11]。依据阻抗函数获取城市交通网络中各路径行驶时间。当达到或超过通行能力路径时，设定路径行驶时间无穷大。

(4)研究各起讫点段最短路径，同时求解最短路径行驶时间T′(j,s)。若计算中起讫点对间无最短路径时，说明两点之间无路径存在，因此无需继续计算；城市交通网络中最大迂回系数为：T′(j,s)≥δT(j,s)(δ>1)，城市交通网络受迂回限制，因此此种情况下停止计算该起讫点间交通分布量，记录停止计算的各起讫点对交通情况。

(5)当T′(j,s)<δT(j,s)时，证明该起讫点路径行驶时间有限，此时按照步骤6继续进行；否则停止计算，城市交通网络容量为此时所有起讫点对间交通分布量相加[12-13]。

(6)将所有停止计算的起讫点对删除，所有起讫点对间交通分布量相对比例在存在的最短路径满足T′(j,s)<δT(j,s)时保持不变，但交通分布比例矩阵p(m)内的元素值和维数会存在变化，因此使m=m+1，回到步骤2继续运算。

以上计算城市交通容量过程中，考虑了最大迂回系数δ。

1.2 城市交通网络最短路径算法优化

依据迂回限制下城市交通网络总容量，构建城市交通网络模型Q=R(V,E)。R为迂回限制下城市交通网络总容量。V表示将节点综合后形成的新节点集合；E为非负实数，表示相邻节点间距。

E={δdab|dab=F(Y1,Y2,Y3,…)}

(4)

式中，Y1为道路间几何距离即简单距离因子；Y2为路面等级因子；Y3为拥挤程度因子。

利用阻抗值形容通行能力受人、车流量与路面等级作用而引起的变化，城市交通小区内拥挤程度与路段等级利用阻抗值大小来区分[14]。用阻抗值虽然不能表示出受影响的具体大小，但是可以互相进行比较，作为计算依据。

采用优化Dijkstra最短路径算法从城市交通网络模型中道路起点到道路终点，利用二叉树方法按其方向性进行搜索，直至搜索到最短路径为止。其搜索流程如图1所示。

图1 二叉树方法搜索流程

假设r(dj,pj)为城市交通网络中各节点的标号，r表示起点和节点j间迂回限制容量，起点s与节点j最短路径距离为dj，若两点间无相连路径，则其距离为无限大，pj为起点s与节点j最短路径距离的前一节点。用Dijkstra算法获取最短距离是基于顶点进行二叉树循环，循环次数与节点数n相同，随着循环的继续形成了节点s为中心的树，此树随着循环的继续一步步向四周扩大，直到寻找到最短路径计算结束。因该算法计算过于复杂，大部分分支对求最短路径并无帮助，因此需要对此算法进行优化[15]。

求城市交通网络中随机节点s与节点j的最短路径dj，由各节点与各边形成此路径。若dj间各道路与节点s和节点j为同方向，则计算较容易，但是大部分情况，最短路径的节点与边通常不在一条线，因为起点为s，因此将dj简化为从s至j与从j至s两条最短路径，计算过程如下：

(2)从节点s出发，找到节点s与节点j间直线距离夹角最小的边，设A1为此边端点，则有：

(5)

其中，和节点s相关连的节点共有D1个；

从节点j出发，找到节点j与节点s间直线距离夹角最小的边，设B1为此边端点，则有：

(6)

其中，和节点j相关连的节点共有D2个。

起始点为s时选择点为A1，那么前点为A1。重复以上操作直至获取起点是A1同时从A1至j距离最短的边夹角最小。此时获取的路径链为该交通网络中路径最短解。若最终结果为两条或多条，将其经过站点及阻抗值记录，并选择最为合适的路径。

(3)将s、j作为根节点的直线段两端夹角最小的边加入二叉树，利用二叉树方法对其所有节点标记起来，直至与s或j点重合为止。为使计算简便精准，利用广度优先方法遍历该二叉树，可大大减少节点遍历数；对需要加入路径队列的节点实施判断，若该点为终点，那么无需对该点进行计算，更新受该点影响的节点长度。利用以上优化算法计算后，若最终结果大于1，通过对比最终计算出的最优路径阻抗值，选择最合适的路径作为最终结果。

2 实验分析

为验证本文算法的实用性，实验以某城市交通路网为例，在MapInfo环境下对该城市地图实施矢量化，将MapX在VB环境下进行二次开发，便于快速搜索该城市交通网络最短路径。实验平台的计算机配置为Core i3-7100，内存大小256 G，硬盘大小500 G。该交通网络中含有节点数386个，路段共769条。在该交通网络中随机选取10个点，对比分析本文算法、文献[7]算法、文献[8]算法的最短路径优化结果，见表1。

表1 三种算法计算最短路径结果

表1在十个节点间最短路径计算结果，可以看出本文算法比文献[7]算法和文献[8]算法在每两个节点间距离都明显小于其它两种方法，并且本文算法计算路径时选择的节点与路段均为最少，很大程度的缩短了交通路径，说明了本文算法在城市交通网络中计算最短路径的有效性。原因是本文方法利用二叉树方法按其方向性进行搜索，此树随着循环的继续一步步向四周扩大，遍历了所有有可能性的路径，避免了路径对比不全的问题。

三种方法在计算十个节点间最短路径过程中迭代次数见图2。

图2 三种算法迭代次数对比

从图2可以看出，本文算法在计算城市交通网络最短路径时迭代次数明显低于其它两种方法，在9次计算中，迭代次数均在20次左右，远远低于其他两种方法。迭代次数的减少不仅使计算用时降低，而且避免了由于迭代次数过多造成的计算不准确，进一步验证了本文算法的计算效率。

三种算法在城市交通网络最短路径计算用时结果见图3。

图3 三种算法计算用时对比

通过图3三种方法计算城市交通网络最短路径计算用时可以看出，本文算法计算十个节点间最短距离用时在0.1s左右，明显低于文献[7]算法和文献[8]算法。尤其是文献[8]算法在计算1-2节点时，用时高达0.75 s，高于本文算法0.65 s，可以看出本文算法具有较高的计算效率。原因是在使用二叉树搜索最短路径时，利用广度优先方法遍历该二叉树，大大减少了节点遍历数，减少了路径计算时间。

在该实验平台中，依据实验选用三种算法模拟实际出行，选择参数相同的汽车依据三种算法按照时速50km/h进行仿真模拟，实验考虑车辆与行人拥堵，交通红绿灯等状况。统计三种算法仿真用时，具体数据见表2。

表2 三种方法最短路径仿真用时

从表2可以看出，本文算法在考虑了交通状况下的十个节点间最短路径仿真用时最短，本文算法中考虑了城市交通网络迂回路径的限制，使得交通路径运行时间明显缩短，增加了本文算法的实用性，验证了本文算法在实际应用中的有效性。

为验证本文算法对迂回限制下不同城市交通网络中最短路径求解的适用性，在本文实验平台中随机产生具有10—100个节点的网络拓扑，交通网络中的节点与边随机选取[0,200]范围内的整数。将本文算法与文献[7]算法和文献[8]算法循环200次对比仿真结果的准确率，仿真结果见图4。

图4 三种算法100个节点准确率对比

由图4可以看出，文献[7]算法在随机产生100个节点计算最短路径时准确率平均达到70%，而文献[8]算法准确率平均达到了75%，本文算法在随机产生100个节点计算最短路径时准确率平均高达99%，本文算法准确率远远高于其他算法，说明了本文算法在节点数目大时，城市交通网络情况复杂时，运算结果同样准确。

表3为随机产生100个节点计算最短路径时三种方法计算用时。

表3 三种算法计算100个节点用时对比

表3可以看出，节点个数与计算用时成正比增长，本文算法计算大量节点时用时明显少于文献[7]算法和文献[8]算法，本文算法在计算100个节点时，用时仅为0.37 s，而文献[7]算法与文献[8]算法用时达到了1.34 s与2.01 s，本文算法比其它两种算法减少了0.97 s与1.64 s，验证了本文算法具有较高的计算效率。

三种算法的鲁棒性对比结果如图5所示。

图5 三种算法鲁棒性对比

分析图5可以看出，本文算法在计算100个节点最短路径时鲁棒性最好，平均在95%左右，并且本文算法鲁棒性不受节点数量增大的影响，且变化较为稳定，而文献[7]算法和文献[8]算法鲁棒性随着随着节点数的增加而降低，且变化幅度较大，说明这两种算法不稳定，从鲁棒性变化幅度方面验证了本文算法在面对大量数据时稳定性。原因是计算城市交通容量过程中，考虑了最大迂回系，以此为基础构建的城市交通网络模型使得在网络过载或者受到攻击的情况下，计算也可以较好的进行。

以上大量实验可以看出，本文算法在计算某城市交通网络最短路径时，求解过程中搜索的节点与边为三种方法中最少的，并且计算过程中迭代次数最少，计算用时少于另两种方法，计算结果最为准确，可以精准的计算出迂回限制下该城市交通网络最短路径。为验证本文算法操作大量节点时稳定性，在实验平台随机选取了100个节点通过三种方法进行运算，结果可知本文算法在计算100个道路节点时准确率高达99%，计算用时低至0.37 s，本文算法鲁棒性最好，再次验证了本文算法的精准性与实用性。

3 结 语

最短路径计算是城市交通网络中最基本以及最重要的应用。以往搜索交通网络中最短路径计算的是两个节点之间的几何距离最短路径，该最短路径应用在公路交通网络中具有重要的意义，但是对于城市交通网络，存在城市道路路面等级问题与车辆或行人拥挤程度问题，因此几何距离最短路径并不代表为最优路径，本文算法在计算最短路径的前提下，考虑了道路迂回限制，增大了算法的实用性。经过大量实验证明，本文算法计算路径时选择的节点与路段均为最少，很大程度的缩短了交通路径，本文算法在计算时间、计算迭代次数、计算精准度以及鲁棒性方面都优于对比方法，实际应用价值高。在未来随着信息技术的不断提高，需要将最短路径计算与导航技术有机结合，以提高最短路径计算的综合实用性，实现城市交通流的有序流动。