基于改進螢火蟲優化算法的傷員救援車輛調度

朱惠如， 葉春明

(上海理工大學 管理學院， 上海 200093)

0 引 言

各種重大自然災害和意外災害發生后，受傷人數在短時間內迅速增加且分布廣泛，與受傷人數相比，救護車明顯短缺，限時組織應急救援行動，合理區分傷員受傷程度，優化傷員救援車輛調度，在有限時間內最大程度地將傷員送至醫療中心，提升傷員救援效率，減少人員傷亡，顯得尤為重要[1]。

當前車輛調度模型所采用的優化方法有最優化算法和智能優化算法。最優化算法也稱為精確算法，包括分支定界算法、Dijkstra 算法、時間依賴網絡( Time Dependent Network，TDN) 算法以及動態規劃算法等；智能優化算法包括遺傳算法、模擬退火算法、禁忌搜索算法、蟻群算法等。大規模的車輛調度問題屬于一種難度極大的組合優化問題，最優化算法求解速度極慢[2]。現有文獻表明，群智能優化算法——螢火蟲算法在求解調度問題時，算法步驟簡單，易于實現，且全局搜索能力更強[3]。但是在求解救援車輛調度問題時存在不足，如對于初始解分布的依賴，迭代過程收斂速度慢且求解精度較低，同時系統易陷入局部最優解。針對這些問題，通過對螢火蟲算法的進一步研究，提出了基于慣性權重的螢火蟲算法及基于混沌算法的螢火蟲算法。雖然性能要優于標準螢火蟲優化算法，但算法的收斂速度及局部尋優能力等方面仍有待提高。

為獲得更優的傷員救援車輛調度優化結果，將標準螢火蟲優化算法從多種群學習機制和高斯變異規則兩種優化內容著手，實現更加符合傷員救援特殊情況下的車輛調度。

1 傷員救援車輛調度數學模型

1.1 問題描述

某重大突發災害的爆發使多個地點均受到不同程度影響，根據指揮中心預測確定各災點位置、需求量及受災程度，附近某大型醫療救援中心有K輛傷員荷載量一定的相同的救援車，車輛從該醫療中心出發，對各災點傷員實施應急救援并載上傷員一同駛回醫療中心，且每個災點只被一輛車救援，目標是最小化救援時間和救援路程。

1.2 數學模型

1.2.1 模型假設

為了簡化實際救援過程中的復雜的約束，假設條件如下：

(1)災害影響的受災點位置、受災害的影響程度、實際交通流量和待救傷員數量已知；

(2)救援車輛類型相同且荷載人數唯一并已知；

(3)每個災點都被救援，且只有一次；

(4)受災害影響不同災點處的傷員的在途可堅持時間不同；

(5)各救援車輛從某救援中心出發，最終回到該救援中心。

1.2.2 模型的構建

針對應急救援對于時效性的強需求，可構建如下以救援時間最少和救援路徑最短為目標的雙目標調度模型，目標函數式(1)和式(2)表示最小化所有救援車輛總行駛時間和總路程：

(1)

(2)

其中，K為醫療中心救援車輛總量，任一救援車輛用k表示(k=1,2,…,K)；nk為第k輛車歷經并救援受災點的個數(nk=0表示未使用第k輛車)；rki代表路線集合Rk中第i個途徑的受災點；rk0表示車輛從醫療中心出發；rk(nk+1)表示車輛回到醫療中心；Tij為車輛從受災點i到j的行駛時間；Dij代表受災點i到j的距離(i,j=0,1,…,N)，i,j=0代表醫療中心。

其中約束條件如下：

(2)每輛車在行駛路徑上歷經受災點的個數限制0≤nk≤N，N表示受災點總個數；

(4)車輛抵達前后兩受災點處實施救援的時間關聯表達式，如式(3)所示：

srk(i-1)+uTrk(i-1)·qrk(i-1)+Trk(i-1)rki=srki

(3)

其中，uTi表示在受災點i處安排每位傷員上車所耗時間；

(5)救援車輛到達不同受災點的時間窗約束，si表示救援車輛抵達受災點i的時刻：srki≤bi，[0,bi]表示救援車輛須到達受災點i的時間窗；

(6)對各受災點處傷員在途可堅持時間的約束ci：srk(nk+1)-srki≤ci；

(7)只有當第k輛車至少歷經1個受災點時才參與救援，此時取sign(nk-1)=1，否則認為該車輛未實施應急救援，如式(4)所示：

(4)

(8)所有車輛行駛路線集合如式(5)所示：

Rk={rk0，rk1，…，rki，…，rknk，rk(nk+1)}

(5)

(9)車輛行駛時間的預測如式(6)所示：

(6)

其中，Vij表示車輛從i到j的通行速度。

2 改進螢火蟲算法設計

2.1 標準螢火蟲算法

2.1.1 算法原理

把搜索空間中每個可行解看作一個螢火蟲個體，搜索過程可以看作螢火蟲之間的吸引，將數學模型最優結果的求解模擬成螢火蟲個體向最優螢火蟲個體位置的移動。最優解的特性是使得目標函數值最小或者最大，處于最佳位置的螢火蟲個體所表現出的特性是其攜帶的熒光素量最多。

2.1.2 算法數學描述

初始時刻，每一只螢火蟲均攜帶相同數量的熒光素l0，隨機的分布在搜索空間V中，xi(t)代表第i只螢火蟲在第t次迭代時在V中所處的位置，則第i只螢火蟲在第t次迭代后所攜帶的熒光素的值可由適應度函數f(xi(t))求得。通過每次迭代時更新螢火蟲的位置，得到迭代后每個螢火蟲所攜帶的熒光素的數量。一般的，基本螢火蟲算法(GSO)優化算法包括以下5個步驟：

(1)個體所攜帶的熒光素的濃度求解：通過適應度函數f(xi(t))可求得螢火蟲處于位置xi(t)時所攜帶的熒光素的量，之后利用公式(7)即可求出個體所攜帶的熒光素的濃度：

li(t)=(1-ρ)li(t-1)+γf(xi(t))

(7)

其中，ρ表示熒光素消失率，γ表示熒光素更新率，ρ，γ∈[0,1]。

(8)

其中，‖xi(t)‖表示螢火蟲個體間的距離。

(3)螢火蟲個體i向個體j移動的概率Pij(t)；利用公式(9)計算t次迭代時鄰域集合Ni(t)內移動的概率Pij(t)：

(9)

(4)螢火蟲個體i位置的更新：利用公式(10)計算螢火蟲移動后的位置：

(10)

其中，s表示螢火蟲個體移動步長。

(5)螢火蟲個體的動態決策域半徑的更新：利用公式(11)更新動態決策半徑：

β(nt-|Ni(t)|)}}

(11)

其中，rs表示螢火蟲個體的最大感知域半徑；nt表示螢火蟲個體鄰域的閾值；β表示動態決策域半徑的更新率。

2.2 螢火蟲算法的缺陷及改進

震后傷員救援車輛調度屬于離散型問題，而基本螢火蟲算法(GSO)主要用于實數、連續型組合優化問題的求解，無法有效更新此類離散型的救援路徑序列。本文采用離散化處理的基礎上，為避免算法過早收斂和陷入局部最優，進一步采用了多種群學習機制和高斯變異規則來對算法進行優化。

2.2.1 多種群學習機制

種群是指同一時間生活在一定區域內的所有個體。在種群內，個體之間相互競爭、適者生存；在多個種群中，種群間相互學習、共同進步，本文結合多種群思想與標準螢火蟲算法，將螢火蟲算法分為以下兩個階段：

階段1以數量為標準，將標準螢火蟲算法中的螢火蟲個體分為數量相同的多個螢火蟲種群，并對每個螢火蟲種群設置不同的參數，以對比每個種群的優化效果；

階段2求解階段1劃分的不同螢火蟲種群的最優值與最差值，并用前一種群的最優值替換為下一種群的最差值，根據替換得到的最優值重新定位各螢火蟲種群中螢火蟲個體的位置，通過對所有種群最優解的比較即可得到全局最優解。

2.2.2 高斯變異

在螢火蟲算法的迭代過程中，螢火蟲的收斂速度會隨著密度的增高而減慢，后期易陷入局部極值點的困境。為解決該問題，本文在螢火蟲個體的位置更新過程中引進高斯變異。過程如式(12)：

xi=xi·[1+k·N(0,1)]

(12)

其中，xi表示第i只螢火蟲當前的狀態；k是在區間(0，1)之間的遞減變量；N(0,1)為服從均值為1，方差為1的正態分布的隨機向量。

2.2.3 編碼與解碼

螢火蟲算法只能用于連續領域中相關問題的解決，針對離散組合優化問題，本文對每個螢火蟲個體進行離散化處理。在螢火蟲算法的解空間中，將螢火蟲個體位置向量xi={xi1,xi2,…,xin}的每個分量表示為一個受災點，其中每個分量均取自于(0，1)區間的隨機數，再將分量按照升序編碼方式重新排列，排列后將分量所在位置和分量所代表的災點的被救援順序關聯起來，以明確各災點在救援路徑中的被救順序。

2.3 算法步驟

改進后的螢火蟲算法實現步驟如下：

(2)計算螢火蟲個體適應度值，并更新其熒光素值，并將各子群中的最佳適應度值記為fibest，計入子群記錄板；

(3)依據螢火蟲移動概率公式選擇下一步移動的對象；

(4)更新移動后螢火蟲個體的位置、鄰域半徑以及熒光素值；

(5)查詢各子群記錄板。當子群內有連續3次最優解及其位置沒有更新時，則可判斷為該子種群內的螢火蟲已陷入局部極值點[4]，此時需判斷各子群fibest是否連續3次不變化或連續變化幅度很小(小于μ，μ表示高斯變異的控制參數，數值在10-4～10-6之間)。若是，則算法陷入局部極值范圍內，此時必須開始進行變異操作，轉(6)，否則，轉(7)；

(6)利用高斯變異對該子種群添加擾動，令螢火蟲跳出局部搜索空間；

(7)不同種群間相互學習，選擇前一個種群的最優解替代下一個種群的最差解；

(8)若達到迭代次數，則輸出結果，否則返回第2步。

改進后的算法流程如圖1所示。

圖1 改進螢火蟲優化算法流程圖

3 算例

3.1 算例背景

現假設某地突發大規模自然災害，導致20個受災點有不同程度人員傷亡，位于中心的醫院分派5個救援車隊分別將20個受災點的傷員接回醫院接受救治，每個車隊最多可以運載13個傷員，且一次運輸的最大行程是60 km，車輛的行駛速度統一為40 km/h。隨機產生待救點坐標、傷員人數、受災程度等信息，并根據受災程度級別為每個受災點設置不同的時間窗和傷員在途可堅持時間窗，受災等級1～受災等級4表示受災害影響程度越來越小，見表1。現利用新建立的模型合理協調各救援車輛行駛路徑，使傷員得到高效迅速的救援。

表1 各受災點信息及時間窗設置

3.2 求解結果

表2 算例求解結果

圖2 改進螢火蟲算法優化過程

3.3 結果對比

利用調度中經典遺傳算法對本文算例求解，設置交叉概率、變異概率分別為0.9、0.1，求解10次后選擇最優值的尋優過程如圖4所示，對比結果見表3。由表3可知本文提出的改進螢火蟲算法在求解本文算例時優化速度更快。

圖3 救援車輛行駛路徑

圖4 遺傳算法尋優過程

表3 算法結果對比

4 結束語

災后傷員救援車輛是有限的，且傷員最佳救援時機受傷情輕重影響，因此選擇最優的車輛調度方案，才能確保傷員有效及時地救治。

本文對改進的螢火蟲優化算法和遺傳算法的尋優過程進行了對比，得到如下結論：

(1)通過引入多種群結構，每只螢火蟲可以在各群內不斷優化，最終得到多條最優路徑，不同的種群間可以交流經驗和共享信息，增加了種群多樣性，提高了算法優化性能；

(2)在算法迭代時，對螢火蟲個體位置進行高斯變異，拓展螢火蟲的搜索范圍，避免陷入局部極值點，提高了全局搜索性能；

(3)在迭代次數相同的情況下( 如T=100) ，本文改進螢火蟲算法能夠迅速趨穩，收斂速度更快；同時整體救援時間大大縮短，幅度高達618 min，救援效率提升了18.66%。