劉婷婷 于衛(wèi)紅

摘要：物流配送網(wǎng)絡(luò)最短路線的規(guī)劃不僅能提高商品運(yùn)輸效率，還能節(jié)約時(shí)間成本和運(yùn)輸成本。本文根據(jù)物流配送最短路線規(guī)劃的現(xiàn)狀，利用最小生成樹(shù)法對(duì)現(xiàn)有問(wèn)題進(jìn)行分析。通過(guò)資料整合、建立實(shí)例模型、使用Kruskal算法建立模型、比較權(quán)值大小并用canvas畫(huà)布顯示最終路徑圖形等過(guò)程，得出物流配送網(wǎng)絡(luò)的最佳路徑，最后用Java實(shí)現(xiàn)整個(gè)模型，得出最短路徑和最低時(shí)耗方案。

關(guān)鍵詞：最小生成樹(shù);Kruskal算法;物流配送中心;最短路徑規(guī)劃

引言

電子商務(wù)作為一類(lèi)嶄新的商業(yè)模式，與傳統(tǒng)商業(yè)模式下配送中心不同的是，電子商務(wù)時(shí)代下的配送中心往往需要提供送貨上門(mén)的服務(wù)，這也成為了一筆額外的支出，因此，規(guī)劃出合理的路線圖也是很重要的。目前關(guān)于物流配送網(wǎng)絡(luò)問(wèn)題，研究方法主要有運(yùn)籌學(xué)的應(yīng)用、仿真技術(shù)評(píng)價(jià)方法、遺傳算法等。研究也主要集中于解決時(shí)間最優(yōu)和配送中心最優(yōu)選址的問(wèn)題，研究成果主要有：2013年，趙慧娟、湯兵勇、張?jiān)圃凇痘趧?dòng)態(tài)規(guī)劃法的物流配送路徑的隨機(jī)選擇》提出在基本的動(dòng)態(tài)規(guī)劃算法基礎(chǔ)上，結(jié)合物流配送的路徑選擇問(wèn)題，引入配送途中道路的擁堵因子，隨機(jī)修正配送路徑的相應(yīng)權(quán)值，動(dòng)態(tài)調(diào)整選擇配送路徑。2015年，朱金鳳在《基于成本約束的冷鏈物流配送網(wǎng)絡(luò)規(guī)劃》中提出了“服務(wù)半徑”的概念，將物流節(jié)點(diǎn)的配送時(shí)耗轉(zhuǎn)換為物流節(jié)點(diǎn)的服務(wù)半徑，并最終通過(guò)一系列的約束條件來(lái)表示決策變量之間的關(guān)系。2015年，鈕亮、張寶友在《基于云計(jì)算求解城市物流配送最短路徑研究》中提出了基于MapReduce的并行算法和GIS仿真結(jié)合的求解方法。雖然目前解決物流配送最短路徑規(guī)劃的方法有很多，但是也存在著一些不足之處。本文基于目前的研究成果，采用Kruskal算法構(gòu)建物流配送網(wǎng)絡(luò)最短路線規(guī)劃模型，并用實(shí)例進(jìn)行了驗(yàn)證。

1、物流配送最短路線規(guī)劃相關(guān)算法簡(jiǎn)介

目前關(guān)于最短路線的主要研究方法有整數(shù)線性規(guī)劃法、Dijkstro算法、Floyd- Warsholl算法、遺傳算法、Bellman-Ford算法、蟻群算法等。

Dijkstro算法利用起點(diǎn)為中心，向外層層擴(kuò)展，最終求解出最短路徑。但是，Dijkstra算法只適用于權(quán)值非負(fù)的情況，當(dāng)權(quán)值為非負(fù)的時(shí)候，就不再適用了。Floyd-Warshall算法解決了弧長(zhǎng)必須非負(fù)的問(wèn)題，但是面對(duì)只需從一個(gè)頂點(diǎn)到其他各個(gè)頂點(diǎn)最短距離的問(wèn)題時(shí)，F(xiàn)loyd-Worshall算法的時(shí)耗非常長(zhǎng)。遺傳算法，原理來(lái)自于生物界優(yōu)勝劣汰的進(jìn)化規(guī)律，是一種隨機(jī)化搜索的方法。首先通過(guò)對(duì)問(wèn)題的參數(shù)集進(jìn)行編碼，隨機(jī)產(chǎn)生一個(gè)種群，計(jì)算適應(yīng)函數(shù)和選擇率，進(jìn)行選擇、交叉、變異操作，直到滿(mǎn)足迭代收斂條件為止。受啟發(fā)于螞蟻在尋找食物過(guò)程中的路徑的行為的蟻群算法，具有分布計(jì)算、信息正反饋和啟發(fā)式搜索的特征，本質(zhì)上是進(jìn)化算法中的一種啟發(fā)式全局優(yōu)化算法。

此外，近年來(lái)還提出了一些新的算法，比如，基于最短路徑的局部隨機(jī)游走方法、求解點(diǎn)到點(diǎn)的最短路徑的高效下界算法以及在路網(wǎng)上檢索k近鄰的基于預(yù)處理的近似算法等。

Kruskol算法相對(duì)于以上算法簡(jiǎn)便、易于實(shí)現(xiàn)，對(duì)解決結(jié)點(diǎn)比較少的情況，執(zhí)行效率高。因此，本文用Kruskal算法構(gòu)建模型研究了大連海事大學(xué)郵件收發(fā)中心快遞配送的最短路徑規(guī)劃問(wèn)題。

2、基于Kruskal算法的最短路線規(guī)劃模型

Kruskol算法的主要思想是從源結(jié)點(diǎn)開(kāi)始，按路徑長(zhǎng)度遞增的次序，依次找結(jié)點(diǎn)到源結(jié)點(diǎn)的最短通路，從而產(chǎn)生最短路徑。

使用該算法對(duì)物流配送網(wǎng)絡(luò)最短路線進(jìn)行規(guī)劃主要遵循如下步驟：

（1）初始化頂點(diǎn)：給所有頂點(diǎn)編號(hào)，并將頂點(diǎn)序號(hào)存儲(chǔ)在頂點(diǎn)數(shù)組之中。將圖的信息按照起點(diǎn)、終點(diǎn)、權(quán)重的順序存儲(chǔ)在結(jié)構(gòu)體數(shù)組edge中（如公式1所示）。

edge.start= start; edge.end= end;

edge.weight= weight

（公式1）

（2）權(quán)重排序：將所有權(quán)重按照從小到大的順序排序，并設(shè)置臨時(shí)變量存儲(chǔ)最小權(quán)重，式中edge[edge size（）] .weight表示帶權(quán)路徑圖的所有權(quán)值（如公式2所示）。

Minweight=min{edge[edge.size（）] .weight（公式2）

（3）構(gòu)建最小生成樹(shù)：按照權(quán)重從小到大的順序依次將弧和相應(yīng)的頂點(diǎn)取出，在每次取的時(shí)候判斷是否會(huì)形成回路，若形成回路，則刪除弧，依次構(gòu)建最小生成樹(shù)（如圖1所示）。

3、實(shí)例：大連海事大學(xué)郵件收發(fā)中心快遞配送最短路徑規(guī)劃

3.1 建立校園矢量圖

本實(shí)例選取了大連海事大學(xué)郵件量最多的8個(gè)教學(xué)樓與實(shí)驗(yàn)樓為例，首先通過(guò)百度地圖建立校園矢量圖，圖中各個(gè)配送點(diǎn)的位置是基于實(shí)際位置和實(shí)際大小的關(guān)系而建立的，以確保后期利用該矢量圖求最短路徑的準(zhǔn)確性，建立校園矢量圖（如圖2所示）。

3.2 數(shù)據(jù)測(cè)量

以郵件中心和各個(gè)配送點(diǎn)為節(jié)點(diǎn)，根據(jù)實(shí)際情況，一共有36條配送路線，為確保實(shí)際距離和路線的準(zhǔn)確性，經(jīng)過(guò)多次人工測(cè)量、百度地圖檢驗(yàn)，得到各節(jié)點(diǎn)之間的距離長(zhǎng)度（如圖3所示）。

3.3 數(shù)據(jù)導(dǎo)入及處理

將實(shí)際距離的數(shù)據(jù)作為各節(jié)點(diǎn)之間的權(quán)重，導(dǎo)入到Java程序中，并存放在data文件中，從文件中將數(shù)據(jù)導(dǎo)入到Java程序中。為了簡(jiǎn)化數(shù)據(jù)，將郵件中心、知行樓、機(jī)電樓、圖書(shū)館、積學(xué)樓、水上訓(xùn)練館、綜合樓、文海樓、管理樓，依次用數(shù)字1-9表示（如圖4所示）。

在Java程序中用sort函數(shù)對(duì)導(dǎo)入的實(shí)際距離數(shù)據(jù)進(jìn)行排序，得到的排序結(jié)果（如圖5所示）。

3.4 Kruskal算法對(duì)最短路徑的實(shí)現(xiàn)

實(shí)際距離排序之后，運(yùn)行程序，得到路線模型圖以及最短路徑結(jié)果圖（如圖6所示）、（如圖7所示）。

研究中使用Javo語(yǔ)言對(duì)上述算法進(jìn)行了完整的實(shí)現(xiàn)，程序執(zhí)行后，生成如圖6和圖7的路線模型，在畫(huà)布中實(shí)現(xiàn)最小生成樹(shù)，并得出最終最小生成樹(shù)的路徑總長(zhǎng)度為3978米，最短路線為2->3、3->5、4->5、8->9、7->9、5->6、1-->4、5->8，即表示從郵件中心到各個(gè)配送點(diǎn)的最終路線（如圖8所示）。

4、結(jié)論

在原有配送網(wǎng)絡(luò)的基礎(chǔ)上，對(duì)配送路線進(jìn)行合理地規(guī)劃，不僅能夠及時(shí)地滿(mǎn)足客戶(hù)的需求，而且可以節(jié)約配送中心的運(yùn)輸成本。本文結(jié)合實(shí)例，選擇Kruskal算法作為生成最短路徑的算法，并利用Javo實(shí)現(xiàn)，得到物流配送網(wǎng)絡(luò)的最短路徑。

在實(shí)際工作中，配送路線會(huì)受到很多外在因素的影響和制約，后續(xù)研究中，將綜合考慮地理環(huán)境、交通狀況等因素對(duì)配送的影響，使得最終的物流配送最短路徑更加符合實(shí)際需求。

參考文獻(xiàn)：

[1]趙慧娟，湯兵勇，張?jiān)?基于動(dòng)態(tài)規(guī)劃法的物流配送路徑的隨機(jī)選擇[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（04）：110-112.

[2]朱金鳳，萇道方，林丹萍.基于成本約束的冷鏈物流配送網(wǎng)絡(luò)規(guī)劃[J].江蘇農(nóng)業(yè)科學(xué)，2015，43（11）：572-575.

[3]鈕亮，張寶友.基于云計(jì)算求解城市物流配送最短路徑研究[J].科技通報(bào)，2015，31（05）：184-188+213.

[4]曹魯寅，羅斌，欽明浩.用遺傳算法求解最短路徑問(wèn)題[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(xué)版），1996（03）：112 -116.

[5]沈顯君著，自適應(yīng)粒子群優(yōu)化算法及其應(yīng)用：清華大學(xué)出版社，2015.06

[6]王云峰.基于最短路徑的隨機(jī)游走算法研究與應(yīng)用[D].北京交通大學(xué)，2012.