基于鯨魚群優化算法的帶Sigmoid滿意度應急車輛調度問題①

范 祥,葉春明,曹 磊

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

針對突發公共事件后應急車輛調度問題,國內外學者做了較多研究[1–5],文獻[1]針對多地區同時發生災害時,需及時展開救援工作問題,設計了改進遺傳算法對所建模型求解,并做了多組仿真實驗,結果表明,改進算法在滿足救援物資時間上取得了較大提高.文獻[2]考慮災害發生后受損道路對車輛調度的影響,根據道路實際狀況建立了運輸車輛調度模型;文獻[3]針對大規模突發事件下應急車輛調度問題,用物資未滿足度的形式對災民的損失進行量化,構建最小化災民損失和應急車輛調度費雙目標的混合整數規劃模型.文獻[4]針對災后需求不確定問題,假設需求服從正態分布,構建了帶時間窗的應急車輛調度模型,設計了兩階段遺傳算法,最后通過實例驗證了模型與算法的有效性.然而,學者在建模時默認受災點對于期待被救援的時間要求不存在差異,本文考慮到不同程度受災點對救援時間的緊迫性不同,引入Sigmoid時間滿意函數,構建應急車輛調度模型.車輛調度問題作為NP問題的一種,一些經典的算法(動態規劃、分支定界等)在尋優速度上效果欠佳,因此需要尋找一種在可接受的時間范圍內能夠求得問題最優解或近似最優解的方法.有研究表明[6],鯨魚群算法(Whale Swarm algorithm,WSA)在求解高維函數優化問題上具有一定優勢.鑒于鯨魚群算法局部搜索部分是一個隨機搜索的過程,局部尋優能力欠佳,本文設計了基于混沌序列的搜索算子,為了提高算法搜索效率,又對搜索區域進行動態化處理,進而提出了本文改進的混沌鯨魚群算法.

1 應急情景描述與數學模型

1.1 情景描述

假定某地突發大規模公共事件,現有一個應急救援中心,該救援中心有同種車型的救援車輛若干,負責對多個受災點進行救援物資的運輸工作,且受災點的受災程度不同.為了確保救援任務的順利進行,現需要對救援車輛的路線進行合理安排,要求使得總配送任務的平均時間滿意度較高以及行駛距離較低(成本較低).

本文通過借鑒文獻[7]關于地震發時被困人員生存概率函數以及文獻[8]關于突發大規模疫情后城市救援有效度函數,引入時間滿意度函數來評價救援效果.綜合考慮,采用了降指數Sigmoid時間滿意度函數(見圖1)對救援效果評價,這里假設降指數Sigmoid時間滿意度函數是通過Tangent Sigmoid函數截取和翻轉得到,見公式(1).

式中,β是正的時間敏感系數,參數β越大,函數的敏感度越高,即對應于受災點對救援時間的敏感度高.

1.2 模型建立

建模之前作幾方面假設:各受災點與救援中心的位置已知;單個受災點的需求量不大于單車最大容量,且不允許出現車輛超載現象;各受災點的物資需求量已知且為同一類物品;計算中只考慮單程配送問題,即只研究救援中心到受災點這一配送過程,但救援車輛完成配送后需要返回救援中心;救援中心同時對多個受災點進行救援,每輛車只進行一次救援,無缺貨發生.

圖1 Sigmoid時間滿意度函數示意圖

建立的數學模型如下:

式(2)表示最大化所有受災點的平均時間滿意度;式(3)表示最小化救援活動中車輛行駛的距離;式(4)表示對于救災點i的救援任務由車輛k來完成,不允許分車分批運輸;式(5)和式(6)為了確保到達受災點的救援車輛必須去下一地點;式(7)表示車輛到達救災點j處的時間sj等于到達上一救災點的時間si加上逗留時間ti再加上i到j運輸時間tij;式(8)和式(9)表示兩個變量間的關系,其中式(8)表示給受災點j實施救援的車輛k來自i處,即前序節點的唯一性,式(9)表示到達受災點i處的救援車輛為車輛k,即到達某個受災點的車輛唯一性;式(10)表示規定每次救援任務均從救援中心出發且出發時刻記為0,即s0=0;式(11)定義了受災點i對救援時間的滿意度.

2 基于鯨魚群算法的應急調度算法

2.1 標準鯨魚群算法

鯨魚群算法是通過模擬自然界中鯨魚進行捕食等群體活動時,通過超聲波與同伴進行交流的行為特性而發展來的一種新型的元啟發式算法.當鯨魚發現了食物源,它會發出聲音(超聲波)通知附近的其它鯨魚關于食物質量好壞和數量多少的信息.因此,每只鯨魚將收到大量來自附近鯨魚的通知信息,然后根據這些信息移動到適當的地方尋找食物.

介紹鯨魚群算法產生候選種群之前,首先介紹鯨魚發出超聲波的相對強度.并從數學角度對鯨魚群算法的優化機理作如下描述.

定義1.鯨魚發出超聲波的相對強度為

其中,ρ0指超聲波源的強度,根據大量實驗的經驗,對幾乎所有的案例,ρ0都可以設置為2.η為衰減系數,它取決于介質的物理化學性質和超聲波本身的屬性(如超聲波頻率),對于函數優化問題,影響η的的因素與目標函數的特征有關,包括函數的維度、定義域和峰值分布.因此在對不同的函數進行優化時,需要設置適當的η值.

鯨魚在捕食的過程中,如果距離“最近且較優”的鯨魚較近,鯨魚將積極地向它隨機移動;反之,鯨魚會消極地隨機移動,因此經過一段時間的迭代就會形成一些子種群.每只鯨魚都隨機游向“最近且較優”的鯨魚來尋找更好的食物,由于隨機運動是鯨魚行為的一個重要特征,故本文采用超聲波衰減的隨機移動規則來探索獲得新位置的迭代公式,如公式(13)所示.

定義2.鯨魚x被吸引向鯨魚y移動的位置更新公式由以公式(13)決定.

算法實現優化的過程是:先將鯨魚群體隨機散布在解空間中,每一頭鯨魚所處的位置不同發出的超聲波強度也不一樣,對鯨魚進行初始化;通過公式(12)比較,鯨魚積極地向超聲波強度(“最近且較優”)的鯨魚移動;根據公式(13)來計算跟新后的位置,這樣通過多次迭代之后,所有個體將會向超聲波強度最高的鯨魚聚集,從而實現尋優的目的.其中,在每一次迭代前,判斷算法是否達到預先設計的最大迭代次數,若達到,算法終止,否則繼續迭代.鯨魚群算法流程如圖2所示.

圖2 鯨魚群算法流程

2.2 混沌鯨魚群優化算法

2.2.1 算法原理

本文采用邏輯自映射函數對鯨魚群算法的尋優化過程進行擾動,可提高算法的效率.邏輯自映射函數的數學表達式為式(14):

從上式中可以看出,當迭代初始值不為0時,就會發生混沌,映射的定義域為(–1,1),且不為0和0.5.d表示搜索的空間維度.混沌優化的過程為:在搜索過程的某個時刻,鯨魚個體i位于D維空間內的某一位置.根據邏輯自映射函數的性質,首先,按照式(15)將個體空間的每一維映射到(–1,1)上.其次,按照式(14)進行載波操作,從而獲得了新的新混沌變量序列.最后,將獲得的混沌變量序列按照式(16)變換到原解空間,在此尋優過程中,如果發現更優的解,則將這個最新位置代替鯨魚i原先的位置.否則,進入新一輪混沌搜索,直到搜索次數達到預先設定的次數.

其中,上述兩式中的aid和bid分別表示鯨魚個體i第d維變量的搜索上下界.

為了平衡運算時間與求解精度,本文沒有將全部的鯨魚個體進行混沌化,選取了部分鯨魚作為精英個體進行混沌運算.與此同時,為了使得搜索效率提高,本文使搜索區域進行動態化處理,使算法在初期搜索范圍廣一些,以免過早陷入局部最優;在后期搜索范圍小一些,使得收斂速度加快,用式(17)來動態收縮搜索區域.

2.2.2 基于問題的鯨魚編碼與譯碼

鯨魚群算法是一種基于種群的全局智能尋優方法,搜索空間中的每一頭鯨魚都對應尋優空間中的一個解,且對應一個目標函數值.每頭鯨魚的位置向量X是一個2N維的向量,前半部分N維向量用來定義受災點所使用的車輛,每一維隨機數取(0,M–1)之間整數(向上取整),M表示車輛數,后半部分N維向量用來定義車輛的救援順序,每一維隨機數取(0,1)之間的實數,對于同一輛車救援多個受災點,救援順序由這N維基因位置上的數值決定,數值大的先救援,數值相等時,近左優先.假設有8個受災點,3輛救援車輛,某一鯨魚的向量表示如圖3.

圖3 鯨魚群算法編碼及解碼過程

前面8個基因位使得受災點對應分配一輛救援車輛,8個受災點對應的救援車輛分別為1、2、1、2、3、1、2、3,從而可以得出車輛1救援受災點1、3、6,救援順序則根據后面L維向量基因位的數值大小,跟據上文所述,車輛1的救援安排為0-1-6-3-0.同理,車輛2的救援安排為0-4-2-7-0,車輛3的救援安排為0-5-8-0.

2.3 適應度值計算

為了計算鯨魚個體的適應度值,綜合考慮z1和z2兩個目標,給出計算公式如下:

其中,ε為一極小正數,防止分母為零;λ為決策偏好因子,取值(0,0.5),這樣取一方面考慮了應急物流時間緊迫性的特點,使得對時間滿意度賦予了較高的權重,另一方面又兼顧了應急物流的弱經濟性.適應度函數前半部分為與成本有關的函數,后半部分為與時間效用有關的函數,分別表示救援成本和救援有效度對適應度函數的影響.從上述公式可以看出,在距離函數z2較小、救援滿意度函數z1較大時適應度值越大.與一般的多目標加權求和適應度函數不同,本文適應度函數考慮到不同量級的目標函數對適應度值影響程度的差異性,因此在后項中引入調節因子,以均衡z1和z2對適應度函數的影響.

2.4 算法步驟

綜上所述,混沌鯨魚群算法的基本步驟如下:

Step 1.初始化算法基本參數:設置鯨魚數目Q,衰減系數η,精英群體比例n%,混沌搜索迭代次數H,最大搜索次數Iter_MAX或搜索精度.

Step 2.在搜索區域內隨機初始化鯨魚的空間位置,根據所處位置計算鯨魚的目標函數值,將其作為各自的最大超聲波強度ρ0.

Step 3.根據式(12)計算群體中鯨魚的相對超聲波ρ,根據式(13)更新鯨魚的空間位置.

Step 4.對鯨魚個體進行評估,選取性能最好的n%的個體作為精英,采用混沌優化策略進行優化;選取性能最差的n%的個體,重新隨機產生新的鯨魚個體予以替代.

Step 5.根據式(17)動態收縮搜索區域.

Step 6.根據移動后的鯨魚位置,重新計算各鯨魚的最大超聲波強度.

Step 7.當滿足最大搜索次數或達到搜索精度時,轉至Step 8,否則轉Step 3,進行下一次搜索.

Step 8.輸出全局最優個體與全局極值點,算法結束.

3 實驗仿真及分析

本文實驗環境為:PC計算機處理器主頻2.3 GHz,酷睿i7 3610QM處理器,內存8 GB,在Win10系統下的Matlab 2010a 的編程軟件.針對本文所設計的突發公共事件下的應急車輛調度問題進行對比實驗.鯨魚群算法中所涉及的各種參數設置目前均沒有嚴格的理論依據,故本文所設置的參數值都是經過反復實驗最終確定如下:設置鯨魚數目Q=100,衰減系數η=1.5,超聲波源的強度ρ0=2,精英群體比例20%,混沌搜索迭代次數50,最大搜索次數Iter_MAX=200.模擬退火算法是一種發展較成熟的啟發式算法,學者們利用此方法求解車輛調度問題取得了一定成果[9,10],本文擬采用模擬退火算法進行對比實驗,相關參數設置為:初始溫度T0=1000,下降比率p=0.95,終止溫度Tend=10,內循環次數Nnei=200.

3.1 算例設計

現假設某地區發生地震,政府部門需從一個應急救援中心向多個應急救援待救點進行救援物資的配送,救援中心有多輛配送車輛可以利用.由于缺少真實的實驗數據,本文構建了三組實驗數據(見表1、表2、表3),針對三組實驗分別采用載貨量為80、130和160單位的車輛配送,每組實驗僅采用一種車型且均以75 KM/H勻速行駛.本文考慮四個受災等級(災情1-災情4),數字越大表示受災點對救援時間的要求越高,sigmoid時間滿意度函數需要設置四個不同的β值,分別設置為0.1、0.2、0.3、0.5,EL設為1H,即救援車輛在1小時之內到達受災點的滿意度為100%,超過1小時后會隨著時間的推移,不同等級的受災點的滿意度會相應降低.

表1 8個受災點實驗數據

表2 14個受災點實驗數據

表3 25個受災點實驗數據

3.2 實驗結果及分析

對三個算例分別采用模擬退火SA、鯨魚群算法WSA和混沌鯨魚群算法CWSA各獨立求解20次,對三組方案的求解效果進行比較,求解結果如表4所示.由于篇幅有限,文章僅列出了三種算法針對25個受災點最優實驗結果,如最優行駛方案對比(表5)、最優行駛路徑(圖4–圖6)以及三種規模迭代對比(圖7–圖9).

從表4可以看出,在處理較小規模車輛調度情況下,三種算法處理能力差距較小,SA求解的穩定性上相對有優勢、但不明顯.隨著求解規模的擴大,改進的鯨魚群算法效果較明顯.相比原始鯨魚群算法,無論在滿意度與行駛距離上都得到了的改進,且求解結果較為穩定.

針對25個受災點的救援問題,表5給出了三種算法最優尋優結果,可以看出:三種算法給出解的救援滿意度均較好;CWSA算法相比另外兩種算法,救援成本較低.綜上,針對基本鯨魚群算法的改進策略是有效的.此外,對于14個受災點的應急救援問題,三種算法求得的最優解滿意度較低,這可能是由案例本身決定的.救援車輛數目的選取對受災點的滿意度存在影響,當增加救援車輛的數目時,可以提高救援滿意度.

表4 算法尋優結果分析

圖4 CWSA救援車輛最優行駛路徑

圖5 SA救援車輛最優行駛路徑

圖6 WSA救援車輛最優行駛路徑

圖7 迭代對比(8×3)

圖8 迭代對比(14×4)

圖9 迭代對比(25×5)

4 結束語

本文通過分析大規模突發公共事件后特征,引入時間滿意度函數,建立了平均滿意度與行駛距離為目標的數學模型,針對鯨魚群算法局部搜索能力較弱,設計了改進的鯨魚群算法對模型進行求解.通過實驗仿真,驗證了模型及改進算法的有效性.應急救援具有復雜性、動態性、難解性等特點,建立不同的應急車輛調度模型應對不同救援場景,并設計更為有效的算法將是我們今后研究的重點.

表5 25個受災點最優方案對比