[發明專利]考慮交叉口轉向的最短路徑拍賣算法

無效

• 申請號: 200910033091.8
• 申請日: 2009-06-11
• 公開（公告）號: CN101571404A
• 公開（公告）日: 2009-11-04
• 發明（設計）人: 程琳;杜牧青
• 申請（專利權）人: 東南大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06F17/30;G08G1/00
• 代理公司: 南京經緯專利商標代理有限公司
• 代理人: 許 方

1、一種考慮交叉口轉向的最短路徑拍賣算法，其特征在于包括如下步驟：

對于有向網絡G(V，E，A，D)：

(1)給定路徑起點r和終點s，在價格矢量p中為路徑起點r增設虛擬上游結點0；

(2)初始化路徑P和價格矢量p：

P＝(r)，p_l，k＝0，∀l∈V,]]>k∈Γ^-1(l)

p_r，0＝0

(3)取路徑P的末結點表示為結點i，選擇結點i的下游結點j，當(i,j)∉P]]>時，如果滿足條件pi,h<min(i,j)∈E{aij+pj,i+dh,i,j},]]>進入步驟A，否則進入步驟B：

A.收縮路徑：令pi,h=min(i,j)∈E{aij+pj,i+dh,i,j},]]>收縮路徑P，轉到下一個迭代過程，其中：收縮路徑P是指當路徑P不僅包含路徑起點r時，移除此時路徑P中的末結點，當路徑P僅包含路徑起點r時，路徑P保持不變；

B.延伸路徑：通過第二結點j_i來延伸路徑P，ji=arg{min(i,j)∈E{aij+pj,i+dh,i,j}},]]>如果第二結點j_i是終點s，則迭代終止，P就是要求的最短路徑，否則轉入下一個迭代過程；

(4)重復步驟(3)，直到算法推出，此時，路徑P即為路徑起點r和終點s之間的最短路徑，最短路徑長度等于p_i，h-p_r，0；

其中：V-所有結點集合；E-路段的集合；A-路段費用集合；D-交叉口轉向費用集合；i-路徑P的末結點，j-結點i的下游結點，k、l-網絡中任意結點，h-結點i的上游結點，h∈Γ^-1(i)，i、j、h均為自然數；Γ^-1(l)-結點l的上游結點集合；Γ^-1(i)-結點i的上游結點結合；a_ij-路段(i，j)的行駛費用，a_ij∈A；(i，j)-從結點i指向其下游結點j的有向路段，(i，j)∈E；(h，i，j)-由結點i與其上游結點h和下游結點j三者唯一確定的在結點i處的轉向動作；d_h，i，j-轉向動作(h，i，j)對應的轉向費用，d_h，i，j∈D；j_i-{a_ij+p_j，i+d_h，i，j}中最小和值對應的下游結點j；p_l，k-結點l處以k為上游結點價值量；p_r，0-起點r處以0為虛擬上游結點價值量；p_i，h-結點i處以h為上游結點價值量；p_j，i-結點j處以i為上游結點價值量。