一种基于分层交通网络的动态路径选择算法

陈端芝

(福建财会管理干部学院 计算机系，福建 福州350001)

许多导航仪只能提供一种较为初级的出行者系统.根本原因是所基于的信息是静态交通网.动态交通网与静态交通网不同的表现在于每一时刻每条道路的阻抗不同，每一转向延误也不同.目前在国内外动态最短路径研究主要有以下三类思想.

第一类是以传统的静态算法思想为基础，通过引入时间要素，将其应用到动态的最优路径寻优中来.如动态的 Dijksta 算法思想[1].

第二类是通过对道路交通流的建模，综合考虑各种动态因素对最优路径选取的影响来选取实时的最优路径.如建立道路交通流的变分不等式模型[2]和随机时间依赖网络模型[3]等.

第三类是借助GIS 数据库技术，结合 Dijkstra 算法来实时寻优，如文献[4，5]等.

本文结合我国国情，通过修改层次空间推理模型，构造监控数据库来反映时段数据，在计算时根据不同分区路段信息加载时段数据，然后依据所得网络结构求解动态最短路径.

1 层次空间路径选择算法

多数道路层次推理模型，如文献[6][7]中提出的推理模型都是将路网结构分层次存储，不断运用平面算法求出从低层节点(不论起止点)所在层次求出上层网络入口节点路径，直到所求得的节点与目标节点在同一层次时，再运用一次平面算法获得在该层次的路径，最后将所得到的不同层次的路径整合而得到解.这些模型在理论上具有一定可行性，但实际运用中有三个缺陷.

(1)道路是有方向性的，各方向路段费用不同，而且实际路网都存在交通控制信息.网络结构随时间变化.(2)实际上有时在某个片区内支路的平均流速比干路快得多，达到已经可以忽略支路不良因素影响的程度，这时区内支路比干路更具优势.(3)实际道路并不能横、纵分割形成标准网格，所能形成的是近似网格.网格相同、相邻或相间的判断就与网格编号有关.

本文结合福州道路网络特点改造层次空间路径选择算法，采用节点、路段信息分两层存储，计算时合并计算，具体描述如下：

(1)决定起算节点(选择层次较低的节点，即Bj为层次j的节点).

(2)提取Bj所在网格数据并入上层(层次k)网格数据.

(3)若i=k，转(4)否转(5).

(4)判断Ai和Bj所在的层次k网格是否相同、相邻或相间，是则提取相应网格并入上层网格数据，后采用平面算法计算.相同、相邻或相间的判断改为判定提取的网格个数，相邻判断依据是横向或纵向实际提取的网格个数为二，相间判断依据是横向或纵向实际提取的网格个数为三.否则，对所提取各个网格，判断网格内四个方向流速与干路平均流速的比值是否大于预定的值(不同时段比值不同，通过对10条路段不同时刻交通流实验，空闲时刻为1，交通拥堵时刻为1.15比较接近驾驶者心理)，若存在有一个以上的方向达到要求，则扩展该网格数据至上层数据，然后采用平面算法计算.

(5)若i

2 费用计算公式与数据库设计

2.1 费用计算公式

我国的许多交通系统模拟软件(如“运交之星”等)大都借用美国《通行能力手册》中的计算公式来估算道路阻抗和转向延误.实际道路监控系统能提供的各道路流量和各转向流量，因此将二者联系起来，计算各路段和各转向的费用.

(1)道路阻抗计算公式.用美国公用道路局于1964年提出的BPR模型[8]是最具代表性的研究成果，其形式如下：

t(q)=t0[1+α(qS)β]

(1)

式中t(q)为流量为q时路段上行驶时间；t0为零流量时的行驶时间；S为路段实用通行能力；可以用饱和流量公式计算；α，β为模型参数，常取α=0.9，β=4.0；t0的计算可采用道路的路段长度除以最大限速，实际流量q由监控系统给出，路段实用通行能力S，一般说明为路段设计时所确定的通行能力.

(2)转向延误计算公式.采用美国《通行能力手册》的延误公式[8]作为交叉口延误dijh(Xijh)，就有

dijh(xijh)=0.38SijhCjSijh-xijh(1-λijh)2+173(xijhSijhλijh)2

[(xijhSijhλijh-1)+(xijhSijhλijh-1)2+16xijhSijh2λijh]

(2)

上式中，h、i、j:道路网络上的节点，即交叉口；dijh：流向(i，j，h)的延误时间；Xijh：从路段(i，j)流向h上的交通流量(含路段(i，j))；

Sijh:表示进口道(i，j，h)的饱和流量；本计算中Sijh=2000(PCU/h)(对∀i、j、h)；

λijh：流向(i，j，h)上的绿信比；十字交叉路口：左转=0.9，直行=0.30，右转=1.0；三岔路口：左转=0.45，右转=1.0；

Cj：交叉口j的信号周期时间；一般可根据交叉口路灯的相位来获得，两相位40s，三相位60s，四相位80s.

2.2 GIS数据库扩展

为计算动态最优路径所需的路段权值(路段阻抗和转向阻抗)可以通过一种查表结合计算的方式来获得.因此在交管中心要维护这两个表，要提供给车载设备在某时刻各路段的通行时间以及转向延误时间的估计值.为了维护分层模型的运算，实际还要维护分区时段车流状态表.下面列举了三个表.

表1为动态路段费用表.用于记录各路段不同时段费用.

表2为动态转向费用表.用于记录某转向节点的转向费用，服务器端负责维护整个表.

表3为分区时段车流状态表.

表4为时段划分说明表.

表1 路段费用库

表2 转向费用库

表3 分区车流状态表

注：时段划分采用非均等时段划分，对福州市交通监控信息处理，将一天的交通状况划分为四种情况，具体如下表所示.时段编号是根据时段划分从0：00开始进行编号.

表4 时段划分说明表

3 带转向的路径选择求解算法设计

分层最短路径的计算，最终要转化为平面算法求解.本系统采用十字链表分别表示节点与节点的链接构成路段，再用路段与路段的链接构成转向表示.具体形式可参见文献[9].

带转向的路径求解算法可以有节点标号法和弧标号法.本系统选用弧标号算法，弧标号算法的框架由文献[10]给出.该算法需要管理一个候选弧集Q：对∀a∈Q，它的邻接弧的标号有进一步改进的可能.算法的每一步根据一定的策略从Q中取出一条弧a对其进行扫描，即检查a的每条邻接弧b是否满足式Cb<=Ca+σab+Pb，若不满足，则置

Cb=Ca+σab+Pb，

Pb=Pa，

同时将b加入Q.重复以上步骤，直到Q为空，这时得到了从r到所有弧的最短路径.其中σab表示弧a到弧b的转向费用.

算法运行过程中， 使用一个最小四叉堆Heap来存放标记的弧段对象， 堆元素的关键字是起始点到该弧段的最小时间开销.算法伪代码如下:

int SearchRoute ( a， b，e ，tr)//a表示起始点，b表示结束点，e表示弧段集合，tr表示转向集合，函数返回与终点相连的路段ID

Begin algorithm:

Heap设置为空;

k.m_V=0;

for (每个弧段标号) { //初始化

double i.m_V= maxValue; //记录弧段当前最小初始化为最大值

CString i.P = k; //弧段的父亲弧段为空 }

for (与起点a直接相连的出度弧段i) {

i.turn=0; // i.trun 是弧段i的时间权值

i.P = K; }

Heap.Insert (k.m_V，k) ; //把弧段对象以当前费用为关键字插入最小四叉堆

while (1) { //继续搜索

if (Heap为空) return; //搜索失败， 算法结束

double min;int arc；

Heap.ExtractMin (&min， arc);

//堆弹出元素当前费用最小的弧段arc及其费用min;

if ( arc 的终点是b) { //目的弧段已被永久标记

return arc;

Break; //算法结束， 搜索成功. }

for (弧段arc的所有出度弧段) {

if (min +N.Turn + j .cost

j .m_ V = min + N.Turn + j.cost;

j .P = arc;

Heap.Insert (j.m_V ，j) ; //把该弧段对象插入堆 }

}

}

End algorithm

算法执行前要先对数据进行处理，对节点数据、路段数据、路段——转向数据采用按分区形式排序，对时段数据也如此，不同的是同时按时段排序相同时段数据集中存储，这样方便连续读取数据.

4 算法验证

本文采用福州市区地图和交通监控数据信息进行验证，地图经转化后并设定分区如图1所示.

图1 福州市区道路网路

图1中粗线条为主要干道，细线条为主要支道路，以粗线划分交通区.交通区中包含编号信息(两个数字分别表示横纵向编号)，其区间编号如图1所示.

4.1 交通网络转向引起的路径的选取变化

图2列举了由于引入有向线表示路径后，基于相同的道路延误数据(白天非交通高峰期)，西禅寺-鼓楼区政府，将起点和终点互换，最短路径的结果不一致.而一般导航地图结果是一致的(求得是最短路径).图中线路1描绘的是从西禅寺到鼓楼区政府的路径，全程4.1公里，路上行程约9.5分钟，经过5个路口，转向时间花费3.5分钟；线路2描绘的是鼓楼区政府到西禅寺的路径，全程4.6公里，路上行程也大约11分钟，经过7个路口转向花费约5.2分钟.线路3表示一般地图的最短路径，路径长度3.4公里，但经过8个路口(西禅寺-鼓楼区政府)或11个路口(鼓楼区政府-西禅寺)，可见时间上肯定开销大.线路1，2两条路径所经过的路口时最少的，也就是转向费用是最低的，这也与出租车的驾驶员观点是一致的.

图2 转身对路径选取的影响

4.2 测试结果与Dijkstra算法对比

模拟试验共提取交叉点513个，路段数据2128个，设定转向点费用数据239014条，道路阻抗数据102144条.交叉点中位于主干路的有302个，其中主干路与主干路的交叉点只有49个，有198个属于干路与支路的三叉型交叉点采用两相位信号灯机制，城市中一般都采用干路优先的管理策略，三叉路口上大多禁止左转弯，故直行车辆延误可看作为0，因此，实际在干路进行路径选择时大大减少了无谓的计算次数与比较次数，优化了时间复杂度.由于没有同类算法，因此本算法仅与Dijkstra算法(取起终点间所有各区域子层与上层图合并构成网络模型)进行比较(见表5).

表5 运行时间比较

注：本算法在给道路赋予实际权值后就“鼓楼区政府-西禅寺”、“鼓楼区政府-省政府”、“鼓楼区政府-仓山区政府”等路径诱导的测试结果和出租车司机的一般行驶路线较为一致.

5 结语

随着我国 ITS水平的不断提高，最优路径的计算将会逐渐向中心型计算方式转变.交管中心掌握了关于路网的更多信息，可由交管部门对动态最优路径问题建立分层搜索数学模型，再根据该模型对实时最优路径求解.需要导航的出行者仅需向交通管理中心发送他在路网中的位置、时间和交通工具的类型等特征参数，交管中心就可以依据相应时刻路网和出行者两方面的信息，选出一条最接近真实情况的最优路径提供给出行者作路径决策.随着我国交通智能化水平的提高，新的更符合实际交通状况的动态最优路径算法也必将不断涌现.

参考文献：

[1]郑大永，郑宏剑.汽车无线通信平台系统[J].中国无线电，2007(7):33-35.

[2]Shelley lee.国外智能交通系统简介[J].数字社区&智能—家居，2007(5):76-80.

[3]Wardrop j g .some theoretical aspects of road traffic research[J]. proceeding of institution of civil engineers，1952，11(1).325-378.

[4]Chen H K ， Hsueh C F.A model and an algorithm for the dynamic user-optimal route choice problem[J]. Transportation research，1998，32B(3).219-234.

[5]王炜，徐吉谦，杨涛，等.城市交通规划理论及其应用[M].南京:东南大学出版社，1998 .

[6]李楷，钟耳顺，曾志明，等.基于分层网络拓扑结构的最优路径算法[J].中国图象图形学报，2006(7):1004-1009.

[7]李建元，师军.基于层次空间推理模型的交通网络最优路径算法[J].计算机工程，2006，32(20):207-209.

[8]美国交通研究委员会.道路通行能力手册[M].北京:人民交通出版社，2007.

[9]陈端芝.基于分层交通网络的动态路径选择模型研究 [D].福州:福州大学，2009:30-36.

[10] KIRBY R F，POTTS R B. The minimum route problem for networks with turn penalties and prohibitions[J].Transportation Research，1969，3:397-408.