基于智能優化算法的車輛路徑問題的研究與應用

張亞龍 肖銀寶

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

關鍵詞：智能計算；路徑規劃；鯨魚算法；VRP

1概述

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

2研究方案

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

3傳統鯨魚優化算法的實現

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

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

鯨魚優化算法個體更新位置方式如下：

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

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

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

Xi（t+1）=X（t）+Deblcos（2πl）（1）

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

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

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

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

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

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

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

若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）表示當前種群中第i只鯨魚個體的位置到當前最優鯨魚個體位置距離，A=2a×r1－a，C=2×r2，其中，r1，r2為［0，1］之間的隨機數。

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

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

4對傳統鯨魚算法的改進

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

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

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

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

4.1采用新的收縮因子

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

a=2－2tItermax（7）

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

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

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

4.2引入自適應權重

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

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

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

4.3引入Metropolis準則

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

假設前一狀態為X（n），系統受到一定擾動，狀態變為X（n+1），相應地，系統能量由E（n）變為E（n+1），定義系統由X（n）變為X（n+1）的接收概率為P，則P的概率計算公式為：

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

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

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

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

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

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

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

4.4算法流程

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

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

Step2構建解空間，根據適應度函數，計算鯨魚種群中的每個鯨魚個體的所在位置的適應度值，確定初始種群中個體的最優位置和種群全局最優位置，初始個體適應度值最小的對應最優位置，就是初始種群的全局最優位置；

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

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

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

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

Step7判斷是否達到種群最大迭代次數Itermax，如果達到最大迭代次數，輸出最優鯨魚個體位置，得到最優鯨魚個體的可行路徑，計算結束，否則轉到Step3，重復執行Step3至Step6，達到最大迭代次數時，輸出求解結果。

5分析總結

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

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

主要創新點：

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

（2）優化參數的選擇，提高其收斂性，提高算法運行效率，可更好地應用于復雜問題。

參考文獻：

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

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

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

［4］余賢星.一種改進的多領導鯨魚優化算法［J］.軟件工程，2022，25（11）：2834.

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

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

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

［8］崔東文.鯨魚優化算法在水庫優化調度中的應用［J］.水利水電科技進展，2017，37（03）：7276+94.

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

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

項目：本文受到廣東高校重點領域專項新一代信息技術重點領域專項項目（2021ZDZX1019）的技術及經費支持

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