物流配送中的最優路徑規劃模擬軟件研究與開發

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

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

關鍵詞：路徑優化；A Star算法；Java

中圖分類號：G642 文獻標識碼：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）

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

2 系統分析（System analysis）

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

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

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

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

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

4 軟件程序類設計（Software program class design）

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

5 系統實現（System implementation）

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

部分核心代碼如下：

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 系統測試（System test）

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

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

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

參考文獻（References）

[1] CayS.Horstmann.Java核心技術[M].北京：電子工業出版社，

2011.

[2] 王慶等.電子商務環境下物流配送路徑優化研究[J].天津商業

大學學報，2010，（03）：27-30.

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

（1）：102-103.

作者簡介：

蔣秀蓮（1968-），女，碩士，副教授.研究領域：信息系統.

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

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

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

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