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

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

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

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

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

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

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

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

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

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

1 問(wèn)題描述和模型建立

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

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

1.2 符號(hào)與變量

1.3 模型建立

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

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

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

2.1 解的表示

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

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

圖1 解的表示

2.2 初始種群的生成

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

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

2.3 快速非支配排序

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

式中：為目標(biāo)函數(shù)的數(shù)量；C為第個(gè)個(gè)體的擁擠度；1、–1為個(gè)體沿著帕累托邊界的2個(gè)相鄰個(gè)體；F()為個(gè)體的第個(gè)目標(biāo)函數(shù)值。在所有個(gè)體中，排序值更靠前和擁擠度更大的個(gè)體更優(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)者比例過(guò)低，跟隨者的比例過(guò)高，可能導(dǎo)致算法無(wú)法充分進(jìn)行全局搜索而陷入局部最優(yōu)解。在算法迭代后期，跟隨者的數(shù)量過(guò)少，導(dǎo)致局部搜索不充分，會(huì)影響搜索的精度。

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

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

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

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

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

圖2 Cross1操作演示

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

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

圖3 Cross2操作演示

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

2.6 追隨者位置更新

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

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

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

圖4 Cross3操作演示

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

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

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

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

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

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

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

圖5 單點(diǎn)變異

圖6 兩點(diǎn)交換

圖7 單點(diǎn)插入

圖8 逆轉(zhuǎn)

圖9 倉(cāng)庫(kù)棄用

2.7 精英保留機(jī)制

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

2.8 算法步驟

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

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

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

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

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

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

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

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)。為了測(cè)試所提算法的性能，使用改進(jìn)后的標(biāo)準(zhǔn)算例庫(kù)中的部分算例及根據(jù)實(shí)際情景生成的一組算例進(jìn)行求解，并對(duì)結(jié)果進(jìn)行分析。

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

Tab.1 Relative data of test examples

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

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

3.3 算例結(jié)果分析

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

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

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

Tab.2 Effect of parameter Np on solution

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

Tab.3 Comparison of algorithm results

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

3.4 仿真實(shí)驗(yàn)分析

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

表4 候選倉(cāng)庫(kù)坐標(biāo)

Tab.4 Candidate depot coordinates

為了驗(yàn)證算法及算法各個(gè)步驟的有效性，將未引入領(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)行對(duì)比，見(jiàn)表6?？梢钥闯觯惴ㄇ蟮玫慕?jīng)濟(jì)成本、時(shí)間成本及道路安全性都存在明顯差距，這是由路徑規(guī)劃不同所致。從各個(gè)算法求得的平均值來(lái)看，采用ISSA算法求得的經(jīng)濟(jì)成本、時(shí)間成本及道路安全性都優(yōu)于其他算法，說(shuō)明在進(jìn)行一系列改進(jìn)后，在一定程度上提高了算法的尋優(yōu)能力。

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

Tab.5 Information of demand point

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

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é)論

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

此研究也存在一些不足，如只考慮了確定性方案，而現(xiàn)實(shí)中信息的滯后性會(huì)導(dǎo)致很多信息不確定。后續(xù)會(huì)進(jìn)一步考慮不確定情況對(duì)結(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] 劉長(zhǎng)石, 彭怡, 寇綱. 震后應(yīng)急物資配送的模糊定位-路徑問(wèn)題研究[J]. 中國(guó)管理科學(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

國(guó)家自然科學(xué)基金（72101149）；教育部人文社會(huì)科學(xué)基金（21YJC630087）；國(guó)家外國(guó)專(zhuān)家項(xiàng)目（G2023013029）