一種基于Dijkstra 的物流配送路徑優化算法設計
2023-01-24 12:51:44先夢瑜
電子設計工程 2023年2期
先夢瑜
（西安航空職業技術學院，陜西西安 710089）
隨著互聯網購物平臺規模的不斷擴大，人們的購物方式也從實體店購物逐漸向電商購物轉移[1]。據統計，在我國網絡銷售高峰期的郵政包裹處理量高達29 億件。保證數量如此巨大的包裹群在規定時間送至顧客手中，這對物流配送中心要求極高。要求電商必須對物流配送的各個步驟進行全方位地把握，對物流中心分配速度進行調控，對車輛以及人力進行合理調度。而在上述運輸流程中，物流配送路徑的選擇是決定快遞時效的關鍵因素[2]。
配送路徑的選擇本質是數學中的運籌學問題，該問題的最優解是從一個物流節點到另一個物流節點的最短路徑，對應的算法同時還需滿足實時性。常見的計算最短路徑算法有A*算法[3]、Dijkstra 算法[4]以及Floyd算法等。物流配送模型也可被看作是單源最短路徑的求解，Dijkstra 算法有較大優勢。Dijkstra算法受到了諸多研究學者的關注，同時眾多學者對其進行優化以獲得更優的性能。通常，優化Dijkstra算法從數據結構的方向進行。例如文獻[5-6]中，提出使用堆結構以及最短路徑樹結構對數據進行構建從而提升算法性能。該文將對傳統Dijkstra 算法進行改進，進而提升最短路徑算法性能。
1 算法設計
1.1 Dijkstra算法
Dijkstra 算法由英國人迪科斯徹在十九世紀提出。該算法通過廣度的優先搜索[7-9]進而對有向圖路徑之間的最短距離進行計算。常見的算法舉例如圖1 所示，即使用Dijkstra 算法建立從0 節點到其他幾個節點的最短路徑樹。
算法執行的流程為：
1）建立節點數據集合，命名為S和U，集合U的含義為未找到最短路徑的節點，節點數據集合表示的是所有節點，因此S為找到最短路徑的節點。那么，集合U和集合S就組成了全部的節點。
2）構建數據矩陣d[i]，該數據矩陣為節點0 到其他節點最短路徑集合。之后構建初值為零的矩陣t[i]，在未找到最短路徑時，最短路徑的尋找不會停止。
3）初始路徑尋找。首先尋找與節點0 相連接的路徑長度，將其放入到矩陣t中。由圖1 可知，d[1]=100，d[2]=30。以此類推，尋找完所有路徑后，t[0]=1，此時節點0 遍歷完畢。
4）路徑距離比較。比較路徑的長度值，即比較d[1]、d[2]，…，d[4]的長度。由圖1 可知，d[4]的長度最短，所以此時記t[4]=1，表示節點0 到節點4 的路徑值最短。之后，循環此過程直到結束。最終遍歷完成的結果如表1 所示。
表1 路徑樹遍歷結果
1.2 標號數學模型
而將該方法抽象為數學表達，可以通過圖論的相關知識獲取。假設集合G為h階的帶權圖，其可以表示為三維集合G=
假設為G的初始頂點v1和vi最小路徑的權值，假如頂點集合中的vi被所標號，即可以認定vi值在第r個步驟獲得了標號。
假設為初始頂點v1到vj的實時路徑上界，若頂點vj得到了標號，即vj在第r個步驟獲得了一個臨時標定。
假設Ur集合為第r個步驟的通過集，則Ur集合中的元素為已經獲得標號的頂點v。同理，可以設置Kr集合為第r個步驟的未通過集，則Kr集合中的元素為未獲得編號的頂點v。
該編號算法的計算機偽代碼為：
可以從其數學模型中看到，該算法符合其廣度性要求，算法的復雜度較高，算法要經過所有的節點。因此，該算法在系統簡單的情況下應用價值較高。而對于路徑網絡復雜的情況算法完成時間過高，其應用價值較低，故需要對算法進行優化。
1.3 Dijkstra多標號并行算法
由上述分析可以看出，廣度性作為算法的特性嚴重拖慢了算法處理速度，該文使用多標號并行的方法提升算法的處理速度。
下面對多標號算法進行描述，在對標號進行選擇時，若有多個不同的頂點在相同的步驟點數均擁有相同的最小編號時，則這些頂點應同時被標定[10]。這也說明，使用多個頂點并行運行的算法可以極大地減少運行時間，進而提升算法的性能。
假設r>0，加入存在圖中的頂點值vi屬于Ur-1集合，則有以下等式成立：
由此可見，頂點v集合中的頂點在第r個步驟可以被同時標記。此時假設標號只對vi進行標記，不對vj頂點進行標記。則在第r個步驟會存在vn，有以下關系：
假設在第r個步驟被修改，則有以下關系式：
因此可以看出，在某個步驟選擇vj進行標號并不會對后續遍歷的步驟產生影響。運用該多標號的方法，可以大幅縮減標號的次數，進而縮短算法運行的時間。
并行算法的思想和計算機結構極為契合，計算機可以使用多個處理器或處理器的多個線程協同計算。并行計算過程和串行計算過程的對比示意圖如圖2 所 示[11]。
圖2 串并行計算過程對比
在上文提到的多標號Dijkstra 算法中，雖然多標號可以縮短算法執行時間，但是對于一個頂點而言，多標號算法會將相鄰的兩個點同時選擇為臨時性的標號，這也會增加計算量。因此在多標號算法執行過程中加入并行算法，這可從計算角度大幅度提升算法運行速度。
使用并行算法需要注意多個線程造成的資源共用問題，多個線程同時運行可能會訪問同一個資源，由此便會造成線程堵塞進而影響執行效率。因此，需要根據執行算法的平臺對線程進行分配。
該文多標號并行算法的執行流程圖如圖3所示。
圖3 該文算法流程圖
1.4 算法對比分析
算法性能對比通常從執行準確率和執行速度進行分析。
1）執行速度[12-13]。傳統Dijkstra 算法采用串行搜索的模式對各個節點進行遍歷，傳統方法時間復雜度為O(n2)，其中n為路徑中的頂點個數。多標號的Dijkstra 算法通過修改標號改為臨時標號的方法降低時間復雜度，時間復雜度應為O(h(n+lgn))。并行多標號的Dijkstra 算法可以通過k個線程同時運行，因此總的時間復雜度將會在多標號法的基礎上減少，時間復雜度應為O(h(n/k+lgn))。
2）由執行準確度[14]的概念可知，當頂點數n較小時，傳統算法由于算法遍歷數較少，所以并行算法運行準確度大致相同，提升效果不明顯。而當頂點數n較大時，遍歷數量較多，那么和并行算法運行準確度相差則較大。
2 實驗設計
2.1 數據環境選擇與配置
該文所驗證的算法類型為并行算法，因此使用多核處理器運行算法。文中選擇的實驗硬件平臺參數如表2 所示。
表2 數據環境配置
使用并行算法需要注意多個線程造成的資源共用問題，多個線程同時運行可能會訪問同一個資源，由此就會造成線程堵塞。因此，在運行代碼前需要對CPU 線程進行分配。如圖4 所示，如果數組長度設定為64，則此時CPU 的每個線程就會負責兩個頂點的遍歷工作[15]。
圖4 線程分配舉例
2.2 實驗測試
最短路徑算法通常使用特定的公開測試圖集進行性能分析，圖集中的圖分為隨機圖和特定圖。測試圖由頂點和邊數組成，為了和其他算法性能進行對比，該文實驗使用7 幅隨機圖進行測試。隨機圖通常是固定頂點數，使用某個概率分布或函數對邊數進行控制。該文隨機生成的隨機圖屬性如表3所示。
文中測試分為運行時間測試及準確率測試兩個部分。首先，使用傳統Dijkstra 算法、多標號Dijkstra算法以及該文算法進行運行時間的對比測試，測試結果如表4 所示。
表4 運行時間測試結果
由測試結果可以看出，多標號算法相比傳統算法有明顯的改進。與傳統算法相比，多標號算法在復雜圖中的運行時間提升更為明顯。在20 000 個頂點時，多標號算法運算時間相比傳統Dijkstra 算法減少約0.929 s。而該文算法是對多標號算法進行并行化處理，該算法和多標號算法相比又得到了進一步的提升。當圖頂點的個數增加到10 000 以上時，運行時間會顯著縮短，且頂點個數越多，該文所提算法的運行速度越快。
并行算法的另一個重要指標是并行加速比，并行加速比指的是并行算法相對串行算法提升的倍數。并行加速比的定義式如式（4）所示：
根據式（4）可以計算出該文算法的并行加速比，總結如表5 所示。
表5 該文算法并行加速比計算結果
從算法并行加速比可以看出，當隨機圖的頂點個數增加時，算法并行加速比呈現出增長的態勢。但是可以看到圖1、圖2 以及圖3 算法并行度趨于1甚至小于1。這是因為在多線程工作時，如果數據量較小，多線程算法效能無法達到最大，所以在小數據集上多線程算法優勢不明顯。但當圖中頂點達到9 000 個時，算法并行加速比可以達到1.60，此時多線程并行計算的優勢便可以體現出來。
由上文實驗測試結果可以看出，該文設計的多線程并行Dijkstra 算法相比傳統的Dijkstra 算法有較大的提升。而根據當前物流處理數據維度高、數據量大的特點使用并行算法更為合適，因此具有較高的工程應用價值。
3 結束語
傳統的Dijkstra 路徑求解算法無法處理當前海量的包裹配送路徑最短問題，該文對Dijkstra 算法進行改進，在遍歷過程中使用了多標號的方法提升求解速度，同時使用并行計算的方法對求解過程實現了加速。實驗結果表明，在數據量較大的情況下，該文算法的綜合性能較為理想，運行時間大幅縮短。此外，其并行加速比較高，能夠充分體現出并行算法的優勢。
