智慧物流中的最優配送路徑規劃問題

史屹琛 賈伯年

摘要??? 隨著國家對智慧城市的大力發展，智慧物流作為智慧城市發展中的一部分，有著很大的作用，通過發展智慧物流，可以極大的提高物流效率，降低物流成本，加速產業的發展。本文針對貨物在倉庫之間的配送路徑規劃問題，對Dijkstra算法進行分析，加以改進，挑選出最優的配送路徑。

【關鍵詞】智慧物流 最優路徑規劃 Dijkstra算法

1 前言

智慧物流首次由IBM提出，并在2009年12月由中國物流技術協會信息中心、華夏物聯網、《物流技術與應用》編輯部聯合提出概念。隨著信息技術快速發展，中國的智慧物流也受到了極大的影響。“智慧物流”是指通過智能硬件、物聯網、大數據等智慧化技術與手段，提高物流系統分析決策和智能執行的能力，提升整個物流系統的智能化、自動化水平。

通過智慧物流，在一下幾方面會帶來極大的進步：

（1）降低物流成本，提高企業利潤;

（2）加速物流產業的發展，成為物流業的信息技術支撐;

（3）節約消費者的購物成本，讓消費者放心;

（4）可以提高社會各部門工作效率，尤其是提高政府部門工作效率。

分析物流的最優路徑是發展智慧物流中極為重要的一部分，可以極大的節省配送成本，提高配送效率。

2 常用路徑搜索算法

尋路問題屬于組合優化的范疇，從路徑搜素策略上可分為三類，第一類是局部最優化算法，但并無法獲得全局最優解，例如貪心算法，第二類是全局最優化算法，以獲取全局最優解為目的，主要的算法有Dijkstra算法，floyed算法等，最后一類是計算智能算法。

本文將對Dijkstra算法在物流配送中的應用進行探究。

3 Dijkstra算法

Dijkstra算法使用了BFS（廣度優先搜索）解決單源最短路問題。算法的基本思路就是先將所有節點分成兩組第一組用S表示為已求出的最短路徑的頂點集合，第二組用U表示剩余頂點，U中的每個頂點對應著一條由源點到達該點的最短路徑，起始時S中只含有一個源點，每求得一條最短路，就在U中更新相應的點對應的最短路徑，按照最短路徑遞增的次序把U中的點加入到S中，直到確定了到目標結點的最短路，也就是所有節點都在S中，算法結束。

基本步驟如下：

（1）把起始點加入到S中，即S={v0}，起點到自己的距離為0。更新源點v到U（處源點外其他點）上的最短距離，若存在邊相連則更新為最短距離，若無邊相連則更新為∞

（2）從U中選擇一個權值較小的點u，加入到S中。

（3）以（2）中取出的u為中間節點，更新源點到U中剩余頂點的最短路徑。其調整過程如下：dist[i]表示從起始節點到頂點i的最短距離，掃描u的所有出邊，若dist[j]>dist[u]+weight，則使用dist[u]+weight更新dist[j]。

（4）重復步驟（2），（3）。

4 Dijkstra算法在物流配送中的運用

假設提前已經知道每段配送路的長度和花費時間，在物流配送問題中，要用盡可能短的時間，走盡可能短的距離，到達目的地。

首先我們建立圖論模型如圖1所示。

其中節點表示起點，終點及中間的補給站，這里假設0號節點為起點，6號節點為重點，其余節點為補給站，每條路徑有t和d兩個權值，權值t表示預期要花費的時間，權值d表示道路的長度，本文將所有的道路都假定為雙向道路，所以此圖為無向圖。

傳統的Dijkstra算法只考慮路徑長度，本文在考慮路程短的同時還考慮到運送花費時間，對經典的Dijkstra算法加以改進，第（2）步中從U中選擇一個權值較小的點u，加入到S中，如果有多個點滿足這個條件，選擇花費時間最少的那條路徑所連的點，這樣則可是的路徑規劃最優。

在這個模型中，我們要從起始節點0到達終點6，為了減少成本，我們要選擇最短的路徑。如果是根據經典的Dijkstra算法，我們先把0這個節點加入到集合S中，再去更新源點0到達U中剩余節點的最短路徑。因為d[2]

5 結語

本文基于Dijkstra算法的理論知識，針對智慧物流配送這個特定情境下的具體運用進行討論，對如何選擇最優路徑進行了分析探究，利用改進的Dijkstra算法搜索出一條路徑最短，成本最低的路徑。

參考文獻

[1]張本俊，周海嬌，劉淑琴.改進Dijkstra算法在公共交通出行的研究[J].物聯網技術，2018，8（11）：45-48.

[2]李元臣，劉維群.基于Dijkstra算法的網絡最短路徑分析[J].微計算機應用，2004（03）：295-298+362.