鄧會馨, 武俊麗

(佳木斯大學(xué)信息電子技術(shù)學(xué)院,黑龍江 佳木斯 154007)

0 引 言

近年來,隨著公路和鐵路交通運輸?shù)母咚侔l(fā)展,配送運輸行業(yè)也隨之迅猛發(fā)展。汽車配送運輸面臨著城市交通路線復(fù)雜、配送用戶多,危險品安全裝卸等問題,例如成品油二次配送問題[1],因此保持車輛運輸成本耗費的最小化是很重要的。配送問題可以簡化為車輛路徑優(yōu)化問題,即在一定約束條件下通過調(diào)度可用車輛為配送節(jié)點提供高效的服務(wù)。因此,研究優(yōu)化配送車輛路徑問題,在降低配送成本和提升用戶滿意度等方面具有重要理論意義和現(xiàn)實意義。車輛路徑問題自提出以來就得到了國內(nèi)外研究者們的廣泛關(guān)注,展開了大量深入研究。精確式算法是一類可獲得具體問題的最優(yōu)解的精確方案[2],但隨著問題規(guī)模的擴大,求解時所需的計算時間呈指數(shù)型增長。因此,許多學(xué)者采用啟發(fā)式算法以在一定時間范圍內(nèi)獲得較高質(zhì)量的近似解進行了廣泛研究。一類以“構(gòu)造”思想為代表的經(jīng)典啟發(fā)式算法[3-4]率先在車輛路徑優(yōu)化領(lǐng)域獲得應(yīng)用。該類算法的出現(xiàn)在一定程度上彌補了精確式算法在求解中大型規(guī)模的車輛路徑問題時的局限性。此外,一類根據(jù)優(yōu)化目標(biāo)在連續(xù)迭代中不斷更新個體結(jié)構(gòu)的元啟發(fā)式算法[5]逐漸成為近年來主流的解決方案。元啟發(fā)式算法包含但不限于蟻群優(yōu)化算法[6]、遺傳算法[7]以及粒子群算法[8]。其中,蟻群優(yōu)化算法借助其特有的正反饋、自組織、以及分布式機制等特點在路徑優(yōu)化領(lǐng)域得到了廣泛應(yīng)用。但收斂速度慢,全局尋優(yōu)能力不足,容易陷入局部最優(yōu)等不足仍然存在。文中,從避免早期盲目搜索、防止迭代后期搜索停滯以及提高算法收斂速度三方面對蟻群算法進行了綜合改進,以全面提高求解精度和搜索效率。研究基于上述的改進蟻群算法(improved ant colony algorithm, IACA),針對帶路徑約束、時間窗約束和容量約束的車輛路徑優(yōu)化問題,提出優(yōu)化以最小化配送車輛路徑總成本為目標(biāo)函數(shù)的算法。最后,基于Solomon基準(zhǔn)數(shù)據(jù)集[9]展開對比試驗進行該算法的高效性和實用性驗證。

1 問題描述

帶約束條件的車輛路徑問題可以描述為:假設(shè)車輛集合K(K={1,…,m})和節(jié)點集合V(V={0}∪V0) 已知,其中,配送中心用0表示,配送節(jié)點用V0(V0={1,…,n})表示。要求通過調(diào)度可用車輛規(guī)劃出一條能為一組已知分布情況和需求量的配送節(jié)點提供配送服務(wù)的路線。假設(shè)任意車輛都從配送中心出發(fā),完成若干配送節(jié)點的配送任務(wù)后返回配送中心;每段配送路線中所有配送節(jié)點的需求量之和不超過單個車輛的最大載重量;單個車輛可以服務(wù)多個配送節(jié)點,但每個配送節(jié)點能且僅能被服務(wù)一次且不允許拆分交貨;車輛對每個配送節(jié)點的配送服務(wù)必須在配送節(jié)點限制的時間窗范圍內(nèi)進行。車輛路徑的優(yōu)化目標(biāo)是使構(gòu)建的配送路線總行駛里程最短,運輸時間最少和配送成本最小。

考慮帶約束條件的車輛路徑問題的數(shù)學(xué)模型公式(1)所示:

同時滿足下列條件

(2)

(3)

(4)

(6)

(7)

(8)

(11)

2 改進的蟻群算法

為提高蟻群算法在帶約束條件的車輛路徑問題中的求解性能,從三方面對蟻群算法進行了改進:對參與條件轉(zhuǎn)移概率的候選節(jié)點列表進行預(yù)處理減少路線構(gòu)建過程計算的時間復(fù)雜度;提出插入式節(jié)約算法用于改進初始配送路線提高尋優(yōu)精度;改進信息素更新策略加快算法收斂速度。

2.1 狀態(tài)轉(zhuǎn)移概率

根據(jù)蟻群系統(tǒng)算法[6],當(dāng)車輛k位于位置i時對下一位將要訪問的配送節(jié)點s的選擇規(guī)則如下:

(12)

其中,τiu表示連接節(jié)點i到節(jié)點u的路徑中的信息素強度;ηiu表示螞蟻節(jié)點i轉(zhuǎn)移至節(jié)點u的期望值,與連接兩點的路徑長度呈反比;α,β(α,β>0)代表信息素啟發(fā)因子和期望啟發(fā)因子的相對強弱;allowedk表示能接受在節(jié)點i服務(wù)完成后被車輛k訪問的節(jié)點集合;q是[0,1]區(qū)間內(nèi)呈均勻分布的隨機數(shù);q0是介于(0,1)之間的一個常數(shù),它的大小決定了利用先驗知識與探索新路徑之間的相對重要性;S是根據(jù)公式(13)描述的轉(zhuǎn)移概率產(chǎn)生的候選節(jié)點。

(13)

其中,pijk(t)表示t時刻車輛k在結(jié)束對節(jié)點i的服務(wù)后選擇節(jié)點j作為下一個服務(wù)對象的概率,離螞蟻當(dāng)前位置較近或與當(dāng)前節(jié)點i相連路徑中信息素含量較高的節(jié)點被選擇的概率較大。

傳統(tǒng)蟻群算法對下一個節(jié)點選擇在所有尚未被服務(wù)的節(jié)點中進行,該過程的時間復(fù)雜度達到O(n2),收斂速度較慢。為減少搜索空間加快算法收斂速度,提出在節(jié)點轉(zhuǎn)移之前先利用公式(2)-(4)進行候選節(jié)點的篩選更新參與條件轉(zhuǎn)移計算的節(jié)點取值范圍。

篩選過程的主要步驟如下:

(1)輸入包含所有未訪問節(jié)點的集合V'0及現(xiàn)有路線R'。假設(shè)現(xiàn)有路線R'中最后訪問的節(jié)點是r1。

(2)對未訪問節(jié)點集合V'0進行遍歷,假設(shè)當(dāng)前未訪問節(jié)點是r2,根據(jù)公式(2)-(4)判斷能否將r2作為r1服務(wù)結(jié)束后下一個被訪問的節(jié)點。

(3)將步驟(2)中滿足不等式成立條件的節(jié)點存儲于候選節(jié)點列表allowedk。

(4)輸出候選節(jié)點列表allowedk,作為公式(12)-(13)中參數(shù)的取值范圍。

2.2 插入式節(jié)約算法

其中,num(Rk)是計算路段Rk的節(jié)點數(shù)量的函數(shù)。

(1)Type I類型插入Type II類型的算法

(15)

(2)Type II類型插入Type II類型的算法

假設(shè)執(zhí)行插入操作的對象是Type II類型的路段Rl和路段Rm,要求將路段Rl中所有配送節(jié)點插入路段Rm中,若在兩路段合并過程中存在不滿足公式(2)-(11)插入操作則代表插入失敗。

(16)

2.3 信息素更新策略

在所有螞蟻完成一次迭代搜索之后,需要更新所有路徑上的信息素。為明顯區(qū)分不同質(zhì)量的路徑以對后續(xù)蟻群的搜索方向提供指導(dǎo),基于全局信息素更新策略提出按公式(17)進行信息素更新,即僅最優(yōu)路線中的路徑能成功遺留新釋放的信息素。

τij(t+1)=(1-ρ)×τij(t)+Δτij

(17)

其中,τij(t)表示t時刻連接配送節(jié)點i與配送節(jié)點j的路徑上的信息素含量;ρ表示局部信息素?fù)]發(fā)因子,取值為區(qū)間為(0,1);Δτij表示螞蟻在連接配送節(jié)點i與配送節(jié)點j的路徑上釋放的信息素,如式(18)所示:

其中,Q表示信息素常量;Zbest代表最優(yōu)路線的總成本。

3 改進蟻群算法優(yōu)化車輛路徑問題的步驟

改進蟻群算法優(yōu)化車輛路徑問題的步驟如下所示:

步驟1種群初始化。設(shè)置最大迭代次數(shù)Iter,種群數(shù)量P,初始信息素濃度τ0,信息素?fù)]發(fā)因子ρ,啟發(fā)因子α,β,概率常數(shù)q0,信息素常量Q。初始化距離矩陣,信息素矩陣,設(shè)置全局最優(yōu)解Sglobal的配送路線為空,對應(yīng)的目標(biāo)值函數(shù)為一個極大值。

步驟2構(gòu)造螞蟻的初始配送路線。首先,根據(jù)2.1節(jié)提出的預(yù)處理確定候選節(jié)點范圍allowedk;其次,結(jié)合α,β,q0以及信息素矩陣,采用公式(12)確定當(dāng)前路段的下一個訪問節(jié)點s,直至完成所有配送節(jié)點的訪問或不存在可用車輛,得到一條配送路線R。

步驟3優(yōu)化螞蟻的配送路線R。首先,采用公式(15)將剩余節(jié)點插入已有路線;其次,采用公式(16)對存在合并條件的路段進行優(yōu)化;然后,按公式(1)計算新配送路線R′對應(yīng)的目標(biāo)函數(shù)值ZR′;最后,用配送列表S記錄所有螞蟻構(gòu)造的配送路線和對應(yīng)的目標(biāo)函數(shù)值。

步驟4整合配送列表S中的配送方案。將配送列表S中目標(biāo)函數(shù)值高于平均目標(biāo)函數(shù)值的配送路線刪除,并采用公式(16)對目標(biāo)值低于或等于平均目標(biāo)函數(shù)值的配送路線R′進行優(yōu)化得到R″;然后,按公式(1)計算當(dāng)前路線R″對應(yīng)的目標(biāo)函數(shù)值ZR″。

步驟5優(yōu)化配送列表S中的配送方案。若ZR″

步驟6更新全局最優(yōu)解Sglobal。若局部最優(yōu)解Slocal的目標(biāo)函數(shù)值小于全局最優(yōu)解Sglobal的目標(biāo)函數(shù)值,則用局部最優(yōu)解Slocal更新全局最優(yōu)解Sglobal。

步驟7全局信息素更新。結(jié)合ρ,Q以及全局最優(yōu)解Sglobal,按公式(17)提出的信息素更新策略進行全局信息素更新。

步驟8循環(huán)執(zhí)行步驟2～7,直至達到最大迭代次數(shù)Iter,輸出全局最優(yōu)解Sglobal。

4 算例測試與對比

采用Python 3.10編程語言測試,進行第3部分提出的改進蟻群算法(IACA)與改進的煙花算法(improved firework algorithm, IFA)算法[10]的對比實驗。實驗中IACA算法的各類參數(shù)設(shè)值如下:信息素?fù)]發(fā)因子ρ=0.2;信息素啟發(fā)因子α=4;期望啟發(fā)因子β=2;種群規(guī)模P=100;初始信息素τ0=10;信息素常量Q=10;迭代次數(shù)Iter=80;概率常數(shù)q0=0.2。表1從最優(yōu)路線花費的成本(Z)和使用的車輛數(shù)(N)兩方面對實驗結(jié)果進行了總結(jié),其中,Gap數(shù)值通過Gap=(IFA-IACA)/IACA×100%計算所得。

表1 IACA與IFA的實驗結(jié)果對比

由表1可知,IACA在C系列所有測試集中獲得的最優(yōu)路線的總成本均低于通過IFA獲得的結(jié)果。其中,在C202測試集中獲得了最大8.25%提升的最優(yōu)解,在C101測試集中獲得了最小1.98%的最優(yōu)解,平均較IFA的最優(yōu)解具有4.12%的提高。此外,IACA分別在50%的R系列測試集和60%的RC系列測試集中獲得了較IFA更低成本的最優(yōu)路線。其中,在R系列測試集中獲得的最大提升出現(xiàn)在R202測試集中;在RC系列測試集中獲得的最大提升出現(xiàn)在RC202測試集中。IACA能夠在眾多測試集中獲得更優(yōu)的結(jié)果,說明優(yōu)化階段提出的插入式節(jié)約算法具有提升種群多樣性和尋優(yōu)精度的效果;基于偽隨機比例的狀態(tài)轉(zhuǎn)移規(guī)則和精英化的信息素更新策略對于引導(dǎo)蟻群搜索和加快算法收斂具有有效性。

5 結(jié) 語

針對優(yōu)化帶約束條件的車輛路徑問題,提出了改進蟻群優(yōu)化算法,對待訪問節(jié)點列表采用預(yù)處理過程縮短蟻群路線構(gòu)建過程中的計算時間,針對剩余節(jié)點和已有路線設(shè)計的插入策略對指導(dǎo)后續(xù)蟻群搜索方向、提升可行解質(zhì)量方面具有積極作用。僅針對最優(yōu)路線的全局信息素更新方案避免了信息素的無限積累有助于提高算法收斂速度。通過與IFA算法進行最優(yōu)目標(biāo)值對比,驗證了針對蟻群算法提出的改進策略在提高求解精度和搜索效率方面具有有效性。未來將繼續(xù)探索該問題衍生問題的解決方案。