基于FA-IACS算法的車輛路徑問(wèn)題優(yōu)化*

劉巍巍， 孫宇彤， 安小宇， 高鑫禹， 孫晨曦

(1. 沈陽(yáng)工業(yè)大學(xué) 機(jī)械工程學(xué)院， 沈陽(yáng) 110870； 2. 鄭州輕工業(yè)大學(xué) 電氣信息工程學(xué)院， 鄭州 450002)

車輛路徑問(wèn)題(vehicle routing problem，VRP)是Dantzing和Razmer在1959年提出的一個(gè)典型NP難問(wèn)題[1]，一般通過(guò)啟發(fā)式算法和精確算法來(lái)進(jìn)行求解.啟發(fā)式算法具有效率高、求解精度高的特點(diǎn)，相比之下，精確算法效率較低且通常只有在問(wèn)題規(guī)模較小時(shí)才能獲得精確解.現(xiàn)如今，學(xué)者們的研究重點(diǎn)主要放在啟發(fā)式算法上，包括蟻群算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)算法、粒子群算法、模擬退火算法等.蟻群算法具有在解決車輛路徑問(wèn)題方面較強(qiáng)的全局搜索能力和較大的算法改進(jìn)彈性優(yōu)勢(shì)，但傳統(tǒng)蟻群系統(tǒng)(ant colony system，ACS)算法在尋優(yōu)過(guò)程中存在過(guò)早收斂、容易陷入局部最優(yōu)，且收斂到全局最優(yōu)要花費(fèi)較長(zhǎng)時(shí)間等缺點(diǎn)[2].因此，探尋一種改進(jìn)的ACS算法，使其能夠同時(shí)提高VRP問(wèn)題的求解速度和求解質(zhì)量具有重要意義.

近年來(lái)，國(guó)內(nèi)外許多專家學(xué)者提出了不同的改進(jìn)方案以使蟻群算法更適配于VRP問(wèn)題.Kao等[3]針對(duì)蟻群算法求解VRP時(shí)信息素停滯問(wèn)題，混合蟻群算法和粒子群算法在蟻群算法中嵌入了信息素干擾的方法，提高了算法準(zhǔn)確性，但容易過(guò)早收斂；Huang等[4]為了避免蟻群算法陷入局部最優(yōu)，使用角運(yùn)動(dòng)改進(jìn)蟻群算法應(yīng)用于應(yīng)急服務(wù)救援車輛的路徑規(guī)劃，并進(jìn)一步使用經(jīng)典ACS的轉(zhuǎn)移概率選擇規(guī)則的路徑權(quán)重矩陣，以提高路徑搜索的準(zhǔn)確性，但該算法較為復(fù)雜且導(dǎo)致計(jì)算耗時(shí)較長(zhǎng)；胡立栓等[5]針對(duì)蟻群算法容易陷入局部最優(yōu)的問(wèn)題，引入局部迭代搜索方式使算法能保持解的多樣性，能夠跳出局部最優(yōu)，并用以求解VRP問(wèn)題.

本文針對(duì)蟻群算法的缺陷，提出了改進(jìn)蟻群系統(tǒng)算法(firefly algorithm and improved ant colony system algorithm，F(xiàn)A-IACS)，將蟻群算法的啟發(fā)函數(shù)因子進(jìn)行改進(jìn)，增強(qiáng)算法全局搜索速度；利用螢火蟲算法的搜索方式在探尋解空間方面具有多樣性這一特點(diǎn)，對(duì)螢火蟲算法(firefly algorithm，F(xiàn)A)的種群初始化等部分進(jìn)行改進(jìn)，提出了一種新的編碼方案來(lái)編碼螢火蟲的種群庫(kù).在算法最后加入信息素震蕩程序，保障算法的可靠性.所提出的算法具有更高的效率，且能有效地避免算法陷入局部最優(yōu).

1 問(wèn)題描述及數(shù)學(xué)模型的建立

VRP問(wèn)題的基本約束模型，即有容量約束的車輛路徑優(yōu)化問(wèn)題(capacitated vehicle routing problem，CVRP)，由一組具有非負(fù)需求的節(jié)點(diǎn)和一個(gè)擁有車隊(duì)的中央倉(cāng)庫(kù)組成[6-7]，可以表示為G={V，E}.其中，頂點(diǎn)集V={v0，v1，…，vn}由中央倉(cāng)庫(kù)v0、n個(gè)顧客v1，v2，…，vn以及對(duì)稱邊集E={(vi，vj)vi，vj∈V}組成.由于CVRP問(wèn)題需要考慮配送中心數(shù)量和車輛型號(hào)等很多因素[8]，為了便于研究，本文做出以下基本假設(shè)：1)所使用的車輛皆為具有已知容量Q的相同車輛；2)所有車輛以相同的恒定速度行駛；3)節(jié)點(diǎn)需求量已知；4)每個(gè)節(jié)點(diǎn)都有且僅有一輛車；5)每個(gè)節(jié)點(diǎn)的需求量不能超過(guò)車輛的配送容量.

目標(biāo)函數(shù)是在滿足車輛凈需求和容量限制的同時(shí)，通過(guò)使用最少數(shù)量的車輛來(lái)求解最小行駛總距離.求解最小行駛總距離可表示為minZ.數(shù)學(xué)模型可表示為

(1)

確保每輛車的最大載重量必須在車輛的限制(容量)范圍內(nèi)，其約束條件表達(dá)式為

(2)

式中：di為第i個(gè)節(jié)點(diǎn)的貨物需求；Q為車輛的最大容量限制，為一個(gè)常數(shù).

確保距離和使用時(shí)間不能超過(guò)車輛的最大允許距離，其約束條件表達(dá)式為

(3)

式中：tij為從節(jié)點(diǎn)i到節(jié)點(diǎn)j的運(yùn)輸時(shí)間；si為節(jié)點(diǎn)i的服務(wù)時(shí)間；T為車輛返回時(shí)間限制.

保證所有路徑為閉合回路，即車輛由配送中心出發(fā)，回到配送中心，其約束條件表達(dá)式為

(4)

保證最多允許K條路線，其約束條件表達(dá)式為

(5)

如果車輛由節(jié)點(diǎn)i到節(jié)點(diǎn)j，則Xij為1，否則為0，其約束條件表達(dá)式為

(6)

2 FA-IACS算法設(shè)計(jì)

2.1 算法步驟

FA-IACS算法先進(jìn)行初始化，并啟動(dòng)算法，對(duì)狀態(tài)轉(zhuǎn)移概率進(jìn)行改進(jìn)選擇下一節(jié)點(diǎn)，直至客戶集為空，進(jìn)行螢火蟲搜索，對(duì)螢火蟲的編碼方式進(jìn)行改進(jìn)，然后對(duì)信息素進(jìn)行更新，在最小迭代次數(shù)時(shí)進(jìn)行判斷路徑是否有優(yōu)化，無(wú)優(yōu)化則進(jìn)行信息素震蕩，否則，則繼續(xù)算法迭代.算法流程如圖1所示.

圖1 FA-IACS算法流程Fig.1 Flow chart of FA-IACS algorithm

2.2 算法過(guò)程

算法運(yùn)行前參數(shù)設(shè)定包括：蟻群算法的迭代次數(shù)Nc，最大迭代次數(shù)Ncmax，最小迭代次數(shù)Ncmin，當(dāng)前最優(yōu)解Gbest.

1) 啟動(dòng)算法

將“m”螞蟻放在倉(cāng)庫(kù)中.設(shè)置Nc=1、Gbest=∞.對(duì)距離啟發(fā)函數(shù)因子進(jìn)行改進(jìn).

傳統(tǒng)蟻群算法多采用當(dāng)前節(jié)點(diǎn)i和下一節(jié)點(diǎn)j之間歐幾里得距離的倒數(shù)作為啟發(fā)函數(shù)因子，這種啟發(fā)函數(shù)因子只是考慮了此刻節(jié)點(diǎn)與下一節(jié)點(diǎn)，而忽略了節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)之間的關(guān)系，因此會(huì)造成盲目路徑搜索，致使搜索效率低和時(shí)間長(zhǎng)等問(wèn)題[9].在本文中，對(duì)啟發(fā)式函數(shù)因子進(jìn)行改進(jìn).將距離啟發(fā)函數(shù)因子更改為下一個(gè)節(jié)點(diǎn)j和目標(biāo)節(jié)點(diǎn)z之間的歐幾里德距離的倒數(shù).改進(jìn)后螞蟻路徑搜索的過(guò)程中各節(jié)點(diǎn)距離目標(biāo)節(jié)點(diǎn)越近，二者期望值越小，當(dāng)當(dāng)前節(jié)點(diǎn)可選擇的下一節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)距離更近時(shí)，則期望值越大，其被選中的概率越大.這將有利于改進(jìn)螞蟻盲目搜索這一缺點(diǎn)，增強(qiáng)算法全局搜索能力和算法收斂速度.

改進(jìn)的啟發(fā)式函數(shù)因子表達(dá)式為

(7)

ηjz=1/d(j，z)

(8)

式中：j、z兩點(diǎn)的坐標(biāo)分別為(xj，yj)和(xz，yz)；d(j，z)為節(jié)點(diǎn)(j，z)的歐幾里得距離.

2) 尋找路徑

(9)

根據(jù)式(10)選擇下一個(gè)要訪問(wèn)的節(jié)點(diǎn)，即

(10)

式中：τij為螞蟻k在路徑(i，j)上所釋放的信息素含量；a為螞蟻信息素啟發(fā)因子，表示軌跡相對(duì)重要程度的參數(shù)；b為節(jié)點(diǎn)(i，j)間的轉(zhuǎn)移期望啟發(fā)因子，表示能見(jiàn)度的相對(duì)重要度的參數(shù).每只螞蟻附帶清空表，每到達(dá)一個(gè)節(jié)點(diǎn)則清空客戶集中該節(jié)點(diǎn)數(shù)據(jù)，當(dāng)客戶集為空時(shí)，則螞蟻已訪問(wèn)過(guò)所有節(jié)點(diǎn)[10-11]，判斷是否違反了車輛的容量限制，如果違反了則返回到倉(cāng)庫(kù)，并且開(kāi)始規(guī)劃新路線，如果沒(méi)有則進(jìn)行下一步驟.

3) 螢火蟲搜索未開(kāi)發(fā)解空間

蟻群算法中的蟻群會(huì)遵循信息素濃度，尋找信息素濃度較高的路徑，導(dǎo)致ACS陷入局部最佳狀態(tài)[12-14].因此，應(yīng)用FA算法來(lái)搜索較少探索的其他有可能的區(qū)域.

由蟻群算法產(chǎn)生的“m”個(gè)解可以視為螢火蟲的數(shù)量“m”.由于CVRP是最小化目標(biāo)問(wèn)題，因此，每個(gè)螢火蟲的光強(qiáng)度設(shè)定為等于目標(biāo)函數(shù)值的倒數(shù).

根據(jù)光強(qiáng)度對(duì)“m”螢火蟲進(jìn)行分類.具有最小目標(biāo)函數(shù)值的螢火蟲即是最好的螢火蟲，其他螢火蟲對(duì)最佳螢火蟲的吸引度β可視為光強(qiáng)度函數(shù)，其表達(dá)式為

(11)

式中：β為螢火蟲之間的吸引度，吸引度與觀察螢火蟲所看到的光線成比例；β0為在r=0處的吸引度，r為螢火蟲與光源的距離；rij為兩個(gè)螢火蟲之間的距離；γ為光吸收系數(shù).螢火蟲i向螢火蟲j的運(yùn)動(dòng)xi可表示為

(12)

螢火蟲的運(yùn)動(dòng)通過(guò)式(12)中給出的吸引度β和隨機(jī)移動(dòng)α的函數(shù)進(jìn)行控制，α∈[0，1].

為了使FA適應(yīng)離散優(yōu)化問(wèn)題，提出了一種新的方案來(lái)編碼螢火蟲.螢火蟲編碼為節(jié)點(diǎn)集合，F(xiàn)A指數(shù)代表節(jié)點(diǎn)訪問(wèn)序列號(hào).“0”標(biāo)志著新路線的開(kāi)始，最后一個(gè)“0”表示整個(gè)過(guò)程的結(jié)束.以十節(jié)點(diǎn)為例，螢火蟲編碼方式如表1所示.

表1 螢火蟲編碼方式Tab.1 Firefly coding modes

定義兩個(gè)螢火蟲之間的距離rij為兩個(gè)螢火蟲之間由不同節(jié)點(diǎn)鏈接的鏈路總和，則表1中的rij為3(鏈路4-9，5-6以及6-7).

4) 返回到蟻群算法

在由FA搜索出的m解中，選擇具有最小目標(biāo)函數(shù)值的螞蟻?zhàn)鳛樽顑?yōu)解，即Gbest.

5) 信息素更新

通過(guò)FA搜索出的最佳解決方案m用于更新Gbest和螞蟻選擇的最佳路徑上的信息素濃度.螞蟻可以在最佳路徑上沉積信息素，用來(lái)引導(dǎo)后來(lái)的螞蟻進(jìn)行搜尋[15].此外，為了模仿天然螞蟻，隨著時(shí)間的推移，一些信息素會(huì)隨之蒸發(fā).因此，更新的信息素濃度τ′，其表達(dá)式為

(13)

(14)

在最佳路徑方案中存放的額外信息素為

(15)

式中，ξ為尾隨的螞蟻數(shù)量.

6) 信息素震蕩程序

判斷最小迭代次數(shù)Ncmin次迭代后路徑是否有優(yōu)化，如果迭代中沒(méi)有改進(jìn)路線，為了克服停滯不前的問(wèn)題，提出了震蕩程序以解決局部最優(yōu)的問(wèn)題.

震蕩程序設(shè)置為更新邊緣的信息素濃度，而不是更新解決方案中字符串，因?yàn)楦伦址赡軙?huì)導(dǎo)致解決方案變?yōu)椴豢尚薪?震蕩程序能夠使螞蟻探索新路線并避免選擇相同的重復(fù)邊緣.

7) 輸出Gbest并停止.

3 仿真及結(jié)果分析

3.1 參數(shù)選取

為了全面驗(yàn)證所提出的FA-IACS算法的有效性，本文針對(duì)小規(guī)模標(biāo)準(zhǔn)算例1及大規(guī)模標(biāo)準(zhǔn)算例2兩個(gè)案例問(wèn)題進(jìn)行了測(cè)試，將FA-IACS算法與標(biāo)準(zhǔn)ACS算法以及文獻(xiàn)[5]中的改進(jìn)蟻群算法(improved ant colony algorithm，IACA)組成了一個(gè)對(duì)比仿真實(shí)驗(yàn).小規(guī)模標(biāo)準(zhǔn)算例1取自國(guó)際VRP算例庫(kù)中經(jīng)典案例，大規(guī)模標(biāo)準(zhǔn)算例2選取CVRP Set CMT算例集中的5個(gè)算例.仿真設(shè)備CPU為Intel Core 2 Duo CPU T6400 2.00 GHz 2 GHz，操作系統(tǒng)為Windows7旗艦版，開(kāi)發(fā)環(huán)境為Matlab2014a.q0、a、b和ρ等參數(shù)值取自文獻(xiàn)[16]，參數(shù)取值如表2所示.

表2 仿真參數(shù)Tab.2 Simulation parameters

3.2 小規(guī)模標(biāo)準(zhǔn)算例1

為了更好地比較算法之間性能，本文采用國(guó)際VRP算例庫(kù)中經(jīng)典案例中的E_n22_k4，E_n30_k3，E_n33_k4，E_n51_k5進(jìn)行測(cè)試，時(shí)間單位為秒，仿真結(jié)果如表3所示.從表3中可以看出，F(xiàn)A-IACS算法在標(biāo)準(zhǔn)案例中算法仍具有較高的精度，對(duì)近似最優(yōu)解的偏差率更低，準(zhǔn)確性更高；而計(jì)算時(shí)間上該算法也大幅度地縮短了小規(guī)模案例計(jì)算時(shí)間，如算例E_n22_k4，本算法計(jì)算時(shí)間為15.45 s，與ACS的90.45 s，以及IACA算法的60 s相比具有更快的速度，證明了本文算法的高效性.圖2為算例E_n22_k4中三種算法計(jì)算100次目標(biāo)值的變化情況.從圖2中可以看出，ACS算法得出的目標(biāo)值較高，且穩(wěn)定性較差，所得結(jié)果波動(dòng)性較強(qiáng)，而本文算法目標(biāo)值最低，且穩(wěn)定性更好，波動(dòng)幅度更低.

表3 標(biāo)準(zhǔn)算例1仿真結(jié)果分析Tab.3 Analysis of simulation results for standard examples 1

圖2 E_n22_k4算例三種算法目標(biāo)值對(duì)比Fig.2 Comparison of target values for E_n22_k4 example obtained with three algorithms

3.3 大規(guī)模標(biāo)準(zhǔn)算例2

為了驗(yàn)證本文所用算法在求解大規(guī)模VRP問(wèn)題時(shí)的表現(xiàn)，選用選取CVRP Set CMT算例集中的5個(gè)算例.在查閱大量VRP問(wèn)題研究后，發(fā)現(xiàn)大多文獻(xiàn)所采用的問(wèn)題規(guī)模屬于小規(guī)模案例，并不能完全驗(yàn)證算法的有效性.因此，本實(shí)驗(yàn)選取具有較大規(guī)模節(jié)點(diǎn)的標(biāo)準(zhǔn)算例進(jìn)行測(cè)試.實(shí)驗(yàn)結(jié)果如表4所示，時(shí)間單位為秒.從實(shí)驗(yàn)結(jié)果可以看出，本文算法在大規(guī)模案例中偏差率更低，最高偏差率僅為0.02%，計(jì)算時(shí)間也明顯優(yōu)于其他兩種算法.

表4 標(biāo)準(zhǔn)算例2仿真結(jié)果分析Tab.4 Analysis of simulation results for standard examples 2

4 結(jié) 論

本文構(gòu)建了一個(gè)可以更加有效求解VRP問(wèn)題的FA-IACS算法，改進(jìn)蟻群系統(tǒng)算法的狀態(tài)轉(zhuǎn)移概率，將蟻群系統(tǒng)算法與螢火蟲算法的搜索機(jī)制相結(jié)合，改進(jìn)螢火蟲編碼方式和距離測(cè)量技術(shù)，同時(shí)將螞蟻路線上的信息素交換過(guò)程作為信息素震蕩方案，使算法可靠性更高.通過(guò)小規(guī)模仿真實(shí)驗(yàn)可以看出，本文算法在解決方案質(zhì)量和收斂速度方面要優(yōu)于其他兩種算法，通過(guò)大規(guī)模仿真實(shí)驗(yàn)可以看出，F(xiàn)A-IACS算法在大規(guī)模案例中表現(xiàn)也十分優(yōu)秀.實(shí)驗(yàn)結(jié)果表明，本文算法在搜尋全局最優(yōu)解、穩(wěn)定性和收斂性上具有一定的優(yōu)勢(shì).由于本文算法的參數(shù)是根據(jù)相關(guān)文獻(xiàn)的經(jīng)驗(yàn)值及實(shí)驗(yàn)測(cè)試值來(lái)確定的，采用單組參數(shù)對(duì)不同規(guī)模算例進(jìn)行求解，對(duì)路徑的隨機(jī)性選擇會(huì)產(chǎn)生一定的影響.