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

劉 馨，張 強

(東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318)

0 引 言

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

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

1 綠色車輛路徑問題

1.1 問題描述

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

1.2 數學模型

(1)

(2)

(3)

s.t.

(4)

(5)

(6)

(7)

(8)

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

2 求解GVRP的離散烏賊算法設計

2.1 離散烏賊算法原理

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

2.2 算法個體編碼

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

圖1 配送路徑的結構

2.3 初始解的構造

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

步驟1 令配送中心0為起點，未加入路徑的客戶點集合為V， 隨機選取集合V中的一個客戶點加入已訪問路徑中，作為已訪問路徑的起點；

步驟3 隨機生成一個實數m∈[0,1]， 令m分別減去各待訪問客戶點被選擇的概率Pij， 當m-Pij≤0時，判斷是否滿足車輛的容量約束，若是，則轉步驟4；否則轉步驟1[8]；

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

2.4 烏賊細胞的位置更新

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

(1)更新方式選擇

在DCOA算法中，采用switch語句在 [1,2,3,4] 隨機選取一個數字，當case1時，烏賊通過色素細胞和虹彩細胞協同作用對光線進行反射；當case2時,烏賊通過虹彩細胞對光線進行反射；當case3時，烏賊對穿過色素細胞的光線進行反射；當case4時，烏賊通過白色素細胞對光線進行反射。為了保持烏賊算法位置更新特點，定義case1和case4進行全局搜索，case2和case3進行局部搜索。

(2)全局搜索策略

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

圖2 swap法

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

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

(3)局部搜索策略

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

圖4 2-opt法

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

圖5 shift法

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

2.5 離散烏賊算法具體流程

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

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

3 實驗與分析

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

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

圖7 A-n32-k5最優路徑

圖8 A-n33-k5最優路徑

圖9 A-n33-k6最優路徑

圖10 A-n46-k7最優路徑

圖11 A-n62-k8最優路徑

圖12 A-n60-k9最優路徑

表1 3種算法實驗結果對比

為了進一步驗證本文所提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)對本文建立的數學模型進行求解。為簡化問題，假設配送車輛為同車型，其中Cf=6.02、Ce=86.35[17]、C=100、δ=2.73 (參考IPCC2006給定的柴油轉化系數)，車速均為50 km/h。測試算例包括從32～62不同數量的客戶點和不同最大車輛數，對于每種測試算例，算法采用相同的參數設置，最大迭代次數G=1000，種群數100，每種算法獨立運行10次，采用最優總距離(TD)，最優車輛數(NV)以及最小成本(BestCost)來評價算法的性能。實驗結果見表2。

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

表2 實驗結果對比

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

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

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

4 結束語

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