基于智能優(yōu)化算法的車輛路徑問題的研究與應(yīng)用

張亞龍 肖銀寶

摘要：在電子商務(wù)蓬勃發(fā)展的大環(huán)境下，物流行業(yè)已經(jīng)成為推動我國經(jīng)濟發(fā)展的重要力量，人們對物流配送的要求也越來越高，如何科學(xué)合理地規(guī)劃配送車輛的路線，實現(xiàn)高效率、低成本是當(dāng)前學(xué)者們研究的重點。物流配送遍及生產(chǎn)生活的方方面面，面對日益復(fù)雜的道路環(huán)境，隨著信息化水平的提升，這使得用智能計算推動物流配送模式革新有著重要意義。本文通過科學(xué)合理的方法對復(fù)雜的車輛路徑問題（VRP）的衍生問題，即帶時間窗的車輛路徑問題和同時取送貨的車輛路徑問題（VRPSPDTW）進行求解，主要通過對現(xiàn)有的鯨魚優(yōu)化算法進行研究，針對鯨魚算法求解問題后期種群多樣性缺失的問題，引入新的收斂因子、自適應(yīng)權(quán)重和Metropolis準則對其進行補足，將其應(yīng)用至實際問題中，驗證其可行性。

關(guān)鍵詞：智能計算；路徑規(guī)劃；鯨魚算法；VRP

1概述

隨著電子商務(wù)行業(yè)的強勁發(fā)展，物流行業(yè)逐漸成為推動我國經(jīng)濟發(fā)展的主要力量，物流配送的車輛路徑問題，越來越得到有關(guān)學(xué)者的重視，車輛路徑作為經(jīng)典的組合優(yōu)化問題一直是研究的熱點與難點。隨著信息技術(shù)的快速發(fā)展，計算機算力大幅提升，使得啟發(fā)式算法求解車輛路徑及其衍生問題更加科學(xué)合理。本文主要從車輛路徑問題的發(fā)展現(xiàn)狀，傳統(tǒng)鯨魚優(yōu)化算法方案的優(yōu)缺點，對其進行改進，來提高其運行效率。

2研究方案

WOA算法是一種群智能優(yōu)化算法，靈感來自海洋中座頭鯨獨有的氣泡網(wǎng)捕食方式。座頭鯨發(fā)現(xiàn)獵物后，通過制作氣泡網(wǎng)的方式，以形似螺旋的路徑進行捕食，其具體行為包括包圍捕食、螺旋更新位置及搜索獵物。鯨魚種群捕食過程中，通過最佳個體的位置來進行位置更新，最終收斂域最優(yōu)目標值附件，但經(jīng)典的鯨魚優(yōu)化算法存在有收斂性慢，算法后期迭代缺乏種群多樣性，易陷入局部最優(yōu)。本文在基本的鯨魚優(yōu)化算法上加以改進，通過采用新的收縮因子方法，較好地調(diào)節(jié)了全局和局部的搜索能力。引入自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。引入Metropolis準則，通過以一定的概率接受較差的點來提升全局尋優(yōu)能力，避免了算法陷入局部最優(yōu)解。

3傳統(tǒng)鯨魚優(yōu)化算法的實現(xiàn)

車輛路徑問題及其衍生問題一直是NPHard問題，其約束條件繁雜，在對其目標問題建模后，根據(jù)鯨魚優(yōu)化算法包括三種更新個體位置的方式，分別是氣泡攻擊、搜索捕食、包圍獵物，對問題進行求解。

當(dāng)鯨魚在包圍捕獲獵物時，首先要確定獵物位置，但是獵物在搜索空間中的位置往往是不確定的。鯨魚優(yōu)化算法將獵物位置或者接近目標獵物的位置作為當(dāng)前最優(yōu)候選解，其他鯨魚個體通過最優(yōu)候選解來更新自身所在的位置。

鯨魚優(yōu)化算法個體更新位置方式如下：

設(shè)p為［0，1］之間的隨機數(shù)，p是捕食機制概率，則：

若p0.5，則鯨魚個體采用氣泡攻擊方式以螺旋式形式進行個體位置更新，即當(dāng)前鯨魚個體以螺旋式的方式向當(dāng)前最佳鯨魚個體靠近。

氣泡攻擊方式下的鯨魚個體位置更新公式為：

Xi（t+1）=X（t）+Deblcos（2πl(wèi)）（1）

D=X（t）－Xi（t）（2）

其中，Xi（t+1）表示下一代第i只鯨魚的位置，X（t）表示當(dāng)前時刻全局最優(yōu)向量，即當(dāng)前最優(yōu)鯨魚個體位置，b為常數(shù)，定義了對數(shù)螺旋的形狀；l為［－1，1］的隨機數(shù)。D=X（t）－Xi（t）表示為第i只鯨魚個體的位置到當(dāng)前最優(yōu)鯨魚個體位置的距離。

若p<0.5且A1，則鯨魚個體采用搜索捕食方式進行個體位置更新，即鯨魚個體可能不向最佳鯨魚個體靠近，而是隨機選擇一只鯨魚個體靠近。

搜索捕食方式下得鯨魚個體位置更新公式為：

Xi（t+1）=Xrand（t）－A×D（3）

D=C×Xrand（t）－Xi（t）（4）

其中，假設(shè)在d維空間中，Xrand（t）表示為當(dāng)前鯨魚種群中隨機一只鯨魚個體的位置，D=C×Xrand（t）－Xi（t）表示為當(dāng)前種群中第i只鯨魚個體的位置到當(dāng)前種群中隨機一只鯨魚位置的距離，A=2a×r1－a，C=2×r2，其中，r1，r2為［0，1］之間的隨機數(shù)。

若p<0.5且A<1，則鯨魚個體采用包圍獵物的方式進行個體位置更新。

包圍獵物方式下得鯨魚個體位置更新公式為：

Xi（t+1）=X（t）－A×D（5）

D=C×X（t）－Xi（t）（6）

其中，D=C×X（t）－Xi（t）表示當(dāng)前種群中第i只鯨魚個體的位置到當(dāng)前最優(yōu)鯨魚個體位置距離，A=2a×r1－a，C=2×r2，其中，r1，r2為［0，1］之間的隨機數(shù)。

當(dāng)鯨魚算法訪問完所有的客戶，第一次迭代完成，每條鯨魚均找到了對應(yīng)的行駛路徑，相當(dāng)于車輛完成了一次運行，在達到最大迭代次數(shù)時，選取所有迭代次數(shù)中整體適應(yīng)度值最小的鯨魚所選的路徑，作為全局最優(yōu)路徑，總路徑最短的鯨魚為全局最優(yōu)解。

傳統(tǒng)鯨魚算法解決車輛路徑問題時會有兩個缺點：（1）根據(jù)鯨魚優(yōu)化算法三個位置更新公式，不難看出，位置更新是通過最優(yōu)個體的位置變動來更新此時鯨魚個體的位置，會造成種群多樣性的丟失，對于大規(guī)模問題算法初期，解的搜索具有盲目性。（2）經(jīng)典鯨魚優(yōu)化算法缺少擾動機制，存在算法后期收斂速度慢，易陷入局部最優(yōu)等缺陷。

4對傳統(tǒng)鯨魚算法的改進

鯨魚優(yōu)化算法是元啟發(fā)式群智能優(yōu)化算法，雖然有良好的啟發(fā)性，但存在著求解精度低、收斂速度慢、易陷入局部最優(yōu)解的情況。針對以上幾個缺陷做出以下改進：

（1）通過采用新的收縮因子方法，較好地調(diào)節(jié)了全局和局部的搜索能力。

（2）引入自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。

（3）引入Metropolis準則，通過以一定的概率接受較差的點來提升全局尋優(yōu)能力，避免了算法陷入局部最優(yōu)解。

4.1采用新的收縮因子

傳統(tǒng)的鯨魚優(yōu)化算法的收縮因子為線性收縮因子，a的值從2到0線性下降，其收斂速度較慢，導(dǎo)致搜索時間較長，降低了算法的效率，傳統(tǒng)的搜索因子公式為：

a=2－2tItermax（7）

本文通過采用非線性收縮因子的方法，較好地調(diào)節(jié)了算法的全局和局部搜索能力，新的收縮因子公式如下：

a=2－2sinμtItermaxπ+φ（8）

其中Itermax是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)，μ、φ是表達式的相關(guān)系數(shù)，為使收斂因子a滿足從2至0遞減，選取μ=1/2，φ=0；用新的收斂因子公式計算系數(shù)向量A，設(shè)r1，r2為［0，1］之間的隨機數(shù)，則A=2a×r1－a，系數(shù)向量C=2×r2。

4.2引入自適應(yīng)權(quán)重

通過鯨魚算法的所搜機制可知，位置更新是通過最優(yōu)個體的位置變動來更新此時鯨魚個體的位置，會造成種群多樣性的丟失，對于大規(guī)模問題算法初期，解的搜索具有盲目性。自適應(yīng)權(quán)重ω的公式如下：

ω=1－etItermax－1/e－1（9）

其中Itermax是最大迭代次數(shù)，t為當(dāng)前迭代次數(shù)。通過采用自適應(yīng)權(quán)重策略很好地保持了種群的多樣性，使算法的收斂性和搜索性提升。

4.3引入Metropolis準則

1953年，Metropolis提出重要性采樣方法，即以概率來接受新狀態(tài)，而不是使用完全確定的規(guī)則，稱為Metropolis準則。

假設(shè)前一狀態(tài)為X（n），系統(tǒng)受到一定擾動，狀態(tài)變?yōu)閄（n+1），相應(yīng)地，系統(tǒng)能量由E（n）變?yōu)镋（n+1），定義系統(tǒng)由X（n）變?yōu)閄（n+1）的接收概率為P，則P的概率計算公式為：

P=1，E（n+1）<E（n）

exp（－En+1－E（n）T），x0（10）

當(dāng)狀態(tài)轉(zhuǎn)移之后，如果能量減小了，那么這種轉(zhuǎn)移就被接受了。如果能量增大了，就說明系統(tǒng)偏離全局最優(yōu)位置更遠了，此時算法不會立即將其拋棄，而是進行概率判斷。首先在區(qū)間［0，1］產(chǎn)生一個均勻分布的隨機數(shù)ε，如果ε<P，這種轉(zhuǎn)移將被接受，否則拒絕轉(zhuǎn)移，進入下一步，如此循環(huán)。

其核心思想是當(dāng)能量增加時以一定概率接收，即陷入局部最優(yōu)時有一定概率能跳出局部最優(yōu)，其中以能量的變化量和T進行決定概率P的大小，所以P這個值是動態(tài)的。

經(jīng)典鯨魚優(yōu)化算法缺少擾動機制，存在算法后期收斂速度慢、易陷入局部最優(yōu)等缺陷。在更新鯨魚種群中的鯨魚個體后，根據(jù)Metropolis準則，以一定的概率接受劣質(zhì)個體。概率公式計算如下：

P1=e－fXit+1－fXi（t）/fXi（t）T（11）

其中，T為當(dāng)前迭代次數(shù)時的溫度，初始迭代溫度T0為100。fXi（t）為第i只鯨魚當(dāng)前迭代下的最優(yōu)路徑，fXi（t+1）是下一次迭代下第i只鯨魚的最優(yōu)路徑。每次迭代后的降溫公式為：T=αT，其中，α為降溫速率，設(shè)定為0.99。

4.4算法流程

下圖為改進的鯨魚優(yōu)化算法流程圖，整個算法對問題的求解過程分為以下步驟：

Step1初始化鯨魚算法的相關(guān)參數(shù)，包括種群規(guī)模N、當(dāng)前迭代次數(shù)t、最大迭代次數(shù)Itermax、初始溫度T0和降火速率系數(shù)α；

Step2構(gòu)建解空間，根據(jù)適應(yīng)度函數(shù)，計算鯨魚種群中的每個鯨魚個體的所在位置的適應(yīng)度值，確定初始種群中個體的最優(yōu)位置和種群全局最優(yōu)位置，初始個體適應(yīng)度值最小的對應(yīng)最優(yōu)位置，就是初始種群的全局最優(yōu)位置；

Step3采用非線性的方法計算收縮因子a，計算并更新鯨魚優(yōu)化算法系數(shù)向量A，C；

Step4引入自適應(yīng)權(quán)重ω，根據(jù)鯨魚個體更新公式、更新鯨魚種群中的所有鯨魚個體的位置，得到每只鯨魚的初始可行路徑；

Step5位置更新結(jié)束后，使用Metropolis準則更新種群；

Step6對Metropolis準則進行降溫，T=αT；

Step7判斷是否達到種群最大迭代次數(shù)Itermax，如果達到最大迭代次數(shù)，輸出最優(yōu)鯨魚個體位置，得到最優(yōu)鯨魚個體的可行路徑，計算結(jié)束，否則轉(zhuǎn)到Step3，重復(fù)執(zhí)行Step3至Step6，達到最大迭代次數(shù)時，輸出求解結(jié)果。

5分析總結(jié)

本課題主要是應(yīng)用鯨魚優(yōu)化算法，通過對其改進以便更好加快算法的收斂速度和求解精度，以此來更好地滿足實際應(yīng)用對效率和準確性的需求。

雖然創(chuàng)造性地從收縮因子方面及引入自適應(yīng)權(quán)重和Metropolis準則來改進鯨魚算法，但是僅從鯨魚種群多樣性和擾動機制上考慮是不夠的，在未來的研究中還需要進一步加深。

主要創(chuàng)新點：

（1）通過對傳統(tǒng)鯨魚算法的改進，提高其搜索性能，增加其擾動機制，并采用Metropolis準則來增強其跳出局部最優(yōu)的能力。

（2）優(yōu)化參數(shù)的選擇，提高其收斂性，提高算法運行效率，可更好地應(yīng)用于復(fù)雜問題。

參考文獻：

［1］唐彥，張進軍.基于改進的鯨魚優(yōu)化算法的物流車輛配送路徑規(guī)劃［J］.隴東學(xué)院學(xué)報，2021，32（05）：610.

［2］龐燕，羅華麗，邢立寧，等.車輛路徑優(yōu)化問題及求解方法研究綜述［J］.控制理論與應(yīng)用，2019（10）：15731584.

［3］楊博，李昌華，李智杰，等.改進鯨魚算法及其在路徑規(guī)劃的應(yīng)用［J］.計算機測量與控制，2021，29（02）：187193+201.

［4］余賢星.一種改進的多領(lǐng)導(dǎo)鯨魚優(yōu)化算法［J］.軟件工程，2022，25（11）：2834.

［5］楊柳，王潁超，侯漢坡.冷鏈低碳配送路徑優(yōu)化研究［J］.商業(yè)經(jīng)濟研究，2019（17）：104107.

［6］謝沖沖，李瑩.基于改進算法的移動機器人路徑規(guī)劃［J］.重慶大學(xué)學(xué)報，2021，44（12）：140148.

［7］陳榮，王雯陽，卞東東.基于鯨魚算法的循環(huán)取貨路徑優(yōu)化研究［J］.物流科技，2021，44（10）：2832.

［8］崔東文.鯨魚優(yōu)化算法在水庫優(yōu)化調(diào)度中的應(yīng)用［J］.水利水電科技進展，2017，37（03）：7276+94.

［9］高嘉，任亞明.基于模擬退火算法組合優(yōu)化問題的求解［J］.企業(yè)科技與發(fā)展，2021（05）：6668.

［10］鄧紹強，郭宗建，李芳，等.基于Metropolis準則的自適應(yīng)模擬退火粒子群優(yōu)化［J］.軟件導(dǎo)刊，2022，21（06）：8591.

項目：本文受到廣東高校重點領(lǐng)域?qū)ｍ椥乱淮畔⒓夹g(shù)重點領(lǐng)域?qū)ｍ楉椖浚?021ZDZX1019）的技術(shù)及經(jīng)費支持

作者簡介：張亞龍（1997—），男，漢族，河南洛陽人，碩士研究生在讀，研究方向：智能優(yōu)化算法及應(yīng)用；肖銀寶（1973—），男，漢族，云南昆明人，碩士，助理研究員，研究方向：科技管理及信息化。