賀智明,鄭 麗,梁 文
(江西理工大學(xué) 信息工程學(xué)院,江西 贛州 341000)
車(chē)輛路徑問(wèn)題(vehicle routing problem,VRP)是指一組車(chē)輛從指定點(diǎn)出發(fā),且遍歷到一系列特定點(diǎn)的路線[1]。由于該問(wèn)題的傳統(tǒng)求解方法效果不佳,如精確算法[2]和啟發(fā)式算法[3,4]。因此,學(xué)者們將AI技術(shù)與啟發(fā)式算法結(jié)合,如:模擬退火算法[5]、禁忌搜索算法[6]、遺傳算法[7]和蟻群算法[8]等。相對(duì)而言,蟻群算法(ant colony,ACO)在尋徑方面占據(jù)獨(dú)特優(yōu)勢(shì)。然而,當(dāng)問(wèn)題規(guī)模較大時(shí),算法易陷入局部困境,無(wú)法對(duì)搜索空間進(jìn)行深層次挖掘。為此,學(xué)者們做出不同的改進(jìn),例如:文獻(xiàn)[9]將人工免疫和ACO算法相結(jié)合,有效解決緊急糧食分配問(wèn)題;徐坤等[10]將信息素?fù)]發(fā)因子采用萊維飛行模式更新,提高了算法的全局尋優(yōu)能力;王飛鵬等[11]在求解TSP問(wèn)題的最優(yōu)解集中按比例選取部分解集構(gòu)造近似骨架,并基于近似骨架對(duì)問(wèn)題分段求解,有效解決算法精度不高等問(wèn)題。
上述改進(jìn)方法主要通過(guò)改變部分更新規(guī)則或同其它算法互補(bǔ)。然而ACO算法中關(guān)鍵參數(shù)的設(shè)置以及群體的合作行為都直接影響著算法性能。為此,本文提出自適應(yīng)動(dòng)態(tài)搜索蟻群算法(ADACO),通過(guò)實(shí)驗(yàn)性配置關(guān)鍵組合參數(shù)和自適應(yīng)偽隨機(jī)策略協(xié)助群體選擇合理的轉(zhuǎn)移方向。此外,信息素強(qiáng)度的分段化設(shè)定有效預(yù)防了群體長(zhǎng)時(shí)間滯留于困境中而無(wú)法跳脫的現(xiàn)象,減少了時(shí)間開(kāi)銷(xiāo)。
本小節(jié)針對(duì)車(chē)輛路徑問(wèn)題建立數(shù)學(xué)模型,其中包括模型假設(shè)、符號(hào)說(shuō)明和目標(biāo)優(yōu)化函數(shù)的設(shè)定。
依據(jù)實(shí)際問(wèn)題對(duì)該模型做出如下假設(shè):
(1)指定配送中心負(fù)責(zé)完成一系列需求點(diǎn)的配送服務(wù);
(2)配送中心以及各個(gè)需求點(diǎn)的相對(duì)地理位置和對(duì)應(yīng)需求量是明確給定的;
(3)車(chē)輛配送完畢,返回指定配送中心;
(4)配送車(chē)輛是同種規(guī)格,不存在些許誤差;
(5)不考慮城市交通堵塞問(wèn)題;
(6)配送車(chē)輛始終以勻速行駛,單位距離內(nèi)的配送成本是等同的,因此行駛距離可代表配送成本;
(7)每個(gè)需求點(diǎn)當(dāng)且僅當(dāng)由一臺(tái)配送車(chē)輛服務(wù),且該車(chē)輛服務(wù)的所有需求點(diǎn)的需求量之和小于或等于車(chē)輛的額定限載量。
該模型包含的相關(guān)符號(hào)說(shuō)明見(jiàn)表1。
表1 相關(guān)符號(hào)說(shuō)明
首先,決策變量如下
目標(biāo)優(yōu)化函數(shù)如式(1)所示
(1)
其中,cij計(jì)算如式(2)所示
(2)
cok表示配送中心調(diào)度成本;cs表示單位距離內(nèi)車(chē)輛行駛成本;當(dāng)i=0時(shí),需要配送車(chē)輛越多,總的成本也隨之增加。由式(2)可知,減少配送車(chē)輛的派遣數(shù)量以及縮短車(chē)輛的行駛距離是降低配送成本的關(guān)鍵所在。
相關(guān)約束條件如式(3)至式(11)所示
(3)
(4)
(5)
(6)
(7)
(8)
xijk(xijk-1)=0,i=1,2,…,n
j=1,2,…,nk=1,2,…,m
(9)
yik(yik-1)=0,i=1,2,…,nk=1,2,…,m
(10)
(11)
其中,式(1)表示配送總成本達(dá)到最小;式(2)表示成本費(fèi)用計(jì)算;式(3)表示車(chē)輛k單次累計(jì)配送量不高于車(chē)輛額定限載量;式(4)表示車(chē)輛k單次累計(jì)配送距離不超過(guò)車(chē)輛最大限定行駛距離;式(5)表示單個(gè)需求點(diǎn)i僅由一臺(tái)車(chē)輛負(fù)責(zé)配送;式(6)表示共有m臺(tái)車(chē)輛參與配送;式(7)和式(8)表示兩個(gè)變量之間的關(guān)系;式(9)和式(10)表示兩變量均滿足0-1約束;式(11)表示配送過(guò)程中不存在回路現(xiàn)象。
M.Dorigo,V.Maniezzo和A.Colorni等意大利學(xué)者長(zhǎng)期研究自然界中蟻群覓食尋徑行為,發(fā)現(xiàn)不管地理環(huán)境多復(fù)雜,蟻群經(jīng)常能克服重重困難和阻礙,在洞穴和食物之間找到一條最佳路徑。究其根本,螞蟻在走過(guò)的路上均會(huì)放置一種稱(chēng)之為“信息素”的分泌物質(zhì)。某條路徑上經(jīng)過(guò)的螞蟻越多,分泌物則堆積越多,分泌物的濃度也會(huì)不斷增強(qiáng)。此外,螞蟻對(duì)該分泌物具有一定的感知能力,它們會(huì)根據(jù)路徑上分泌物濃度的高低去選擇路徑。然而,隨著時(shí)間的逐步增加,分泌物質(zhì)會(huì)出現(xiàn)漸進(jìn)式蒸發(fā)現(xiàn)象。因此,路徑上剩余分泌物質(zhì)濃度的高低與吸引后來(lái)螞蟻數(shù)量的多少成正比,從而形成一種正反饋機(jī)制。這種機(jī)制能夠幫助蟻群在“深度挖掘”和“合理利用”之間尋求一個(gè)最佳臨界點(diǎn),即時(shí)找到最佳路徑。為此,學(xué)者們多次模擬該生物相互合作的社會(huì)性和組織性群體行為,最終在20世紀(jì)90年代初期提出啟發(fā)式ACO算法[8]。圖1從整體視角規(guī)劃出該算法的邏輯結(jié)構(gòu),為解決實(shí)際問(wèn)題提供了清晰而有力的幫助和支持。
圖1 ACO算法的基本邏輯結(jié)構(gòu)
ACO算法一經(jīng)提出,學(xué)者們紛紛將蟻群尋徑思想運(yùn)用到經(jīng)典TSP問(wèn)題上。近些年來(lái),學(xué)者們又在單回路TSP問(wèn)題上逐步衍生出多回路TSP問(wèn)題,即VRP問(wèn)題。換言之,TSP是VRP的基礎(chǔ)問(wèn)題。因此,本小節(jié)以求解TSP的ACO算法為基礎(chǔ)建立求解VRP的ACO算法模型。
(12)
其中,Jk(i)={1,2,…,n}-τk表示螞蟻k下一步允許選擇的城市;列表τk記錄著此次迭代中螞蟻k的已訪問(wèn)城市,在接下來(lái)的遍歷中不能再次訪問(wèn)列表τk中的城市;τij(t)表示t時(shí)刻路徑(i,j)上信息素的數(shù)量;ηij表示啟發(fā)因子,一般取路徑(i,j)距離的倒數(shù):ηij=1/dij;α和β分別表示路徑上信息素累積量和啟發(fā)信息的權(quán)重比例。
當(dāng)所有螞蟻均實(shí)現(xiàn)遍歷任務(wù)后,各條路徑上的信息素?cái)?shù)量根據(jù)式(13)和式(14)更新
τij(t+n)=(1-ρ)τij(t)+Δτij(t)
(13)
(14)
(15)
其中,Q為正常數(shù),Lk表示螞蟻k在此次迭代中所走過(guò)的路徑長(zhǎng)度。
針對(duì)ACO算法的不足,本文基于原有算法的框架做出一些改進(jìn),以提高算法的性能和效率。
本文采用隨機(jī)性選擇和確定性選擇相結(jié)合的策略,并自適應(yīng)性調(diào)整轉(zhuǎn)移概率,引導(dǎo)算法探索最優(yōu)路徑和提高算法的收斂性能。詳細(xì)地講,算法在搜索之前,根據(jù)式(16)中的偽隨機(jī)分布轉(zhuǎn)移規(guī)則(pseudo-random distribution transition rule,PRDTR)先執(zhí)行狀態(tài)轉(zhuǎn)換的選擇操作,使得搜索個(gè)體更加傾向于選擇信息素累積量多且距離較近的城市j
(16)
(17)
(2)信息素強(qiáng)度的動(dòng)態(tài)調(diào)整
由式(12)可知,當(dāng)α=0時(shí),只有路徑啟發(fā)信息β發(fā)揮著作用,此時(shí)算法等同于最短路徑尋優(yōu),如式(18)所示
(18)
當(dāng)β=0時(shí),路徑啟發(fā)信息β為0,只有路徑信息因子α引導(dǎo)搜索個(gè)體進(jìn)行單純性地隨機(jī)搜索,如式(19)所示
(19)
為使算法能夠在α和β的相互作用下始終維持在“深度探索”和“合理利用”的臨界點(diǎn)。本文采用式(20)中的分段函數(shù)Qi替代式(15)中的常數(shù)Q,使得路徑上信息素?cái)?shù)量變化時(shí),群體均能夠有根據(jù)地選擇路徑,改善了群體尋徑時(shí)的盲目性選擇
(20)
其中,式(20)對(duì)應(yīng)著不同區(qū)間內(nèi)的不同取值。當(dāng)函數(shù)最優(yōu)值在某一時(shí)間段內(nèi)持續(xù)沒(méi)有變化,說(shuō)明整個(gè)搜索過(guò)程可能陷入局部誤區(qū),此時(shí)分段函數(shù)的設(shè)定強(qiáng)制增加或減少路徑上信息素?cái)?shù)量的導(dǎo)向,賦予算法跳出局部誤區(qū)的能力。
通過(guò)2.1至2.3小節(jié)對(duì)基本ACO算法、算法模型及其改進(jìn)方面的詳細(xì)介紹,本文提出ADACO算法,且該算法求解車(chē)輛路徑問(wèn)題的偽代碼描述如下:
算法1:求解車(chē)輛路徑問(wèn)題的ADACO算法
輸入:目標(biāo)優(yōu)化函數(shù)minZ,關(guān)鍵參數(shù)α、β、ρ,最大迭代次數(shù)iterations,起始點(diǎn)螞蟻只數(shù)o等各項(xiàng)相關(guān)實(shí)驗(yàn)參數(shù),起始點(diǎn)和一系列需求點(diǎn)的位置坐標(biāo)、相應(yīng)需求量。
輸出:全局配送方案及配送成本
(1) nc=1
(2) while nc≤iterations// 停滯條件
(3) for k=1:o// 對(duì)o只螞蟻循環(huán)
(4) whileτk=0 // 禁忌表為0
(5) for j=1:n// 對(duì)n個(gè)需求點(diǎn)循環(huán)
(6) if 禁忌表τk中不包含需求點(diǎn)j
(7) 將需求點(diǎn)j添加到待訪問(wèn)需求點(diǎn)列表Jk(i)中
(8) end if
(9) end forj
(10) forj= 1:Jk(i)
(11) if 剩余車(chē)載量≥待訪問(wèn)需求點(diǎn)的需求量
(12) 根據(jù)式(16)選擇待訪問(wèn)需求點(diǎn)j, 計(jì)算裝載距離,并更新禁忌表τk和待訪問(wèn)需求點(diǎn)列表Jk(i)
(13) else
(14) 起始點(diǎn)重新發(fā)出一臺(tái)車(chē)且車(chē)輛編號(hào)加1, 按照式(16)和式(17)繼續(xù)遍歷剩余的待訪問(wèn)需求點(diǎn)j
(15) end if
(16) end forj
(17) end whileτk
(18) 計(jì)算構(gòu)造解的路徑長(zhǎng)度, 即配送成本
(19) end fork
(20) 依據(jù)式(13)-式(15)和式(20)更新各路徑信息素增量Δτij, 進(jìn)而更新全局路徑信息素τk
(21) nc = nc +1
(22) 清空禁忌表τk
(23) end while nc
(24) 輸出最佳配送方案以及對(duì)應(yīng)的配送成本
針對(duì)上述偽代碼的描述,分析其時(shí)間復(fù)雜度:第(5)-第(9)步設(shè)置待訪問(wèn)需求點(diǎn)列表的時(shí)間復(fù)雜度為O(n),第(10)-第(16)步單只螞蟻通過(guò)自適應(yīng)偽隨機(jī)選擇并遍歷需求點(diǎn)的時(shí)間復(fù)雜度均為O(n),第(4)-第(17)步單只螞蟻構(gòu)造解的時(shí)間復(fù)雜度為O(n2),第(3)-第(19)步o只螞蟻構(gòu)造解的時(shí)間復(fù)雜度為O(o·n2),第(2)-第(23)步o只螞蟻經(jīng)過(guò)iterations次循環(huán)的時(shí)間復(fù)雜度為O(o·n2·iterations)。由此可以看出ADACO算法較原有算法沒(méi)有增加多余的時(shí)間開(kāi)銷(xiāo),由此驗(yàn)證該算法的可行性。
為了驗(yàn)證算法改進(jìn)前后的高效性,本文采用鄭州市“家輝生鮮”連鎖店貨物配送問(wèn)題作為實(shí)驗(yàn)案例,其測(cè)試環(huán)境:Windows操作系統(tǒng);i5處理器;雙核2.5G CPU;4.0 G內(nèi)存;1 T硬盤(pán);MATLAB R2016a仿真平臺(tái)。
該連鎖店的倉(cāng)庫(kù)每天都會(huì)向各個(gè)連鎖分店進(jìn)行生鮮補(bǔ)給,最大化滿足廣大顧客的生活需求。以下是通過(guò)高德地圖獲取到倉(cāng)庫(kù)以及20個(gè)分店的相對(duì)位置,如圖2所示。編號(hào)1-20是各個(gè)連鎖店的分布位置,“★”代表倉(cāng)庫(kù)的位置。
圖2 倉(cāng)庫(kù)及連鎖分店的分布位置
為了方便測(cè)試,將倉(cāng)庫(kù)及各個(gè)連鎖分店的位置坐標(biāo)映射至XOY平面上,其中倉(cāng)庫(kù)編號(hào)為0,對(duì)應(yīng)的位置坐標(biāo)為(100,400)。各連鎖分店的位置坐標(biāo)及對(duì)應(yīng)的每日需求補(bǔ)給量見(jiàn)表2,表2中的位置坐標(biāo)信息轉(zhuǎn)化到直角坐標(biāo)系上,如圖3所示。
表2 連鎖分店位置坐標(biāo)及補(bǔ)給量
ACO算法中,龐大的參數(shù)系彼此關(guān)聯(lián),密切影響著算法的性能,其中起主要作用的參數(shù)分別為:路徑信息素因子α、路徑啟發(fā)因子β和信息素蒸發(fā)比例ρ。因此,α、β以及ρ的組合配置是衡量算法性能指標(biāo)和求解效率的關(guān)鍵因素。
圖3 直角坐標(biāo)系下倉(cāng)庫(kù)及連鎖分店的位置分布
為了得到組合參數(shù)的最佳配置,本小節(jié)在上述測(cè)試案例的TSP問(wèn)題上進(jìn)行實(shí)驗(yàn),按照修改一個(gè)參數(shù)的值,另外兩個(gè)參數(shù)值保持不變的規(guī)則斟酌最佳參數(shù)的設(shè)定。初始默認(rèn)參數(shù)為α=1,β=1,ρ=0.7,iterations為100次,每組實(shí)驗(yàn)分別運(yùn)行10次,實(shí)驗(yàn)結(jié)果如圖4所示。
圖4 α、β、ρ的不同配置對(duì)算法性能的影響
其中,最差、平均、最優(yōu)路徑長(zhǎng)度以及差值分別表示10次運(yùn)行結(jié)果中的最大值、平均值、最小值、最大值與最小值之差。差值越小,說(shuō)明系統(tǒng)越穩(wěn)定,解的質(zhì)量也越好。上述實(shí)驗(yàn)結(jié)果可以看出3個(gè)關(guān)鍵參數(shù)的最佳配置為:α=1,β=4,ρ=0.7。
結(jié)合案例,其它相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置見(jiàn)表3。
本小節(jié)在“家輝生鮮”實(shí)際案例中,對(duì)4種算法進(jìn)行測(cè)試和對(duì)比分析。其中,對(duì)改進(jìn)的兩個(gè)方面分別測(cè)試,得到自適應(yīng)轉(zhuǎn)移蟻群算法(AACO)和動(dòng)態(tài)導(dǎo)向蟻群算法(DACO),另外兩組則為ACO算法和ADACO算法。
表3 相關(guān)實(shí)驗(yàn)參數(shù)設(shè)置
表4列出了4種算法各自運(yùn)行10次所對(duì)應(yīng)的配送成本、收斂代數(shù)以及CPU運(yùn)行時(shí)間。在配送成本和收斂代數(shù)兩方面,ACO算法的配送成本大多集中于4750附近,最大值為4758,最小值為4744,始終沒(méi)有一個(gè)較大的突破,收斂代數(shù)也呈現(xiàn)跌宕起伏的狀態(tài),不具穩(wěn)定性;AACO算法的配送成本則相對(duì)穩(wěn)定,主要趨于4729附近,其中配送成本為4725的概率占據(jù)30%,收斂代數(shù)同樣沒(méi)有明顯的規(guī)律性;DACO算法得到的配送成本較于前兩者更具穩(wěn)定性,始終維持在4710-4715之間,且4710出現(xiàn)的概率為40%,迭代次數(shù)也相應(yīng)收斂于30代。對(duì)比前三者可知,ADACO算法不僅在配送成本方面則有了一個(gè)實(shí)質(zhì)性的進(jìn)展和突破,不再局限于4700的約束,且以50%的概率歸攏于4674,而且最佳的收斂代數(shù)曾達(dá)到26.26。此外,10次運(yùn)行結(jié)果中,4種算法的CPU運(yùn)行時(shí)間都是參差不齊的,但是觀察其最佳值、平均值和最差值,ACO算法均高于其它3種算法,而ADACO算法則略勝一籌。
表4 各算法的運(yùn)行結(jié)果比較
通過(guò)對(duì)4種算法運(yùn)行10次結(jié)果的縱橫對(duì)比以及多方面分析,得到AACO算法、DACO算法和ADACO算法較于ACO算法的提升力度和改進(jìn)空間,見(jiàn)表5,ADACO算法提升力度尤為明顯。
表5 各類(lèi)算法較于ACO算法的提升力度/%
對(duì)照表4中的相關(guān)數(shù)據(jù),圖5給出了ACO算法中最差配送方案及其對(duì)應(yīng)且出現(xiàn)次數(shù)最多的配送成本和收斂代數(shù)。圖6-圖8則給出了其它3種算法的最佳配送方案、配送成本以及收斂代數(shù)。
觀察圖5-圖8可得,4種配送方案中2號(hào)和4號(hào)車(chē)輛的行駛路線一致,1號(hào)和3號(hào)車(chē)輛的行駛路線稍有差別,配送成本也是各不相同。其中,各方案中單位車(chē)輛的行駛路線及配送成本見(jiàn)表6,圖9也直觀地展示了4種方案的細(xì)微差別。對(duì)照?qǐng)D表,并結(jié)合相關(guān)實(shí)驗(yàn)數(shù)據(jù)綜合性地研究和分析,ACO算法在第32代繪制出最佳配送方案,如圖5(a)所示。表6顯示了該算法中1號(hào)車(chē)輛的行駛路線為:0-20-16-14-13-12-0,該車(chē)輛在遍歷完20號(hào)、16號(hào)分店后轉(zhuǎn)向14號(hào)分店,直接違背了公理“兩點(diǎn)之間線段最短”,由此可以判定該路線不是最優(yōu)的。此外,從圖5(b)可以看出,該算法在第5代的配送成本幾乎接近4710,有突破瓶頸的跡象,然而卻沒(méi)能穩(wěn)定于這一點(diǎn),而且算法長(zhǎng)期處于動(dòng)蕩搜索狀態(tài),最終歸攏于4758,說(shuō)明該算法具有一定的提升空間;AACO算法和DACO算法分別在第29代和第31代繪制出最佳配送方案,如圖6(a)和圖7(a)所示。對(duì)比這兩種配送方案,清晰地看到兩者之間僅3號(hào)車(chē)輛的行駛路線略有不同,但總的配送成本卻相差15,這項(xiàng)差值充分說(shuō)明DACO算法中3號(hào)車(chē)輛的行駛路線是可取的。從圖6(b)可得知,AACO算法同比ACO算法在收斂代數(shù)上縮短了9.68%,并降低了0.69%的配送成本。圖7(b)清楚顯示DACO算法在第20代有陷入局部困境的跡象,但信息素強(qiáng)度區(qū)間性設(shè)置引導(dǎo)群體在第30代及時(shí)逃離困境構(gòu)造新的解,并且配送成本最終降低并穩(wěn)定于4710;圖8顯示ADACO算法的最佳配送方案于第27代繪制完畢,同圖7(a)相比,兩者僅1號(hào)車(chē)輛的行駛路線不同,然而對(duì)應(yīng)的配送成本卻迅速降低到4674,而且也不存在交叉或ACO算法中1號(hào)車(chē)輛的繞路現(xiàn)象,由此可判斷ADACO算法1號(hào)車(chē)輛的配送路線為最佳路線。此外,ADACO算法中3號(hào)車(chē)輛的行駛路線與DACO算法相同,均為可取路線。
圖5 ACO算法規(guī)劃的配送路線及配送成本
圖6 AACO算法規(guī)劃的配送路線及配送成本
圖7 DACO算法規(guī)劃的配送路線及配送成本
圖8 ADACO算法規(guī)劃的配送路線及配送成本
表6 單位車(chē)輛具體配送方案及配送成本
圖9 4種算法單位車(chē)輛的配送成本
綜上所述,AACO算法和DACO算法較于原有算法在時(shí)間效率和配送成本方面均有小幅度提升,然而卻遠(yuǎn)遠(yuǎn)不夠。通過(guò)將兩種改進(jìn)方法進(jìn)行有效結(jié)合,吸收兩者優(yōu)點(diǎn)得到ADACO算法,而且ADACO算法也展示了具有突破性進(jìn)展的優(yōu)化效果以及全面的提升能力。由此可見(jiàn),ADACO算法在求解車(chē)輛路徑問(wèn)題上更具高效性。
針對(duì)原有算法求解車(chē)輛路徑問(wèn)題時(shí)的不足,本文在初始時(shí)刻對(duì)關(guān)鍵參數(shù)采用試湊法設(shè)定,保證群體充分利用有效信息。迭代初期引入時(shí)變參數(shù),并在擇徑之前產(chǎn)生一個(gè)隨機(jī)數(shù)與之比較,使得群體按照既定的偽隨機(jī)自適應(yīng)規(guī)則選擇轉(zhuǎn)移方向。當(dāng)算法狀態(tài)持久不變時(shí),信息素強(qiáng)度的分段化有效誘導(dǎo)群體跳脫困境繼續(xù)探索。最后基于測(cè)試案例對(duì)優(yōu)化前后的算法進(jìn)行多次仿真,結(jié)果表明所提算法規(guī)劃的配送方案最優(yōu),大幅度縮減了配送成本和時(shí)間開(kāi)銷(xiāo)。本文算法適用于以菜鳥(niǎo)驛站為代表的物流業(yè)務(wù),為了滿足多元化需求,派送和拾取同步進(jìn)行且增加時(shí)間窗的服務(wù)將作為下一步的研究方向。