基于鯨魚群優(yōu)化算法的帶Sigmoid滿意度應(yīng)急車輛調(diào)度問題①

范 祥,葉春明,曹 磊

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

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

1 應(yīng)急情景描述與數(shù)學(xué)模型

1.1 情景描述

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

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

式中,β是正的時(shí)間敏感系數(shù),參數(shù)β越大,函數(shù)的敏感度越高,即對應(yīng)于受災(zāi)點(diǎn)對救援時(shí)間的敏感度高.

1.2 模型建立

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

圖1 Sigmoid時(shí)間滿意度函數(shù)示意圖

建立的數(shù)學(xué)模型如下:

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

2 基于鯨魚群算法的應(yīng)急調(diào)度算法

2.1 標(biāo)準(zhǔn)鯨魚群算法

鯨魚群算法是通過模擬自然界中鯨魚進(jìn)行捕食等群體活動時(shí),通過超聲波與同伴進(jìn)行交流的行為特性而發(fā)展來的一種新型的元啟發(fā)式算法.當(dāng)鯨魚發(fā)現(xiàn)了食物源,它會發(fā)出聲音(超聲波)通知附近的其它鯨魚關(guān)于食物質(zhì)量好壞和數(shù)量多少的信息.因此,每只鯨魚將收到大量來自附近鯨魚的通知信息,然后根據(jù)這些信息移動到適當(dāng)?shù)牡胤綄ふ沂澄?

介紹鯨魚群算法產(chǎn)生候選種群之前,首先介紹鯨魚發(fā)出超聲波的相對強(qiáng)度.并從數(shù)學(xué)角度對鯨魚群算法的優(yōu)化機(jī)理作如下描述.

定義1.鯨魚發(fā)出超聲波的相對強(qiáng)度為

其中,ρ0指超聲波源的強(qiáng)度,根據(jù)大量實(shí)驗(yàn)的經(jīng)驗(yàn),對幾乎所有的案例,ρ0都可以設(shè)置為2.η為衰減系數(shù),它取決于介質(zhì)的物理化學(xué)性質(zhì)和超聲波本身的屬性(如超聲波頻率),對于函數(shù)優(yōu)化問題,影響η的的因素與目標(biāo)函數(shù)的特征有關(guān),包括函數(shù)的維度、定義域和峰值分布.因此在對不同的函數(shù)進(jìn)行優(yōu)化時(shí),需要設(shè)置適當(dāng)?shù)摩侵?

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

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

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

圖2 鯨魚群算法流程

2.2 混沌鯨魚群優(yōu)化算法

2.2.1 算法原理

本文采用邏輯自映射函數(shù)對鯨魚群算法的尋優(yōu)化過程進(jìn)行擾動,可提高算法的效率.邏輯自映射函數(shù)的數(shù)學(xué)表達(dá)式為式(14):

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

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

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

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

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

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

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

2.3 適應(yīng)度值計(jì)算

為了計(jì)算鯨魚個體的適應(yīng)度值,綜合考慮z1和z2兩個目標(biāo),給出計(jì)算公式如下:

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

2.4 算法步驟

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

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

Step 2.在搜索區(qū)域內(nèi)隨機(jī)初始化鯨魚的空間位置,根據(jù)所處位置計(jì)算鯨魚的目標(biāo)函數(shù)值,將其作為各自的最大超聲波強(qiáng)度ρ0.

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

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

Step 5.根據(jù)式(17)動態(tài)收縮搜索區(qū)域.

Step 6.根據(jù)移動后的鯨魚位置,重新計(jì)算各鯨魚的最大超聲波強(qiáng)度.

Step 7.當(dāng)滿足最大搜索次數(shù)或達(dá)到搜索精度時(shí),轉(zhuǎn)至Step 8,否則轉(zhuǎn)Step 3,進(jìn)行下一次搜索.

Step 8.輸出全局最優(yōu)個體與全局極值點(diǎn),算法結(jié)束.

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

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

3.1 算例設(shè)計(jì)

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

表1 8個受災(zāi)點(diǎn)實(shí)驗(yàn)數(shù)據(jù)

表2 14個受災(zāi)點(diǎn)實(shí)驗(yàn)數(shù)據(jù)

表3 25個受災(zāi)點(diǎn)實(shí)驗(yàn)數(shù)據(jù)

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

表4 算法尋優(yōu)結(jié)果分析

圖4 CWSA救援車輛最優(yōu)行駛路徑

圖5 SA救援車輛最優(yōu)行駛路徑

圖6 WSA救援車輛最優(yōu)行駛路徑

圖7 迭代對比(8×3)

圖8 迭代對比(14×4)

圖9 迭代對比(25×5)

4 結(jié)束語

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

表5 25個受災(zāi)點(diǎn)最優(yōu)方案對比