改進樽海鞘算法求解帶時間窗的應急選址路徑問題

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

改進樽海鞘算法求解帶時間窗的應急選址路徑問題

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

（上海理工大學 管理學院，上海 200093）

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

選址?路徑問題；應急物資；時間窗；改進樽海鞘算法

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

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

現有研究針對應急LRP問題重點考慮的是經濟因素和時間因素，而實際情境中災后設施與道路可能會遭到一定破壞，在山區等環境惡劣地區這些因素會對救援人員的生命造成威脅，因而應該考慮物資配送過程中的安全性。文中引入道路安全性系數，構建一個多目標帶時間窗的災后選址?路徑模型。

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

1 問題描述和模型建立

1.1 問題描述與模型假設

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

1.2 符號與變量

1.3 模型建立

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

2 求解多目標LRP問題的改進樽海鞘優化算法

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

2.1 解的表示

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

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

圖1 解的表示

2.2 初始種群的生成

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

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

2.3 快速非支配排序

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

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

2.4 領導者-跟隨者自適應調整

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

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

計算改進后的領導者?跟隨者，每代中領導者數量等于p,跟隨者數量等于(1–)p，p為種群數量，自適應權重因子的計算見式（21）。

式中：為當前迭代次數;max為最大迭代次數；init為控制參數的初始值；final為控制參數的終值。自適應權重因子在算法迭代中隨著迭代次數而變化，由init、final確定。經過多次對比實驗，最終將init取為0.7，將final取為0.3，用于動態控制算法初始時和結束時樽海鞘領導者和追隨者的數量，更好地平衡算法的全局搜索和局部開發能力。

2.5 領導者位置更新

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

圖2 Cross1操作演示

Cross1，如圖2所示，1和2分別為領導者和食物源的部分，表示需求點和救援倉庫的分配關系，隨機生成的交叉點為3，將1和2點位3后的部分互換，交換彼此的需求點和救援倉庫分配策略，得到子代11和22，新產生的子代個體不僅可以學習食物源個體的分配策略，也可能會產生更優質量的解。

Cross2，將領導者個體與食物源個體的部分進行交叉，部分表示配送順序策略。如圖3所示，1為領導者的部分，2為食物源的部分，作為2個父代，隨機生成的交叉點為3、6，選擇兩點位之間的基因，在另一個父代上找到這些基因的位置，保持未選中的基因不變，按照選中的基因在另一父代上的出現順序，交換2個父代個體中基因的位置，生成11、22。通過這種交叉方式可以學習到食物源個體的配送順序策略，在增強種群多樣性的同時也可能產生更優解。

圖3 Cross2操作演示

將領導者個體和食物源個體的部分與部分進行交叉操作，并隨機從子代[1111]或[2222]中選擇一個作為新的領導者個體的位置。

2.6 追隨者位置更新

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

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

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

圖4 Cross3操作演示

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

單點變異：隨機選取一個位置，將其對應的所屬倉庫進行變異操作。如圖5所示，隨機選中變異的位置是3，原本為4號倉庫服務，標記為紅色，隨機生成新的1號倉庫為需求點配送物資。

兩點交換：隨機選取位置和，將其對應的所屬倉庫的序號互換。如圖6所示，隨機選中的2個位置為3、6，標記為紅色，將3號需求點和6號需求點所歸屬倉庫互換，形成新的解。原來3號需求點由4號倉庫服務，6號需求點由3號倉庫服務，交換之后，3號需求點由3號倉庫服務，6號需求點由4號倉庫服務。

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

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

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

同理，對于部分有3種搜索操作，操作步驟與相似，針對部分的操作改變了需求點的順序，針對不同部分有不同的領域操作，在增強種群多樣性的同時，也可能產生更優解。

圖5 單點變異

圖6 兩點交換

圖7 單點插入

圖8 逆轉

圖9 倉庫棄用

2.7 精英保留機制

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

2.8 算法步驟

這里提出的改進多目標樽海鞘算法步驟如下。

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

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

3）對種群進行非支配排序和擁擠度的計算，評估每個個體的目標函數值，并給每個個體排序。根據排序確定領導者和追隨者。分配領導者和追隨者種群，根據式（21）更新，前p個的樽海鞘個體為領導者，剩余個體為追隨者。

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

5）根據2.5節的策略更新領導者位置，根據2.6節的策略更新追隨者位置。

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

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

3 算例分析

采用Matlab 2016b，算法運行環境采用AMD Ryzen 5 5600H 處理器、3.30 GHz、內存16.0 GB、64位Windows 10操作系統。為了測試所提算法的性能，使用改進后的標準算例庫中的部分算例及根據實際情景生成的一組算例進行求解，并對結果進行分析。

3.1 實驗設計

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

表1 測試算例相關信息

Tab.1 Relative data of test examples

3.2 參數設置

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

3.3 算例結果分析

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

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

表2 種群數量p對解的影響

Tab.2 Effect of parameter Np on solution

表3 算法結果對比

Tab.3 Comparison of algorithm results

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

3.4 仿真實驗分析

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

表4 候選倉庫坐標

Tab.4 Candidate depot coordinates

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

表5 需求點信息

Tab.5 Information of demand point

表6 算法改進對比

Tab.6 Algorithm improvement comparison

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

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

表8 理想解的路徑規劃

Tab.8 Route planning for the ideal solution

4 結論

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

此研究也存在一些不足，如只考慮了確定性方案，而現實中信息的滯后性會導致很多信息不確定。后續會進一步考慮不確定情況對結果的影響，更加全面地考慮災后物資調度的規劃與決策。

[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] 劉長石, 彭怡, 寇綱. 震后應急物資配送的模糊定位-路徑問題研究[J]. 中國管理科學, 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] 張達敏, 陳忠云, 辛梓蕓, 等. 基于瘋狂自適應的樽海鞘群算法[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] 李志杰, 王力, 張習恒. 改進樽海鞘群優化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

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