考虑交叉口转向的最短路径标号算法

摘要

本发明公开了一种考虑交叉口转向的最短路径标号算法，涉及对道路最短路径网络表示方法的改进。该方法先根据路段费用及交叉口转向费用信息生成星型数据结构，通过该数据结构的层级关系，建立起结点、路段、转向三者之间的对应联系，便于最短路径算法对路网信息的检索。该算法与传统标号算法步骤基本相同，但在每一步标号时，须对当前结点的下游结点每一个转向行为分别计算当前结点标号、下游路段费用、下游结点转向费用之和，并与对应下游结点的最短路径标号做比较，以更新标号，并最终产生最短路径树，在此基础上求解已知起点和终点之间的最短路径。本发明内存占用空间小，便于网络信息更新，明确了不同转向动作间的区别。

主权项

1、一种考虑交叉口转向的最短路径标号算法，其特征在于包括如下步骤：对于有向网络G(V，E)：(1)初始化创建链表S，将路径起点r加入链表S中，初始化标号如下：${\lambda }_{i,m_j}=\infty ,p_{i,m_j}=\left(\mathrm{0,0}\right),\forall i\in V$${\lambda }_{r,m_k}=0,\forall k\in \Gamma \left(r\right)$(2)取链表S中第一个结点为以下步骤中的上游结点iA.检测该上游结点i下游的结点j，并通过步骤B检查每个结点j的标号；B.如果所有的结点j都被检查过，返回步骤(1)，否则，选择一个没有被检查过的结点j，作如下步骤：a.对每个结点j的动作m_k作如下运算：${\lambda }_{j,m_k}=\min \{{\lambda }_{j,m_k},\xi (i,j,m_k)+\tau (i,j)+{\lambda }_{i,m_j}\},\forall j\in \Gamma \left(i\right)$如果的值被改变，记录上游结点i为结点j的紧前结点i_j以及紧前结点处的转向动作m_k，即令$p_{j,m_k}=(i_j,m_k),$否则，不做任何修改，完成后，继续下一个动作m_k′；b.对于结点j的最后一个动作|Γ(j)|+1作如下运算：${\lambda }_{j,\left|\Gamma \left(j\right)\right|+1}=\min \{{\lambda }_{j,\left|\Gamma \left(j\right)\right|+1},\xi (i,j,|\Gamma \left(j\right)|+1)+\tau (i,j)+{\lambda }_{i,m_j}\},\forall j\in \Gamma \left(i\right)$通常情况ξ(i，j，|Γ(j)|+1)＝0如果λ_{j，|Γ(j)|+1}的值被改变，记录上游结点i为结点j的紧前结点i_j以及紧前结点处的转向动作m_k，即令p_{j，|Γ(j)|+1}＝(i_j，m_k)，否则，不做任何修改；c.如果结点j的任意一个标号被改进，就将结点j插入到链表S的尾部，重复步骤(2)，直到链表S为空；(3)结束算法到达终点s的最短路径费用被记录在标号λ_{s，|Γ(s)|+1}中，并通过紧前结点标号p_{s，|Γ(s)|+1}逐个结点反向追踪得到由起点r到达终点s最短路径；其中：i-结点j的上游结点，j-结点i的下游结点，k-结点j的下游结点，j∈Γ(i)，k∈Γ(j)，i、j、k均是自然数；V-所有结点集合；E-路段的集合；Γ(i)-结点i的下游结点集合；Γ(j)-结点j的下游结点集合；Γ(r)-起点r的所有下游结点集合；Γ(s)-终点s的所有下游结点集合；-结点i处第m_j个转向动作对应的最短路径长度标号；-结点i处第m_j个转向动作对应的最短路径紧前结点标号；-起点r处第m_k个转向动作对应的最短路径长度标号；m_k-结点j的转向动作，m_k＝1，2，...，|Γ(j)|，|Γ(j)|+1；|Γ(j)|表示Γ(j)中元素的个数；-结点j处第m_k个转向动作对应的最短路径长度标号；ξ(i，j，m_k)-车辆从结点i行驶到结点j作转向动作m_k产生的费用；τ(i，j)-通过路段(i，j)所需的行驶费用；-结点j处第m_k个转向动作对应的最短路径紧前结点标号；|Γ(j)|+1-终点s的最后-个转向动作，即路径在终点s处终止；λ_{j，|Γ(j)|+1}-以结点j为路径终点对应的最短路径长度标号；λ_{s，|Γ(s)|+1}-终点s对应的最短路径长度标号；ξ(i，j，|Γ(j)|+1)-车辆从结点i行驶到结点j并以结点j为路径终点产生的费用；p_{j，|Γ(j)|+1}-以结点j为路径终点对应的最短路径紧前结点标号；p_{s，|Γ(s)|+1}-终点s对应的最短路径紧前结点标号。