多策略改進麻雀搜索算法的同時取送貨車輛路徑規劃

肖 磊 （沈陽大學 機械工程學院，遼寧 沈陽 110003）

0 引 言

同時取送貨車輛路徑問題(Vehicle Routing Problem with Simultaneous Pick-up and Distribution, VRPSPD)是經典VRP的擴展，由Min H在研究圖書館書籍配送與回收問題時首次提出。VRPSPD作為傳統逆向物流的拓展，將取貨需求融入配送過程中，比單獨進行配送或取貨更能減少配送車輛數量，從而提高客戶滿意度和車輛裝載率，降低不確定性成本，并實現物流資源的最大化利用。隨著物流需求的增長，VRPSPD被視為一種更科學和合理的配送方式，并逐漸成為學術界的研究熱點。

高振迪等[1]針對庫存不平衡問題，提出了一種基于模糊客戶需求的多商品多批次車輛路徑規劃模型，并采用改進禁忌搜索算法進行求解。孟姍姍等[2]提出了一種卡車與無人機相結合的配送模式，并采用改進模擬退火算法優化路徑。王新杰等[3]研究了基于共享車輛與客戶訂單的多配送中心聯合取送貨車輛路徑問題，并證明了大聯盟配送方式具有穩定性和成本節省優勢。解永亮等[4]針對多溫區冷鏈物流配送問題，提出了混合蟻群算法的解決策略。張烜熒等[5]采用超啟發式分布估計算法來解決帶有軟時間窗的物流取送貨車輛配送問題。袁曉建等[6]通過在VRPSDP中引入時間窗，建立數學模型并設計了一種改進的量子算法對模型進行求解。

本文主要研究軟時間窗約束下的取送貨車輛路徑規劃，首先構建了整數規劃模型以達到最低成本和最高客戶滿意度，然后采用改進麻雀搜索算法求解模型，并通過實例驗證其優越性，最終得到了最優路徑圖。

1 問題描述及建模

1.1 問題描述

同時取送貨車輛路徑規劃問題可描述為：一個配送中心為其所服務區域提供取送貨服務，要求在滿足客戶需求的情況下完成服務后返回配送中心，配送車輛必須為所有客戶點提供服務。本文建立了一個以最低總成本和最高客戶滿意度為目標的數學模型，涉及車輛運行成本、調用成本和時間窗懲罰成本，同時需滿足客戶約束條件與需求。模型中對變量的定義見表1。

本文現提出以下假設：設定單一配送中心；已知客戶需求量且不超過車輛最大載重；車輛型號、載重能力和速度相同；已知客戶地點與配送中心間距離；僅為每位客戶服務一次；同車實現取送混合裝載；不考慮天氣因素。

1.2 數學建模

基于上述問題描述和變量的定義，構建雙目標VRPSPD數學模型如下。

目標函數（1）—（3）分別為車輛運行成本、調用成本和時間懲罰成本；式（4）為最小總成本；式（5）為最小顧客不滿意度。約束條件式（6）為每個客戶節點被訪問且僅被訪問一次；式（7）—（8）為每輛車有且僅有配送一次；式（9）—（14）為車輛載重約束；式（15）—（16）為服務時間約束；式（17）為車輛行駛里程約束；式（18）為決策變量。

2 求解算法

2.1 麻雀搜索算法

麻雀搜索算法（Sparrow Search Algorithm, SSA）由Xue J K于2020年首次提出，此新型群體智能優化算法的靈感來自雀鳥的覓食與反捕食行為。SSA算法中有發現者、追隨者和警戒者，分別按照各自規則進行位置更新，更新規則如下。

其中，t為當前迭代次數，T為最大迭代次數，Xij為第i個麻雀在j維中的位置信息。α∈（0，1]的隨機數，R2∈[0，1]為預警值，ST∈[0.5，1]為安全值。Q為隨機數，L是維數為1×d的矩陣，元素全為1。

其中，Xp為追隨者的最佳位置，是全局最差位置，A+是一個隨機賦值為1或-1的矩陣，其維度為1×d，且A+=AT（AAT）-1。

其中，為全局最優位置，β為步長控制參數，K∈[-1，1]的隨機數，fi為麻雀個體的適應度值，fg和fw為最佳和最差的適應度值，ε是極小常數。

2.2 改進麻雀搜索算法

2.2.1 立方混沌映射

本文針對麻雀搜索算法初始化階段存在的局部最優和收斂精度問題，采用混沌立方映射方法。這種方法利用混沌理念的偶然性和規則性特點，實現特定范圍內的均勻分布，從而提高算法的穩定性和收斂精度。因混沌立方映射展現出優越的不可預見性和分布均衡性，所以本文采用混沌立方映射來優化麻雀搜索算法的初始階段。

假設初始麻雀種群由n個d維個體組成，在d維空間中隨機產生麻雀個體為Xi=（x1，x2，x3...，xd），即隨機生成一個每維都在[-1，1]區間內的d維向量作為第一個個體。

其中，Xi表示麻雀實際個體的變量值；Xlb和Xub為解空間中每個個體在各維度上的上下邊界。

2.2.2 精英反向學習策略

反向學習策略（Opposition-Based Learning, OBL）是計算智能領域的一種新興策略，其通過尋找反向解并比較優劣，可提高群體多樣性和解質量，避免局部最優。

精英反向學習策略（Elite Opposition-Based Learning, EOBL）針對反向學習策略在某些情況下無法更容易搜索到全局最優解的問題進行了改進，EOBL通過引入精英策略與精英個體進行反向學習，生成精英反向解，并選擇優秀個體，以提高種群多樣性，從而更有效地尋找全局最優解。

設Xi=（xi，1，xi，2，…，xi，d）為d維空間中的一個普通粒子，普通粒子的某個自身極值點為精英粒子，即精英反向解定義如下。

其中，Xij∈[aj，bj]，m是精英反向系數，為0-1間的隨機數，[caj，cbj]為第j維搜索空間的動態邊界，可通過下式計算得到：

當反向解處于邊界之外，就需要進行越界處理，公式如下。

2.2.3 正余弦優化算法

正余弦優化算法(Sin Cos Algorithm，SCA)是由Mirjalili于2016年創立的新穎群體智能優化算法。此算法利用了正弦和余弦函數的振動特性來執行優化搜索，它的優點包括參數較少、結構簡單以及算法收斂性能佳，公式如下。

其中，Xi為第i個待優化變量，Li和Ui分別為Xi的上界和下界。

SCA基于適應度函數計算每個個體的適應度值，并將最優個體記錄為X*。在搜索過程中個體位置更新公式如下。

其中，為第t代種群中的第i個個體位置，為最優個體位置。a為大于1的常數，設a=2。t為當前迭代次數，tmax為最大迭代次數。r2∈（0，2π），r3∈（0，2），r4∈（0，1）。

2.2.4 ISSA 算法流程

本文提出的ISSA算法，采用立方映射混沌算子和反向選擇策略進行種群初始化。通過精英反向學習策略增強多樣性，結合正弦余弦算法優化追隨者位置更新，并采用線性遞減方法控制警戒者數量，以提高全局搜索能力、探索效率和收斂速度。警戒者數量的線性遞減公式如下：

其中，Numb為現有的警戒者數目，t為當前的迭代次數，tmax為最大迭代次數，Numbint表示初始警戒者數量。

改進后麻雀算法的具體算法步驟如下。

Step1：初始化麻雀數量，定義相關參數；

Step2：利用立方混沌映射方法初始化種群；Step3：加入OBL提高種群的多樣性，令t=1；

Step4：若算法沒有達到最大迭代次數tmax，則計算個體適應度值，并記錄最佳個體及其位置；

Step5：根據式（24）和（26）更新發現者的位置；

Step6：根據式（28）更新追隨者的位置；

Step7：根據式（21）更新警戒者位置，根據式（30）在算法后期對警戒者數量進行控制；

Step8：進行動態邊界控制，縮小搜索范圍；

Step9：獲取更新后的麻雀種群；

Step10：判斷算法是否達到最大迭代次數tmax，若達到，則輸出最優解，否則回到Step4。

ISSA流程圖如圖1所示。

3 仿真實驗與結果分析

3.1 案例描述及實驗參數設置

本文選取M物流企業作為實例，來檢驗所建立的路徑規劃模型和改進的麻雀搜索算法。M物流企業在某區域設有一個營業部，其作為配送中心服務于周邊的攬投點，攬投點每日需要取送貨服務。現選取M物流企業某一天的數據進行求解，表2展示了當天33個客戶的具體相關信息。模型及配送車輛的相關參數設置見表3。

表2 配送中心及各客戶點相關信息表

表3 模型及配送車輛的相關參數

本文使用ISSA、SSA、GA和WOA四種算法求解該實例，并使用MATLAB 2022b進行編程求解。實驗參數設定：種群大小為50，最大迭代次數為100，麻雀種群的發現者比例為0.3，預警者比例為0.1，警戒閾值為0.7，GA的突變率為0.05，精英個體數為10，WOA的參數配置參考了文獻[7]。實驗進行了10次運算，選取總成本最小并且客戶滿意度最高的路徑作為最優路徑。

3.2 實驗結果分析

基于上述信息，本次實驗分別使用ISSA、SSA、GA、WOA算法求解同時取送貨車輛路徑規劃問題。首先將配送中心與客戶的地址坐標、需求量、客戶時間窗和服務時間作為算法輸入，然后將前文構建的總成本和客戶滿意度函數作為算法的適應度函數。同時，使用MATLAB進行編程計算，并對運行結果進行分析和比較。圖2和圖3展示了四種算法迭代優化收斂圖和車輛最優行駛路徑圖，優化結果對比見表4。

圖2 各算法迭代曲線圖

圖3 四種算法的最優路徑規劃圖

表4 ISSA、SSA、GA 和WOA 算法的路徑優化結果對比

由圖2可知，ISSA算法的收斂曲線斜率最高，展現出優越的最優解逼近能力和多次跳出局部最優的特點。這主要得益于算法使用混沌映射和反向學習策略來獲取初始種群分布，以降低優化過程的隨機性，從而在早期獲取良好的初始位置優勢。ISSA算法在計算開始階段生成的初始解可能性能較差，但隨著迭代的進行，解會逐漸向最優解靠攏，并在第80代時產生最優解。ISSA算法在SSA算法的基礎上，結合了立方混沌映射、精英反向學習策略和正余弦優化算法的優點，顯示出更強的全局搜索能力和尋優能力。在解決復雜的同時取送貨車輛路徑問題時，ISSA算法相較于SSA、GA和WOA算法，展現出更佳的效果和實用性。

圖3展示了ISSA、SSA、GA和WOA四種算法的配送路線圖，從圖中可以觀察到，每條配送路徑上的客戶點分布呈現出相對分散的狀態。ISSA算法的最優配送方案只需要3輛車，而其他三種算法的最優配送方案則需要4輛車。

由表4可知，采用ISSA算法進行配送所需的總成本最低，費用為11 038.101 3元，同時客戶滿意度最高，達到0.977 5，顯著優于SSA、GA和WOA算法。這驗證了本文針對標準麻雀優化算法所提出的改進策略是有效的。通過對時間窗和服務質量進行控制，不僅提高了客戶滿意度，也有助于企業維護客戶關系，從而促進企業更好地發展。這也證實了本文提出的基于ISSA算法的同時取送貨配送路徑規劃方法具有有效性和優勢。

4 結 語

本文構建了帶有軟時間窗的同時取送貨車輛路徑規劃問題模型，其優化目標為最小化總成本和最大化客戶滿意度。為提高算法效果，研究將立方混沌映射、精英反向學習策略和正余弦優化算法融入麻雀搜索算法中。針對M物流公司33個攬投點的實際需求，本文使用ISSA算法解決了問題。通過與SSA、GA和WOA等其他算法的比較發現，ISSA算法在配送總成本和客戶滿意度方面均優于其他三種算法，證實了ISSA算法解決同時取送貨車輛路徑規劃問題的有效性和優勢。本文預設所有的配送均能一次完成，然而在現實中，配送不成功也可能對總體成本產生影響，因此，未來的研究可以進一步探討配送的失敗率對整體配送成本的影響。