物流配送中的最優(yōu)路徑規(guī)劃模擬軟件研究與開發(fā)

蔣秀蓮+張亞楠+宋祎寧+韓莉+嵇杰

摘 要：信息社會，企業(yè)間的競爭日漸激烈。隨著網(wǎng)絡(luò)購物的普及，物流配送日漸發(fā)展壯大，已成為第三方利潤源泉，受到物流等相關(guān)企業(yè)的高度重視。合理科學(xué)的物流配送路徑，可實現(xiàn)快速配送、提高配送質(zhì)量、降低配送成本，提高經(jīng)濟(jì)效益。使用軟件模擬物流配送中的路徑規(guī)劃問題，對于物流企業(yè)選擇優(yōu)化的配送路徑和信息化具有一定的意義。

關(guān)鍵詞：路徑優(yōu)化；A Star算法；Java

中圖分類號：G642 文獻(xiàn)標(biāo)識碼：A

Research and Development of Simulation Software for Optimal Path

Planning in Logistics Distribution

JIANG Xiulian，ZHANG Yanan，SONG Yining，HAN Li，JI Jie

（School of Management，Xuzhou Institute of Technology，Xuzhou 221008，China）

Abstract：In the information society，the competition among enterprises is increasingly fierce.With the popularity of online shopping， logistics distribution gradually development and growth，has become the third profit source，subject to logistics and other related enterprises attach great importance.Reasonable and scientific logistics distribution path，which can realize fast delivery，improve the quality of distribution，reduce distribution costs，improve the economic benefit.Use software to simulate the path planning problem in logistics distribution，for logistics enterprises to select optimal distribution route and the information has certain significance.

Keywords：path optimization；A star algorithm；Java

1 引言（Introduction）

配送是物流中的關(guān)鍵環(huán)節(jié)，優(yōu)化配送路徑，可以較低的運送成本、快捷的響應(yīng)速度、在最短的時間內(nèi)，把貨物送至用戶手中。為達(dá)此目的，企業(yè)需要對配送過程進(jìn)行科學(xué)合理的規(guī)劃，此規(guī)劃過程主要包括三方面的因素：時間因素，成本因素，環(huán)境因素。物流配送環(huán)節(jié)涉及的時間因素包括：對客戶的要求給予及時快速響應(yīng)、確保貨物安全準(zhǔn)時送達(dá)目的地；配送成本因素主要解決的問題是如何最大限度地減少運送車次，包括購置車輛成本及在貨品運輸中的損耗、配送工人工資等；環(huán)境因素主要包括最大限度地避免不必要的運輸行駛，這樣可減少交通擁堵以及空氣、噪音的污染等。在當(dāng)今不斷發(fā)展的電子商務(wù)背景下，消費者網(wǎng)上購物次數(shù)較多，物流企業(yè)主要依賴電動車完成貨物配送，存在較大的安全隱患。如何針對網(wǎng)絡(luò)交易不斷發(fā)展的新形式，降低配送成本，提高配送效率，減少安全隱患是擺在企業(yè)面前的重要問題。電子商務(wù)的蓬勃發(fā)展為使物流發(fā)展萌生了一系列新的特點，如信息化、自動化、柔性化、網(wǎng)絡(luò)化、社會化、標(biāo)準(zhǔn)化等。面對這些變化，根據(jù)企業(yè)的實際能力和客戶的現(xiàn)實需求建立強(qiáng)有力的配送系統(tǒng)是物流企業(yè)的現(xiàn)實選擇。物流配送中涉及到的配送路徑的選擇、到達(dá)客戶時間的選擇等一系列問題都直接關(guān)系到企業(yè)的運作成本和信譽(yù)。如物流配送沒有能夠按照客戶的要求進(jìn)行，則貨物可能被拒收甚至退貨，這樣就會對企業(yè)產(chǎn)生極為不利的影響，在信息化時代的網(wǎng)絡(luò)購物不斷發(fā)展的環(huán)境下更是如此。針對以上情況，本文著力開發(fā)一種物流配送最優(yōu)路徑規(guī)劃模擬軟件，以期能夠更好的幫助物流企業(yè)解決當(dāng)前普遍存在的配送成本高、路徑選擇難度大、顧客滿意度低等一系列問題，解決好“最后一公里”問題，使物流企業(yè)能夠?qū)﹄娮由虅?wù)下的訂單做出最快反應(yīng)，不斷提升企業(yè)的核心競爭力。

2 系統(tǒng)分析（System analysis）

在B2C電子商務(wù)物流配送中，配送運輸車輛裝載當(dāng)天要配送的貨品從倉庫出發(fā)，按照規(guī)劃好的最優(yōu)配送路線為客戶配送貨品，最后返回倉庫。IT系統(tǒng)在配送之前需要根據(jù)客戶的配送地址間線路間距、經(jīng)驗路況做分析計算出一條最優(yōu)配送路徑。在配送過程中，如果某路段堵車，則需要動態(tài)調(diào)整配送路線。物流配送路徑優(yōu)化模擬軟件按照物流配送日常流程進(jìn)行設(shè)計，要保證系統(tǒng)運行流暢，并充分滿足路徑優(yōu)化各方面需求。此外，界面應(yīng)做到布局合理、模塊清晰。

使用Java語言開發(fā)設(shè)計物流配送路徑優(yōu)化模擬軟件，Java技術(shù)具有卓越的通用性、高效性、平臺移植性和安全性[1]。模擬軟件主要具有以下功能：可以自由選擇起點，可以自由選擇終點，可以根據(jù)實際情況修改障礙物的位置與數(shù)量，動態(tài)生成最優(yōu)化路徑。用戶通過使用物流配送路徑優(yōu)化模擬軟件，能高效完成路徑的優(yōu)化選擇。通過模擬軟件，能夠避開障礙物陷阱，快速到達(dá)目的地。

物流配送路徑優(yōu)化模擬軟件為普通物流配送提供了一個信息化的模擬平臺，算法的效率直接影響路徑選擇的效率，算法應(yīng)該能夠避免現(xiàn)實路況中可能的陷阱。路徑搜索是路徑規(guī)劃的首要問題，路徑搜索和規(guī)劃大致分為兩類，全局規(guī)劃方法和局部規(guī)劃方法。在全局規(guī)劃方法中將障礙物映射到構(gòu)型空間，得到障礙區(qū)域和自由區(qū)域然后在自由區(qū)域里尋找最佳路徑，在此基礎(chǔ)上發(fā)展了許多智能算法，包括A Star算法，D Star算法，遺傳算法，模擬退火算法和蟻群算法。本模擬軟件路徑選擇優(yōu)化采用A Star啟發(fā)式搜索算法，對于路徑搜索過程中的路徑分支進(jìn)行評估，以選擇最佳分支，并且具有可采納性，若存在問題的解，則一定能夠找到[2]。endprint

3 A Star算法分析（A Star algorithm analysis）

A Star算法最初來源于DFS與BFS兩種搜索策略，將各種不同的搜索問題抽象為搜索樹的形式，為其后進(jìn)行的優(yōu)化打下基礎(chǔ)。A Star算法作為啟發(fā)式算法中重要的一種，被廣泛應(yīng)用在最優(yōu)路徑求解和一些策略設(shè)計的問題上。A Star算法的核心部分，是其中一個估值函數(shù)f（n）=g（n）+h（n）的設(shè)計。A Star算法的核心是每次選取下一個當(dāng)前搜索點時，是從全部已探知的但未搜索過的點中，選取f值最小的結(jié)點進(jìn)行展開。而所有“已探知的但未搜索過點”可以通過一個按f值升序的隊列（即優(yōu)先隊列）進(jìn)行排列。這樣，在整體的搜索過程中，只要按照類似廣度優(yōu)先的算法框架，從優(yōu)先隊列中彈出隊首元素（f值），對其可能子結(jié)點計算g、h和f值，直到優(yōu)先隊列為空（無解）或找到終止點為止[3]。A Star算法與BFS和DFS的關(guān)聯(lián)在于，當(dāng)g（n）=0時，類似于DFS，當(dāng)h（n）=0時，類似于BFS。

4 軟件程序類設(shè)計（Software program class design）

系統(tǒng)主要包含UML整體圖、Main類、Map2D類、MapOperator類、MapTemp類、PathFinder類、TileAssemble類、TileObjectAbstract類等。在Main類里，通過構(gòu)建run線程，控制程序界面的顯示，加入鍵盤監(jiān)聽，用來顯示菜單以及各類結(jié)點的顯現(xiàn)。利用Map2D類初始化程序界面，設(shè)定界面的寬和高，并且規(guī)定了模擬中各節(jié)點的大小。使用MapOperator類設(shè)定寬度值、長度值以及地點、終點和障礙物的坐標(biāo)，繪出界面背景以及路徑。MapTemp類作為地圖類，作用為初始化地圖、障礙物等。PathFinder類為算法的核心類，用于構(gòu)建OpenList與CloseList，增加尋找鄰居節(jié)點方法、尋找周圍最合適節(jié)點方法以及構(gòu)建路徑結(jié)構(gòu)方法。TileAssemble繼承TileObjectAbstract類，并構(gòu)建了Start類、Empty類、Block類、Goal類、Path類，可以在面板上畫出不同類型節(jié)點。TileObjectAbstract類作為一個抽象類，用來判斷路徑中所尋找的節(jié)點是否為障礙物，并且使用displayMyself方法繪出各種元素。

5 系統(tǒng)實現(xiàn)（System implementation）

為了使模擬軟件更加易用，直接采用提示面板的方式，用空格鍵控制菜單的顯示與消失。菜單內(nèi)容上做到了簡潔明了。

部分核心代碼如下：

public class PathFinder {

private LinkedList m_openList；

private LinkedList m_closedList；

public PathFinder（）{

this.m_openList = new LinkedList（）；

this.m_closedList = new LinkedList（）； }

public LinkedList findPath（Map2D map） throws NullPointerException， ClassNotFoundException{

this.m_openList.clear（）；

this.m_closedList.clear（）；

Point start = new

Point（map.getTile（TileAssemble.Start.class.getName（）））；

Point goal = new Point（map.getTile（TileAssemble.Goal.class.getName（）））；

……

6 系統(tǒng)測試（System test）

（1）普通路徑測試。對于普通路徑的測試，模擬軟件正常的給出了所對應(yīng)的模擬路線，未出現(xiàn)意料之外的狀況發(fā)生。由此，對于普通路徑的尋找與測試，符合預(yù)期，故本模擬軟件在實際使用中，可以對于日常大多數(shù)普通路徑進(jìn)行模擬，并且都能夠給出較為便捷、直觀的預(yù)測路徑。

（2）狹長形陷阱測試。為了充分測試現(xiàn)實中可能出現(xiàn)的路況問題，防止車輛在配送過程中陷入狹長形陷阱，此處模擬線路，可以通過預(yù)判以及計算路徑花費，正確的避開狹長形陷阱，符合預(yù)期。

（3）圓弧形陷阱測試。測試圓弧形陷阱，模擬軟件仍能夠避開陷阱，而選取較優(yōu)線路，符合預(yù)期。

參考文獻(xiàn)（References）

[1] CayS.Horstmann.Java核心技術(shù)[M].北京：電子工業(yè)出版社，

2011.

[2] 王慶等.電子商務(wù)環(huán)境下物流配送路徑優(yōu)化研究[J].天津商業(yè)

大學(xué)學(xué)報，2010，（03）：27-30.

[3] 周春輝，李詩高.Dijkstra算法與A*算法研究[J].軟件導(dǎo)刊，2007，

（1）：102-103.

作者簡介：

蔣秀蓮（1968-），女，碩士，副教授.研究領(lǐng)域：信息系統(tǒng).

張亞楠（1992-），男，本科.

宋祎寧（1996-），女，高中理科.

韓 莉（1993-），女，本科.

嵇 杰（1993-），男，本科.endprint