先夢瑜

（西安航空職業(yè)技術(shù)學(xué)院，陜西西安 710089）

隨著互聯(lián)網(wǎng)購物平臺規(guī)模的不斷擴大，人們的購物方式也從實體店購物逐漸向電商購物轉(zhuǎn)移[1]。據(jù)統(tǒng)計，在我國網(wǎng)絡(luò)銷售高峰期的郵政包裹處理量高達29 億件。保證數(shù)量如此巨大的包裹群在規(guī)定時間送至顧客手中，這對物流配送中心要求極高。要求電商必須對物流配送的各個步驟進行全方位地把握，對物流中心分配速度進行調(diào)控，對車輛以及人力進行合理調(diào)度。而在上述運輸流程中，物流配送路徑的選擇是決定快遞時效的關(guān)鍵因素[2]。

配送路徑的選擇本質(zhì)是數(shù)學(xué)中的運籌學(xué)問題，該問題的最優(yōu)解是從一個物流節(jié)點到另一個物流節(jié)點的最短路徑，對應(yīng)的算法同時還需滿足實時性。常見的計算最短路徑算法有A*算法[3]、Dijkstra 算法[4]以及Floyd算法等。物流配送模型也可被看作是單源最短路徑的求解，Dijkstra 算法有較大優(yōu)勢。Dijkstra算法受到了諸多研究學(xué)者的關(guān)注，同時眾多學(xué)者對其進行優(yōu)化以獲得更優(yōu)的性能。通常，優(yōu)化Dijkstra算法從數(shù)據(jù)結(jié)構(gòu)的方向進行。例如文獻[5-6]中，提出使用堆結(jié)構(gòu)以及最短路徑樹結(jié)構(gòu)對數(shù)據(jù)進行構(gòu)建從而提升算法性能。該文將對傳統(tǒng)Dijkstra 算法進行改進，進而提升最短路徑算法性能。

1 算法設(shè)計

1.1 Dijkstra算法

Dijkstra 算法由英國人迪科斯徹在十九世紀提出。該算法通過廣度的優(yōu)先搜索[7-9]進而對有向圖路徑之間的最短距離進行計算。常見的算法舉例如圖1 所示，即使用Dijkstra 算法建立從0 節(jié)點到其他幾個節(jié)點的最短路徑樹。

算法執(zhí)行的流程為：

1）建立節(jié)點數(shù)據(jù)集合，命名為S和U，集合U的含義為未找到最短路徑的節(jié)點，節(jié)點數(shù)據(jù)集合表示的是所有節(jié)點，因此S為找到最短路徑的節(jié)點。那么，集合U和集合S就組成了全部的節(jié)點。

2）構(gòu)建數(shù)據(jù)矩陣d[i]，該數(shù)據(jù)矩陣為節(jié)點0 到其他節(jié)點最短路徑集合。之后構(gòu)建初值為零的矩陣t[i]，在未找到最短路徑時，最短路徑的尋找不會停止。

3）初始路徑尋找。首先尋找與節(jié)點0 相連接的路徑長度，將其放入到矩陣t中。由圖1 可知，d[1]=100，d[2]=30。以此類推，尋找完所有路徑后，t[0]=1，此時節(jié)點0 遍歷完畢。

4）路徑距離比較。比較路徑的長度值，即比較d[1]、d[2]，…，d[4]的長度。由圖1 可知，d[4]的長度最短，所以此時記t[4]=1，表示節(jié)點0 到節(jié)點4 的路徑值最短。之后，循環(huán)此過程直到結(jié)束。最終遍歷完成的結(jié)果如表1 所示。

表1 路徑樹遍歷結(jié)果

1.2 標號數(shù)學(xué)模型

而將該方法抽象為數(shù)學(xué)表達，可以通過圖論的相關(guān)知識獲取。假設(shè)集合G為h階的帶權(quán)圖，其可以表示為三維集合G=。假設(shè)G中的Vi和Vj不是相鄰節(jié)點，則需要使G的初始頂點v1和vi之間的路徑達到最小值。

假設(shè)為G的初始頂點v1和vi最小路徑的權(quán)值，假如頂點集合中的vi被所標號，即可以認定vi值在第r個步驟獲得了標號。

假設(shè)為初始頂點v1到vj的實時路徑上界，若頂點vj得到了標號，即vj在第r個步驟獲得了一個臨時標定。

假設(shè)Ur集合為第r個步驟的通過集，則Ur集合中的元素為已經(jīng)獲得標號的頂點v。同理，可以設(shè)置Kr集合為第r個步驟的未通過集，則Kr集合中的元素為未獲得編號的頂點v。

該編號算法的計算機偽代碼為：

可以從其數(shù)學(xué)模型中看到，該算法符合其廣度性要求，算法的復(fù)雜度較高，算法要經(jīng)過所有的節(jié)點。因此，該算法在系統(tǒng)簡單的情況下應(yīng)用價值較高。而對于路徑網(wǎng)絡(luò)復(fù)雜的情況算法完成時間過高，其應(yīng)用價值較低，故需要對算法進行優(yōu)化。

1.3 Dijkstra多標號并行算法

由上述分析可以看出，廣度性作為算法的特性嚴重拖慢了算法處理速度，該文使用多標號并行的方法提升算法的處理速度。

下面對多標號算法進行描述，在對標號進行選擇時，若有多個不同的頂點在相同的步驟點數(shù)均擁有相同的最小編號時，則這些頂點應(yīng)同時被標定[10]。這也說明，使用多個頂點并行運行的算法可以極大地減少運行時間，進而提升算法的性能。

假設(shè)r>0，加入存在圖中的頂點值vi屬于Ur-1集合，則有以下等式成立：

由此可見，頂點v集合中的頂點在第r個步驟可以被同時標記。此時假設(shè)標號只對vi進行標記，不對vj頂點進行標記。則在第r個步驟會存在vn，有以下關(guān)系：

假設(shè)在第r個步驟被修改，則有以下關(guān)系式：

因此可以看出，在某個步驟選擇vj進行標號并不會對后續(xù)遍歷的步驟產(chǎn)生影響。運用該多標號的方法，可以大幅縮減標號的次數(shù)，進而縮短算法運行的時間。

并行算法的思想和計算機結(jié)構(gòu)極為契合，計算機可以使用多個處理器或處理器的多個線程協(xié)同計算。并行計算過程和串行計算過程的對比示意圖如圖2 所 示[11]。

圖2 串并行計算過程對比

在上文提到的多標號Dijkstra 算法中，雖然多標號可以縮短算法執(zhí)行時間，但是對于一個頂點而言，多標號算法會將相鄰的兩個點同時選擇為臨時性的標號，這也會增加計算量。因此在多標號算法執(zhí)行過程中加入并行算法，這可從計算角度大幅度提升算法運行速度。

使用并行算法需要注意多個線程造成的資源共用問題，多個線程同時運行可能會訪問同一個資源，由此便會造成線程堵塞進而影響執(zhí)行效率。因此，需要根據(jù)執(zhí)行算法的平臺對線程進行分配。

該文多標號并行算法的執(zhí)行流程圖如圖3所示。

圖3 該文算法流程圖

1.4 算法對比分析

算法性能對比通常從執(zhí)行準確率和執(zhí)行速度進行分析。

1）執(zhí)行速度[12-13]。傳統(tǒng)Dijkstra 算法采用串行搜索的模式對各個節(jié)點進行遍歷，傳統(tǒng)方法時間復(fù)雜度為O(n2)，其中n為路徑中的頂點個數(shù)。多標號的Dijkstra 算法通過修改標號改為臨時標號的方法降低時間復(fù)雜度，時間復(fù)雜度應(yīng)為O(h(n+lgn))。并行多標號的Dijkstra 算法可以通過k個線程同時運行，因此總的時間復(fù)雜度將會在多標號法的基礎(chǔ)上減少，時間復(fù)雜度應(yīng)為O(h(n/k+lgn))。

2）由執(zhí)行準確度[14]的概念可知，當頂點數(shù)n較小時，傳統(tǒng)算法由于算法遍歷數(shù)較少，所以并行算法運行準確度大致相同，提升效果不明顯。而當頂點數(shù)n較大時，遍歷數(shù)量較多，那么和并行算法運行準確度相差則較大。

2 實驗設(shè)計

2.1 數(shù)據(jù)環(huán)境選擇與配置

該文所驗證的算法類型為并行算法，因此使用多核處理器運行算法。文中選擇的實驗硬件平臺參數(shù)如表2 所示。

表2 數(shù)據(jù)環(huán)境配置

使用并行算法需要注意多個線程造成的資源共用問題，多個線程同時運行可能會訪問同一個資源，由此就會造成線程堵塞。因此，在運行代碼前需要對CPU 線程進行分配。如圖4 所示，如果數(shù)組長度設(shè)定為64，則此時CPU 的每個線程就會負責兩個頂點的遍歷工作[15]。

圖4 線程分配舉例

2.2 實驗測試

最短路徑算法通常使用特定的公開測試圖集進行性能分析，圖集中的圖分為隨機圖和特定圖。測試圖由頂點和邊數(shù)組成，為了和其他算法性能進行對比，該文實驗使用7 幅隨機圖進行測試。隨機圖通常是固定頂點數(shù)，使用某個概率分布或函數(shù)對邊數(shù)進行控制。該文隨機生成的隨機圖屬性如表3所示。

文中測試分為運行時間測試及準確率測試兩個部分。首先，使用傳統(tǒng)Dijkstra 算法、多標號Dijkstra算法以及該文算法進行運行時間的對比測試，測試結(jié)果如表4 所示。

表4 運行時間測試結(jié)果

由測試結(jié)果可以看出，多標號算法相比傳統(tǒng)算法有明顯的改進。與傳統(tǒng)算法相比，多標號算法在復(fù)雜圖中的運行時間提升更為明顯。在20 000 個頂點時，多標號算法運算時間相比傳統(tǒng)Dijkstra 算法減少約0.929 s。而該文算法是對多標號算法進行并行化處理，該算法和多標號算法相比又得到了進一步的提升。當圖頂點的個數(shù)增加到10 000 以上時，運行時間會顯著縮短，且頂點個數(shù)越多，該文所提算法的運行速度越快。

并行算法的另一個重要指標是并行加速比，并行加速比指的是并行算法相對串行算法提升的倍數(shù)。并行加速比的定義式如式（4）所示：

根據(jù)式（4）可以計算出該文算法的并行加速比，總結(jié)如表5 所示。

表5 該文算法并行加速比計算結(jié)果

從算法并行加速比可以看出，當隨機圖的頂點個數(shù)增加時，算法并行加速比呈現(xiàn)出增長的態(tài)勢。但是可以看到圖1、圖2 以及圖3 算法并行度趨于1甚至小于1。這是因為在多線程工作時，如果數(shù)據(jù)量較小，多線程算法效能無法達到最大，所以在小數(shù)據(jù)集上多線程算法優(yōu)勢不明顯。但當圖中頂點達到9 000 個時，算法并行加速比可以達到1.60，此時多線程并行計算的優(yōu)勢便可以體現(xiàn)出來。

由上文實驗測試結(jié)果可以看出，該文設(shè)計的多線程并行Dijkstra 算法相比傳統(tǒng)的Dijkstra 算法有較大的提升。而根據(jù)當前物流處理數(shù)據(jù)維度高、數(shù)據(jù)量大的特點使用并行算法更為合適，因此具有較高的工程應(yīng)用價值。

3 結(jié)束語

傳統(tǒng)的Dijkstra 路徑求解算法無法處理當前海量的包裹配送路徑最短問題，該文對Dijkstra 算法進行改進，在遍歷過程中使用了多標號的方法提升求解速度，同時使用并行計算的方法對求解過程實現(xiàn)了加速。實驗結(jié)果表明，在數(shù)據(jù)量較大的情況下，該文算法的綜合性能較為理想，運行時間大幅縮短。此外，其并行加速比較高，能夠充分體現(xiàn)出并行算法的優(yōu)勢。