基于蟻群算法的VRPTW問題優(yōu)化研究

黃秋彬 賀超

【摘要】針對目前物流配送過程中客戶對于送貨準(zhǔn)時性要求日益提升的問題，對每個客戶采用時間窗管理約束，作為NP-Hard問題，啟發(fā)式算法常被用于解決VRPTW問題。本文選取重慶市某物流企業(yè)的配送情況進(jìn)行實例研究，選取其中具有代表性的16個客戶點，并對客戶進(jìn)行時間窗管理約束，同時運(yùn)用蟻群算法進(jìn)行路徑規(guī)劃研究，研究表明蟻群算法作為啟發(fā)式算法中的一種能夠有效用于解決VPIPTW問題。

【關(guān)鍵詞】物流配送；VRPTW問題；蟻群算法

一、引言

車輛路徑問題（VRPTW）是物流配送研究中的核心問題，其中對客戶加以時間窗約束的車輛路徑問題則被稱作帶時間窗的車輛路徑問題（VRPTW），在競爭愈加激烈的現(xiàn)代物流行業(yè)，客戶的滿意度是每個物流企業(yè)都需重視的問題，同時考慮到每個客戶適宜收貨時間的差異性，對客戶進(jìn)行不同的時間窗約束顯然更為符合現(xiàn)實情況，因此VRPTW一直受到廣大學(xué)者的廣泛關(guān)注和不斷研究。對于VRPTW問題的研究方法總體可分為兩類：一類是精確算法、另一類是啟發(fā)式算法。其中精確算法具有較高的求解精度，但由于其求解難度會隨著問題的復(fù)雜度的增加而呈現(xiàn)指數(shù)型增長，難以保證其求解速度。與精確算法相比較而言，啟發(fā)式算法能夠有效運(yùn)用于大規(guī)模問題的求解，更具有實用性。目前較為常用的啟發(fā)式算法包括蟻群算法、模擬退火算法、粒子群算法、模擬退火算法等[1]，本文選取蟻群算法進(jìn)行VRPTW問題的優(yōu)化研究。

二、蟻群算法流程

傳統(tǒng)的VRPTW問題指的是在滿足客戶需求量和時間窗限制的前提下，研究配送成本和懲罰成本總和最小的車輛路徑問題。蟻群算法最早的提出是為了應(yīng)用于旅行商問題（TSP），隨著蟻群算法的不斷改善及優(yōu)化，如今蟻群算法已能夠較好運(yùn)用于VRPTW問題的求解。

以下是蟻群算法的基本步驟：

（1）nc←0（其中nc代表迭代次數(shù)；各τij以及△τi，j進(jìn)行初始化；m只螞蟻被放置于n個頂點上。

（2）將各螞蟻的初始出發(fā)點放置于當(dāng)前解集之中；每一只螞蟻k（k=1，2，3，…，m）按照概率pi，jk移至下一個頂點j；將頂點j置于當(dāng)前解集。 （3）計算各螞蟻爬行的路徑長度Lk（k=1，2，3，…，m）；記錄當(dāng)前的最優(yōu)解。

（4）按照相應(yīng)的方程對軌道強(qiáng)度進(jìn)行修改。

（5）對各邊弧（i，j），置△τi，j←0，nc←nc+1。

（6）若nc小于原先設(shè)定的迭代次數(shù)并且沒有退化行為（即找到的都是相同的解），則轉(zhuǎn)至步驟（2）.

（7）結(jié)束算法并輸出最優(yōu)解。

三、實例研究

為了驗證所提蟻群算法在VRPTW問題中的有效運(yùn)用性，選取重慶市某物流企業(yè)的配送情況進(jìn)行實例研究，選取其中具有代表性的16個客戶點，并對客戶進(jìn)行時間窗管理約束，同時運(yùn)用蟻群算法進(jìn)行路徑規(guī)劃研究，相應(yīng)的客戶信息如表1所示：

基于表1中的客戶信息，采用蟻群算法進(jìn)行路徑優(yōu)化研究，具體的路徑優(yōu)化結(jié)果如圖1及表2所示：

四、結(jié)論

本文在研究了蟻群算法的基礎(chǔ)上，選取重慶市某物流企業(yè)作為研究對象，對16個客戶進(jìn)行帶時間窗約束下的路徑規(guī)劃研究。MATLAB運(yùn)行結(jié)果顯示蟻群算法能夠較快收斂，在較短時間內(nèi)得到最優(yōu)解，有效證明了蟻群算法在VRPTW問題上的實用性，為相應(yīng)的研究提供了借鑒思路。

參考文獻(xiàn)：

[1]何小鋒，馬良.帶時間窗車輛路徑問題的量子蟻群算法[J].系統(tǒng)工程理論與實踐，2013，33（5）：1255-1261.

[2]唐靜.基于蟻群算法車輛路徑問題的研究與應(yīng)用[D].中國科學(xué)院大學(xué)，2014.

[3]劉志碩，申金升，柴躍廷.基于自適應(yīng)蟻群算法的車輛路徑問題研究[J].控制與決策，2005，20（5）：562-566.