求解帶時(shí)間窗車(chē)輛路徑問(wèn)題的改進(jìn)型煙花算法

牛群，劉 軍

(蘭州理工大學(xué) 機(jī)電工程學(xué)院，甘肅 蘭州 730050)

0 引言

車(chē)輛路徑問(wèn)題(vehicle routing problem，VRP)由DANTZIG和RAMSER于1959年在研究卡車(chē)配送汽油行駛路徑問(wèn)題時(shí)提出。當(dāng)前VRP考慮實(shí)際生活中的約束，在基本VRP上增加客戶配送的時(shí)間窗要求，并提出帶時(shí)間窗車(chē)輛路徑問(wèn)題(vehicle routing problem with time windows，VRPTW)，更貼近實(shí)際情況。

VRP自提出以來(lái)就受到廣泛關(guān)注。EKSIOGLU總結(jié)出常用求解方法可分為解析算法和啟發(fā)式算法[1]。解析算法包括分支界定法、動(dòng)態(tài)規(guī)劃法等。由于VRP是NP-hard問(wèn)題[2]，計(jì)算時(shí)間會(huì)隨著客戶數(shù)增多呈指數(shù)級(jí)增長(zhǎng)，在實(shí)際應(yīng)用中受限。啟發(fā)式算法在可接受的計(jì)算成本內(nèi)能找到近優(yōu)解，使用迭代方式實(shí)現(xiàn)尋優(yōu)過(guò)程，通過(guò)反饋信息，根據(jù)搜索規(guī)則及時(shí)更新并縮小搜索范圍，當(dāng)解或迭代次數(shù)達(dá)到預(yù)設(shè)值時(shí)終止。目前啟發(fā)式算法分為構(gòu)造啟發(fā)式、改進(jìn)啟發(fā)式和元啟發(fā)式。

G. CLARK和J.R.WRIGHT[3]的經(jīng)典節(jié)約算法，GILLET[4]的高效掃描算法，SOLOMON[5]的插入啟發(fā)式、節(jié)約啟發(fā)式、鄰近啟發(fā)式等，都是根據(jù)相應(yīng)插入準(zhǔn)則，將客戶迭代地插入到當(dāng)前可行路徑中，直到所有客戶都被安排。構(gòu)造啟發(fā)式算法在解的質(zhì)量上存在差距。LIN[6]的2-OPT和3-OPT算法，在插入過(guò)程暫時(shí)接受不可行解，然后改進(jìn)使其可行。改進(jìn)啟發(fā)式在構(gòu)造啟發(fā)式的初始解的基礎(chǔ)上改進(jìn)，擴(kuò)大了初始解的搜索空間。改進(jìn)型啟發(fā)式算法易陷入局部最優(yōu)。為跳出局部最優(yōu)，對(duì)搜索空間多樣化探索，發(fā)展了遺傳算法[7]、蟻群優(yōu)化[8]和煙花算法[9]等算法。GILLETT[10]用自適應(yīng)文化基因算法來(lái)求解VRPTW，并與遺傳算法作了比較。

當(dāng)前煙花算法與其改進(jìn)算法已被廣泛應(yīng)用，例如油料作物施肥問(wèn)題與電力系統(tǒng)重構(gòu)問(wèn)題[11]等，但在VRPTW中應(yīng)用不多，本文將煙花算法用于求解VRPTW，為解決此類(lèi)問(wèn)題提供新思路。

1 帶時(shí)間窗的車(chē)輛路徑問(wèn)題

基于VRP相關(guān)理論的基本假設(shè)：1) 對(duì)客戶僅進(jìn)行送貨；2) 客戶需求量及時(shí)間窗一定；3) 每個(gè)客戶僅被一輛車(chē)服務(wù)一次；4) 給定配送中心及客戶位置；5) 車(chē)輛具有相同載重；6)車(chē)輛不得超過(guò)最大載重；7) 每個(gè)客戶在指定時(shí)間窗內(nèi)進(jìn)行，超過(guò)則不可行或加以懲罰；若早到需等待；8) 只有一個(gè)配送中心，車(chē)輛從配送中心出發(fā)并最終返回；9) 所有道路均暢通，不考慮突發(fā)情況。

VRPTW模型如下：用有向圖G=(C,E)定義，由客戶集C={0,1,2,…,n,n+1}和弧集E組成。節(jié)點(diǎn)0和n+1代表配送中心，其他n個(gè)頂點(diǎn)集合記為N。每個(gè)客戶i(i∈N)需求為di，服務(wù)時(shí)間為si和時(shí)間窗[ei，li]，ei和li分別代表最早和最晚開(kāi)始時(shí)間。假設(shè)車(chē)速=1，則行駛距離等于行駛時(shí)間。tij表示客戶i到客戶j(i,j∈N)的行駛距離；Cij代表車(chē)輛每條弧的成本。引入決策變量x和s，車(chē)輛k從客戶i行駛到客戶j(i≠j,i≠0,j≠n+1)，則決策變量xijk等于1，否則為0。決策變量sik表示車(chē)輛k開(kāi)始為客戶提供服務(wù)的時(shí)間。

(1)

約束條件：

(2)

(3)

(4)

(5)

(6)

(7)

sik+tij-(1-xijk)k=sjk,?jN,?iN,?kK

(8)

ei≤si≤li,?iN

(9)

目標(biāo)函數(shù)式(1)表示最小化配送總成本；式(2)為確保每輛車(chē)需求總和不超過(guò)其最大載重； 式(3)-式(6)表示保證每輛車(chē)從配送中心離開(kāi)，在服務(wù)完客戶后返回配送中心；式(7)表示保證每個(gè)客戶被一輛車(chē)服務(wù)一次；式(8)表示車(chē)輛從客戶i行駛到客戶j，不能在sik+tij之前到達(dá)客戶j；式(9)表示確保滿足所有時(shí)間窗。

2 求解VRPTW的改進(jìn)型煙花算法

譚營(yíng)在2010年提出煙花算法，通過(guò)模擬煙花爆炸行為建立相應(yīng)模型。其思路是將初始生成煙花看作解空間中部分可行解，煙花爆炸生成火花過(guò)程類(lèi)比為在原有煙花的鄰域搜索過(guò)程，爆炸半徑為相鄰煙花位置的選擇。通過(guò)煙花適應(yīng)度值的信息交互，煙花對(duì)應(yīng)的適應(yīng)度值大，則在較大范圍內(nèi)生成較少火花，擁有全局搜索能力；反之，適應(yīng)度值小，在較小范圍內(nèi)生成更多火花，具備更強(qiáng)局部搜索能力。

2.1 解決方案表示

在求解時(shí)，用一維向量表示解決方案，每一個(gè)數(shù)字代表一個(gè)客戶，解決方案的長(zhǎng)度代表客戶總數(shù)，路徑數(shù)量等于“0”的個(gè)數(shù)減1。在圖1中，第一條路徑有3個(gè)客戶，第2、第3條路徑都有2個(gè)客戶。

圖1 解決方案表示

2.2 適應(yīng)度評(píng)估函數(shù)

通過(guò)適應(yīng)度評(píng)估個(gè)體質(zhì)量?jī)?yōu)劣，因VRPTW是多目標(biāo)優(yōu)化問(wèn)題，所以用加權(quán)求和將其轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題。適應(yīng)度F(x)計(jì)算如下：

(10)

(11)

加權(quán)系數(shù)α和β分別是車(chē)輛數(shù)及行駛距離的權(quán)重參數(shù)。根據(jù)經(jīng)驗(yàn)確定為α=100，β=0.001。

2.3 爆炸產(chǎn)生火花數(shù)

對(duì)于每個(gè)煙火xi(對(duì)應(yīng)問(wèn)題解決方案)，生成火花數(shù)量需在爆炸之前計(jì)算。為使煙花差異化，根據(jù)適應(yīng)度值來(lái)控制爆炸產(chǎn)生火花數(shù)目。公式如下：

(12)

其中：Ni為第i個(gè)煙花的火花數(shù)量；M是限制火花數(shù)量常數(shù)；Ymax是當(dāng)前種群適應(yīng)度最大值；f(xi)是個(gè)體xi適應(yīng)度值；ε是避免分母為0的極小常數(shù)值；其中M為50，N為5。由于生成火花數(shù)是一個(gè)整數(shù)，因此通過(guò)式(13)將其轉(zhuǎn)換為整數(shù)，其中a為0.04，b為0.8。

(13)

2.4 爆炸操作

爆炸算子是將進(jìn)行爆炸的煙花與目前存在的煙花及最優(yōu)個(gè)體進(jìn)行交叉重組產(chǎn)生新的火花。用示例給出解釋?zhuān)簆1為等待爆炸煙花，p2代表所有煙花及火花中最優(yōu)個(gè)體。p1的3條路徑R1為4—8—2—9，R2為1—7和R3為3—5—6。步驟a)：從p1中選擇R2，p2中選擇R3。將給定個(gè)體在所選路徑中移除，在p1中移除5和9，產(chǎn)生C1。同樣，在p2中移除5和6，生成C2。步驟b)：將5和9重新插入到C1，同時(shí)將1和7重新插入到C2。首先插入哪個(gè)是隨機(jī)的，若插入之后路徑不滿足約束，則插入點(diǎn)不可行。步驟c)：5和9都被插入到C1中恰當(dāng)位置。若沒(méi)找到可行插入點(diǎn)，則建立一條新路徑?？蛻?沒(méi)有被插入到p2當(dāng)前路徑中，因此創(chuàng)建新路徑。爆炸操作示意如圖2所示。

圖2 爆炸操作示意圖

自適應(yīng)爆炸半徑核心是使用已產(chǎn)生火花來(lái)計(jì)算最優(yōu)煙花的爆炸半徑，通過(guò)這一代信息來(lái)計(jì)算下一代最優(yōu)煙花的半徑。自適應(yīng)半徑是一種全新的控制步長(zhǎng)方式，爆炸半徑是否具有自適應(yīng)能力對(duì)算法性能至關(guān)重要。公式如下：

(14)

自適應(yīng)半徑的計(jì)算，首先選擇一個(gè)個(gè)體，用它與最優(yōu)個(gè)體之間的距離作為下一次爆炸半徑。必須滿足條件：1) 適應(yīng)度值比這一代的煙花差；2) 到最優(yōu)個(gè)體的距離是滿足1) 的個(gè)體中最短的；3) 確保目標(biāo)函數(shù)至少比這一代進(jìn)步要大，在下一次爆炸中找到更好位置；4) 確保半徑收斂。雖然無(wú)法保證半徑每次都減小，但當(dāng)?shù)螖?shù)足夠大、火花數(shù)量足夠多時(shí)，還是收斂的。

將計(jì)算的自適應(yīng)半徑乘以特定系數(shù)λ=1.3(經(jīng)驗(yàn)值)以控制全局和局部搜索的平衡，A(g+1)←λ·A(g+1)，λ過(guò)小會(huì)過(guò)快收斂，λ過(guò)大將不會(huì)收斂。為減少火花數(shù)量有限的影響，采用簡(jiǎn)單平滑機(jī)制A(g+1)←0.5·[A(g)+A(g+1)] ，將計(jì)算的自適應(yīng)半徑和該代爆炸半徑的平均值作為下一代爆炸半徑。

2.5 變異操作

引入變異火花加強(qiáng)種群多樣性，變異算子主要作用是增強(qiáng)局部搜索能力，免于陷入局部最優(yōu)。在此采用高斯變異火花位置，計(jì)算如下：

(15)

其中g(shù)是服從均值為1、方差為1的高斯分布的隨機(jī)數(shù)。

2.6 選擇策略

用基于距離的選擇策略選出剩余N-1個(gè)個(gè)體組成下一代群體。算法的分布式信息共享機(jī)制，是基于免疫濃度思想的選擇，使煙花分布在不同區(qū)域不聚集來(lái)避免早熟。采用歐氏距離度量?jī)蓚€(gè)個(gè)體之間距離：

(16)

其中：d(xi，xj)表示任意兩個(gè)個(gè)體xi和xj之間的歐氏距離，R(xi)表示個(gè)體xi與其他個(gè)體的距離之和；K是由爆炸算子產(chǎn)生的火花位置和高斯變異產(chǎn)生的火花位置的集合。個(gè)體選擇采用輪盤(pán)賭的方式，個(gè)體被選中的概率p(xi)表示為：

(17)

得出個(gè)體距離更遠(yuǎn)的個(gè)體具有更多的機(jī)會(huì)成為下一代個(gè)體，此選擇方式保證了算法的種群多樣性。

3 實(shí)驗(yàn)結(jié)果與分析

通過(guò)對(duì)Solomon數(shù)據(jù)集的測(cè)試來(lái)驗(yàn)證改進(jìn)型煙花算法對(duì)VRPTW求解的適用性和有效性。此數(shù)據(jù)集包含100個(gè)客戶點(diǎn)，分為R1、R2、C1、C2、RC1和RC2 6個(gè)子類(lèi)。C類(lèi)在地理位置上是聚類(lèi)的，R類(lèi)是隨機(jī)的，RC是兩種情況的混合。對(duì)于R1、C1和RC1類(lèi)問(wèn)題，車(chē)輛載重小且時(shí)間窗緊，每輛車(chē)服務(wù)較少客戶；相反，R2、C2和RC2具有大載重和寬松時(shí)間窗，每輛車(chē)服務(wù)較多客戶。算法采用Matlab2014a編程，在Intel Core i5-3240MCPU@3.40GHz雙核處理器，操作系統(tǒng)為32位的Windows7環(huán)境下運(yùn)行。

用車(chē)輛數(shù)和行駛總里程評(píng)價(jià)最優(yōu)解，通常固定成本高于運(yùn)輸成本，因此最小化車(chē)輛數(shù)優(yōu)先級(jí)高于最小化行駛總里程，本文選取部分計(jì)算結(jié)果與已公布最優(yōu)解比較。表1和表2得到的距離改進(jìn)顯著，但以增加額外車(chē)輛為代價(jià)，如R103和RC102。在R2及RC2中，車(chē)輛數(shù)大多等于當(dāng)前最優(yōu)解，但行駛總里程得到很好優(yōu)化，如R204和RC207。算法的群體多樣性使得算法跳出局部極值收斂到全局最優(yōu)，另外自適應(yīng)半徑作為時(shí)變趨化步長(zhǎng)使得局部搜索與全局搜索達(dá)到適應(yīng)性平衡，在搜索時(shí)首先從有前途的鄰域開(kāi)展全局搜索，然后減慢開(kāi)展局部搜索，從而得到最優(yōu)解。

表3是IFWA的平均表現(xiàn)。通過(guò)比較表3、表1及表2，發(fā)現(xiàn)10次的平均結(jié)果與最優(yōu)解相差不大，且平均結(jié)果都在可接受范圍內(nèi)，說(shuō)明算法求解整體性能穩(wěn)定。對(duì)解質(zhì)量而言，使用該算法求解VRPTW具有可行性和有效性。在爆炸和變異算子作用下，根據(jù)煙花適應(yīng)度值產(chǎn)生不同個(gè)數(shù)的火花和不同的爆炸半徑，保證火花個(gè)數(shù)和爆炸半徑的多樣性；高斯變異保證爆炸的多樣性；通過(guò)選擇策略保留的煙花保證煙花的多樣性，以上群體多樣性的3個(gè)方面確保算法全局收斂。算法采用動(dòng)態(tài)信息策略，保證在每次搜索中每個(gè)煙花都對(duì)搜索作出貢獻(xiàn)，以達(dá)到快速尋優(yōu)。

表1 IFWA與硬時(shí)間窗最佳公布結(jié)果比較

表2 IFWA與軟時(shí)間窗最佳公布結(jié)果比較

表3 所羅門(mén)基準(zhǔn)下的IFWA平均表現(xiàn)

4 結(jié)語(yǔ)

通過(guò)模擬煙花爆炸行為，設(shè)計(jì)了一種改進(jìn)型煙花算法。求解帶時(shí)間窗車(chē)輛路徑問(wèn)題。在迭代過(guò)程中通過(guò)優(yōu)化控制策略對(duì)爆炸半徑提出改進(jìn)，使得爆炸半徑實(shí)現(xiàn)自適應(yīng)量化，有效提升算法的局部搜索能力。算法的分布式信息共享機(jī)制還避免了早熟。通過(guò)對(duì)測(cè)試算例與已知最優(yōu)解比較，表明改進(jìn)型煙花算法具有較好的求解精度，能夠有效處理帶時(shí)間窗車(chē)輛路徑問(wèn)題。

研究表明，改進(jìn)型煙花算法在VRPTW上的成功應(yīng)用拓寬了實(shí)際應(yīng)用領(lǐng)域，為求解實(shí)時(shí)動(dòng)態(tài)、復(fù)雜VRP問(wèn)題提供了新思路。在此基礎(chǔ)上，進(jìn)一步考慮實(shí)際生活中客戶需求的動(dòng)態(tài)變化、道路實(shí)際交通情況等影響因素，將會(huì)是下一步研究重點(diǎn)。