基于集成物流網絡的路徑優化問題探究

陳 纓,陳向宜,王雪輝

（國網四川省電力公司電力科學研究院,四川成都,610072）

基于集成物流網絡的路徑優化問題探究

陳 纓,陳向宜,王雪輝

（國網四川省電力公司電力科學研究院,四川成都,610072）

由于物流集成網絡能夠規劃物流作業流程，整合物流資源，從而提高物流運作效率，發揮物流規模化優勢，因此，本文在集成物流網絡的背景下，探討路徑優化問題，在傳統的Dijkstra算法基礎上，采用了完全二叉樹對Dijkstra算法進行改進，并以煙草商業企業為例說明集成物流網絡的特點與優勢，驗證算法的有效性。研究結果表明：改進后的Dijkstra算法能夠降低時間復雜度，提高運行效率，為企業大規模的集成物流網絡分析應用提供了一種的有效的方法。

集成物流網絡；Dijkstra算法；路徑優化；煙草商業企業

0 引言

隨著全球經濟的發展以及競爭的加劇，物流作為第三利潤源泉越來越受到企業的重視。企業通過利用現代物流和信息技術，建立了完整的物流網絡，使其不斷的向集成化、自動化、信息化發展。路徑優化是物流網絡規劃的關鍵問題，本文以集成物流網絡為背景，結合Dijkstra算法，旨在探究Dijkstra算法在物流網絡的應用，實現路徑優化，降低物流成本。同時，為了提高Dijkstra算法的運行速度和效率，本文將對Dijkstra算法進行改進，并進行數值仿真分析以驗證算法的有效性。

1 問題的描述與Dijkstra算法

隨著我國物流產業的發展，物流配送中心建設逐步完善，這為集成物流網絡的發展奠基了基礎，集成物流網絡強調的是物流倉儲、配送的集成性，應用“系統集成”的思維，從物流網絡運作整體要素角度，對當前的物流網路進行合理規劃，保證貨物的及時配送，及時滿足顧客的需求，降低物流成本。其中，路徑優化是物流網絡的關鍵問題，合理的路徑安排不僅可以節約物流總成本，還可以減少物流配送過程中的不確定性，降低物流風險，保障物流服務的效率。

集成物流網絡的優化問題主要是解決起點到終點的最短路

2 改進的Dijkstra算法

由于傳統的Dijkstra算法需要遍歷每個網絡節點，降低了運行效率，鑒于此，本文采用完全二叉樹原理對Dijkstra算法進行了改進。完全二叉樹是效率較高的數據結構，經常應用于堆排序，而采用完全二叉樹對Dijkstra算法進行改進時，為了維護節點集合的數據結構，需要通過建立優先級隊列，并且隊列數組中每一個節點各自都有一個相應的關鍵字。其相應的步驟為：

（2）最短路徑的選取：對優先級隊列進行調整，調用SelectBT選擇節點，找到出發到的最小路徑。

（5）算法終止。

從遍歷節點數目而言，Dijkstra算法則是遍歷了所以的節點，運行時間是，而改進的Dijkstra算法只需要遍歷完全二叉樹的節點即可，每次調整都是將新節點加到完全二叉樹的最后一層，運行時間是，說明采用改進的Dijkstra算法要比傳統的Dijkstra算法執行效率更高，大大節約了計算時間。另一方面，還可以對完全二叉樹進行改進，通過建立索引等方式提高完全二叉樹的查找能力，快速定位網絡節點，縮短時間，進一步優化算法。

3 集成物流網絡路徑優化問題的Dijkstra算法實現

為了說明集成物流網絡路徑優化的Dijkstra算法實現問題，本文以煙草商業企業的物流網絡為例。從整體上看，我國煙草商業企業的物流網絡大多是按照行政區域劃分，由總公司將卷煙中轉到各分公司，再由各分公司負責配送到當地的零售戶手中，這種層級式的物流配送造成了物流組織結構臃腫，物流資源運行效率低下，不利于實現規模化效益。因此，煙草商業企業在煙草專賣制度下，對物流進行整合，降低物流網絡層次，形成集成物流網絡，即在一定區域內建立幾個規模較大的配送中心，打破原有的行政區域劃分，由一個配送中心負責多個行政區域的卷煙配送。具體來說，由卷煙工業公司將卷煙送往幾個大的配送中心；接著，配送中心按照客戶的需求將卷煙直接配送至零售戶，或者是配送到中轉站；最后，中轉站再負責相關零售戶的配送。

由于整合之后增加了物流配送中心的網點數目，假設其中一個配送中心需要配送的網點數較多，為54個，分布情況如圖1所示。其中，節點20是配送中心，即起點，其余節點是零售戶或是中轉站，各個節點之間的距離如表1所示，、表示節點，表示距離。現該配送中心需要向中轉站和零售戶配送卷煙，需要計算配送中心到各節點的最短路徑，以安排車輛運輸，以發揮配送的時效性，縮短物流配送時間。計算過程如下。

Study on Path Optimization Based on the Integrated Logistics Network

Chen Ying,Chen Xiangyi,Wang Xuehui
(State Grid Electric Power Company Electric Power Research Institute of Sichuan Province,Sichuan Chengdu,610072)

Because the integrated logistics network can standard operating processes and integrate logistics resources in order to improve the efficiency of logistics operation and develop scale superiority of logistics,this paper discusses the path optimization problem under the background of the integrated logistics network,and on the basis of traditional Dijkstra algorithm,it adopts complete binary tree to improve the Dijkstra algorithm.Meanwhile,this paper takes the tobacco commercial enterprise as an example to indicate the characteristics and advantages of the integrated logistics network and verify the validity of the improved Dijkstra algorithm. The results show that the improved Dijkstra algorithm can reduce the time complexity and improve operational efficiency,which provides an effective method for companies to analyze large-scale integrated logistics network.

integrated logistics network;Dijkstra algorithm;path optimization;tobacco commercial enterprise

圖1 物流集成網絡圖