求解綠色車輛路徑問題的離散烏賊算法

劉 馨，張 強(qiáng)

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引 言

近年來世界各國倡導(dǎo)綠色發(fā)展，以降低能耗、減少碳排放為目標(biāo)的綠色車輛路徑問題(green vehicle routing problem，GVRP)已經(jīng)成為學(xué)術(shù)界研究的熱點(diǎn)。趙志學(xué)等[1]提出一種考慮交通擁堵區(qū)域的多車型物流配送綠色車輛路徑問題，設(shè)計(jì)一種混合差分進(jìn)化算法進(jìn)行求解；方文婷等[2]提出了一種混合蟻群算法，利用混合蟻群算法對建立的冷鏈物流路徑優(yōu)化數(shù)學(xué)模型進(jìn)行求解；劉長石等[3]建立了碳排放量最小為目標(biāo)的時(shí)變車輛路徑數(shù)學(xué)模型,設(shè)計(jì)一種改進(jìn)蟻群算法對問題進(jìn)行求解。

烏賊優(yōu)化算法(cuttlefish optimization algorithm，COA)是由Adel Sabry Eesa等[4]提出的一種新型的啟發(fā)式優(yōu)化算法。目前，許多研究者將COA算法應(yīng)用于不同的工程領(lǐng)域。舒緯偉等[5]將COA用于解決無人機(jī)航跡規(guī)劃問題，使得航跡規(guī)劃搜索范圍減少；Adel Sabry Eesa等在入侵檢測系統(tǒng)特征選擇過程中引入COA，得到具有更高準(zhǔn)確率的特征子集；錢洲元等[6]提出了一種自適應(yīng)COA，用于解決離線航跡規(guī)劃問題，提高了航跡規(guī)劃精度。在現(xiàn)階段的研究中，COA算法主要在連續(xù)性問題的應(yīng)用中取得了較好的成果，并且在求解問題數(shù)目較多且復(fù)雜時(shí)COA算法易陷入局部最優(yōu)。為了進(jìn)一步優(yōu)化COA的性能，本文提出了一種離散烏賊算法(discrete cuttlefish optimization algorithm，DCOA)，在DCOA中為提高初始細(xì)胞群的優(yōu)良性引入輪盤賭機(jī)制；此外，在全局搜索中引入基于精英片段的交叉策略，在局部搜索中引入2-opt法和shift法，進(jìn)一步強(qiáng)化算法的求解性能。最后通過仿真實(shí)驗(yàn)驗(yàn)證算法的改進(jìn)效果，并將DCOA在本文建立模型的求解結(jié)果與其它5種算法的求解結(jié)果進(jìn)行對比，DCOA取得了很好的尋優(yōu)效果。

1 綠色車輛路徑問題

1.1 問題描述

本文研究的GVRP可描述為：從一個(gè)配送中心出發(fā)的若干輛配送車對一定數(shù)量的顧客進(jìn)行配送服務(wù)，每輛配送車在服務(wù)完一條路徑上的全部客戶后都要返回到配送中心，通過對配送車輛和配送路徑的合理安排，使總目標(biāo)函數(shù)最小。為了便于分析和研究，做出如下假設(shè)：①從配送中心出發(fā)若干車型相同的配送車輛，在各自完成對配送路徑上所有客戶的配送任務(wù)后，需返回配送中心；②每輛配送車輛裝載的總貨物不得超過車輛的最大裝載限制；③每輛車可以對一條配送路徑上的多個(gè)客戶點(diǎn)進(jìn)行配送，但每條路徑上的客戶點(diǎn)只能由一輛配送車輛進(jìn)行配送服務(wù)；④每條配送路徑的總需求量小于等于配送車輛的最大承載量；⑤每條配送路徑中配送中心與各客戶點(diǎn)之間都是相互連通的，每個(gè)客戶點(diǎn)之間也是相互連通的道路。

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

(1)

(2)

(3)

s.t.

(4)

(5)

(6)

(7)

(8)

其中，目標(biāo)函數(shù)(1)為最小化車輛固定使用成本、燃油消耗成本F1和碳排放成本F2之和；約束條件(4)表示配送車輛從配送中心出發(fā)，依次為配送路徑上的每位客戶服務(wù)完后再返回配送中心；約束條件(5)保證每個(gè)客戶只能被一輛配送車輛服務(wù)一次；約束條件(6)、條件(7)保證配送路徑上各個(gè)客戶點(diǎn)之間是相互連通的，即配送車輛為客戶i進(jìn)行配送服務(wù)后，一定會從客戶點(diǎn)i離開前往下一個(gè)待服務(wù)的客戶點(diǎn)j； 約束條件(8)表示每輛配送車的最大載貨量不能超過該配送車的最大載重量Q。

2 求解GVRP的離散烏賊算法設(shè)計(jì)

2.1 離散烏賊算法原理

烏賊是一種生活在深海中的軟體動物，是水中的變色能手。其體內(nèi)聚集著數(shù)百萬個(gè)色素細(xì)胞，可以在極短的時(shí)間內(nèi)做出反應(yīng)調(diào)整身體顏色，以便適應(yīng)環(huán)境，逃避敵害。通過研究烏賊獨(dú)特的變色機(jī)制，Adel Sabry Eesa提出一種新型元啟發(fā)式算法，即COA算法，利用色素細(xì)胞(pigment cell)、虹彩細(xì)胞(iridophores)和白色素細(xì)胞(leucocyte)的共同協(xié)作來改變皮膚的顏色。該算法模擬烏賊皮膚細(xì)胞變色過程中的兩個(gè)主要進(jìn)程：反射(reflection)和可見(visibility)，反射進(jìn)程即細(xì)胞對光線的反射，可見進(jìn)程即烏賊可見度的匹配模式，這兩個(gè)進(jìn)程被用來作為全局最優(yōu)的搜索策略[7]。標(biāo)準(zhǔn)的烏賊算法主要用于對連續(xù)變量進(jìn)行優(yōu)化和求解，但是GVRP問題中涉及到的變量都是在空間中呈離散分布的。為了更好解決GVRP問題，本文提出一種離散烏賊算法。

2.2 算法個(gè)體編碼

在GVRP問題中配送中心與顧客節(jié)點(diǎn)均為分布在空間中的離散點(diǎn)，因此采用非負(fù)整數(shù)編碼。烏賊皮膚細(xì)胞位置按照規(guī)則與GVRP配送路徑上的客戶點(diǎn)是相互對應(yīng)關(guān)系。配送中心用0表示，顧客點(diǎn)為1,2,…,n。 由配送中心出發(fā)的配送車輛，一次對配送路徑上的客戶點(diǎn)服務(wù)后，需返回配送中心。例如由一個(gè)配送中心為10個(gè)客戶進(jìn)行配送，根據(jù)每輛車的裝載能力約束可得如 {0,2,5,7,10,0,1,4,6,0,3,8,9,0} 的解(圖1)，表示由3輛車進(jìn)行配送，3輛車的配送路徑分別 {0,2,5,7,10,0},{0,1,4,6,0},{0,3,8,9,0}。

圖1 配送路徑的結(jié)構(gòu)

2.3 初始解的構(gòu)造

初始細(xì)胞群個(gè)體對路徑節(jié)點(diǎn)的合理選擇，可以提高細(xì)胞群的整體質(zhì)量，本文為提高初始解的質(zhì)量保證初始解選擇的隨機(jī)性引入輪盤賭機(jī)制，保證各個(gè)點(diǎn)被選中的概率均等且被選中的概率與每個(gè)點(diǎn)的適應(yīng)度值成正比，同時(shí)不斷拓展和發(fā)現(xiàn)新的配送路徑，有效提高算法跳出局部最優(yōu)的能力。設(shè)dij為顧客i與j之間的距離，配送車輛規(guī)格相同，載重量為W， 具體操作如下：

步驟1 令配送中心0為起點(diǎn)，未加入路徑的客戶點(diǎn)集合為V， 隨機(jī)選取集合V中的一個(gè)客戶點(diǎn)加入已訪問路徑中，作為已訪問路徑的起點(diǎn)；

步驟3 隨機(jī)生成一個(gè)實(shí)數(shù)m∈[0,1]， 令m分別減去各待訪問客戶點(diǎn)被選擇的概率Pij， 當(dāng)m-Pij≤0時(shí)，判斷是否滿足車輛的容量約束，若是，則轉(zhuǎn)步驟4；否則轉(zhuǎn)步驟1[8]；

步驟4 在已訪問路徑中加入客戶點(diǎn)j， 重復(fù)步驟2～步驟3，直到集合V中所有的客戶點(diǎn)都加入已訪問路徑中。

2.4 烏賊細(xì)胞的位置更新

在GVRP中，烏賊細(xì)胞的每一維數(shù)值都是整數(shù)，在空間中都是離散型的編碼方式，原有的烏賊細(xì)胞位置更新方式不適用于組合優(yōu)化問題，所以這就需要重定義烏賊優(yōu)化算法中3種皮膚細(xì)胞的對光線的反射操作。

(1)更新方式選擇

在DCOA算法中，采用switch語句在 [1,2,3,4] 隨機(jī)選取一個(gè)數(shù)字，當(dāng)case1時(shí)，烏賊通過色素細(xì)胞和虹彩細(xì)胞協(xié)同作用對光線進(jìn)行反射；當(dāng)case2時(shí),烏賊通過虹彩細(xì)胞對光線進(jìn)行反射；當(dāng)case3時(shí)，烏賊對穿過色素細(xì)胞的光線進(jìn)行反射；當(dāng)case4時(shí)，烏賊通過白色素細(xì)胞對光線進(jìn)行反射。為了保持烏賊算法位置更新特點(diǎn)，定義case1和case4進(jìn)行全局搜索，case2和case3進(jìn)行局部搜索。

(2)全局搜索策略

在case1中使用swap法，主要通過在路徑間進(jìn)行搜索，具體方式為：在當(dāng)前配送方案中隨機(jī)選取兩條配送路徑，在兩條配送路徑中分別選取一個(gè)客戶點(diǎn)，對兩個(gè)客戶點(diǎn)的位置進(jìn)行交換后形成兩條新的配送路徑。如圖2所示，對隨機(jī)選出的客戶點(diǎn)i和j進(jìn)行交換后，形成了兩條新的配送路徑。

圖2 swap法

在case4中為防止種群多樣性的不足，采用基于精英片段的交叉策略，基本操作為：在精英個(gè)體R中隨機(jī)截取i、j之間的序列片段r，將序列片段r插入路徑方案W的尾部，同時(shí)將原路徑方案W中與序列片段r重復(fù)的元素刪除，得到基于精英的新路徑方案W′。 基于精英的交叉過程如圖3所示。

圖3 基于精英片段的交叉策略

(3)局部搜索策略

在case2中使用2-opt方法，進(jìn)行路徑內(nèi)搜索。首先用本文提出的初始化種群的方法隨機(jī)生成一個(gè)路徑方案，在該路徑方案中隨機(jī)選取一條路徑，在該路徑內(nèi)選取兩個(gè)客戶點(diǎn)i、j， 將i和j之間的客戶點(diǎn)相互交換位置，形成一條新的路徑。若新路徑的適應(yīng)度降低，則保留改變后的路徑。2-opt法的操作過程如圖4所示。

圖4 2-opt法

在case3中使用shift方法，進(jìn)行路徑間搜索。首先用本文提出的初始化種群的方法隨機(jī)生成一個(gè)路徑方案，在該路徑方案中隨機(jī)選取兩條路徑，分別在兩條路徑中選取兩個(gè)客戶點(diǎn)i、j， 交換i和j的位置形成兩條新的路徑。若新路徑的適應(yīng)度降低，則保留改變后的路徑。shift法的操作過程如圖5所示。

圖5 shift法

本文提出的DCOA算法主要分為3個(gè)階段：初始化種群階段，通過引入輪盤賭機(jī)制提高初始解的質(zhì)量和選擇的隨機(jī)性，保持發(fā)現(xiàn)新路徑的能力；全局搜索階段，通過swap法和基于精英片段的交叉策略，保留了進(jìn)化過程中的有利信息，避免尋優(yōu)的盲目性，有利于種群的全局進(jìn)化方向；局部搜索階段，通過2-opt和shift方法，增加了種群的多樣性，避免算法陷入局部最優(yōu)。所以DCOA理論上具有較好的全局搜索能力和局部尋優(yōu)能力。

2.5 離散烏賊算法具體流程

基于標(biāo)準(zhǔn)烏賊算法的更新方式，本文設(shè)計(jì)了更適合解決GVRP問題的離散烏賊算法。首先利用輪盤賭機(jī)制在搜索空間里隨機(jī)產(chǎn)生N個(gè)皮膚細(xì)胞，將細(xì)胞平均分為4組并計(jì)算出每個(gè)細(xì)胞的適應(yīng)度，保留最優(yōu)的細(xì)胞到下一代；其次按照4組細(xì)胞各自的更新方式，選出當(dāng)前最好的細(xì)胞；再次對更新后的細(xì)胞進(jìn)行評估，找出最佳細(xì)胞。這樣通過多次搜索和選擇后，烏賊可以選出最好的皮膚細(xì)胞，以保證適應(yīng)當(dāng)前環(huán)境。離散烏賊算法求解GVRP問題的流程如圖6所示。

圖6 離散烏賊算法求解GVRP問題的流程

3 實(shí)驗(yàn)與分析

為了驗(yàn)證本文所提離散烏賊算法DCOA在求解不同規(guī)模和類型問題的有效性，選取文獻(xiàn)[9-11]中使用的 Augerat 標(biāo)準(zhǔn)測試集進(jìn)行仿真實(shí)驗(yàn)，其中n后面的數(shù)字代表客戶總數(shù)，k后面的數(shù)字代表最大的車輛數(shù)目。DCOA具體參數(shù)設(shè)置：最大迭代次數(shù)G=1000， 種群數(shù)100。對每個(gè)問題獨(dú)立求解10次取平均值，并將DCOA與文獻(xiàn)[8]提出的自適應(yīng)遺傳灰狼優(yōu)化算法(adaptive genetic grey wolf optimizer algorithm，AGGWOA)和文獻(xiàn)[9]提出的變鄰域量子煙花算法(variable neighborhood quantum fireworks algorithm，VNQFWA)對各算例求解的結(jié)果進(jìn)行對比。利用MATLAB R2015a軟件進(jìn)行實(shí)驗(yàn)。表1為本文DCOA以及文獻(xiàn)[8]提出的自適應(yīng)遺傳灰狼優(yōu)化算法AGGWOA和文獻(xiàn)[9]提出的變鄰域量子煙花算法VNQFWA對算例求解的最優(yōu)總距離TD和最優(yōu)車輛數(shù)NV。

由表1可以看出，DCOA在求解A-n32-k5、A-n39-k6、A-n46-k7問題時(shí)結(jié)果均優(yōu)于AGGWOA和VNQFWA，在求解A-n36-k5、A-n37-k6、A-n45-k6、A-n54-k7、A-n60-k9問題時(shí)，求得的最優(yōu)總距離均優(yōu)于AGGWOA，在求解A-n44-k6時(shí)，求得的最優(yōu)總距離均優(yōu)于VNQFWA，在求解A-n33-k5、A-n33-k6、A-n34-k5、A-n37-k5時(shí)，相較于AGGWOA和VNQFWA的最優(yōu)總距離有所偏移，但是平均偏移率僅為1.08%。由此說明DCOA在求解不同類型和規(guī)模的CVRP問題時(shí)均有較好的性能。圖7～圖12為DCOA求解部分算例的最優(yōu)路徑圖。

圖7 A-n32-k5最優(yōu)路徑

圖8 A-n33-k5最優(yōu)路徑

圖9 A-n33-k6最優(yōu)路徑

圖10 A-n46-k7最優(yōu)路徑

圖11 A-n62-k8最優(yōu)路徑

圖12 A-n60-k9最優(yōu)路徑

表1 3種算法實(shí)驗(yàn)結(jié)果對比

為了進(jìn)一步驗(yàn)證本文所提DCOA在求解綠色車輛路徑問題的性能，本文分別用DCOA與模擬退火算法[12](simu-lated annealing，SA)、蝙蝠算法[13](bat algorithm，BA)、粒子群算法[14](particle swarm optimization，PSO)、布谷鳥算法[15](cuckoo search，CS)、蟻群算法[16](ant colony optimization，ACO)對本文建立的數(shù)學(xué)模型進(jìn)行求解。為簡化問題，假設(shè)配送車輛為同車型，其中Cf=6.02、Ce=86.35[17]、C=100、δ=2.73 (參考IPCC2006給定的柴油轉(zhuǎn)化系數(shù))，車速均為50 km/h。測試算例包括從32～62不同數(shù)量的客戶點(diǎn)和不同最大車輛數(shù)，對于每種測試算例，算法采用相同的參數(shù)設(shè)置，最大迭代次數(shù)G=1000，種群數(shù)100，每種算法獨(dú)立運(yùn)行10次，采用最優(yōu)總距離(TD)，最優(yōu)車輛數(shù)(NV)以及最小成本(BestCost)來評價(jià)算法的性能。實(shí)驗(yàn)結(jié)果見表2。

表2總結(jié)了6種算法優(yōu)化得到的最優(yōu)總距離TD、最優(yōu)車輛數(shù)NV和最小成本BestCost。由表2分析可知，在求解本文建立的綠色車輛路徑模型問題中，DCOA得到的優(yōu)化結(jié)果最好。在迭代過程中，DCOA算法引入基于精英片段的交叉策略，可以更好調(diào)控最優(yōu)個(gè)體與其它個(gè)體之間的距離，提高算法的全局搜索能力，更容易找到潛在的優(yōu)秀解；此外，隨著迭代次數(shù)的增加，DCOA通過2-opt法和shift法增強(qiáng)局部搜索能力，避免算法過早陷入局部最優(yōu)解，算法可以充分挖掘搜索空間。這里限于篇幅原因，僅列出6種算法在A-n34-k5、A-n45-k6、A-n60-k9這3種算例上運(yùn)行時(shí)的最小成本迭代圖，如圖13～圖15所示，可以看出DCOA的收斂速度始終優(yōu)于其它5種算法，并且在顧客數(shù)量逐漸增大時(shí)，DCOA的優(yōu)勢體現(xiàn)的更加明顯，可以更快找到總成本更低的最優(yōu)解。綜上所述，從模型求解結(jié)果驗(yàn)證來看，DCOA算法在求解大規(guī)模數(shù)據(jù)量的問題時(shí)，仍具有較好的尋優(yōu)能力，可以得到較優(yōu)的結(jié)果，提高車輛配送的經(jīng)濟(jì)效益。

表2 實(shí)驗(yàn)結(jié)果對比

圖13 A-n34-k5總成本迭代

圖14 A-n45-k6總成本迭代

圖15 A-n60-k9總成本迭代

4 結(jié)束語

本文針對GVRP問題的求解，首先建立了以最小化總成本為目標(biāo)的數(shù)學(xué)模型，然后將標(biāo)準(zhǔn)烏賊算法進(jìn)行離散化，提出了離散烏賊算法，利用輪盤賭機(jī)制建立初始細(xì)胞群，提高了細(xì)胞群的優(yōu)良性，重定義烏賊算法的細(xì)胞位置更新策略，并提取當(dāng)前最優(yōu)解的信息作為精英片段來指導(dǎo)細(xì)胞群向著有利的方向進(jìn)化。通過采用DCOA算法求解Augerat的16個(gè)算例，并比較DCOA與SA、BA、PSO、CS、ACO算法在求解GVRP時(shí)的計(jì)算結(jié)果，對比發(fā)現(xiàn)DCOA算法在求解GVRP時(shí)效果最好，并在A-n32-k5、A-n36-k5、A-n37-k6、A-n39-k6和A-n46-k7這5個(gè)算例中更新了當(dāng)前國際最優(yōu)解，有5個(gè)算例取得了當(dāng)前國際最優(yōu)解。下一步的研究目標(biāo)為進(jìn)一步改進(jìn)離散烏賊算法，以加強(qiáng)其在車輛路徑規(guī)劃問題上的應(yīng)用。