多策略改進(jìn)麻雀搜索算法的同時(shí)取送貨車輛路徑規(guī)劃

肖 磊 （沈陽大學(xué) 機(jī)械工程學(xué)院，遼寧 沈陽 110003）

0 引 言

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

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

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

1 問題描述及建模

1.1 問題描述

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

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

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

基于上述問題描述和變量的定義，構(gòu)建雙目標(biāo)VRPSPD數(shù)學(xué)模型如下。

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

2 求解算法

2.1 麻雀搜索算法

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

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

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

其中，為全局最優(yōu)位置，β為步長控制參數(shù)，K∈[-1，1]的隨機(jī)數(shù)，fi為麻雀個(gè)體的適應(yīng)度值，fg和fw為最佳和最差的適應(yīng)度值，ε是極小常數(shù)。

2.2 改進(jìn)麻雀搜索算法

2.2.1 立方混沌映射

本文針對(duì)麻雀搜索算法初始化階段存在的局部最優(yōu)和收斂精度問題，采用混沌立方映射方法。這種方法利用混沌理念的偶然性和規(guī)則性特點(diǎn)，實(shí)現(xiàn)特定范圍內(nèi)的均勻分布，從而提高算法的穩(wěn)定性和收斂精度。因混沌立方映射展現(xiàn)出優(yōu)越的不可預(yù)見性和分布均衡性，所以本文采用混沌立方映射來優(yōu)化麻雀搜索算法的初始階段。

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

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

2.2.2 精英反向?qū)W習(xí)策略

反向?qū)W習(xí)策略（Opposition-Based Learning, OBL）是計(jì)算智能領(lǐng)域的一種新興策略，其通過尋找反向解并比較優(yōu)劣，可提高群體多樣性和解質(zhì)量，避免局部最優(yōu)。

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

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

其中，Xij∈[aj，bj]，m是精英反向系數(shù)，為0-1間的隨機(jī)數(shù)，[caj，cbj]為第j維搜索空間的動(dòng)態(tài)邊界，可通過下式計(jì)算得到：

當(dāng)反向解處于邊界之外，就需要進(jìn)行越界處理，公式如下。

2.2.3 正余弦優(yōu)化算法

正余弦優(yōu)化算法(Sin Cos Algorithm，SCA)是由Mirjalili于2016年創(chuàng)立的新穎群體智能優(yōu)化算法。此算法利用了正弦和余弦函數(shù)的振動(dòng)特性來執(zhí)行優(yōu)化搜索，它的優(yōu)點(diǎn)包括參數(shù)較少、結(jié)構(gòu)簡單以及算法收斂性能佳，公式如下。

其中，Xi為第i個(gè)待優(yōu)化變量，Li和Ui分別為Xi的上界和下界。

SCA基于適應(yīng)度函數(shù)計(jì)算每個(gè)個(gè)體的適應(yīng)度值，并將最優(yōu)個(gè)體記錄為X*。在搜索過程中個(gè)體位置更新公式如下。

其中，為第t代種群中的第i個(gè)個(gè)體位置，為最優(yōu)個(gè)體位置。a為大于1的常數(shù)，設(shè)a=2。t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)。r2∈（0，2π），r3∈（0，2），r4∈（0，1）。

2.2.4 ISSA 算法流程

本文提出的ISSA算法，采用立方映射混沌算子和反向選擇策略進(jìn)行種群初始化。通過精英反向?qū)W習(xí)策略增強(qiáng)多樣性，結(jié)合正弦余弦算法優(yōu)化追隨者位置更新，并采用線性遞減方法控制警戒者數(shù)量，以提高全局搜索能力、探索效率和收斂速度。警戒者數(shù)量的線性遞減公式如下：

其中，Numb為現(xiàn)有的警戒者數(shù)目，t為當(dāng)前的迭代次數(shù)，tmax為最大迭代次數(shù)，Numbint表示初始警戒者數(shù)量。

改進(jìn)后麻雀算法的具體算法步驟如下。

Step1：初始化麻雀數(shù)量，定義相關(guān)參數(shù)；

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

Step4：若算法沒有達(dá)到最大迭代次數(shù)tmax，則計(jì)算個(gè)體適應(yīng)度值，并記錄最佳個(gè)體及其位置；

Step5：根據(jù)式（24）和（26）更新發(fā)現(xiàn)者的位置；

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

Step7：根據(jù)式（21）更新警戒者位置，根據(jù)式（30）在算法后期對(duì)警戒者數(shù)量進(jìn)行控制；

Step8：進(jìn)行動(dòng)態(tài)邊界控制，縮小搜索范圍；

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

Step10：判斷算法是否達(dá)到最大迭代次數(shù)tmax，若達(dá)到，則輸出最優(yōu)解，否則回到Step4。

ISSA流程圖如圖1所示。

3 仿真實(shí)驗(yàn)與結(jié)果分析

3.1 案例描述及實(shí)驗(yàn)參數(shù)設(shè)置

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

表2 配送中心及各客戶點(diǎn)相關(guān)信息表

表3 模型及配送車輛的相關(guān)參數(shù)

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

圖2 各算法迭代曲線圖

圖3 四種算法的最優(yōu)路徑規(guī)劃圖

表4 ISSA、SSA、GA 和WOA 算法的路徑優(yōu)化結(jié)果對(duì)比

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

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

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

4 結(jié) 語

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