智慧物流中的最優(yōu)配送路徑規(guī)劃問題

史屹琛 賈伯年

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

【關(guān)鍵詞】智慧物流 最優(yōu)路徑規(guī)劃 Dijkstra算法

1 前言

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

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

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

（2）加速物流產(chǎn)業(yè)的發(fā)展，成為物流業(yè)的信息技術(shù)支撐;

（3）節(jié)約消費(fèi)者的購物成本，讓消費(fèi)者放心;

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

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

2 常用路徑搜索算法

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

本文將對Dijkstra算法在物流配送中的應(yīng)用進(jìn)行探究。

3 Dijkstra算法

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

基本步驟如下：

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

（2）從U中選擇一個權(quán)值較小的點(diǎn)u，加入到S中。

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

（4）重復(fù)步驟（2），（3）。

4 Dijkstra算法在物流配送中的運(yùn)用

假設(shè)提前已經(jīng)知道每段配送路的長度和花費(fèi)時間，在物流配送問題中，要用盡可能短的時間，走盡可能短的距離，到達(dá)目的地。

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

其中節(jié)點(diǎn)表示起點(diǎn)，終點(diǎn)及中間的補(bǔ)給站，這里假設(shè)0號節(jié)點(diǎn)為起點(diǎn)，6號節(jié)點(diǎn)為重點(diǎn)，其余節(jié)點(diǎn)為補(bǔ)給站，每條路徑有t和d兩個權(quán)值，權(quán)值t表示預(yù)期要花費(fèi)的時間，權(quán)值d表示道路的長度，本文將所有的道路都假定為雙向道路，所以此圖為無向圖。

傳統(tǒng)的Dijkstra算法只考慮路徑長度，本文在考慮路程短的同時還考慮到運(yùn)送花費(fèi)時間，對經(jīng)典的Dijkstra算法加以改進(jìn)，第（2）步中從U中選擇一個權(quán)值較小的點(diǎn)u，加入到S中，如果有多個點(diǎn)滿足這個條件，選擇花費(fèi)時間最少的那條路徑所連的點(diǎn)，這樣則可是的路徑規(guī)劃最優(yōu)。

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

5 結(jié)語

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

參考文獻(xiàn)

[1]張本俊，周海嬌，劉淑琴.改進(jìn)Dijkstra算法在公共交通出行的研究[J].物聯(lián)網(wǎng)技術(shù)，2018，8（11）：45-48.

[2]李元臣，劉維群.基于Dijkstra算法的網(wǎng)絡(luò)最短路徑分析[J].微計(jì)算機(jī)應(yīng)用，2004（03）：295-298+362.