改進(jìn)樽海鞘算法求解帶時間窗的應(yīng)急選址路徑問題

徐帆，馬良，張惠珍，陳曦

改進(jìn)樽海鞘算法求解帶時間窗的應(yīng)急選址路徑問題

徐帆，馬良，張惠珍*，陳曦

（上海理工大學(xué) 管理學(xué)院，上海 200093）

為使應(yīng)急物資及時高效地送到災(zāi)區(qū), 針對多目標(biāo)應(yīng)急選址?路徑問題，在考慮災(zāi)區(qū)的時間窗及物資運(yùn)輸過程中道路安全的情況下，以最小化經(jīng)濟(jì)成本、最小化時間懲罰成本及最大化道路安全性為目標(biāo)，構(gòu)建多目標(biāo)優(yōu)化模型。同時，設(shè)計改進(jìn)的樽海鞘算法求解問題，以驗證模型的可行性和算法的有效性。根據(jù)模型的特征對樽海鞘算法進(jìn)行改進(jìn)，運(yùn)用隨機(jī)生成和貪心算法相結(jié)合的方式生成初始解，利用交叉算子和鄰域搜索算子改進(jìn)原始算法的位置更新操作，引入非支配排序遺傳算法（NSGA-Ⅱ）的精英保留策略，以提高算法的性能。經(jīng)過多個算例測試，該算法能快速獲得一簇Pareto解，與基本樽海鞘算法進(jìn)行對比后可知，改進(jìn)后的算法性能更優(yōu)越。對于災(zāi)后及時響應(yīng)的應(yīng)急選址路徑問題，采用改進(jìn)的樽海鞘算法具有一定優(yōu)越性，并在多個目標(biāo)權(quán)衡的情況下，可供決策者根據(jù)目標(biāo)的偏好找到較滿意的解，對于研究應(yīng)急選址路徑問題具有一定的參考價值。

選址?路徑問題；應(yīng)急物資；時間窗；改進(jìn)樽海鞘算法

近年來，地震、洪澇等自然災(zāi)害突發(fā)事件頻繁發(fā)生。根據(jù)中國應(yīng)急管理部與自然資源部等部門核定公布的數(shù)據(jù)顯示，2022年我國自然災(zāi)害以洪澇、干旱、地震為主，共計造成1.12億人次受災(zāi)，直接經(jīng)濟(jì)損失高達(dá)2 386.5億元（http://www.mem.gov.cn/）。在應(yīng)急管理中，救援倉庫的設(shè)施選址問題（Facility Location Problem，F(xiàn)LP）與車輛路徑問題（Vehicle Routing Problem，VRP）是很重要的2個子問題，它們整合了戰(zhàn)略和戰(zhàn)術(shù)決策[1]。將這2個子問題的綜合問題稱為選址?路徑問題（Location-Routing Problem, LRP）。

目前，有大批學(xué)者在應(yīng)急物流選址?路徑上進(jìn)行了相關(guān)研究。Vahdani等[2]考慮了具有不同容量水平的配送中心和倉庫位置，以及倉庫的庫存和路線的可靠性，構(gòu)建了一個兩階段多目標(biāo)的混合整數(shù)模型。Zhang等[3]建立了一個考慮出行時間、應(yīng)急救援費(fèi)用和二氧化碳排放的不確定性多目標(biāo)應(yīng)急響應(yīng)選址規(guī)劃模型，并將不確定性仿真與遺傳算法結(jié)合對模型進(jìn)行求解。Wei等[4]考慮時間窗和成本，建立了帶時間窗的應(yīng)急選址?路徑多目標(biāo)模型，并利用混合蟻群算法進(jìn)行求解。Shen等[5]基于粒子群算法結(jié)合禁忌搜索的混合兩階段算法，求解了一種模糊低碳應(yīng)急選址?路徑問題。劉長石等[6]針對震后物資配送模糊選址?路徑問題，設(shè)計了一種混合免疫遺傳算法，以應(yīng)對震后應(yīng)急。

現(xiàn)有研究針對應(yīng)急LRP問題重點(diǎn)考慮的是經(jīng)濟(jì)因素和時間因素，而實(shí)際情境中災(zāi)后設(shè)施與道路可能會遭到一定破壞，在山區(qū)等環(huán)境惡劣地區(qū)這些因素會對救援人員的生命造成威脅，因而應(yīng)該考慮物資配送過程中的安全性。文中引入道路安全性系數(shù)，構(gòu)建一個多目標(biāo)帶時間窗的災(zāi)后選址?路徑模型。

由于LRP問題屬于NP-hard問題[7]，精確算法在求解大規(guī)模LRP問題時其速度通常較緩慢，甚至無法求到一個可行解，采用智能優(yōu)化算法可以在短時間內(nèi)找到滿意解[8]。樽海鞘算法（Salp Swarm Algorithm，SSA）[9]是根據(jù)樽海鞘在海洋中移動和覓食時的群體聚集行為提出的群智能優(yōu)化算法，相較于遺傳算法、蟻群算法等經(jīng)典算法，SSA算法的參數(shù)較少，具有結(jié)構(gòu)簡單、收斂速度快、控制參數(shù)少等優(yōu)點(diǎn)，自開發(fā)以來廣泛應(yīng)用于特征選擇[10-11]、圖像[12]、工程設(shè)計[13-14]等多個領(lǐng)域，但很少應(yīng)用于應(yīng)急物資調(diào)度領(lǐng)域內(nèi)的選址?路徑等離散型問題中。文中基于SSA算法求解所構(gòu)建的多目標(biāo)LRP問題模型，并根據(jù)LRP模型的特征對SSA算法進(jìn)行改進(jìn)。通過不同規(guī)模的算例測試對構(gòu)建的模型和算法進(jìn)行驗證，并與基本樽海鞘優(yōu)化算法（Salp Swarm Algorithm，SSA）的求解結(jié)果進(jìn)行對比，以驗證算法的可行性和有效性。該算法在得到帕累托前沿面的同時，可供決策者根據(jù)不同目標(biāo)的重要性選擇恰當(dāng)?shù)奈镔Y調(diào)度方案，對應(yīng)急LRP領(lǐng)域具有一定的參考意義。

1 問題描述和模型建立

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

描述研究的LRP問題：給定個候選應(yīng)急倉庫和個需求點(diǎn)，從候選應(yīng)急倉庫中選擇若干條設(shè)施開放，并規(guī)劃配送物資的路徑，求解目標(biāo)為最小化總成本、最小化物資延時送達(dá)的時間懲罰成本和最大化物資運(yùn)輸過程中的道路安全性。針對模型做如下假設(shè)：候選應(yīng)急倉庫與需求點(diǎn)地理位置關(guān)系已知；物資到達(dá)時間已知；車輛行駛的路網(wǎng)狀況已知；需求點(diǎn)的物資需求量已知；應(yīng)急倉庫到需求點(diǎn)及需求點(diǎn)兩兩之間均存在可通行路徑；物資送達(dá)的時間應(yīng)越早越好，因此每個需求點(diǎn)的時間窗為半時間窗，晚到則會產(chǎn)生相應(yīng)的時間懲罰成本。

1.2 符號與變量

1.3 模型建立

目標(biāo)函數(shù)1表示最小化總成本，該成本由3個部分組成：救援倉庫開放所帶來的固定成本、啟用車輛的固定成本和應(yīng)急物資的運(yùn)輸成本，見式（1）。目標(biāo)函數(shù)2表示最小化車輛延時送達(dá)的時間懲罰成本，見式（2）。目標(biāo)函數(shù)3表示最大化車輛行駛的道路安全性，見式（3）。這3個目標(biāo)函數(shù)旨在從成本、時間和安全性3個維度來優(yōu)化物流配送，實(shí)現(xiàn)在滿足服務(wù)要求的同時，達(dá)到成本效益最大化和安全風(fēng)險最小化的目標(biāo)。約束條件1表示只有開放的救援倉庫才能運(yùn)輸物資，見式（4）。約束條件2表示每個需求點(diǎn)有且僅有1輛車對其服務(wù)，見式（5）。約束條件3表示每個需求點(diǎn)有且僅有1個救援倉庫對其進(jìn)行服務(wù)，見式（6）。約束條件4表示救援倉庫之間未連通，見式（7）。約束條件5表示救援倉庫容量限制，即任意一個救援倉庫發(fā)出去的物資不超過倉庫的存儲容量，見式（8）。約束條件6表示車輛容量約束，即每條配送路線的每輛車的負(fù)載低于車容量，見式（9）。約束條件7表示節(jié)點(diǎn)的車輛進(jìn)出流量守恒約束，見式（10）。約束條件8表示消除子回路，見式（11）。約束條件9表示車輛在訪問需求點(diǎn)時違反的時間窗長度，見式（12）。約束條件10表示時間窗口約束，見式（13）。約束條件11～14定義了決策變量及參數(shù)，見式（14）～（17）。

2 求解多目標(biāo)LRP問題的改進(jìn)樽海鞘優(yōu)化算法

樽海鞘算法（Salp Swarm Algorithm，SSA）是一種受樽海鞘群體運(yùn)動和覓食行為啟發(fā)的基于群智能的優(yōu)化算法。在樽海鞘群中，前一半個體為領(lǐng)導(dǎo)者，其余的為追隨者，領(lǐng)導(dǎo)者引導(dǎo)種群，追隨者互相跟隨，所有個體形成一條“鏈”，通過樽海鞘個體的位置更新移動不斷靠近食物源，最后快速準(zhǔn)確地找到最優(yōu)解[15]。此算法主要適用于連續(xù)優(yōu)化問題，算法中樽海鞘的位置更新方法僅適用于連續(xù)空間的搜索。考慮到文中研究的問題屬于離散優(yōu)化問題，根據(jù)選址?路徑問題的特點(diǎn)，并保有算法的特征，設(shè)計一種改進(jìn)的樽海鞘算法。

2.1 解的表示

使用兩段式的實(shí)數(shù)編碼表示每個個體（可行解），所有需求點(diǎn)的數(shù)量為，染色體長度為2，解的構(gòu)成由2個部分構(gòu)成，分別為和，用不同的顏色表示，如圖1所示。假設(shè)救援倉庫、需求點(diǎn)的數(shù)量分別為4、8，解的編碼長度為16，其中表示需求點(diǎn)與救援倉庫的歸屬關(guān)系；表示需求點(diǎn)的初始配送順序。如圖1所示，4個候選救援倉庫中2號救援倉庫未開放，其中需求點(diǎn)4和7由救援倉庫1提供服務(wù)，車輛配送物資的順序為7→4；需求點(diǎn)5、1、6由救援倉庫3提供服務(wù)，車輛配送物資的順序為5→1→6。

同理，需求點(diǎn)2、3、8由救援倉庫4提供服務(wù)，車輛配送物資的順序為3→8→2。這種編碼方式簡單直觀，可體現(xiàn)出開放的倉庫、需求點(diǎn)的歸屬及救援倉庫所服務(wù)的需求點(diǎn)的配送順序。

圖1 解的表示

2.2 初始種群的生成

初始解根據(jù)概率選擇貪心算法或隨機(jī)生成初始種群。其中，貪心算法只在生成需求點(diǎn)和倉庫歸屬關(guān)系時發(fā)揮作用，首先計算出每個需求點(diǎn)到所有候選救援倉庫的距離，按照升序排列，依照概率選擇離自己最近或其他救援倉庫。隨機(jī)生成初始解時，首先隨機(jī)為各個需求點(diǎn)分配救援倉庫，確立需求點(diǎn)與救援倉庫的歸屬關(guān)系，然后隨機(jī)生成路徑規(guī)劃，確立每個救援倉庫為需求點(diǎn)配送物資的順序，計算見式（18）～（19）。

式中：U表示的上界；L表示的下界，最少有一個救援倉庫為需求點(diǎn)提供配送服務(wù)，故L1；最多所有救援倉庫都提供配送服務(wù)，故U為所有候選救援倉庫的數(shù)量。初始解的長度為2，式（18）表示前列需求點(diǎn)與救援倉庫的歸屬關(guān)系，式（19）表示+1列到2列需求點(diǎn)被配送的順序。

2.3 快速非支配排序

在多目標(biāo)問題中，由于多個目標(biāo)之間往往存在沖突，很難找到一個解使所有目標(biāo)函數(shù)最優(yōu)，因此引入NSGA-Ⅱ中的非支配排序和擁擠度的概念[16]，按照每個個體的非支配和支配關(guān)系將他們排序分級，并且根據(jù)擁擠度選出同級別中的優(yōu)解。擁擠度計算需要根據(jù)每個目標(biāo)函數(shù)值按升序總體進(jìn)行排序。然后，將等級中的邊界解（具有最小和最大函數(shù)值的解）的擁擠度設(shè)為無窮大。中間解的擁擠度根據(jù)式（20）計算。

式中：為目標(biāo)函數(shù)的數(shù)量；C為第個個體的擁擠度；1、–1為個體沿著帕累托邊界的2個相鄰個體；F()為個體的第個目標(biāo)函數(shù)值。在所有個體中，排序值更靠前和擁擠度更大的個體更優(yōu)。

2.4 領(lǐng)導(dǎo)者-跟隨者自適應(yīng)調(diào)整

在基本SSA算法中，領(lǐng)導(dǎo)者和追隨者的數(shù)量始終各占種群總數(shù)的一半，這樣導(dǎo)致在算法迭代早期，全局搜索的領(lǐng)導(dǎo)者比例過低，跟隨者的比例過高，可能導(dǎo)致算法無法充分進(jìn)行全局搜索而陷入局部最優(yōu)解。在算法迭代后期，跟隨者的數(shù)量過少，導(dǎo)致局部搜索不充分，會影響搜索的精度。

為了解決這個問題，這里引入了一種領(lǐng)導(dǎo)者?跟隨者自適應(yīng)調(diào)整策略。其中，樽海鞘領(lǐng)導(dǎo)者的數(shù)量會隨著迭代次數(shù)的增加而自適應(yīng)地減少，而跟隨者的數(shù)量會自適應(yīng)地增加。這樣，算法在迭代早期可以保持強(qiáng)大的全局搜索能力，同時算法在迭代后期，其局部搜索能力逐漸增強(qiáng)，從而提高了整體的優(yōu)化精度。

計算改進(jìn)后的領(lǐng)導(dǎo)者?跟隨者，每代中領(lǐng)導(dǎo)者數(shù)量等于p,跟隨者數(shù)量等于(1–)p，p為種群數(shù)量，自適應(yīng)權(quán)重因子的計算見式（21）。

式中：為當(dāng)前迭代次數(shù);max為最大迭代次數(shù)；init為控制參數(shù)的初始值；final為控制參數(shù)的終值。自適應(yīng)權(quán)重因子在算法迭代中隨著迭代次數(shù)而變化，由init、final確定。經(jīng)過多次對比實(shí)驗，最終將init取為0.7，將final取為0.3，用于動態(tài)控制算法初始時和結(jié)束時樽海鞘領(lǐng)導(dǎo)者和追隨者的數(shù)量，更好地平衡算法的全局搜索和局部開發(fā)能力。

2.5 領(lǐng)導(dǎo)者位置更新

這里設(shè)計的改進(jìn)領(lǐng)導(dǎo)者位置部分主要包含交叉操作Cross1、Cross2。交叉操作產(chǎn)生于領(lǐng)導(dǎo)者個體和食物源個體中，有利于平衡算法的全局搜索和局部搜索。食物源個體的選擇：在排序值為1且擁擠度最大的個體中隨機(jī)選擇。Cross1為領(lǐng)導(dǎo)者個體與食物源個體部分的交叉，Cross2為領(lǐng)導(dǎo)者個體與食物源個體部分的交叉操作。具體操作如圖2～3所示。

圖2 Cross1操作演示

Cross1，如圖2所示，1和2分別為領(lǐng)導(dǎo)者和食物源的部分，表示需求點(diǎn)和救援倉庫的分配關(guān)系，隨機(jī)生成的交叉點(diǎn)為3，將1和2點(diǎn)位3后的部分互換，交換彼此的需求點(diǎn)和救援倉庫分配策略，得到子代11和22，新產(chǎn)生的子代個體不僅可以學(xué)習(xí)食物源個體的分配策略，也可能會產(chǎn)生更優(yōu)質(zhì)量的解。

Cross2，將領(lǐng)導(dǎo)者個體與食物源個體的部分進(jìn)行交叉，部分表示配送順序策略。如圖3所示，1為領(lǐng)導(dǎo)者的部分，2為食物源的部分，作為2個父代，隨機(jī)生成的交叉點(diǎn)為3、6，選擇兩點(diǎn)位之間的基因，在另一個父代上找到這些基因的位置，保持未選中的基因不變，按照選中的基因在另一父代上的出現(xiàn)順序，交換2個父代個體中基因的位置，生成11、22。通過這種交叉方式可以學(xué)習(xí)到食物源個體的配送順序策略，在增強(qiáng)種群多樣性的同時也可能產(chǎn)生更優(yōu)解。

圖3 Cross2操作演示

將領(lǐng)導(dǎo)者個體和食物源個體的部分與部分進(jìn)行交叉操作，并隨機(jī)從子代[1111]或[2222]中選擇一個作為新的領(lǐng)導(dǎo)者個體的位置。

2.6 追隨者位置更新

對于追隨者位置的更新，為了更好地對解進(jìn)行局部開發(fā)，設(shè)計了交叉操作Cross3和鄰域搜索，包括單點(diǎn)變異、兩點(diǎn)交換、單點(diǎn)插入、逆轉(zhuǎn)及倉庫棄用。

1）交叉算子。在所有父代中隨機(jī)選擇1個樽海鞘個體，與當(dāng)前追隨者個體進(jìn)行交叉。個體的部分和部分分別是2種不同的交叉方式，其中部分交叉與領(lǐng)導(dǎo)者位置更新時部分的交叉方式Cross1相同，部分的交叉方式Cross3具體操作如圖4所示。

Cross3，追隨者個體和父代樽海鞘個體的部分進(jìn)行交叉，交叉后的個體可以學(xué)到父代個體的配送策略。交叉操作步驟：1為隨機(jī)樽海鞘個體的部分，2為當(dāng)前追隨者的部分，作為2個父代，在1上隨機(jī)生成的交叉點(diǎn)1，選擇位置1上的元素1，其次找到2中位置1的元素2，再回到1中找到元素2所在的位置2，然后找到2中2位置上的元素3。重復(fù)之前操作，直到形成一個環(huán)，環(huán)中的所有元素的位置即是最后選中的位置。如圖4所示，位置2→7→4→2形成一個循環(huán)，將1中相應(yīng)位置的元素替換到2中，形成新的個體11。

圖4 Cross3操作演示

2）鄰域搜索。為了進(jìn)一步提高樽海鞘算法在離散優(yōu)化問題中的尋優(yōu)能力，增強(qiáng)種群的多樣性，結(jié)合LRP問題的特點(diǎn)選擇5種鄰域搜索機(jī)制對解進(jìn)行局部開發(fā)，以相同的概率對解進(jìn)行搜索。鄰域搜索針對部分（需求點(diǎn)與倉庫歸屬關(guān)系）和部分（需求點(diǎn)的配送順序）進(jìn)行搜索。針對部分有5種領(lǐng)域搜索操作，即單點(diǎn)變異、兩點(diǎn)交換、插入、逆轉(zhuǎn)、倉庫棄用。針對部分有3種鄰域搜索操作，即兩點(diǎn)交換、插入、逆轉(zhuǎn)。

單點(diǎn)變異：隨機(jī)選取一個位置，將其對應(yīng)的所屬倉庫進(jìn)行變異操作。如圖5所示，隨機(jī)選中變異的位置是3，原本為4號倉庫服務(wù)，標(biāo)記為紅色，隨機(jī)生成新的1號倉庫為需求點(diǎn)配送物資。

兩點(diǎn)交換：隨機(jī)選取位置和，將其對應(yīng)的所屬倉庫的序號互換。如圖6所示，隨機(jī)選中的2個位置為3、6，標(biāo)記為紅色，將3號需求點(diǎn)和6號需求點(diǎn)所歸屬倉庫互換，形成新的解。原來3號需求點(diǎn)由4號倉庫服務(wù)，6號需求點(diǎn)由3號倉庫服務(wù)，交換之后，3號需求點(diǎn)由3號倉庫服務(wù)，6號需求點(diǎn)由4號倉庫服務(wù)。

單點(diǎn)插入：隨機(jī)選取部分的2個位置和，如圖7所示，用紅色標(biāo)記。將位置的編碼插到的編碼之前，得到新的解。如圖7所示，隨機(jī)選中的位置為3和7，此時3到6號需求點(diǎn)所屬倉庫編碼都向前移動，都發(fā)生了相應(yīng)的改變。

逆轉(zhuǎn)：隨機(jī)選取部分的2個位置和然后將和之間（包括和）的所有序號逆向排序。如圖8所示，選取的2個隨機(jī)位置為3和7，將其中的序號[4 1 3 3 1]進(jìn)行逆向排序，得到新的解。

倉庫棄用：在開放的倉庫索引里隨機(jī)選擇一個棄用倉庫索引，并將其換成任意合理的倉庫索引。具體操作如圖9所示，選中的棄用倉庫索引為4，關(guān)閉4號倉庫，開放2號倉庫，得到新的解。

同理，對于部分有3種搜索操作，操作步驟與相似，針對部分的操作改變了需求點(diǎn)的順序，針對不同部分有不同的領(lǐng)域操作，在增強(qiáng)種群多樣性的同時，也可能產(chǎn)生更優(yōu)解。

圖5 單點(diǎn)變異

圖6 兩點(diǎn)交換

圖7 單點(diǎn)插入

圖8 逆轉(zhuǎn)

圖9 倉庫棄用

2.7 精英保留機(jī)制

在ISSA算法中引入NSGA-Ⅱ的精英保留策略。將位置更新前的父代種群與位置更新后的子代種群合并為一個新種群，然后采用2.3節(jié)的方法，重新計算新種群的非支配排序等級和擁擠度，選取前p（種群數(shù)量）個最優(yōu)的個體為下一代樽海鞘種群。精英保留機(jī)制有利于保留種群中的優(yōu)良個體，提高種群的整體進(jìn)化水平。

2.8 算法步驟

這里提出的改進(jìn)多目標(biāo)樽海鞘算法步驟如下。

1）初始化算法參數(shù)，種群規(guī)模p、算法最大迭代次數(shù)max，樽海鞘個體長度。

2）種群初始化，采用貪心算法與隨機(jī)生成的方式生成p個樽海鞘個體作為初始可行解。

3）對種群進(jìn)行非支配排序和擁擠度的計算，評估每個個體的目標(biāo)函數(shù)值，并給每個個體排序。根據(jù)排序確定領(lǐng)導(dǎo)者和追隨者。分配領(lǐng)導(dǎo)者和追隨者種群，根據(jù)式（21）更新，前p個的樽海鞘個體為領(lǐng)導(dǎo)者，剩余個體為追隨者。

4）確定食物源個體，在排序值最低且擁擠度最大的個體中隨機(jī)選擇一個作為食物源個體。

5）根據(jù)2.5節(jié)的策略更新領(lǐng)導(dǎo)者位置，根據(jù)2.6節(jié)的策略更新追隨者位置。

6）精英保留機(jī)制將更新后的種群與父代種群合為一個大種群，并對其進(jìn)行非支配排序，根據(jù)排序值選擇前p個為新的種群。

7）判斷迭代次數(shù)是否達(dá)到最大迭代次數(shù)max，如果達(dá)到，算法終止，如果未達(dá)到則返回步驟3），循環(huán)操作直到達(dá)到終止條件。

3 算例分析

采用Matlab 2016b，算法運(yùn)行環(huán)境采用AMD Ryzen 5 5600H 處理器、3.30 GHz、內(nèi)存16.0 GB、64位Windows 10操作系統(tǒng)。為了測試所提算法的性能，使用改進(jìn)后的標(biāo)準(zhǔn)算例庫中的部分算例及根據(jù)實(shí)際情景生成的一組算例進(jìn)行求解，并對結(jié)果進(jìn)行分析。

3.1 實(shí)驗設(shè)計

借鑒Prins等[17]提出的標(biāo)準(zhǔn)LRP算例數(shù)據(jù)，所有參數(shù)均無量綱。由于算例庫中無時間窗及道路安全性的相關(guān)數(shù)據(jù)，不完全適合于文中的問題。為了模擬真實(shí)情景，對算例中不同規(guī)模的部分?jǐn)?shù)據(jù)進(jìn)行適當(dāng)改進(jìn)后，生成文中的數(shù)據(jù)集。在生成的數(shù)據(jù)集中，車容量在{70, 150}之間，倉庫容量在{300, 1 000}之間。其中，20-5-1的軟時間窗最晚到達(dá)時間在[50, 300]之間生成，20-5-1b在[100, 400]之間生成，其余算例在[250, 500]之間生成。救援倉庫需要在突發(fā)災(zāi)害后短時間內(nèi)開放，需要耗費(fèi)很多的人力、物力，因此將倉庫的開放成本設(shè)置較高，設(shè)置為8 000，將救援車輛的啟用成本設(shè)置為1 000，單位運(yùn)輸成本設(shè)置為100。同時將違反時間窗口的懲罰值設(shè)置為相對較高的1 000，每個點(diǎn)之間的道路安全性參數(shù)在(0, 1)之間隨機(jī)生成。測試算例的相關(guān)信息如表1所示。

表1 測試算例相關(guān)信息

Tab.1 Relative data of test examples

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

設(shè)置改進(jìn)多目標(biāo)樽海鞘算法的相關(guān)參數(shù)，每個個體的長度=2，表示需求點(diǎn)的數(shù)量。為了準(zhǔn)確評估各個參數(shù)對ISSA算法性能的影響，這里采用參數(shù)調(diào)優(yōu)策略。通過大量實(shí)驗，根據(jù)算法迭代效果設(shè)置max=300。以下主要對種群規(guī)模p進(jìn)行分析。為了測試種群規(guī)模p對算法性能的影響，利用算例20-5-1、50-5-1b進(jìn)行實(shí)驗對比。在保持其他參數(shù)恒定的情況下，設(shè)置種群為0.5、、1.5、2、2.5、3（為算例中的需求點(diǎn)數(shù)量），將實(shí)驗運(yùn)行20次，取帕累托前沿所有非支配解的平均值。

3.3 算例結(jié)果分析

對于每個算例，采用改進(jìn)樽海鞘算法（ISSA）和原始樽海鞘優(yōu)化（SSA）算法都運(yùn)行20次，計算所有非支配解的經(jīng)濟(jì)成本（1）、時間成本（2）、道路安全性（3）的平均值，并找出所有非支配解中的最優(yōu)解，結(jié)果見表3。此外，以50-5-1b為例，給出ISSA和SSA求解的三維帕累托前沿圖，結(jié)果如圖10所示。

由表3可知，ISSA算法在各算例中求解的1、2、3的最優(yōu)值和平均值均優(yōu)于SSA算法。從圖10可以很清晰地看出，ISSA求出的帕累托最優(yōu)解數(shù)量更多，并且帕累托面位于SSA求解出的帕累托面上方，說明改進(jìn)后樽海鞘算法的性能更加優(yōu)越，能得到更滿意的解。

表2 種群數(shù)量p對解的影響

Tab.2 Effect of parameter Np on solution

表3 算法結(jié)果對比

Tab.3 Comparison of algorithm results

圖10 ISSA和SSA求解的Pareto Optimal Surface (50-5-1b)

3.4 仿真實(shí)驗分析

為了進(jìn)一步驗證文中模型和ISSA算法的有效性，選取上海市進(jìn)行模擬實(shí)驗，從上海市的地圖中選取25個醫(yī)院作為需求點(diǎn)，以火車站和機(jī)場作為候選倉庫點(diǎn)。在選取這些點(diǎn)時，綜合考慮了需求點(diǎn)的地理位置和緊急需求等因素。候選倉庫點(diǎn)和需求點(diǎn)的具體信息見表4、5。需求點(diǎn)與候選倉庫點(diǎn)之間的距離根據(jù)經(jīng)緯度坐標(biāo)計算得到。兩點(diǎn)之間的距離根據(jù)式（22）計算。

表4 候選倉庫坐標(biāo)

Tab.4 Candidate depot coordinates

為了驗證算法及算法各個步驟的有效性，將未引入領(lǐng)導(dǎo)者?追隨者自適應(yīng)權(quán)重因子、未加入鄰域搜索及未采用精英保留機(jī)制的算法記為ISSA-Ⅰ、ISSA-Ⅱ、ISSA-Ⅲ，將其運(yùn)行10次，將它產(chǎn)生的最佳目標(biāo)值（best）和最佳目標(biāo)值的平均值（mean）與文中提出的ISSA算法結(jié)果進(jìn)行對比，見表6。可以看出，算法求得的經(jīng)濟(jì)成本、時間成本及道路安全性都存在明顯差距，這是由路徑規(guī)劃不同所致。從各個算法求得的平均值來看，采用ISSA算法求得的經(jīng)濟(jì)成本、時間成本及道路安全性都優(yōu)于其他算法，說明在進(jìn)行一系列改進(jìn)后，在一定程度上提高了算法的尋優(yōu)能力。

表5 需求點(diǎn)信息

Tab.5 Information of demand point

表6 算法改進(jìn)對比

Tab.6 Algorithm improvement comparison

表7 具有代表性的有效解（=4,=25）

Tab.7 Representative valid solutions (m=4, n=25)

表8 理想解的路徑規(guī)劃

Tab.8 Route planning for the ideal solution

4 結(jié)論

針對突發(fā)災(zāi)害后的應(yīng)急物資選址?路徑問題進(jìn)行了研究，為了達(dá)到配送物資的經(jīng)濟(jì)性、時效性及運(yùn)輸過程中的安全性，建立了一個在災(zāi)后及時響應(yīng)的環(huán)境下具有時間窗口的多目標(biāo)選址?路徑模型，以經(jīng)濟(jì)成本最小化、時間懲罰成本最小化及道路安全性最大化為目標(biāo)，為決策救援倉庫選址及救援車輛的配送路線提供方案。為了有效解決多目標(biāo)優(yōu)化問題，根據(jù)LRP模型的特點(diǎn)及基本樽海鞘算法（SSA）的搜索機(jī)制提出了一種改進(jìn)的樽海鞘算法（ISSA），并與未改進(jìn)的基本樽海鞘算法進(jìn)行對比?；诙鄠€算例的分析比較，證實(shí)了文中所提模型和算法的科學(xué)性和有效性，在求解質(zhì)量上具有一定的優(yōu)越性。最后將ISSA用于實(shí)際背景下的算例中，驗證了算法的有效性。同時，在權(quán)衡多個目標(biāo)的狀況下，提供了一種方案可供決策者找到較滿意的解。

此研究也存在一些不足，如只考慮了確定性方案，而現(xiàn)實(shí)中信息的滯后性會導(dǎo)致很多信息不確定。后續(xù)會進(jìn)一步考慮不確定情況對結(jié)果的影響，更加全面地考慮災(zāi)后物資調(diào)度的規(guī)劃與決策。

[1] ZHONG S P, CHENG R, JIANG Y, et al. Risk-Averse Optimization of Disaster Relief Facility Location and Vehicle Routing under Stochastic Demand[J]. Transportation Research Part E: Logistics and Transportation Review, 2020, 141: 102015.

[2] VAHDANI B, VEYSMORADI D, NOORI F, et al. Two-Stage Multi-Objective Location-Routing-Inventory Model for Humanitarian Logistics Network Design under Uncertainty[J]. International Journal of Disaster Risk Reduction, 2018, 27: 290-306.

[3] ZHANG B, LI H, LI S G, et al. Sustainable Multi-Depot Emergency Facilities Location-Routing Problem with Uncertain Information[J]. Applied Mathematics and Computation, 2018, 333: 506-520.

[4] WEI X W, QIU H X, WANG D J, et al. An Integrated Location-Routing Problem with Post-Disaster Relief Distribution[J]. Computers & Industrial Engineering, 2020, 147: 106632.

[5] SHEN L, TAO F M, SHI Y H, et al. Optimization of Location-Routing Problem in Emergency Logistics Considering Carbon Emissions[J]. International Journal of Environmental Research and Public Health, 2019, 16(16): 2982.

[6] 劉長石, 彭怡, 寇綱. 震后應(yīng)急物資配送的模糊定位-路徑問題研究[J]. 中國管理科學(xué), 2016, 24(5): 111-118.

LIU C S, PENG Y, KOU G. Research on Fuzzy Location-Routing Problem in Post-Earthquake Delivery of Relief Materials[J]. Chinese Journal of Management Science, 2016, 24(5): 111-118.

[7] PRODHON C, PRINS C. A Survey of Recent Research on Location-Routing Problems[J]. European Journal of Operational Research, 2014, 238(1): 1-17.

[8] LIU B J, ZHU L, REN J L. Intelligent Optimization Algorithm Grid Computing-Based Applications[J]. Journal of Intelligent & Fuzzy Systems, 2020, 39(4): 5201-5211.

[9] MIRJALILI S, GANDOMI A H, MIRJALILI S Z, et al. Salp Swarm Algorithm: A Bio-Inspired Optimizer for Engineering Design Problems[J]. Advances in Engineering Software, 2017, 114: 163-191.

[10] 張達(dá)敏, 陳忠云, 辛梓蕓, 等. 基于瘋狂自適應(yīng)的樽海鞘群算法[J]. 控制與決策, 2020, 35(9): 2112-2120.

ZHANG D M, CHEN Z Y, XIN Z Y, et al. Salp Swarm Algorithm Based on Craziness and Adaptive[J]. Control and Decision, 2020, 35(9): 2112-2120.

[11] ALJARAH I, HABIB M, FARIS H, et al. A Dynamic Locality Multi-Objective Salp Swarm Algorithm for Feature Selection[J]. Computers & Industrial Engineering, 2020, 147: 106628.

[12] 李志杰, 王力, 張習(xí)恒. 改進(jìn)樽海鞘群優(yōu)化K-means算法的圖像分割[J]. 包裝工程, 2022, 43(9): 207-216.

LI Z J, WANG L, ZHANG X H. Improved Salp Swarm Optimization K-Means Algorithm for Image Segmentation[J]. Packaging Engineering, 2022, 43(9): 207-216.

[13] SALGOTRA R, SINGH U, SINGH S, et al. Self-Adaptive Salp Swarm Algorithm for Engineering Optimization Problems[J]. Applied Mathematical Modelling, 2021, 89: 188-207.

[14] NAUTIYAL B, PRAKASH R, VIMAL V, et al. Improved Salp Swarm Algorithm with Mutation Schemes for Solving Global Optimization and Engineering Problems[J]. Engineering with Computers, 2022, 38(5): 3927-3949.

[15] ZHANG H L, CAI Z N, YE X J, et al. A Multi-Strategy Enhanced Salp Swarm Algorithm for Global Optimization[J]. Engineering with Computers, 2022, 38(2): 1177-1203.

[16] DEB K, PRATAP A, AGARWAL S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-Ⅱ[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[17] PRINS C, PRODHON C, CALVO R W. Solving the Capacitated Location-Routing Problem by a GRASP Complemented by a Learning Process and a Path Relinking[J]. 4OR, 2006, 4(3): 221-238.

Improved Salp Swarm Algorithm for Solving Multi-objective Emergency Location Routing Problem with Time Windows

XU Fan,MA Liang,ZHANG Huizhen*,CHEN Xi

(School of Management, University of Shanghai for Science & Technology, Shanghai 200093, China)

In order to ensure timely and efficient delivery of emergency resources to disaster areas, the work aims to construct a multi-objective optimization model for the multi-objective emergency location routing problem by taking into account the time windows of the disaster area and road safety during resources transportation, with the objectives of minimizing economic costs, time penalty costs, and maximizing road safety. At the same time, an improved salp swarm algorithm is designed to solve the problem, in order to verify the feasibility of the model and the effectiveness of the algorithm. Based on the characteristics of the model, the algorithm was improved by combining random generation and greedy algorithm to generate initial solutions. The position update operation of the original algorithm was improved by crossover operators and neighborhood search operators. The elite retention strategy of NSGA-Ⅱ was introduced to improve the performance of the algorithm. After test of multiple examples, this algorithm could quickly obtain a cluster of Pareto solutions and was compared with the original salp swarm algorithm. The improved algorithm had better performance. For the emergency location routing problem of timely response after a disaster, the improved salp swarm algorithm has certain advantages, and can provide decision-makers with satisfactory solutions based on the preferences of multiple objectives. It has a certain reference value for the field of emergency location routing problems.

location routing problem; emergency resources; time windows; improved salp swarm algorithm

TP301.6；TB485.3

A

1001-3563(2024)05-0220-10

10.19554/j.cnki.1001-3563.2024.05.027

2023-05-11

國家自然科學(xué)基金（72101149）；教育部人文社會科學(xué)基金（21YJC630087）；國家外國專家項目（G2023013029）