最短路徑Auction算法及其在路徑誘導(dǎo)中的應(yīng)用＊

（東南大學(xué)交通學(xué)院 南京 210096）

0 引 言

在路徑誘導(dǎo)模塊中，最短路徑算法成為決定導(dǎo)航性能的關(guān)鍵因素［1］．常用的最短路徑算法可分為兩類：標(biāo)號設(shè)定算法（如Dijkstra算法）和標(biāo)號修正算法（如Bellman－Ford算法）．以上2類算法在應(yīng)用于最短路徑問題時，都是通過先推出指定起始結(jié)點到達其余各點的最短路徑，再通過終點反向追蹤的方法求解起終點之間最短路徑的．這樣的求解思路顯然產(chǎn)生了多余的求解信息．當(dāng)駕駛員在道路網(wǎng)絡(luò)中行車時，通常關(guān)注的僅是從所處位置到達預(yù)定目的地2點之間的最短行車路線．尋求更加符合路徑誘導(dǎo)需求的路徑算法、提高算法的針對性，成為導(dǎo)航系統(tǒng)關(guān)注的焦點．

Auction算法（拍賣算法）于1991年由Bertsekas應(yīng)用于網(wǎng)絡(luò)最短路徑問題［2］．值得關(guān)注的是，Auction算法是一種能夠直接求解“點對點”之間最短路的路徑算法．因此，本文將就該算法在路徑誘導(dǎo)中的應(yīng)用作進一步的討論．

本文將路徑誘導(dǎo)中的“點對點”最短路徑問題，根據(jù)比較試驗討論算法的復(fù)雜性以及影響算法速度的主要因素，評價其在路徑誘導(dǎo)中的適用性．

1 Auction算法的基本原理

1.1 算法原理

Auction算法是模仿現(xiàn)實中的拍賣過程．考慮如下拍賣過程：有n個人和n個物體，遵循“一對一”的原則，實現(xiàn)派對．假設(shè)物體j的價格為pj，要得到這一物體的人必須支付相應(yīng)的價錢．人i與物體j派對可以獲得的效益為aij，純利潤為aij－pj．每個人想獲得使他獲利最大的那一個物體ji，即aiji－pji＝max｛aij－pj｝．因此必須通過競爭和抬高價格，選擇獲益最多的那個物體．經(jīng)過十幾年的發(fā)展，這種算法已經(jīng)推廣用于解決一般的最小費用路徑問題，擇優(yōu)條件也相應(yīng)地發(fā)生了改變，成為較為解決線性網(wǎng)絡(luò)流的綜合性算法，也是近年來較新也較為受到關(guān)注的最短路徑算法．

對于一幅賦權(quán)有向圖，Auction算法是一種能夠求解單一起點和單一終點的最短路問題的簡單方法．這一特點恰恰滿足了路徑誘導(dǎo)技術(shù)中的最短路求解需求．Auction算法在求解過程中，始終維持一條從起點出發(fā)的簡單路徑P．算法的每一步對路徑P中最后一個結(jié)點采取的“延伸”或“收縮”操作．當(dāng)路徑P的最后一個結(jié)點到達指定終點時，算法結(jié)束，且兩點之間的最短路徑得出．

為了直觀的反映Auction算法的迭代過程，Bertsekas將算法過程比喻為“在迷宮中移動的小鼠”．小鼠在迷宮中移動，或者向未知區(qū)域前進，或者沿曾經(jīng)走過的路線返回．每當(dāng)小鼠從一個岔路口（結(jié)點）沿原路返回時，將記錄一個估計值，作為重新回到該結(jié)點時的期望值；每當(dāng)小鼠在向前探索時，根據(jù)對結(jié)點估計值的比較，選擇一個期望最優(yōu)的結(jié)點作為前進目標(biāo)．在如此的前進與返回的過程中，直至找尋到迷宮中的目的地（終點）．由此反映出，Auction算法是一種從起點向終點迭代的探索性算法．

1.2 算法的基本步驟［3］

在給定一個有向網(wǎng)絡(luò)G（V，E）中，V，E分別為G的點集合和弧集合，弧段（i，j）的費用為aij．首先，對算法作如下基本假設(shè)：（1）假設(shè)網(wǎng)絡(luò)中的弧段費用均為正值；（2）假設(shè)除終點外的每一個結(jié)點至少有一條前向弧，對于不滿足條件的結(jié)點，可增加一條指向終點的弧，并賦給它一個很大的弧費用；（3）假設(shè)兩個結(jié)點間在一個方向上最多有一條弧連接（這一點僅僅是為了方便表述，拍賣算法能很好地解決一對結(jié)點間有多條弧連接的情況）．

下面描述最短路徑求解過程：用1表示起點，t表示終點，（i1，i2，…，ik）表示一條路徑．其中：（im，im＋1）表示?。╩＝1，…，k－1）．如果i1，i2，…，ik是各不相同的，則稱（i1，i2，…，ik）為初等路，結(jié)點ik為路徑的終點，所有弧的費用之和就是路徑的長度．

定義P為迭代路徑，在迭代過程中，P＝（i1，i2，…，ik）始終保持為初等路，并不斷延伸和收縮．如果ik＋1不是路徑P 中的結(jié)點，并且（ik，ik＋1）是一條邊，則用結(jié)點ik＋1來延伸P，是指用路徑（i1，i2，…，ik，ik＋1）來代替路徑 P；如果路徑 P不只包含起點i1，收縮P 是指用路徑（i1，i2，…，ik－1）代替路徑P．

定義p＝（p1，p2，…，pn）為網(wǎng)絡(luò)中結(jié)點的價格矢量，其中元素與網(wǎng)絡(luò)結(jié)點一一對應(yīng)，例如pi表示第i個結(jié)點的價值量．在迭代過程中，價格矢量p需滿足如下條件：

pi≤aij＋pj?（i，j）∈E；pi＝aij＋pj

對于路徑P上所有連續(xù)的結(jié)點對，這一條件稱作松弛互補性條件（complementary slackness，簡稱CS條件），這與指派問題Auction算法的CS條件等價，并且，都可以由最小費用流問題的CS條件推導(dǎo)出來．可以證明，如果（P，p）滿足CS條件，i是路徑P中的結(jié)點，則從起點1沿P到結(jié)點i的路徑也是從1到i的最短路，并且p1－pi就是相應(yīng)的最短路長度．

根據(jù)Auction算法求解最短路徑的過程，其“拍賣原則”體現(xiàn)于路徑迭代的每一步中．在最短路徑問題中，以aiji＋pji＝min｛aij＋pj｝取代原始拍賣問題中條件aiji－pji＝max｛aij－pj｝．在路徑P延伸的過程中，將符合條件aiji＋pji＝min｛aij＋pj｝的結(jié)點ji分配給上游結(jié)點i，即以結(jié)點ji延伸路徑P，有在路徑P收縮時，以min｛aij＋pj｝更新價值量pi，記錄該結(jié)點的估計值，便于路徑P再次延伸時的回溯．這便是最短路徑Auction算法中的拍賣原理．

為了使用計算機語言實現(xiàn)Auction最短路徑算法，現(xiàn)給出算法的程序化描述（見圖1）．對于符合基本假設(shè)的道路網(wǎng)絡(luò)，求解從起點1到任意點i的Auction算法的基本步驟如下．

1）初始化（P，p） P＝ （1），pj＝0，j∈V．

圖1 Auction算法流程圖

2）用i表示路徑P的最后一個結(jié)點．如果pi＜min ｛aij＋pj｝，進入下列步驟（1），否則進入（i，j）∈v步驟（2）：（1）收縮路徑．令如果i≠1，收縮P，轉(zhuǎn)到下一個迭代過程；（2）延伸路徑．通過結(jié)點ji來延伸P，ji＝arg｛min｛aij（i，j）∈V＋pj｝｝．如果j是終點t，則迭代終止，P就是要求的最短路徑．否則轉(zhuǎn)入下一個迭代過程．

3）重復(fù)步驟2），直到算法推出．

1.3 算例

為了清楚的說明問題，本文采用了一幅簡單的有向網(wǎng)絡(luò)圖，如圖2所示，通過求解結(jié)點1至結(jié)點4的最短路徑，演示Auction算法在求解網(wǎng)絡(luò)最短路徑時的迭代過程，見表1．

圖3反映了在使用Auction算法求解上述最短路徑問題時，路徑P末節(jié)點的移動軌跡，反映了路徑延伸和收縮的過程．

圖2 簡單的賦權(quán)有向網(wǎng)絡(luò)圖

圖3 路徑P末結(jié)點的移動軌跡

表1 Auction算法求解結(jié)點1到4最短路的迭代過程

2 “點對點”的最短路徑問題

2.1 Auction算法的運算性能分析

最短路徑算法的運算性能主要體現(xiàn)為算法的準(zhǔn)確性和復(fù)雜性．為了進一步反映Auction算法在計算道路網(wǎng)絡(luò)中“點對點”最短路徑時的運算性能，本文采用了隨機生成的賦權(quán)有向網(wǎng)絡(luò)，對Auction算法的運算速度和運算準(zhǔn)確性進行了測試（CPU Intel 1．76GHz），并選用了經(jīng)典的Dijkstra算法作為參照．測試程序采用C＃語言編寫，考慮到路徑誘導(dǎo)系統(tǒng)的硬件環(huán)境，程序使用了單線程的前向的拍賣算法（forward algorithm）．比較測試在不同規(guī)模（結(jié)點數(shù)量規(guī)模、路段數(shù)量規(guī)模）的網(wǎng)絡(luò)中進行，以測試算法的準(zhǔn)確性和運算時間為主，對兩種不同的算法選用相同的起終點進行測試試驗．根據(jù)Auction算法的迭代特點，進行有針對性的測試，得出定量的數(shù)據(jù)分析，反映出算法的主要特點和結(jié)果隨參數(shù)變化的趨勢．

Auction算法的復(fù)雜度可以表示為O（EhL）．h表示起點1到終點t之間最短路徑的最小路段數(shù)；L表示網(wǎng)絡(luò)中路段費用的最大值．E＝I×G．其中，I表示從起點1出發(fā)，路徑長度小于起終點間最短路徑長度的結(jié)點i的數(shù)量；G表示上述結(jié)點i的最大結(jié)點出度．由此可見，影響Auction算法運算速度的主要因素為h，L，I，G幾個參數(shù)．根據(jù)算法的復(fù)雜度分析，本文選擇起、終點間隔（最短路路徑所經(jīng)過結(jié)點的數(shù)目）、網(wǎng)絡(luò)平均結(jié)點出度（路段密度）、網(wǎng)絡(luò)結(jié)點數(shù)作為主要試驗參數(shù)，對于Auction算法的運算性能做出測試．具體試驗過程如下．

1）根據(jù)隨機網(wǎng)絡(luò)生成方法，產(chǎn)生結(jié)點數(shù)量分別為500，1 000，2 000，5 000，10 000的5種規(guī)模的道路網(wǎng)絡(luò)．

2）對于每種結(jié)點數(shù)量的網(wǎng)絡(luò)，產(chǎn)生結(jié)點平均出度分別為2，3，4的3種路段密度不同的網(wǎng)絡(luò)．其中，結(jié)點的平均出度為2，表示一種稀疏的網(wǎng)絡(luò)結(jié)構(gòu)；平均出度為4，表示密集的網(wǎng)絡(luò)結(jié)構(gòu)．按照這樣的方法，共產(chǎn)生15幅隨機網(wǎng)絡(luò)．

3）在這15幅網(wǎng)絡(luò)中，分別測試Auction算法和Dijkstra算法．每幅隨機網(wǎng)絡(luò)，隨機產(chǎn)生100對起終點，對這100對起終點分別使用Auction算法和Dijkstra算法，記錄算法的結(jié)果及性能（最短路徑時間、最短路徑、起終點間隔、算法運行時間）．通過算法運行時間，反映算法的復(fù)雜程度．

4）對于測試結(jié)果，以結(jié)點數(shù)量分為5大類，以路段數(shù)量分為3個次類，進行比較分析．

總體來說，由具有代表性的試驗結(jié)果發(fā)現(xiàn)，2種最短路徑的運算結(jié)果相同，對于所有的起始點對，都能夠通過迭代得到相同的最短路徑．因此，可以說明，兩種基本算法的準(zhǔn)確性相同．但是，在不同規(guī)模的網(wǎng)絡(luò)中，Dijkstra算法均表現(xiàn)出了速度上的優(yōu)越性．如圖4所示，兩種計算方法的運算速度都是隨著網(wǎng)絡(luò)規(guī)模的增加而降低的，Auction算法的速度受網(wǎng)絡(luò)中結(jié)點總數(shù)的影響較大，Dijkstra算法則受網(wǎng)絡(luò)中路段總數(shù)的影響較大．

此外，Auction算法受起終點間隔影響明顯，其運算時間基本隨起終點間最短路徑結(jié)點數(shù)量增加呈遞增趨勢．運算時間呈現(xiàn)波動，在個別點處有下降，如圖5所示，根據(jù)試驗數(shù)據(jù)分析，造成下降的原因是該最短路徑總時間相對較小，在路徑P延伸時易于被優(yōu)先選擇．這樣的測試結(jié)果，是符合Auction算法復(fù)雜性分析的．Auction算法僅在起終點間隔較短時，速度上優(yōu)于Dijkstra算法．這種現(xiàn)象在如圖5所示的大型網(wǎng)絡(luò)中更為明顯．隨著路徑結(jié)點數(shù)量的增加，Auction算法迭代的次數(shù)將明顯增加，運算速度也明顯低于Dijkstra算法．

圖4 包含500個結(jié)點、1 000個結(jié)點和2 000個結(jié)點的網(wǎng)絡(luò)中，2種算法運算速度比較

圖5 包含10 000個結(jié)點的網(wǎng)絡(luò)中，2種算法運算速度的比較

2.2 在路徑誘導(dǎo)中的適用性

根據(jù)路徑誘導(dǎo)設(shè)備的技術(shù)參數(shù)要求［4］，對于現(xiàn)行導(dǎo)航設(shè)備中，其存儲空間已經(jīng)達到了比較高的容量，但處理器主頻速度和內(nèi)存空間大小，還不能與一般的個人計算機相提并論．參考測試程序?qū)\算速度要求高，對內(nèi)存空間需求適中的特點，算法的速度應(yīng)當(dāng)作為首要考慮因素，其次考慮數(shù)據(jù)的存儲空間問題．因此，將最短路徑算法的運行時間控制在1s以內(nèi)是比較合適的，也是用戶可接受的速度．從上一節(jié)對于Auction算法性能的測試和算法復(fù)雜度的討論中發(fā)現(xiàn)，算法能夠準(zhǔn)確的求解網(wǎng)絡(luò)中任意兩點之間的最短路徑，但是在運算速度方面卻與Dijkstra算法有著明顯的差異．Dijkstra算法在所有的測試網(wǎng)絡(luò)中，都能夠?qū)⒂嬎憧刂圃跇O短的時間以內(nèi)（＜0．5s），因此它具有普遍的適用性．Auction算法的速度主要受到起終點間隔的影響，僅在最短路徑結(jié)點數(shù)量較少時，能夠體現(xiàn)出其運算速度的優(yōu)勢．隨著迭代距離的增加，Auction算法的復(fù)雜性迅速提高，運算速度明顯下降，低于Dijkstra算法．Auction算法在實際“點對點”最短路問題的應(yīng)用中，沒有明顯地體現(xiàn)出其算法原理優(yōu)勢，反而在整體性能上低于傳統(tǒng)標(biāo)號路徑算法．因此，單線程的Auction算法在路徑誘導(dǎo)中的適用范圍較為有限，算法的計算步驟有待優(yōu)化和改進．

3 結(jié)束語

盡管Auction算法已經(jīng)在交通分配中，求解單一起點到多個終點的問題，以及多處理器的并行計算中，得到了很好的應(yīng)用［5］，但是作為以“點對點”最短路徑為求解目標(biāo)的算法，單線程的Auction算法并沒有在導(dǎo)航系統(tǒng)的“一對一”問題中體現(xiàn)出其原理上的優(yōu)勢［6－8］．即 Auction算法具有準(zhǔn)確求解網(wǎng)絡(luò)中最短路徑的能力，可是仍然存在速度方面的局限性，僅適用于大型稀疏網(wǎng)絡(luò)結(jié)構(gòu)，或求解起終點間隔較少的最短路問題．因此，Auction算法的整體平均速度較傳統(tǒng)的Dijkstra算法偏低．

綜述之，僅僅是依照當(dāng)前的算法步驟和單線程的算法程序，無法達到預(yù)期的算法效率．通過對于Auction算法的反復(fù)試驗，可以發(fā)現(xiàn)，在算法的求解過程中，最費時的是每步迭代中對當(dāng)前下游結(jié)點最小費用的計算．利用算法迭代過程中的性質(zhì)，減少迭代過程的重復(fù)步驟，將有希望降低算法復(fù)雜性，提高算法的實際效率．此外根據(jù)文獻［3］，雙（多）線程的Auction算法采用雙（多）處理器，在共用價格矢量的基礎(chǔ)上，可同時從起點和終點開始延伸路徑．考慮使用雙處理器的路徑誘導(dǎo)設(shè)備，能夠發(fā)揮Auction算法在多處理器上并行計算的優(yōu)勢，將顯著地提高算法的求解速度．

［1］張 可．車輛導(dǎo)航系統(tǒng)關(guān)鍵技術(shù)研究［D］．北京：北京工業(yè)大學(xué)，2001．

［2］王京元，程 琳．最短路拍賣算法在交通分配中的應(yīng)用［J］．交通運輸系統(tǒng)工程與信息，2006，6（6）：79－82．

［3］BERTSEKAS D P．An auction algorithm for shortest paths［J］．SIAM J．for Optimization，1991（1）：425－447．

［4］王 芬．Dijkstra最短路徑優(yōu)化算法在汽車導(dǎo)航的研究及實現(xiàn)［D］．上海：上海師范大學(xué)，2006．

［5］BERTSEKAS D P，CASTANON D A．The auction algorithm for the transportation problem［J］．Annals of Operations Research，1989，20（1）：67－96．

［6］LEONE R D，PRETOLANI D．Auction algorithms for shortest hyperpath problems［R］．Technical Report OR－CAM－1998－01，Universit′a di Camerino，1998．

［7］BERTSEKAS D P，PALLOTTINO S，SCUTELLA M G．Polynomial auction algorithm for shortest paths［R］．Technical Report TR－16／92，Dipartimento di Informatica，University of Pisa，1992．

［8］PALLOTINO S，SCUTELLA M G．Shortest path algorithms in transportation models：classical and innovative aspects［EB／OL］．http：／／ftp．di．unipi．it／pub／techreports／TR－97－06．ps．Z，1997－06－25．