基于改進Teitz—Bart算法的移動網(wǎng)絡(luò)物流配送系統(tǒng)

宋金萍+侯英姿+方雄

引言

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

1改進的Teitz-Bart算法

Teitz-Bart算法主要的計算是將需求點分配到其最鄰近的供應(yīng)點，并求總的加權(quán)距離。這些距離正是用最短路徑算法求得的。采用類似動態(tài)數(shù)據(jù)結(jié)構(gòu)——供應(yīng)點數(shù)據(jù)串和需求點數(shù)據(jù)串。數(shù)據(jù)串的長度常?？捎脤嶋H應(yīng)用中服務(wù)距離的最大值來限制，可以大大減少計算時間和內(nèi)存。從供應(yīng)點的數(shù)據(jù)串中，可以非常容易找到哪些需求點是在該點的服務(wù)范圍，而從需求點數(shù)據(jù)串中可以找出其相鄰的供應(yīng)點。

Teitz-Bart算法雖然優(yōu)點頗多，但是它的計算量頗大，計算時間長。但是Teitz-Bart算法中是預(yù)先求得數(shù)據(jù)隨時隨用，以此來提高算法的效率。結(jié)合它的這個特點在本系統(tǒng)中修改了其權(quán)值參數(shù)，用一個綜合性的權(quán)值（w）來考量。

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

其中Time為時間，Length為距離，Demand為所需費用，TurnCost為轉(zhuǎn)向花費，當(dāng)轉(zhuǎn)向花費值為負數(shù)的時候一般為禁止轉(zhuǎn)彎。K1，K2，K3為時間、距離和所需費用所占的比例。

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

2路網(wǎng)數(shù)據(jù)模型

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

3應(yīng)用實例

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

本系統(tǒng)探討了基于SuperMap iClient for An-droid（以下均簡稱為iClient）組件包的移動GIS軟件平臺的開發(fā)方法和原理，并在Android+Java+Eclipse平臺上，用iClient組件包設(shè)計實驗與開發(fā)了一套移動網(wǎng)絡(luò)分析物流配送系統(tǒng)?；趇Client的networkAnalyst接口，以SuperMap公司所發(fā)布的長春市區(qū)圖數(shù)據(jù)為例，利用Teitz-Bart算法開發(fā)出一套物流配送系統(tǒng)。

由加粗部分代碼可知此系統(tǒng)的權(quán)重名稱是花費cost，權(quán)重是time，就是修改的權(quán)重參數(shù)，這個參數(shù)更具有計算價值，而且得到的路徑也是最優(yōu)路徑。

系統(tǒng)實現(xiàn)如下圖所示：

4結(jié)束語

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