基于改進Teitz—Bart算法的移動網絡物流配送系統

宋金萍+侯英姿+方雄

引言

物流配送的重點在于配和送兩個方面，配即是主體客戶，送即是貨物運輸。配送中心分配不合理，配送率低，配送路徑選擇不合理等等，都會導致物流成本大幅度增加。物流配送問題可以抽象為多旅行商問題，常用一些啟發式算法來逼近或求最佳結果，常用的算法有遺傳算法，粒子群算法，蟻群算法，禁忌搜索算法和模擬退火算法等。遺傳算法計算量較大，問題越復雜，計算時間越長，穩定性也較差。粒子群算法的網絡權重編碼和遺傳算子的選擇時間比較麻煩，計算時間也較太長，而且要求所有的螞蟻選擇同一路線（即所求的最優線路），在實際計算中，在給定一定循環數的條件下很難達到這種情況。模擬退火算法的收斂速度慢，執行時間長，算法性能與初始值有關，而且參數敏感。上述算法有的計算時間過長，有的計算中極值早熟，影響優化配送路徑的速度和最優路徑的選擇。TeitZ-Ban算法將需求點分配到其最鄰近的供應點，并求總的加權距離，可有效優化配送路徑合理選擇，不會出現極值早熟現象，應用起來也較為簡便，本系統將進一步改進Teitz-Bart算法的權重計算，設計開發一套路徑規劃更優的移動網絡物流配送系統。

1改進的Teitz-Bart算法

Teitz-Bart算法主要的計算是將需求點分配到其最鄰近的供應點，并求總的加權距離。這些距離正是用最短路徑算法求得的。采用類似動態數據結構——供應點數據串和需求點數據串。數據串的長度常常可用實際應用中服務距離的最大值來限制，可以大大減少計算時間和內存。從供應點的數據串中，可以非常容易找到哪些需求點是在該點的服務范圍，而從需求點數據串中可以找出其相鄰的供應點。

Teitz-Bart算法雖然優點頗多，但是它的計算量頗大，計算時間長。但是Teitz-Bart算法中是預先求得數據隨時隨用，以此來提高算法的效率。結合它的這個特點在本系統中修改了其權值參數，用一個綜合性的權值（w）來考量。

W=K1*Time+K2vLength+K3*Demand+TurnCost；

其中Time為時間，Length為距離，Demand為所需費用，TurnCost為轉向花費，當轉向花費值為負數的時候一般為禁止轉彎。K1，K2，K3為時間、距離和所需費用所占的比例。

圖1中邊所具有的數值為邊權。在尋求最優路徑的時候，邊權主要指代的是從起始點出發到終點的過程中所需要的花費，包括時間，費用，道路情況等。邊權值和越大，說明它并不是要選取的路徑。在地點確定了的情況下，邊權值和越小，其路徑最優。本圖中的邊權就是經過此公式計算而得的。路網的通達性與方向性對于路徑的選擇具有很重要的意義，有的路段只是單向路，因此在采用Teitz-Bart算法的時候要注意有向的路網及其通達性。不通達的地方的用∞來表示，進而進行算法的實行，獲取其最短路徑。圖內點間可以用一個鄰接矩陣w來表示。這里存在方向性的問題，所以這個鄰接矩陣的考慮條件就變了。當為單向路的時，w[i，j]=w[i，j]（i≠j）且w[j，i]=∞；當i=j時，w[i，j]=0；當為雙向路的時候，w[i，j]=w[i，i]（i≠j）。得到以下鄰接矩陣：假設V2，V7是供應點，其他的為需求點，花費設為S，則可以通過上面的算法得到12條配送路線。這12種配送路線中只有第五種是最佳的路線其值為36。當需求點為一個的時候，按照算法也有且只有一個供應點對其供應，那么就是獲取其最短路徑即可。

2路網數據模型

路網數據模型由路網結點數據和弧段數據拓撲構網而成，利用屬性表信息來表達網絡的連通性，具體可以通過數據集一對一和一對多的ID關聯值來表達邏輯模型和幾何模型中弧段（Edge）數據集和結點（Node）數據集的拓撲關系。路網數據模型中由公交站點，設施點，交叉路口等點狀物抽象為點成為結點，由道路等線狀地物抽象為線段成為弧段。所有的數據及路網的方向都存儲在SuperMap SDX+的網絡數據集所在的數據源中。

3應用實例

在本實例中，通過指定5個順豐快遞點和N個配送目的地，采用Teitz-Bart算法來實現求得出一條配送花費達到最小或每個配送中心的花費達到最小。

本系統探討了基于SuperMap iClient for An-droid（以下均簡稱為iClient）組件包的移動GIS軟件平臺的開發方法和原理，并在Android+Java+Eclipse平臺上，用iClient組件包設計實驗與開發了一套移動網絡分析物流配送系統。基于iClient的networkAnalyst接口，以SuperMap公司所發布的長春市區圖數據為例，利用Teitz-Bart算法開發出一套物流配送系統。

由加粗部分代碼可知此系統的權重名稱是花費cost，權重是time，就是修改的權重參數，這個參數更具有計算價值，而且得到的路徑也是最優路徑。

系統實現如下圖所示：

4結束語

移動網絡物流配送系統是以Android平臺為基礎，應用JAVA語言，基于SuperMap iClient的networkAnalyst接口開發而成的。考慮到道路的方向性與通達性，由此建立路網數據模型，采用改進后的Teitz-Bart算法，進行多旅行商分析，從而得出最優的配送路徑。通過應用實例可以看出該路徑規劃是可行的，只要獲取了需求點和供應點，它就能快速的擇選出最優路徑，具有很好的實用價值，是一個非常方便快捷的應用程序。endprint