主权项 |
一种基于考虑城市交叉口时间延误的实用路径选择方法,其特征在于该方法包括以下步骤:步骤(1).对待测实地区域采集路网数据,利用其生成路网,并用有向赋权网络G=(V,A,D,C)表示该路网;其中V={v<sub>i</sub>|i=1,2,…,n}为网络G=(V,A,D,C)中的节点集合,表示城市道路交叉口;A={a<sub>ij</sub>|i,j=1,2,…,n}为网络G=(V,A,D,C)中的弧集合,表示城市道路相邻交叉口之间的有向路段;C={c<sub>ij</sub>|i,j=1,2,…,n}为网络G=(V,A,D,C)中的弧权集合,c<sub>ij</sub>表示车辆在弧a<sub>ij</sub>上平均路段行程时间;D={d<sub>ijk</sub>|i,j,k=1,2,…,n}为网络G=(V,A,D,C)中的点权集合,d<sub>ijk</sub>表示弧a<sub>ij</sub>转向弧a<sub>jk</sub>时在节点v<sub>j</sub>处产生的平均转向延误时间;所述的路网数据包括交叉口地理坐标、相邻交叉口间平均路段行程时间以及交叉口平均转向延误时间;步骤(2).设定最优路径的起点和终点,根据当前路网数据,调用改进启发式A<sup>*</sup>算法计算得到最优路径:所述的最优路径起点为节点v<sub>o</sub>,终点为节点v<sub>d</sub>;最优路径由多条首尾相连的弧a<sub>ij</sub>构成,其中弧a<sub>ij</sub>上的节点v<sub>i</sub>和节点v<sub>j</sub>分别为该弧的尾节点和头节点;2.1考察终点节点v<sub>d</sub>的所有入弧,建立目标弧集T;目标弧集T存放以终点V<sub>d</sub>为头节点的所有入弧,初始化T_OPEN=T,<img file="FDA0000593829270000011.GIF" wi="297" he="68" />2.2初始化估价值f<sub>ij</sub>,令f<sub>ij</sub>=M,M为无穷大正数;所述的估价值f<sub>ij</sub>表示在弧a<sub>ij</sub>上产生的起点v<sub>o</sub>至终点v<sub>d</sub>的估计行程时间;2.3在起点v<sub>o</sub>前添加虚拟节点v<sub>o′</sub>,则弧a<sub>o′o</sub>是一条虚拟弧,根据公式f<sub>o′o</sub>=g<sub>o′o</sub>+h<sub>o′o</sub>,g<sub>o′o</sub>=0,故f<sub>o′o</sub>=h<sub>o′o</sub>,p<sub>o′o</sub>=NULL,将弧a<sub>o′o</sub>移入OPEN表中;其中对于弧a<sub>ij</sub>∈A而言,p<sub>ij</sub>为起点V<sub>o</sub>至弧a<sub>ij</sub>头节点v<sub>j</sub>的最短路径上弧a<sub>ij</sub>紧前弧的尾节点的标号;2.4判断OPEN表是否为非空,若是则执行以下操作2.4.1~2.4.4,若否则执行2.5:2.4.1对于OPEN表中的所有弧,选取最小f<sub>ij</sub>值对应的弧,记为a<sub>rs</sub>;将a<sub>rs</sub>从OPEN表中删除,并将a<sub>rs</sub>插入到CLOSE表中;判断弧a<sub>rs</sub>是否在T_OPEN表中,若是则执行步骤2.4.2,若否则执行步骤2.4.3;2.4.2若弧a<sub>rs</sub>在T_OPEN表中,则将其从T_OPEN表中删除,并将a<sub>rs</sub>插入到T_CLOSE表中;然后判断是否<img file="FDA0000593829270000021.GIF" wi="270" he="74" />若是则执行步骤2.5,若否则跳转执行步骤2.4;2.4.3若弧a<sub>rs</sub>不在T_OPEN表中,判断弧a<sub>rs</sub>的头节点v<sub>s</sub>的所有出弧a<sub>st</sub>是否都在CLOSE表中,若是则执行步骤2.4,若否则对不在CLOSE表中的出弧进行考察;然后判断是否成立f<sub>st</sub>>g<sub>rs</sub>+d<sub>rst</sub>+c<sub>st</sub>+h<sub>st</sub>,若是则重新赋予f<sub>st</sub>=g<sub>rs</sub>+d<sub>rst</sub>+c<sub>st</sub>+h<sub>st</sub>,p<sub>st</sub>=r后执行步骤2.4.4,若否则直接执行步骤2.4.4;2.4.4判断弧a<sub>st</sub>是否在OPEN表中,若不在则将该弧移入OPEN表后跳转执行步骤2.4;若在则直接跳转执行步骤2.4;2.5根据T_CLOSE表中各弧紧前弧的尾节点标号p<sub>ij</sub>,回溯得起点v<sub>o</sub>至该弧头节点的最短路径;比较终点v<sub>d</sub>各入弧的估计值f<sub>ij</sub>,取最小估计值对应的终点v<sub>d</sub>入弧;该入弧头节点所对应的最短路径即为起点v<sub>o</sub>至终点v<sub>d</sub>的最优路径;步骤(3).按照步骤(2)得到的最优路径行驶,每间隔Ts时间后,根据路面检测器检测到的实时路网数据对路网进行更新,并检测车辆行驶位置;根据车辆当前行驶位置,选取最近的交叉口设定为当前考察节点,记为v<sub>c</sub>;所述的最近的交叉口是指路段上沿车辆行程方向距离车辆位置最近的交叉口;步骤(4).判断当前考察节点v<sub>c</sub>是否为终点v<sub>d</sub>,若是则算法终止;若否则执行步骤(5);步骤(5).根据当前考察节点v<sub>c</sub>和终点v<sub>d</sub>确定限制搜索区域Z:所述的限制搜索区域Z是指根据路网中各交叉口的地理坐标,运用一些几何规则,对路网范围进行划分;在最优路径的搜索过程中只对落入限制区域Z内的节点和弧段进行考察,忽略限制搜索区域Z外的节点和弧段;步骤(6).根据当前最优路径所对应的路网数据,计算该时段限制搜索区域Z内各路段的行程时间变化率和各交叉口延误时间变化率,最后取所有变化率的平均值λ;步骤(7).判断变化率平均值λ是否大于阈值α,若是则跳转执行步骤(2),并重新赋予v<sub>c</sub>为起点,v<sub>d</sub>为终点,以上述步骤(5)得到的限制搜索区域Z建立新路网;若否则执行步骤(3)。 |