基于GA-PSO混合算法的應急無人機投送站選址優化研究

摘要：針對應急救援任務的緊急性、時間敏感性和不確定性，為提高救援工作的質量和效率，可以采用無人機聯合投放應急物資的方式。然而，無人機受航程、載重量等因素的限制，其投送站點的選址就顯得尤為關鍵。以無人機應急物資投送站和受災區域構成的二級網絡為研究對象，充分考慮需求的模糊性，采用遺傳算法和粒子群相結合的算法進行求解，最后以鄭州市X區為例，并對比遺傳算法和粒子群算法的求解效率，驗證所提模型和算法的有效性和可行性。

關鍵詞：應急物流設施；模糊需求；選址模型；應急無人機投送站

中圖分類號：X913.4" " " 文獻標識碼：A" " " "文章編號：2096-1227（2024）09-0001-03

現階段，隨著城市化步伐的加快、自然資源的開發、氣候的劇烈變化以及生態的失衡，自然災害的發生頻率比以往要高[1]。當自然災害發生時，往往導致道路交通大面積癱瘓，使救援工作難以有效開展。這時無人機作為應急救援設備，能輔助完成搜索、投放物資等工作[2]。然而，無人機受航程、載重、天氣等影響，其投送站的選址就顯得尤為重要[3]。

1 國內外研究現狀

目前，常見的應急選址模型包括：P-中心[4]、K-均值[5]、多目標優化模型[6]等。羅太波等[7]在考慮道路通行容量和通行速度的背景下，以最大完成時間和總完成時間最小化為目標函數，研究路圖上有堵塞時間成本的避難點選址問題。吳瑩等[4]考慮時間、救援關系、成本三方面的限制，建立最小化最大救援時間的P-中心選址模型。宋英華等[8]從公平性、效率性、均衡性視角，構建最小化加權疏散距離、最小化可達性差異的多目標避難場所選址模型。另外，由于實際救援活動中存在需求、時間、路徑等不確定性，因此，也有學者在不確定環境下研究應急選址問題。如朱云辰等[9]設計了基于核酸檢測結果形成城市應急設施的模糊選址范圍，得出“小集聚-大分散”空間規律。Dujuan Wang等[10]在不確定需求和設施中斷情況下，建立一種分布式魯棒優化模型，來優化配送中心和備用倉庫的位置。楊廣映等[11]提出了一種基于二型模糊集理論的應急設施選址方法，以區域人口密度量化應急資源需求程度，構建選址集最大覆蓋模型。閆森和齊金平[12]使用三角模糊數表示應急物資需求的不確定性，同時考慮應急救援成本和應急救援時間兩個目標建立應急物流設施選址模型。

2 算法設計

2.1" 模糊處理

受災點數量：使用三角模糊數來表示受災點數量的模糊需求，即（a，b，c）。其中，a和c分別表示受災點數量的下限和上限，b表示受災點數量的最可能值。隸屬度函數為：

投送點建設成本：使用高斯模糊數來表示，即（m，s）。其中，m表示修建成本的期望值，s表示修建成本的標準差。隸屬度函數為：

投送點的運營成本：使用梯形模糊數來表示，即（a，b，c，d）。其中，a和d分別表示運營成本的下限和上限，b和c分別表示運營成本的最小和最大可能值。隸屬度函數為：

2.2" 粒子群算法初始化

求解適應值：將投送點的位置作為變量，無人機到達受災點的總時間作為目標函數，投送點的位置范圍作為約束條件。具體地定義如下的數學模型：

式中：x＝（x1，x2，x3，x4）——投送點的位置坐標向量；

d＝（d1，d2，…，d8）——受災點的數量向量，用模糊數的中心值代替；

b＝（b1，b2，…，b8）——受災點的位置矩陣，每一行表示一個受災點的坐標；

V1，V2——無人機的速度常數；

a＝（a1，a2，…，an）——投送點的位置矩陣，每一行表示一個投送點的坐標；

n——受災點的數量。

目標函數f（x）表示無人機到達受災點的總時間，約束條件表示無人機的位置必須在投送點的位置范圍內。

更新粒子的速度和位置：記錄每個微粒的歷史最優位置和全局最優位置，這里，用兩個（a﹢b）×a的矩陣來存儲每個微粒的歷史最優位置和全局最優位置，以及相應的目標函數值。

根據速度更新公式和位置更新公式，更新每個微粒的速度和位置，使其向個體最優解和社會最優解靠近。速度更新公式如下：

式中：vik（t）——第i個投送點是否建立變量在第t次迭代時的速度；

pik（t）——第i個投送點是否建立變量在第t次迭代時的歷史最優位置；

gik（t）——第i個投送點是否建立變量在第t次迭代時的全局最優位置；

w——慣性權重；

c1、c2——學習因子；

r1、r2——[0，1]之間的隨機數。

類似地，可以得到第i個投送點前往第j個受災點救援變量在第t﹢1次迭代時的速度：

位置更新公式如下：

2.3" 遺傳算法設計

使用二進制編碼，即將每個解用一個長度為9的二進制向量表示，每位對應一個候選位置，如果該位為1，則表示在該位置建設投送站點，否則不建設。例如[1，0，0，1，0，0，1，0，1]表示在第1、4、7、9個位置建設投送站點。該模型的目標函數是最小化投送站點的總成本，包括建設成本和運行成本。根據模型的定義，總成本是一個模糊數。

式中：xk——一個二進制變量，表示是否在第k個位置建設投送站點；

ck——第k個位置的建設成本；

ok——第k個位置的運行成本，都是三角模糊數。

可以用Matlab的fuzzyarith函數來進行模糊數的加法和乘法運算，得到總成本的模糊數表示。

2.4" 粒子群算法與遺傳算法結合設計

兩個算法是通過一個混合參數來進行結合的，該參數表示每次迭代中使用粒子群算法的概率。如果隨機數小于該參數，則使用粒子群算法更新粒子的位置和速度，否則使用遺傳算法對粒子進行雜交和變異。這樣，粒子群算法和遺傳算法可以交替地對解空間進行搜索，從而提高了解的多樣性和質量。

3 算例分析

3.1" 算例介紹

以鄭州市X區為例，由于無人機航程有限，假設投送站覆蓋范圍最大不超過5km，使用速度與時間的乘積來表示覆蓋范圍。使用三角模糊數來表示受災點數量的模糊需求，其中隸屬度為0的點表示受災點數量為0，隸屬度為1的點表示受災點數量為其左邊界和右邊界的平均值。

為了確定目前X區投送站的最優位置，需要獲取X區所有投送站的數量和經緯度坐標。為了尋找投送站最優數量和最優值才能最大程度覆蓋X區范圍內的受災點的問題，需要計算每個投送站的覆蓋范圍，見圖1。確定每個受災點可以被哪些投送站覆蓋，并計算出每個受災點到覆蓋它的投送站的最短時間。

3.2" 算法對比

分別采用遺傳算法（GA）、粒子群算法（PSO）和兩者結合的混合算法（HGA-PSO）來求解，并比較了三種算法的性能，詳見圖2。實驗結果表明，GA-PSO混合算法具有最快的收斂速度和最好的解質量。

4 結束語

本文以無人機應急物資投送站到受災區域構成的二級網絡為研究對象，考慮需求不確定的投送站選址優化問題，由于無人機受到載重、航程等因素的限制，因此，假設5km為覆蓋范圍，設計了一種遺傳算法和粒子群算法相結合的混合優化算法，并結合鄭州市X區的具體數據，來驗證該算法在求解效率具有良好的效果。

參考文獻

[1]Pradeep Kumar Tarei，Kapil Manohar Gumte，Jayshree Prtnaik，Rina Suryani Oktari.Analysing Barriers to Humanitarian Logistics for Distributing Relief Aid in Pre-and Post-Disaster Situations[J].International Journal of Disaster Risk Reduction，2024，104：104388.

[2]高凱，耿娜，張馨月，等.基于PSO的載荷受限的災后救援任務分配問題[J].重慶師范大學學報（自然科學版），2021，38（4）：10-20.

[3]趙桂紅，張騰飛.一種應急物資無人機末端配送任務分配方法[J].物流技術，2023，42（4）：47-52.

[4]吳瑩，陸愈實.基于P-中心模型的城市軌道交通線網應急救援站選址研究[J].城市軌道交通研究，2024，27（9）：80-86.

[5]張民波，鐘子逸，閆瑾，等.考慮生物危險源擴散的疫區應急物資調配模型[J].中國安全科學學報，2023，33（11）：206-213.

[6]陳靖，景林浩，謝曉君，等.城市應急資源儲備庫選址的多目標優化模型[J].工業安全與環保，2023，49（1）：63-67.

[7]羅太波，鄧潔，李紅梅.考慮道路通行能力差異的多應急避難點選址模型及算法[J].管理工程學報，2024，38（5）：153-163.

[8]宋英華，韓保帥，郭晨.考慮洪澇災害風險的縣域應急避難場所選址模型[J].中國安全科學學報，2024，34（4）：191-198.

[9]朱云辰，程明駿，鄭昕文，等.基于優化第三代非支配排序遺傳算法的城市應急設施模糊選址[J].浙江大學學報（工學版），2024，58（9）：1832-1843.

[10]Dujuan Wang，Jian Peng，Hengfei Yang，et al. Distributionally Robust Location-Allocation with Demand and Facility Disruption Uncertainties in Emergency Logistics[J].Computers amp; Industrial Engineering，2023，184：109617.

[11]楊廣映，門金坤，蔣鵬，等.基于二型模糊集理論的應急設施選址方法[J].大連理工大學學報，2020，60（6）：654-662.

[12]閆森，齊金平.考慮需求不確定的多級應急物流設施選址研究[J].運籌與管理，2022，31（9）：7-13.