混合蟻群算法求解帶軟時(shí)間窗的車輛路徑問題

李 卓 李文霞 巨玉祥 陳曉明 何曉平

(蘭州交通大學(xué)交通運(yùn)輸學(xué)院 蘭州 730070)

0 引 言

車輛路徑問題(vehicle routing problem,VRP)是物流供應(yīng)鏈研究領(lǐng)域的經(jīng)典核心問題[1]，帶軟時(shí)間窗的車輛路徑問題(vehicle routing problem with soft time window,VRPSTW)是組合優(yōu)化中在物資送達(dá)各客戶點(diǎn)設(shè)置了帶有懲罰性質(zhì)的軟時(shí)間窗約束，是經(jīng)典VRP中的一種變體，現(xiàn)實(shí)中快遞配送[2]、應(yīng)急物資調(diào)度[3]、人員救護(hù)[4]等路徑規(guī)劃問題均可被歸納為VRPSTW問題.

考慮到VRPSTW問題的NP-hard性質(zhì)，精確算法在求解具有一定規(guī)模的問題時(shí)已不適用，而啟發(fā)式算法在求解大規(guī)模VRP問題的適用性凸顯，已被學(xué)術(shù)界廣泛認(rèn)可，且不少學(xué)者在傳統(tǒng)算法的基礎(chǔ)上進(jìn)行了改進(jìn).范厚明等[5]將變領(lǐng)域下降搜索應(yīng)用于粒子群算法的擾動(dòng)，提高了算法的搜索性能，并將其應(yīng)用于求解同時(shí)集配車輛路徑問題.郭詠梅等[6]針對(duì)應(yīng)急物流背景下的車輛路徑問題，將人工魚群算法中擁擠度因子引入蟻群算法來指導(dǎo)蟻群的聚集，提高了算法性能.值得注意的是，蟻群優(yōu)化算法在計(jì)算復(fù)雜性和收斂速度方面比較適用于求解VRP及其變體問題，且解的質(zhì)量不依賴于解的初始化，具有較好的魯棒性[7]；然而，由于蟻群算法較強(qiáng)的自組織性和正反饋性，表現(xiàn)出良好收斂性的同時(shí)易陷入局部最優(yōu)，因此，部分學(xué)者通過引入領(lǐng)域搜索[8-9]、精英保留策略或混合其他經(jīng)典啟發(fā)式算法優(yōu)勢(shì)[10-11]來改進(jìn)蟻群算法.近些年來，隨著新興群智能優(yōu)化算法的興起，不少學(xué)者考慮將其應(yīng)用于各自的研究領(lǐng)域[12]，其中螢火蟲算法在許多連續(xù)型優(yōu)化問題中表現(xiàn)出較好的性能[13].由于VRP的離散特性，螢火蟲編碼與解碼是關(guān)鍵環(huán)節(jié)，已有文獻(xiàn)考慮到該問題并對(duì)算法進(jìn)行了改進(jìn).孫俊成等[14]對(duì)解決連續(xù)問題的螢火蟲算法進(jìn)行離散化改進(jìn)，以適應(yīng)于開放式車輛路徑問題的求解.既有研究表明，螢火蟲算法全局搜索能力較強(qiáng)，但獲得解的質(zhì)量高度依賴于解的初始化，算法穩(wěn)健性和收斂性較差.

綜合上述蟻群算法和螢火蟲算法的優(yōu)勢(shì)與不足，為混合算法設(shè)計(jì)提供了思路.基于此，考慮兩種算法的優(yōu)勢(shì)互補(bǔ)，將二者結(jié)合設(shè)計(jì)一種混合算法，算法應(yīng)用于VRPSTW模型的求解，以期保持求解效率的同時(shí)提高求解精度.

1 VRPSTW描述和數(shù)學(xué)模型

1.1 問題描述

基于物流體系中的末端配送，可歸結(jié)為帶軟時(shí)間窗的車輛路徑問題(VRPSTW).具體而言，一個(gè)物資調(diào)度中心，配有足夠數(shù)量的同質(zhì)車輛，路網(wǎng)中有一組客戶需求點(diǎn)，每個(gè)客戶的需求量和服務(wù)持續(xù)時(shí)間必須滿足，考慮盡可能滿足客戶服務(wù)時(shí)間窗的同時(shí)合理規(guī)劃車輛路徑，使總配送成本最小.

需要解決的問題及基本假設(shè)：①車輛從物資調(diào)度中心出發(fā)，服務(wù)若干客戶需求點(diǎn)后返回調(diào)度中心；②每個(gè)客戶點(diǎn)僅由一輛車訪問且只能被訪問一次，其需求量不能超過車輛容量；③車輛為相同車型且運(yùn)輸總量不能超出中心容量限制；④每個(gè)客戶的坐標(biāo)、需求量和服務(wù)持續(xù)時(shí)間已知，且都有服務(wù)時(shí)間窗限制.

1.2 數(shù)學(xué)模型

1.2.1模型參數(shù)

運(yùn)輸網(wǎng)絡(luò)G=(V,A)，主要參數(shù)及相關(guān)變量見表1.

表1 模型參數(shù)及變量

1.2.2模型構(gòu)建

參照傳統(tǒng)車輛路徑問題的優(yōu)化方向，以配送總成本最小為目標(biāo)，構(gòu)建帶軟時(shí)間窗的車輛路徑優(yōu)化模型.

(1)

(2)

(3)

(4)

(5)

(6)

(7)

Tik+ui+tijk≤Tjk+C(1-xijk),

?i,j∈V0,k∈K

(8)

xijk∈{0,1},?i,j∈V,k∈K

(9)

Qk,qi,ui>0,i∈V0,k∈K

(10)

式(1)為最小化配送成本的目標(biāo)函數(shù)；式(2)～(3)為每個(gè)客戶需求點(diǎn)僅被一輛車服務(wù)且僅訪問一次；式(4)為子回路消去約束；式(5)為車輛從調(diào)度中心出發(fā)最終返回調(diào)度中心；式(6)為節(jié)點(diǎn)平衡約束；式(7)為車輛容量限制；式(8)為車輛從服務(wù)上一需求點(diǎn)到訪問下一需求點(diǎn)所要滿足的時(shí)間條件；式(9)～(10)為決策變量和參數(shù)約束.

2 求解VRPSTW的混合蟻群算法

VRPSTW問題是經(jīng)典VRP問題的子問題之一，被認(rèn)為是NP-hard問題.由于該問題的求解規(guī)模較大，精確算法無法解決指數(shù)爆炸問題，難以求得最優(yōu)解.而傳統(tǒng)啟發(fā)式算法求解VRP問題已得到廣泛應(yīng)用，如遺傳算法、蟻群算法、禁忌搜索和模擬退火等均表現(xiàn)出良好的求解效果.因此，通過設(shè)計(jì)改進(jìn)的啟發(fā)式算法以求解VRPSTW問題.

2.1 蟻群算法

(11)

式中：α為信息素重要度因子；β為啟發(fā)式信息重要度因子；alloweds=V/{tabus}為螞蟻s下一步允許訪問的節(jié)點(diǎn)集合，tabus為螞蟻s訪問過的節(jié)點(diǎn)集合，即路徑禁忌表.

啟發(fā)式函數(shù)ηij(t)越大，螞蟻選擇節(jié)點(diǎn)j的概率越大.隨著迭代次數(shù)的增加，路徑(i,j)的信息素濃度τij不斷疊加，同時(shí)殘留的信息素將持續(xù)揮發(fā)，則(t+1)時(shí)刻路徑(i,j)的信息素τij(t+1)濃度更新規(guī)則為

(12)

式中：ρ為信息素?fù)]發(fā)系數(shù)；Q為全局信息素常量；由于模型目標(biāo)是成本最小，則cost(i,j)為路徑(i,j)上的成本.

2.2 螢火蟲算法

螢火蟲算法(firefly algorithm,FA)將搜索空間的每個(gè)可行解模擬為自然界中的螢火蟲個(gè)體，將迭代搜索過程模擬為螢火蟲個(gè)體間的吸引和移動(dòng)過程.其基本原理涉及兩個(gè)主要因素：種群個(gè)體的發(fā)光亮度和個(gè)體間的相互吸引度.發(fā)光亮度與個(gè)體的適應(yīng)值有關(guān)，適應(yīng)值越好，亮度越強(qiáng)；吸引度與發(fā)光亮度成正比，與個(gè)體間的距離成反比；亮度更高的螢火蟲吸引種群中其他個(gè)體朝著其搜索領(lǐng)域內(nèi)更優(yōu)的位置移動(dòng)，以此來完成優(yōu)化過程中螢火蟲個(gè)體位置的更新.

個(gè)體i的發(fā)光強(qiáng)度Ii用適應(yīng)值表示，適應(yīng)函數(shù)一般為目標(biāo)函數(shù)，表示為

Ii=f(Xi),Xi=(xi1,xi2,…,xid)

(14)

若個(gè)體i的亮度大于個(gè)體j，則螢火蟲i對(duì)螢火蟲j的吸引度βi,j隨距離變化

(15)

式中：β0為最大吸引度，即光源處(r=0)；γ為光吸收系數(shù)，γ∈[0.01,100]；ri,j為個(gè)體i與個(gè)體j間的歐式距離.

個(gè)體j被個(gè)體i吸引，位置更新公式為

Xj(t+1)=Xj(t)+

βi,j(Xi(t)-Xj(t))+α

(16)

式中：α為隨機(jī)控制參數(shù)，α∈[-1,1].

2.3 螢火蟲-蟻群混合算法

蟻群算法在VRPSTW問題中得到成功的應(yīng)用[15]，由于其具有較強(qiáng)的信息反饋機(jī)制，對(duì)大規(guī)模問題具有較高的求解效率，但當(dāng)?shù)笃谛畔⑺貪舛冗^高時(shí)易產(chǎn)生信息素停滯，導(dǎo)致過早收斂，從而陷入局部最優(yōu).針對(duì)此問題，考慮螢火蟲優(yōu)化中較劣個(gè)體自組織性地向較優(yōu)個(gè)體的移動(dòng)，促使種群在向優(yōu)勢(shì)個(gè)體聚集的過程中完成個(gè)體位置的迭代更新，在此過程中能搜索到新的解空間.基于此，提出將以上螢火蟲個(gè)體間的尋優(yōu)過程引入蟻群優(yōu)化，綜合二者的優(yōu)勢(shì)提出螢火蟲-蟻群混合算法(ACO_FA)，以期在每次迭代中產(chǎn)生額外的滿意解，用來進(jìn)行螞蟻信息素?cái)_動(dòng)，避免信息素的停滯，改善算法過早收斂的情況并跳出局部最優(yōu).

算法以蟻群算法為基本框架，將螢火蟲個(gè)體的尋優(yōu)過程用于擴(kuò)大搜索的解空間，通過控制迭代過程中信息素的聚集，提出一種信息素交換過程(以下簡(jiǎn)稱FA搜索過程).算法流程見圖1.

圖1 算法流程圖

2.3.1FA搜索過程

提出的算法首先調(diào)用蟻群算法，構(gòu)造各次迭代的可行解集，然后調(diào)用FA搜索過程，對(duì)得到的額外的可行解集進(jìn)行擇優(yōu)處理后與原可行解集結(jié)合，來更新路徑上螞蟻信息素濃度.

由于VRPSTW問題是離散優(yōu)化問題，而螢火蟲算法在求解連續(xù)型問題更為適用，因此，為了使螢火蟲適應(yīng)離散優(yōu)化問題，提出對(duì)初始可行解進(jìn)行重新編碼與解碼，以此將螢火蟲算法應(yīng)用于離散優(yōu)化問題中.

1) 螢火蟲編碼 蟻群算法構(gòu)造各代的初始可行解s；將整數(shù)1～n(n為客戶數(shù)量)按升序形成序列sq1=(0,1,2，…，n)；將蟻群算法中得到的可行解s與序列sq1一一對(duì)應(yīng)后，sq1按可行解s中客戶序號(hào)升序排列，得到客戶點(diǎn)1～n的訪問次序sq2，即編碼的螢火蟲個(gè)體.

2) 位置更新 通過上述編碼方式對(duì)可行解集進(jìn)行螢火蟲編碼，并按式(14)計(jì)算各個(gè)螢火蟲個(gè)體的發(fā)光強(qiáng)度，例如個(gè)體i被編碼為216354，個(gè)體j被編碼為315462，且個(gè)體i的亮度大于個(gè)體j，計(jì)算個(gè)體間各元素的距離，見圖2，rij=6.按式(15)～(16)進(jìn)行螢火蟲個(gè)體各元素位置的更新，形成新的序列sq3，即新的螢火蟲個(gè)體.

圖2 螢火蟲個(gè)體間的距離

3) 螢火蟲解碼 更新后，序列sq3可能出現(xiàn)非整數(shù)或負(fù)數(shù)，對(duì)其進(jìn)行合法化處理：序列sq1與sq3一一對(duì)應(yīng)后，序列sq1按序列sq3升序排列得到序列sq*；判斷sq*是否可行，即是否滿足模型約束，滿足，則輸出，否則，進(jìn)行插入1(客戶點(diǎn))操作修復(fù)不可行解，以此得到FA搜索后的可行解，見圖3.

圖3 FA搜索編碼與解碼

由圖3可知，原可行解為261 435，經(jīng)過FA搜索，更新過的可行解為261 453，在向最優(yōu)個(gè)體移動(dòng)的過程中，原可行解進(jìn)行了領(lǐng)域搜索，改善了解的多樣性.

2.3.2全局信息素更新

對(duì)經(jīng)過FA搜索后獲得的可行解集執(zhí)行精英保留策略，得到的優(yōu)勢(shì)解與原可行解集共同用于更新路徑信息素濃度，在弧段上沉積信息素，以指導(dǎo)后來螞蟻的路徑尋找機(jī)制.路徑(i,j)的信息素濃度τij(t+1)按下式更新：

(17)

(18)

3 算例分析

3.1 實(shí)驗(yàn)設(shè)置

算例的實(shí)驗(yàn)數(shù)據(jù)通過Matlab隨機(jī)生成一個(gè)配送中心和19個(gè)客戶點(diǎn).所有客戶點(diǎn)隨機(jī)分布在(0,70)2的平面坐標(biāo)內(nèi)；客戶需求是區(qū)間[0,20]隨機(jī)產(chǎn)生的整數(shù)(t)，時(shí)間窗等其他信息見表2；車輛行駛速度v=2 km/min；單車載重60 t；客戶單位需求量的服務(wù)時(shí)間為1 min/t；單位距離成本為5元/km.提出的算法相關(guān)參數(shù)見表3.

表2 客戶信息表

表3 提出的算法相關(guān)參數(shù)

3.2 模型計(jì)算結(jié)果及分析

對(duì)于混合蟻群算法的性能，以軟時(shí)間窗條件下的配送總成本最小化為目標(biāo)，通過Matlab軟件編寫程序，在相同的參數(shù)設(shè)置及實(shí)驗(yàn)條件下，分別對(duì)傳統(tǒng)蟻群算法與文中提出的混合算法進(jìn)行500次迭代，并針對(duì)給定的數(shù)值實(shí)驗(yàn)分別運(yùn)行10次程序，統(tǒng)計(jì)結(jié)果見表4.

所有算法在一臺(tái)搭載1.6 GHz的Intel Core i5處理器和4 GB內(nèi)存的計(jì)算機(jī)平臺(tái)上實(shí)現(xiàn)，算法收斂曲線和模型優(yōu)化結(jié)果見圖4～5.

表4 ACO_FA算法與ACO算法數(shù)值實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果

圖4 ACO_FA算法與ACO算法收斂曲線對(duì)比

圖5 ACO_FA算法優(yōu)化結(jié)果

由表4可知，混合算法相較于傳統(tǒng)蟻群算法在解的準(zhǔn)確度上有顯著提高，全局最優(yōu)解優(yōu)化了約15.4%，全局平均解優(yōu)化了約15.6%，反映出算法在優(yōu)化過程中解決了螞蟻信息素停滯的弊端，避免陷入局部最優(yōu)狀態(tài)；其次，解的平均偏差降低了約0.21%，最大偏差降低了約0.48%，說明算法在提高最優(yōu)解質(zhì)量的同時(shí)，對(duì)算法的穩(wěn)健性也有改善，表現(xiàn)出良好的求解性能.由于提出的算法在原有蟻群算法的基礎(chǔ)上增加了FA搜索過程，故需要在領(lǐng)域搜索中花費(fèi)額外的時(shí)間，因此，在計(jì)算中需要更多的時(shí)間.

不同于一般領(lǐng)域搜索的隨機(jī)性擾動(dòng)，算法中的FA搜索過程是有方向的領(lǐng)域搜索，是以本次迭代種群中較優(yōu)解為目標(biāo)進(jìn)行擾動(dòng)，改善每代可行解多樣性的同時(shí)，使搜索過程更有目的性，加快算法的收斂，以期在保持原有的求解效率的同時(shí)提高求解準(zhǔn)確度.由圖4可知，此算法在迭代177次時(shí)達(dá)到最優(yōu)，蟻群算法在迭代158次時(shí)達(dá)到最優(yōu)，基本保持了良好的收斂性.

顯然，此模型可以有效的解決帶軟時(shí)間窗的車輛路徑問題.配送中心在車輛有限載重的條件下，盡可能滿足客戶時(shí)間窗的同時(shí)，使總成本最小，配送最低成本為3 342元，配送路徑1為1-14-2-16-4-5-9-3-1，車輛滿載率為100%；配送路徑2為1-7-6-10-18-8-1，車輛滿載率為95%；配送路徑3為1-15-11-12-17-13-1，車輛滿載率為88.33%；配送路徑4為1-20-19-1，車輛滿載率為43.33%.

4 結(jié) 論

1) 考慮到蟻群算法在迭代過程中的信息素停滯問題，將螢火蟲算法中螢火蟲的尋優(yōu)機(jī)制引入蟻群算法，有目的性的擴(kuò)大搜索的解空間，保持每代解具有多樣性，以此來優(yōu)化螞蟻信息素濃度的更新機(jī)制，克服了陷入局部最優(yōu)的瓶頸，最終提高解的精確度，并且在一定程度上保持了原有算法的求解效率.

2) 改進(jìn)蟻群算法在精確性上有顯著提高，在算法穩(wěn)健性也有較大改進(jìn).僅考慮了單目標(biāo)蟻群算法的性能，設(shè)計(jì)求解多目標(biāo)優(yōu)化問題的蟻群算法將是下一步研究方向.