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

黃秋彬 賀超

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

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

一、引言

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

二、蟻群算法流程

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

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

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

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

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

（5）對(duì)各邊?。╥，j），置△τi，j←0，nc←nc+1。

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

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

三、實(shí)例研究

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

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

四、結(jié)論

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

參考文獻(xiàn)：

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

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

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