中圖分類號：F224.3 文獻(xiàn)標(biāo)志碼：A

Salp swarm algorithm for solving the two-echelon location routing problem with simultaneous pickup and delivery

ZHANG Wenmei， ZHANG Huizhen， HAI Sheshe （Business School， University of Shanghai for Science and Technology，Shanghai 2Ooo93，China）

Abstract： In a two-echelon logistics network， to simultaneously meet the pickup and delivery requirements of each customer， a mixed integer programming model was established to minimize the costs associated with distribution center location， vehicle activation and vehicle transportation. An improved salp swarm algorithm was designed based on the specific characteristics of the model to solve this problem. The greedy clustering algorithm was employed to generate the initial solutions. An adaptive weighting strategy， adjusting food source quantity strategy， elite retention strategy and various search operators were introduced. The constructed model and algorithm were verified through testing instances of different customer sizes，and the original salp swarm algorithm， genetic algorithm， immune algorithm， grey wolf optimizer， and whale optimization algorithm were used for solving the problem. A comparative analysis of the operation results of each algorithm verified the feasibility of the constructed model and the effectiveness of the improved algorithm.

Keywords： location routing problem; two-echelon; simultaneous pickup and delivery; improved salp swarm algorithm

選址路徑問題（location routingproblem，LRP）是交通運(yùn)輸以及運(yùn)籌優(yōu)化領(lǐng)域的重要研究內(nèi)容之一，需同時考慮兩方面的決策問題：設(shè)施選址問題（facilitylocationproblem，F(xiàn)LP）和車輛路徑問題（vehicle routing problem，VRP）[1]。隨著互聯(lián)網(wǎng)的發(fā)展以及全球經(jīng)濟(jì)一體化的深入推進(jìn)，企業(yè)物流運(yùn)作范圍日益擴(kuò)大，物流系統(tǒng)亦呈現(xiàn)出多層級的演進(jìn)態(tài)勢。因此，眾多學(xué)者在標(biāo)準(zhǔn)選址路徑問題的基礎(chǔ)上提出構(gòu)建雙層級選址路徑問題（two-echelonlocation routingproblem，2E-LRP），雙層級物流網(wǎng)絡(luò)設(shè)計逐漸成為研究熱點(diǎn)，對現(xiàn)代物流行業(yè)的發(fā)展具有重要意義。

20世紀(jì)80年代，Jacobsen等[2第一次正式提出2E-LRP，此后，眾多學(xué)者對雙層級選址路徑問題進(jìn)行了模型優(yōu)化及拓展。Cuda等[3對雙層級選址路徑問題、雙層級車輛路徑問題以及多車型路徑規(guī)劃問題中的相關(guān)文獻(xiàn)進(jìn)行介紹和調(diào)查，得出城市物流和多式聯(lián)運(yùn)系統(tǒng)是雙層級物流網(wǎng)絡(luò)中較為關(guān)注的研究內(nèi)容。Pichka等4將第三方物流企業(yè)納入供應(yīng)鏈配送系統(tǒng)，提出了開放式的雙層級選址路徑 問 題（two-echelon open location routingproblem，2E-OLRP），從而增強(qiáng)了2E-LRP問題的現(xiàn)實意義。Nikbakhsh等[5]考慮物流企業(yè)服務(wù)客戶滿意度的因素，以最小化成本為目標(biāo)建立了帶時間窗的雙層級選址路徑問題（two-echelonlocationrouting problem with time window， 2E-LRPTW）模型。除上述研究，關(guān)于2E-LRP的變體及擴(kuò)展還包括：多資源的和多產(chǎn)品的2E-LRP（2E-LRPwithmultisources and multiproducts）[、綠色低碳的 2E-LRP（ low carbon two-echelon location routingproblem，LC2E-LRP）[7]等。

實際交易時，客戶除了送貨需求外，往往還存在取貨需求，標(biāo)準(zhǔn)的LRP僅能滿足客戶的送貨需求而無法滿足客戶的取貨需求，這導(dǎo)致LRP模型已經(jīng)不再符合當(dāng)今物流行業(yè)的實際情況。因此，研究者們提出了同時取送貨的選址路徑問題（location routing problem with simultaneous pickupanddelivery，LRPSPD）。LRPSPD是LRP的拓展，由物流企業(yè)為應(yīng)對客戶需求變化演變而來。針對LRPSPD，國內(nèi)外學(xué)者展開了廣泛而深人的研究。Wang通過采用貪心算法生成初始解并改進(jìn)原始免疫操作，提出了一種混合免疫優(yōu)化算法進(jìn)行求解。劉冬等考慮了車輛完成服務(wù)后不返回倉庫的情況，并改進(jìn)蘑菇算法求解開放式的LRPSPD 模型。Huang[]考慮了客戶的隨機(jī)性需求與確定性需求，提出了一種根據(jù)設(shè)施選擇、客戶分配和車輛路線三階段設(shè)計的禁忌搜索算法。Nadizadeh等[1]針對客戶取貨及送貨需求不確定的情況，設(shè)計了一種貪心聚類算法求解需求模糊的LRPSPD模型。

本文研究的同時取送貨的雙層級選址路徑問題（two-echelon location routing problem withsimultaneous pickup and delivery， 2E-LRPSPD） 是2E-LRP與LRPSPD的結(jié)合，能夠有效優(yōu)化物流網(wǎng)絡(luò)效率并滿足客戶的兩種需求。針對2ELRPSPD，眾多學(xué)者對模型和算法進(jìn)行了多角度的探索。Kusuma等[12]采用CPLEX軟件求解中小型客戶規(guī)模算例。Yildiz等[13]設(shè)計了一種基于分支和切割思想的精確算法。Fan等[4]提出了一種由路徑鏈接算法和可變鄰域下降算法組成的混合啟發(fā)式算法。Du等[15]設(shè)計了一種評估客戶服務(wù)滿意度的函數(shù)，采用非支配排序遺傳算法來求解帶時間窗的2E-LRPSPD模型

目前，大多數(shù)文獻(xiàn)中的2E-LRPSPD模型通常假設(shè)開放的配送中心和每個客戶僅由一輛車提供服務(wù)。考慮到開放的配送中心其取送貨總需求可能大于所派遣車輛的容量，以及客戶的取送貨需求往往小于所派遣車輛容量的情況，本文提出開放的配送中心可由多輛車提供服務(wù)，以及每個客戶僅由一輛車提供服務(wù)的假設(shè)，并且每條路徑上的總?cè)∝浟亢涂偹拓浟坎怀^車輛容量限制

2E-LRP 屬于NP-Hard問題[3]，精確算法在求解較大規(guī)模算例時的時間復(fù)雜度較高，很難求出最優(yōu)解。啟發(fā)式算法具有適用范圍廣、求解速度快等優(yōu)點(diǎn)，能夠在較短的時間內(nèi)求出最優(yōu)解或是近似最優(yōu)解，逐漸成為求解選址路徑問題的主流算法。樽海鞘算法（salp swarm algorithm，SSA）是一種新興群智能優(yōu)化算法，受海洋生物樽海鞘群覓食行為啟發(fā)而形成，由Mirjalili等[于2017年提出，具有操作靈活以及參數(shù)設(shè)置少等特點(diǎn)。本文針對構(gòu)建的2E-LRPSPD模型特性，設(shè)計了一種改進(jìn)的樽海鞘優(yōu)化算法（improvedsalp swarmalgorithm，ISSA）來進(jìn)行求解。

1 2E-LRPSPD

1.1 問題描述與假設(shè)

2E-LRPSPD是現(xiàn)代物流管理的研究重點(diǎn)，對于規(guī)劃最優(yōu)設(shè)施布局和優(yōu)化配送路徑具有重要的意義。本文構(gòu)建的雙層級物流網(wǎng)絡(luò)主要包括倉庫、配送中心、客戶、第一階段車輛以及第二階段車輛。其中：倉庫通常位于遠(yuǎn)離客戶的地方，倉庫無容量限制約束；配送中心位于靠近客戶的地方，具有容量限制約束；第一階段車輛相比較第二階段車輛具有較大的車輛載重容量。整個物流網(wǎng)絡(luò)可以描述為：第一階段車輛從倉庫出發(fā)，訪問開放的配送中心并完成其配送任務(wù)后再返回倉庫；第二階段車輛從開放的配送中心駛出，服務(wù)該配送中心所屬的客戶，滿足取送貨需求后返回配送中心。2E-LRPSPD用以解決配送中心選址、客戶分配以及第一階段和第二階段車輛路徑規(guī)劃的問題。

本文研究的2E-LRPSPD考慮如下假設(shè)：（a）物流網(wǎng)絡(luò)中的倉庫、配送中心以及客戶的節(jié)點(diǎn)位置已知，配送中心容量、第一階段和第二階段車輛的容量限制已知；（b）第一階段車輛從倉庫出發(fā)且完成服務(wù)后回到倉庫，配送中心可由多輛車提供服務(wù)；（c）第二階段車輛只會從開放的配送中心出發(fā)且完成服務(wù)后回到配送中心，每個客戶只能由一輛車提供服務(wù)，并且每個客戶只能被服務(wù)一次；（d）第二階段車輛所服務(wù)的客戶，其取貨需求與送貨需求均不得超過其車輛容量限制，且車輛在配送過程中的載重不得超過其容量限制；（e）每一個客戶由一個配送中心進(jìn)行配送，且該配送中心需滿足所分配客戶的總需求。

1.2 參數(shù)與變量

表1和表2對構(gòu)建數(shù)學(xué)模型所需要的參數(shù)和決策變量進(jìn)行了具體描述及解釋

1.3 數(shù)學(xué)模型

根據(jù)上述假設(shè)條件以及參數(shù)和決策變量的設(shè)定，本文構(gòu)建的2E-LRPSPD模型描述如下：

第一階段約束條件為

h_dik?（h_idk-Q_d+P_d）x_idk，i∈I∪D，d∈I∪D，k∈K

0?h_idk?W_kx_idk，i，d∈I∪D，k∈K

第二階段約束條件為

h_cdν?（h_dcν-q_c+p_c）y_dcν，

d∈D∪C，c∈D∪C，ν∈V

0?h_dcν?W_νy_dcν，d，c∈D∪C，ν∈V

x_idk∈{0，1}，i，d∈I∪D，k∈K

y_dcν∈{0，1}，d，c∈D∪C，ν∈V

Od∈{0，1}，d∈D

z_dc∈{0，1}，d∈D，c∈C

目標(biāo)函數(shù)式（1）表示最小化總成本，總成本包括配送中心建設(shè)成本、第一階段和第二階段車輛啟用成本以及運(yùn)輸成本。約束條件式（2）表示第一階段車輛只會訪問開放的配送中心，且該車輛僅提供一次服務(wù)；式 （3）確保第一階段節(jié)點(diǎn)流量守恒；式（4）、（5）表示第一階段車輛服務(wù)的配送中心取貨和送貨需求均不超過車輛最大載重限制；式（6、（7）確保第一階段車輛服務(wù)過程中的載重變化不超過車輛的最大載重限制；式 （8）表示消除第一階段子回路；式（9）、（10）表示配送中心的取貨和送貨量；式（11）表示每個客戶有且僅有一輛車服務(wù)；式（12）確保第二階段節(jié)點(diǎn)流量守恒；式（13）、（14）表示第二階段車輛服務(wù)的客戶取貨和送貨需求均不超過車輛的最大載重限制；式（15）（16）確保第二階段車輛服務(wù)過程中的載重變化不超過車輛的最大載重限制；式（17）確保每個開放的配送中心其容量能夠滿足所服務(wù)客戶的總需求；式（18）表示消除第二階段子回路；式 （19）確保每個客戶由一個配送中心服務(wù)；式（20）＼～（23）表示決策變量取值范圍。

2 求解2E-LRPSPD的ISSA

SSA是受到海洋動物樽海鞘群覓食行為啟發(fā)而提出的群智能優(yōu)化算法。樽海鞘群以一種鏈?zhǔn)叫袨檫M(jìn)行移動和覓食，其樽海鞘鏈前端為領(lǐng)導(dǎo)者，并指引后端追隨者的移動，且追隨者僅受前方緊鄰個體的引導(dǎo)。因此，SSA具有較強(qiáng)的全局開發(fā)和局部探索能力。SSA最初主要用于求解連續(xù)性問題，隨著國內(nèi)外學(xué)者研究的不斷深入，將此算法的應(yīng)用場景從連續(xù)性問題擴(kuò)展至離散性問題。本文提出的ISSA在SSA的基礎(chǔ)上通過增加食物源數(shù)量，動態(tài)調(diào)整樽海鞘鏈中領(lǐng)導(dǎo)者與追隨者的占比，采用貪心聚類算法生成初始種群，并結(jié)合順序交叉算子、兩點(diǎn)交換算子、單點(diǎn)插入算子和變異算子以提高種群多樣性。

2.1 編碼方式

ISSA采用自然數(shù)編碼，編碼長度由車輛啟用數(shù)和客戶數(shù)決定，為非定長的自然數(shù)數(shù)組，用以表示配送中心建設(shè)方案以及第二階段車輛行駛路線方案。一個解數(shù)組主要包括 m 個配送中心和n 個客戶。假設(shè) n 個客戶的編號為1，2，3，.，n，m 個配送中心的編號為 n+1，n+2，n+3 ，.， n+m ，則解數(shù)組可以表示為1至 n+m 排列組合的一列數(shù)字。若某一配送中心的編號未出現(xiàn)，則表示該配送中心不開放；若某一配送中心編號后出現(xiàn)客戶編號，則表示對該配送中心開放，該配送中心出現(xiàn)的次數(shù)為第二階段車輛啟用數(shù)量，并按照該配送中心的客戶編號順序依次進(jìn)行服務(wù)，直至下一個配送中心編號出現(xiàn)。以圖1所示的編碼為例：假設(shè)有3個候選配送中心，12個客戶。客戶編號為1＼～12，候選配送中心編號為 13～15 。圖1中的解可表示為配送中心13關(guān)閉，而14和15開放；從配送中心14出發(fā)有兩條路線，分別為 142 和 ；從配送中心15出發(fā)有一條路線，為 。

2.2 初始解

初始解的質(zhì)量對于模型求解十分關(guān)鍵，其優(yōu)劣直接影響群智能優(yōu)化算法的收斂速度和精度。本文采用貪心聚類算法，根據(jù)第二階段車輛的容量、客戶的取送貨需求以及客戶之間的距離對客戶進(jìn)行聚類，具體步驟如下：

a.生成一個空聚類，聚類的容量為第二階段車輛的容量，從客戶集中隨機(jī)選擇一個客戶加入該聚類，并將該客戶從客戶集中剔除。

b.從剩余客戶中選擇與已加入聚類客戶距離最近的客戶，判斷是否超過車輛容量限制，若未超過則將該客戶加入當(dāng)前聚類，否則不加入當(dāng)前聚類。c.重復(fù)操作b，繼續(xù)選擇距上一個已聚類的客戶最近的客戶，判斷是否滿足車輛容量限制，直到超過當(dāng)前聚類的容量。重復(fù)以上操作直到所有的客戶被分配完成。

d.計算每個聚類中心的坐標(biāo)， G（x_a，y_a） 用以表示聚類 a 的中心坐標(biāo)， （x_c，y_c） 為客戶 c 的坐標(biāo)， n_a 為該聚類中的客戶數(shù)量，計算公式為

e.計算配送中心 d 到所有聚類中心的距離總和 U_d ， A 表示聚類中心集合，計算公式為

f.計算配送中心的排序指標(biāo) H_d ，計算公式為

g.按照配送中心排序指標(biāo) H_d 將各聚類進(jìn)行分配。將離它最近的聚類分配給排序第一的配送中心，接著分配離它次近的聚類。重復(fù)此操作直至超過配送中心容量，開啟排序序列中下一個配送中心，直到所有聚類都被分配給配送中心為止。

h.根據(jù)上述步驟確定配送中心建設(shè)方案以及客戶分配情況后，采用最近鄰思想（nearestneighbour heuristic，NNH）[14]構(gòu)造第一階段車輛路徑方案。

2.3 自適應(yīng)權(quán)重策略

Mirjalili等[提出的初始SSA算法中，領(lǐng)導(dǎo)者數(shù)量 N_L 和追隨者數(shù)量 N_F 在迭代過程中固定不變，始終為種群總數(shù)的 50% 。然而算法在優(yōu)化過程初始階段時，領(lǐng)導(dǎo)者占種群總數(shù)比例較低，導(dǎo)致全局搜索的性能較差，從而導(dǎo)致局部最優(yōu)的情況出現(xiàn)；在優(yōu)化過程的后期階段，追隨者占種群總數(shù)比例較低，導(dǎo)致局部搜索操作不充分，容易造成算法精度下降。因此，本文采用自適應(yīng)權(quán)重策略動態(tài)調(diào)整領(lǐng)導(dǎo)者與追隨者的占比。在迭代初期增加領(lǐng)導(dǎo)者的數(shù)量，在迭代后期提高追隨者的數(shù)量，從而實現(xiàn)算法較強(qiáng)的全局搜索能力并提高算法精度，避免陷入局部最優(yōu)[7]。領(lǐng)導(dǎo)者數(shù)量為N_L=rN ；追隨者數(shù)量為 N_F=（1-r）N_c 。其中： N 為種群個體總數(shù)；參數(shù) r 為自適應(yīng)權(quán)重因子，計算公式如下所示：

式中： r₀ 、 r₁ 分別為自適應(yīng)權(quán)重因子的初始值和終值； ε 為非線性調(diào)節(jié)系數(shù)； t 為當(dāng)前迭代次數(shù)； T 為最大迭代次數(shù)。 r 的取值與迭代次數(shù)之間呈負(fù)相關(guān)關(guān)系，從而實現(xiàn)隨著算法迭代次數(shù)的增加，領(lǐng)導(dǎo)者數(shù)量逐漸減少，以及追隨者數(shù)量逐漸增加。

同時，基本SSA算法中，食物源個體一般為適應(yīng)度值最佳的個體。為了避免出現(xiàn)局部最優(yōu)的情況，本文增加了食物源的數(shù)量，分別為 F_α 、F_β 、 F_ω 。這3個食物源個體為領(lǐng)導(dǎo)者群中適應(yīng)度值排序前三的個體。

2.4 順序交叉算子

順序交叉（ordercrossover，OX）算子是一種有效的遺傳算法算子，用于產(chǎn)生新的子代個體。OX算子具有一定的隨機(jī)性，有利于提高算法的搜索能力。具體流程如下：

步驟1從食物源和領(lǐng)導(dǎo)者中各選擇一個個體，隨機(jī)選擇這兩個個體的起止位置，記作位置a和位置b（食物源和領(lǐng)導(dǎo)者個體被選擇的位置相同）;

步驟2生成一個新的子代，將食物源個體中位置a到位置b的編碼信息保留在子代相同位置處；

步驟3找出領(lǐng)導(dǎo)者個體中除去位置a到位置b的編碼信息的剩余信息，再將剩余編碼信息按從左向右的順序放入上一步生成的子代個體中

圖2給出了OX算子的具體示例，假設(shè)在第t 次迭代中，被選擇的食物源個體 F_sources（t） 以及領(lǐng)導(dǎo)者個體 F_i（t） 的位置為2和5，將 F_sources（t） 個體位置在2和5之間的編碼信息[5，11，8，1]保留到新個體 F_i（t+1） 的相同位置，找出 F_i（t） 的剩余信息[10，2，7，4，3，6，9，12]，按照從左到右的順序依次插入F_i（t+1） 的剩余位置當(dāng)中，從而得到第 i 個個體更新后的編碼信息。

2.5 兩點(diǎn)交換算子

兩點(diǎn)交換（two-pointsexchange）算子即隨機(jī)選擇父代個體的兩個位置，并將對應(yīng)位置進(jìn)行交換操作。為了避免出現(xiàn)不可行解的情況，在選擇兩點(diǎn)位置時需在客戶點(diǎn)之間進(jìn)行操作。具體流程如下：

步驟1在父代染色體中隨機(jī)設(shè)置兩個隨機(jī)交換點(diǎn)，記作位置a和位置b;

步驟2 交換位置a和位置b的編碼信息從而生成新一代個體。

圖3給出了兩點(diǎn)交換算子的具體示例，假設(shè)父代個體被選擇的位置為2和5，其對應(yīng)的編碼信息為5和1，交換位置2和位置5從而得到新的個體。

2.6 單點(diǎn)插入算子

單點(diǎn)插入（single-point mutation）算子即隨機(jī)選擇父代個體的兩個位置，并將第一個位置的編碼插入第二個位置的前方。具體流程如下：

步驟1在父代染色體中隨機(jī)設(shè)置兩個隨機(jī)交換點(diǎn)，記作位置a和位置b;

步驟2將位置a的編碼信息插入位置b前用于生成新個體。

圖4給出了單點(diǎn)插入算子的具體示例，假設(shè)父代個體被選擇的位置為2和5，其對應(yīng)的編碼信息為5和1，將編碼5插入編碼1前方，從而得到新的個體。

2.7 變異算子

為了提高算法全局搜索能力，同時很好地保留自身信息并且增強(qiáng)種群多樣性，本文引入變異（swapmutation）算子。具體流程如下：

步驟1隨機(jī)選中父代個體中的兩個位置，記為位置a和位置b;

步驟2將位置a和位置b之間的序列進(jìn)行反向排序操作，而原個體中位置a和位置b之外的編碼信息固定不變。

圖5給出了變異算子的具體示例，假設(shè)父代個體被選擇的位置為2和5，其對應(yīng)的編碼信息為[5，11，8，1]，將其反向排序后得到[1，8，11，5]，剩余位置保持不變，從而得到新的個體。

2.8 精英保留策略

在種群更新迭代過程中，具有最優(yōu)適應(yīng)度值的個體為精英個體。精英保留策略即在每一代評估完所有個體的適應(yīng)度后，選擇適應(yīng)度最高的一部分個體作為精英保留到下一代中。這部分個體的數(shù)量可以根據(jù)問題的復(fù)雜性和算法的需求來調(diào)整。同時，種群中其余個體則通過交叉、變異等算子進(jìn)行更新，與精英個體一同構(gòu)成下一代種群。精英保留策略是一種非常有效的進(jìn)化計算策略，避免種群迭代過程中丟失精英個體，有助于提高算法的性能。

2.9 算法流程

根據(jù)本文設(shè)計的2E-LRPSPD模型特征，對SSA進(jìn)行改進(jìn)，圖6給出了ISSA的流程圖，具體步驟描述如下：

步驟1初始化算法參數(shù)，包括種群規(guī)模 N 最大迭代次數(shù) T 、非線性調(diào)節(jié)系數(shù) ε 、自適應(yīng)權(quán)重因子初值 r₀ 與終值 r₁ ：

步驟2 種群初始化，采用貪心聚類算法生成初始種群個體；

步驟3計算個體適應(yīng)度值并排序，將位于前三的個體確定為食物源；

步驟4根據(jù)自適應(yīng)權(quán)重因子 r 分配領(lǐng)導(dǎo)者與追隨者，根據(jù)種群適應(yīng)度值排序，位于前端的個體為領(lǐng)導(dǎo)者，否則為追隨者；

步驟5根據(jù)2.4節(jié)更新策略對領(lǐng)導(dǎo)者進(jìn)行更新;

步驟6 根據(jù)2.5至2.7節(jié)更新策略對追隨者進(jìn)行更新；

步驟7根據(jù)2.7節(jié)更新策略對食物源進(jìn)行更新。

步驟8滿足終止條件，達(dá)到最大迭代次數(shù)則輸出最優(yōu)解，否則返回步驟3。

3 算例分析

本文所有實驗均使用MatlabR2021b編程實現(xiàn)，在Intel（R） Core（TM） i5-12500H2.50 GHz、16GB內(nèi)存、操作系統(tǒng)為64位Window11的筆記本電腦上進(jìn)行測試。

由于2E-LRPSPD沒有標(biāo)準(zhǔn)算例，本文對2E-LRP標(biāo)準(zhǔn)算例中的Prodhon數(shù)據(jù)進(jìn)行相應(yīng)改進(jìn)，采用AM分離法生成客戶的取送貨需求，即客戶送貨需求為算例中的原需求，取貨需求由式（28）所示。本文取0.2和0.8，生成兩個不同類型的問題，稱為Z型和W型算例[18]。表3給出了標(biāo)準(zhǔn)算例庫中8組算例的具體數(shù)據(jù)。

3.1 參數(shù)設(shè)置

本文采用ISSA求解問題模型，為了得到優(yōu)秀的參數(shù)組合，選取算例3作為測試數(shù)據(jù)。經(jīng)過多次實驗后，將最大迭代次數(shù)設(shè)置為 800 。ISSA的相關(guān)參數(shù)包括種群規(guī)模 N 、自適應(yīng)權(quán)重因子初值r₀ 以及終值 r₁ 。其中， N 取 0.5n 、 n 、 1.5n 、 2n 、2.5n 、 3n（n 為算例中需求點(diǎn)的數(shù)量）， r₀ 和 r₁ 的取值如表4所示。在分析某個參數(shù)性能時，其他參數(shù)保持不變。將實驗反復(fù)獨(dú)立運(yùn)行20次得到平均結(jié)果（AVG）、最大結(jié)果（MAX）、最小結(jié)果（MIN）以及平均運(yùn)行時間（TIME），實驗結(jié)果如表5、6所示。根據(jù)表5、6統(tǒng)計的數(shù)據(jù)可以得到參數(shù)水平趨勢圖，如圖7所示。由表5和圖7可以看出： N 取值100時，Z型算例均能取得較好的結(jié)果；W型算例的平均結(jié)果和最大結(jié)果較好。種群規(guī)模過小會導(dǎo)致算法陷入局部最優(yōu)，平均運(yùn)行時間受到種群大小的影響并隨種群規(guī)模的擴(kuò)大而增加，綜合考慮解的質(zhì)量和運(yùn)行時間，種群規(guī)模設(shè)置為100。由表6和圖7可得，兩組算例均在參數(shù)組合3下獲得最佳的平均結(jié)果和最小結(jié)果，且不同組合的自適應(yīng)因子取值對運(yùn)行時間影響不大。綜上所述，本文選取 r₀=0.6 、 r₁=0.4 作為實驗標(biāo)準(zhǔn)。

3.2 算例結(jié)果與分析

針對每組算例，本文對比分析原始樽海鞘算法求解2E-LRPSPD的運(yùn)行結(jié)果。在其他條件保持不變的前提下，對上文給出的每組算例反復(fù)獨(dú)立運(yùn)行20次，將平均結(jié)果、最大結(jié)果、最小結(jié)果以及平均運(yùn)行時間與本文提出的ISSA進(jìn)行對比。SSA由Matlab編寫，運(yùn)行環(huán)境參照上文，運(yùn)行結(jié)果如表7所示。由表7可知，ISSA的平均結(jié)果、最大結(jié)果、最小結(jié)果均優(yōu)于SSA相應(yīng)的運(yùn)算結(jié)果，在求解時間上相比SSA略有增加，但仍在可接受范圍內(nèi)，這說明本文的ISSA在處理2ELRPSPD上是值得信服的。

表8給出了W型算例3的最優(yōu)選址與路徑規(guī)劃方案：倉庫編號為0，客戶編號為 1～50 ，配送中心編號為51＼～55。該方案對配送中心53和54進(jìn)行開放，而未出現(xiàn)的配送中心編號則表示該配送中心不開放。車輛編號為1、2的路線為第一階段倉庫為配送中心提供的服務(wù)順序方案，車輛編號為3＼～14的路線為第二階段配送中心為客戶提供的服務(wù)順序方案。

為了進(jìn)一步說明ISSA求解2E-LRPSPD的有效性，本文選取遺傳算法（geneticalgorithm，GA）、免疫算法（immunealgorithm，IA）、灰狼算法（greywolfoptimizer，GWO）、鯨魚算法（whaleoptimizationalgorithm，WOA）進(jìn)行對比分析。GA和IA為經(jīng)典的群智能優(yōu)化算法，GWO的算法流程參考文獻(xiàn)[19]，WOA的算法流程參考文獻(xiàn)[20]。上述實驗均由Matlab軟件編寫，運(yùn)行環(huán)境參照上文，求解結(jié)果如表9所示。從表9數(shù)據(jù)可以看出，ISSA求解得到的最優(yōu)結(jié)果優(yōu)于其他算法，尤其在100個客戶規(guī)模的算例上提升較為顯著；其次，在求解時間上，ISSA的求解速度相比IA、GWO和WOA較優(yōu)，而對比GA稍有增加。由此證明，ISSA求解2E-LRPSPD具有一定優(yōu)勢，相比其他群智能優(yōu)化算法，在求解質(zhì)量和運(yùn)行時間上表現(xiàn)都更為優(yōu)秀。

4結(jié)論

為適應(yīng)當(dāng)今物流行業(yè)發(fā)展的實際狀況，滿足客戶在取送貨方面的多樣化需求，本文以最小化配送中心建設(shè)成本以及車輛成本為目標(biāo)構(gòu)建2E-LRPSPD模型，并使用改進(jìn)的樽海鞘算法進(jìn)行求解。針對2E-LRPSPD這一類組合優(yōu)化問題，通過引入自適應(yīng)權(quán)重策略、調(diào)整食物源數(shù)量策略、精英保留策略以及多種搜索算子，ISSA增強(qiáng)了種群多樣性，同時也提升了全局搜索能力，顯示出良好的計算性能。改進(jìn)的ISSA具備可擴(kuò)展性，能夠靈活應(yīng)用于其他類型的選址路徑問題中，從而增強(qiáng)其實際應(yīng)用的廣泛性和有效性。為了深化該問題的應(yīng)用價值，后續(xù)研究將進(jìn)一步構(gòu)建綠色低碳的2E-LRPSPD模型，考慮碳排放的因素并設(shè)計相應(yīng)的ISSA進(jìn)行求解。

參考文獻(xiàn)：

[1] VON BOVENTER E. The relationship between transportation costs and location rent in transportation problems[J]. Journal of Regional Science， 1961，3（2）： 27-40.

[2] JACOBSEN S K， MADSEN O B G. A comparative study of heuristics for a two-level routing-location problem[J]. European Journal of Operational Research， 1980，5（6）： 378-387.

[3]CUDA R， GUASTAROBA G， SPERANZA M G. A survey on two-echelon routing problems[J]. Computers amp; Operations Research，2015， 55：185-199.

[4]PICHKA K， BAJGIRAN A H， PETERING ME H， et al. Thetwo echelonopenlocation routingproblem： mathematical model and hybrid heuristic[J]. Computers amp; Industrial Engineering，2018， 121： 97-112.

[5]NIKBAKHSH E， ZEGORDI S H. A heuristic algorithm and a lower bound for the two-echelon location-routing problem with soft time window constraints[J]. Scientia Iranica，2010，17（1）：1755-1759.

[6]RAHMANIY，CHERIF-KHETTAFWR，OULAMARA A.A local search approach for the two-echelon multiproductslocation-routing problem with pickupand delivery[J]. IFAC-PapersOnLine，2015， 48（3）： 193-199.

[7]WANG Y，PENG S G， ZHOU X S，et al. Green logistics location-routing problem with eco-packages[J]. Transportation ResearchPartE：Logistics and Transportation Review， 2020， 143：102118.

[8]WANG X W. Research on hybrid immune algorithm for solving the location-routing problem with simultaneous pickup and delivery[J]. Journal of Cases on Information Technology， 2022， 24（5）： 1-17.

[9]劉冬，張惠珍，劉亞平，等.改進(jìn)蘑菇算法求解開放式同 時送取貨選址-路徑問題[J].控制工程，2023，30（10）： 1801-1811.

[10]HUANG S H. Solving the multi-compartment capacitated location routing problem with pickup-delivery routes and stochasticdemands[J].Computersamp;Industrial Engineering， 2015，87： 104-113.

[11] NADIZADEH A， KAFASH B. Fuzzy capacitated locationrouting problem with simultaneous pickup and delivery demands[J]. Transportation Letters，2017， 11（1）： 1-19.

[12]KUSUMA R M R，YU V F， VANANY I， et al. Mathematical modeling of the two-echelon location routing problem with simultaneous pickup and delivery and parcel locker[C]//Proceedings of 2024 International Conference on System Science and Engineering. Hsinchu， China： IEEE，2024：1-6.

[13] YILDIZ E A， KARAOGLAN I， ALTIPARMAK F. An exact algorithm for two-echelon location-routing problem with simultaneous pickup and delivery[J]. Expert Systems with Applications， 2023，231： 120598.

[14]FAN H M， WU J X，LI X， et al. Presenting a multi-start hybrid heuristic for solving the problem of two-echelon location-routing problem with simultaneous pickup and delivery（2E-LRPSPD）[J].JournalofAdvanced Transportation， 2020， 2020（1）： 9743841.

[15] DU JH， XU W， WU X， et al. Multi-objective optimization fortwo-echelon joint delivery location routing problem considering carbon emission under online shopping[J]. Transportation Letters， 2023，15（8）： 907-925.

[16]MIRJALILI S， GANDOMI A H， MIRJALILI S Z， et al. Salpswarm algorithm：a bioinspired optimizer for engineering design problems[J]. Advances in Engineering Software，2017，114： 163-191.

[17]鮑秀麟，張惠珍，馬良，等.考慮公眾風(fēng)險的多目標(biāo)醫(yī)療 廢物選址路徑問題及樽海鞘算法求解[J].計算機(jī)應(yīng)用研 究，2023，40（3）： 710-716.

[18]KARAOGLANI，ALTIPARMAKF，KARAI，etal.The location routing problem with simultaneous pickup and delivery： formulations and a heuristic approach[J]. Omega， 2012，40（4）： 465-477.

[19]張坤，張惠珍，馬良，等.分布估計灰狼算法求解低碳選 址路徑問題[J].系統(tǒng)管理學(xué)報，2023，32（4）：701-711.

[20]SI Q， LI C Y. Indoor robot path planning using an improved whale optimization algorithm[J]. Sensors， 2023， 23（8）： 3988.

（編輯：丁紅藝）