考慮公平性的面向多災(zāi)點需求應(yīng)急資源調(diào)度

杜雪靈，孟學(xué)雷，楊 貝，湯 霖

(蘭州交通大學(xué) 交通運輸學(xué)院，蘭州 730070)(*通信作者電子郵箱mxl@mail.lzjtu.cn)

0 引言

突發(fā)事件發(fā)生后，人們的正常生活受到影響，生存所必需的資源遭到破壞，需要制定相應(yīng)的應(yīng)急資源調(diào)度方案，在第一時間完成對事故發(fā)生點的資源供給，這種在應(yīng)急條件下研究的資源調(diào)度問題被稱為應(yīng)急資源調(diào)度(Emergence Resource Scheduling, ERS)。在鐵路突發(fā)事件發(fā)生后的應(yīng)急指揮工作中，應(yīng)急資源調(diào)度處于核心關(guān)鍵位置，制定正確合理的應(yīng)急資源調(diào)度方案是重要的應(yīng)急指揮工作之一。

關(guān)于單目標(biāo)優(yōu)化的應(yīng)急資源調(diào)度問題，文獻[1]基于時空網(wǎng)絡(luò)的概念，以最小化運輸成本為優(yōu)化目標(biāo)，解決了大規(guī)模、多商品、有時間窗的多模態(tài)網(wǎng)絡(luò)流問題，提出了兩種啟發(fā)式算法，而實際救援過程中，商品數(shù)量和救援車數(shù)量是不確定的。文獻[2]提出強震后初期搜救的主要目標(biāo)是盡量減少死亡人數(shù)，并引入了動態(tài)優(yōu)化模型，該模型可計算與響應(yīng)相關(guān)的不同任務(wù)的資源性能和效率，求解算法為模擬退火算法。文獻[3]考慮到救護車可能處于忙期的隨機特性，建立了超立方體覆蓋模型，該模型的目標(biāo)是確定每一個時間群集的最小救護車數(shù)量和位置，在需求模式發(fā)生重大變化的同時滿足覆蓋要求，求解算法為禁忌搜索算法。文獻[4]假設(shè)物資擁有量小于車容量，建立了動態(tài)車輛調(diào)度模型，目的是避免延誤，提高設(shè)備利用率；但該模型對于現(xiàn)實的突發(fā)性災(zāi)害具有一定的局限性，沒有將旅行時間和地點群集相結(jié)合進行優(yōu)化。文獻[5]以機會成本最小化為優(yōu)化目標(biāo)，建立了緊急救援資源調(diào)度模型，采用模擬退火算法求解模型，但該模型忽略了救援車輛需求的不確定性。文獻[6]結(jié)合博弈論理論，建立面向多災(zāi)點需求的博弈調(diào)度模型，采用改進的蟻群算法求解，實現(xiàn)調(diào)度“虛擬成本”的最小化，“虛擬成本”的影響因素有災(zāi)情的嚴(yán)重程度、平均速度、響應(yīng)時間和距離。文獻[7]建立了多資源時間-成本調(diào)度模型，以滿足資源需求量為前提，以時間為約束，使總調(diào)度成本最低，采用改進的進化規(guī)劃算法驗證模型；但該模型較簡單，較難滿足大規(guī)模突發(fā)事件的應(yīng)急管理需求。文獻[8]研究了高速公路應(yīng)急救援的動態(tài)模式，目的是使總成本最小化，采用Dijkstra算法驗證模型，但文中的救援時效矩陣是在假設(shè)速度一定，并將最短距離矩陣作為阻抗矩陣的情況下得到的，而實際救援過程中車輛速度會隨路況發(fā)生變化。

關(guān)于多目標(biāo)優(yōu)化的應(yīng)急資源調(diào)度問題，文獻[9]設(shè)計了多時段動態(tài)應(yīng)急資源調(diào)度問題的多目標(biāo)優(yōu)化模型，利用基于分解的多目標(biāo)進化算法求解模型；但該研究假設(shè)車輛的數(shù)量和運輸能力是不受限制的，對實際路網(wǎng)問題考慮較少。文獻[10]建立了多約束整數(shù)線性規(guī)劃模型，以并行方式分配多個應(yīng)急資源，使應(yīng)急響應(yīng)時間最短、應(yīng)急資源成本最小；但該研究提出的啟發(fā)式算法忽略了響應(yīng)時間的約束。文獻[11]以未滿足率最小化和未疏散人員數(shù)最小化為優(yōu)化目標(biāo)，構(gòu)建了多目標(biāo)魯棒優(yōu)化模型，采用結(jié)構(gòu)化魯棒模型的求解方法求解模型；而旅行時間、能力、需求等網(wǎng)絡(luò)數(shù)據(jù)是不確定的，文中沒有對網(wǎng)絡(luò)結(jié)構(gòu)進行優(yōu)化。文獻[12]研究了最短路線、最短時間及服務(wù)水平，以時間為約束建立模型，用改進的遺傳算法、改進的蟻群算法分別求解；但兩種算法在改進的過程中沒有充分考慮到道路及交通情況對算法結(jié)果的影響。文獻[13]考慮了評估災(zāi)害點的災(zāi)害情況和資源需求產(chǎn)生的誤差，將災(zāi)害地區(qū)信息運用改進后的專家打分法量化成災(zāi)情因子，模型的目標(biāo)是延誤時間最小化、成本最小化，求解算法為逐步法，但專家打分法使得災(zāi)情因子具有一定的主觀性。文獻[14]研究了區(qū)域路網(wǎng)交通應(yīng)急資源調(diào)度的優(yōu)化，以總響應(yīng)延遲時間和總預(yù)計響應(yīng)時間加權(quán)之和最小為優(yōu)化目標(biāo)，在資源不確定的條件下建立模型，求解算法為遺傳算法；但該研究以響應(yīng)時間最短為主要目標(biāo)，對資源調(diào)度成本考慮較少。文獻[15]在確保滿足救援能力需求的前提下，對設(shè)備調(diào)度問題進行了研究，目標(biāo)是救援結(jié)束時間最小、調(diào)度費用最小，并設(shè)計了兩階段啟發(fā)式算法。

上述文獻的研究目標(biāo)大多為成本最小[1,5-8,10,12-13,15]、死亡人數(shù)最少[2]、延誤最小[4]、時間最短[10,12-13,15]、未滿足率最小[11]等，對本文有著重要啟發(fā)，但突發(fā)事件發(fā)生之初，供應(yīng)點的資源量往往不能同時滿足多個受災(zāi)點的需求，此時會造成距離供應(yīng)點較遠(yuǎn)的受災(zāi)點獲得的資源量較少甚至沒有的情況，但很少有文獻考慮到多個受災(zāi)點的公平性。本文結(jié)合“軟時間窗”的概念，將救援公平性最大和調(diào)度總成本最小作為優(yōu)化目標(biāo)，構(gòu)建了面向多災(zāi)點需求的多目標(biāo)應(yīng)急資源調(diào)度模型。

1 多目標(biāo)應(yīng)急資源調(diào)度模型

在實際生活中，某些鐵路突發(fā)事件的波及范圍較大且具有傳播效應(yīng)，在突發(fā)事件的影響下可能會產(chǎn)生多個救援需求點，本文從現(xiàn)實角度出發(fā)解決多資源供應(yīng)點與多救援需求點之間的應(yīng)急資源調(diào)度問題，設(shè)計建立多需求點與多供應(yīng)點間的數(shù)學(xué)模型。供應(yīng)點與需求點間的調(diào)度關(guān)系如圖1。

圖1 物資供應(yīng)點與救援需求點的調(diào)度關(guān)系示意圖

1.1 模型假設(shè)

為了增加本文所建立模型的可操作性，需要作如下假設(shè)：1)救援需求點和資源供應(yīng)點的位置關(guān)系已知；2)應(yīng)急所需救援物資數(shù)量可根據(jù)突發(fā)事件影響程度提前預(yù)估；3)應(yīng)急所需救援物資量不隨時間變化；4)假設(shè)救援車輛的目標(biāo)行駛速度為v=100 km/h；5)為加大對時間延誤的懲罰力度，本文假設(shè)遲到懲罰系數(shù)p=1 000。

1.2 模型基礎(chǔ)

設(shè)：S1,S2,…,Si為供應(yīng)點(i∈[1,m])，D1,D2,…,Dj為需求點(j∈[1,n])，模型參數(shù)定義如下：

si表示供應(yīng)點Si(i=1,2,…,m)的物資儲備量。

dj表示需求點Dj(j=1,2,…,n)對資源的需求量。

xij表示0- 1狀態(tài)變量，供應(yīng)點Si向需求點Dj提供救援資源時xij=1；否則，xij=0。

nij表示供應(yīng)點Si為需求點Dj所提供的資源量。

ηj表示需求點Dj的資源滿足程度。

lij表示供應(yīng)點Si到需求點Dj的距離。

αij表示供應(yīng)點Si到需求點Dj各路段的道路暢通程度(因道路擁擠等原因無法達到目標(biāo)行駛速度)。

v表示車輛在路段上的目標(biāo)行駛速度。

tj表示需求點Dj需要獲得資源的目標(biāo)時間。

cij表示供應(yīng)點Si為需求點Dj所提供資源的單位成本。

p表示遲到懲罰系數(shù)。

1.3 模型建立

時間窗總體上可分為“硬時間窗”和“軟時間窗”。“硬時間窗”是指必須在規(guī)定的時間段內(nèi)對客戶進行服務(wù)，超出規(guī)定時間后客戶不再接受服務(wù)；“軟時間窗”是指超過規(guī)定時間段后依然可以對客戶進行服務(wù)，但超出規(guī)定時間的服務(wù)需因時間延誤而接受相應(yīng)的懲罰，遲到成本為遲到時間與遲到懲罰系數(shù)之積[12]。

鐵路突發(fā)事件發(fā)生之初，資源在救災(zāi)環(huán)境中受到限制，應(yīng)急資源的數(shù)量有可能不能同時滿足所有需求點的需求。若只考慮救援效益或救援時間最優(yōu)，則有可能忽略某些距離較遠(yuǎn)的受災(zāi)點，因此考慮每個需求點的公平性更為重要，本文以所有需求點的資源滿足程度的方差來衡量救援的公平性。

綜合考慮前文對問題的分析，本文設(shè)計建立以救援公平性最大和調(diào)度總成本最小為目標(biāo)的應(yīng)急資源調(diào)度模型：

(1)

[lij/(αij·v)-tj]

(2)

(3)

(4)

(5)

(6)

(7)

xij=0或1;i=1,2,…,m,j=1,2,…,n

(8)

nij≥0

(9)

該模型是一個多目標(biāo)模型，式(1)、(2)為目標(biāo)函數(shù)：式(1)表示所有需求點的資源滿足程度的方差最??；式(2)表示調(diào)度總成本最低。式(3)～(9)為約束條件：式(3)表示需求點Dj獲得的資源量不超過其實際需求量；式(4)表示供應(yīng)點Si提供的總資源量不超過其自身存儲量；式(5)表示每個需求點至少有一個供應(yīng)點為其提供救援；式(6)為需求點Dj的資源滿足程度的計算公式；式(7)為所有需求點的平均資源滿足程度的計算公式；式(8)為“0- 1”整數(shù)約束；式(9)為非負(fù)約束。

2 算法設(shè)計

對于多目標(biāo)問題的求解，多數(shù)學(xué)者青睞于啟發(fā)式算法，主要包括：禁忌搜索算法[3]、進化規(guī)劃算法[7]、模擬退火算法[2,5]、遺傳算法[12,14]、蟻群算法[6,12]等；此外，還有Dijkstra算法[8]、并行分配算法[10]、逐步法[13]等。

本文構(gòu)建的基于“軟時間窗”的多目標(biāo)應(yīng)急資源調(diào)度模型是典型的多目標(biāo)規(guī)劃模型，需綜合考慮兩個目標(biāo)函數(shù)。本文兩個目標(biāo)函數(shù)的量綱不同，方差的取值較小，很難將其統(tǒng)一量綱轉(zhuǎn)化為單目標(biāo)求解，而并列選擇遺傳算法可以對兩個目標(biāo)函數(shù)同時進行運算操作，故本文采用并列選擇遺傳算法求解。并列選擇的基本思想是：根據(jù)目標(biāo)函數(shù)的個數(shù)，將種群均等地劃分為與目標(biāo)函數(shù)個數(shù)相等的子種群，為劃分后的各個子種群各自分配一個目標(biāo)函數(shù)，并對其進行獨立的選擇運算，將各個子種群中適應(yīng)度高的個體組成完整的種群，對這個完整的種群進行交叉、變異，生成下一代種群，如此循環(huán)可得到Pareto最優(yōu)解。

兩個目標(biāo)函數(shù)隨迭代次數(shù)變化的曲線如圖2。由圖2可知，兩個目標(biāo)函數(shù)在迭代計算過程中都是逐漸趨于最優(yōu)的，沒有存在相背離的情況。

具體求解過程如下。

步驟1 生成初始染色體。對模型中的0- 1決策變量xij采用長度為1位的二進制編碼，對非決策變量nij采用實數(shù)編碼，根據(jù)編碼方式，在集合S、D中隨機選取i、j，由隨機函數(shù)生成變量xij、nij的值，由此生成初始染色體Pi=[xij|nij],i=1,2,…,N，N為種群規(guī)模。

圖2 目標(biāo)函數(shù)隨迭代次數(shù)變化示意圖

步驟3 通過選擇得到每個子種群中適應(yīng)度高的個體，將這些個體組成完整的種群，對這個完整的種群進行交叉、變異，生成下一代種群，并去除種群中不滿足約束條件的個體，得到新的種群。具體步驟如下。

1)選擇。本文算法中染色體選擇采用適應(yīng)度值比例方法(也可稱為輪盤賭方法)，其選擇概率為：

(10)

其中fi為群體中第i個個體的適應(yīng)度函數(shù)值。

r∈[0,1]是一個隨機數(shù)，若r∈(0,pi]，則選擇個體i。

2)交叉。在本算例中，對于采用二進制編碼的0- 1決策變量xij，交叉操作采用單點交叉，即在二進制編碼中，隨機選擇一個點，以這個點為界限，相互交換變量。

對于采用實數(shù)編碼的非決策變量nij，其需要交叉的染色體數(shù)由交叉概率決定，若交叉概率為pc，則每次需對pc·N的染色體進行交叉。r∈[0,1]是一個隨機數(shù)，若r

(11)

其中：Pm為第m個染色體，Pn為第n個染色體，k為交叉的位置，a為區(qū)間[0,1]內(nèi)的隨機數(shù)。

3)變異。需變異的染色體數(shù)由變異概率決定，若變異概率為pm，則每次需對pm·N的染色體進行變異。r∈[0,1]是一個隨機數(shù)，若r

(12)

其中：Pmax是基因Pik的上界；Pmin是基因Pik的下界；f(g)=r′(1-g/Gmax)2，r′是一個隨機數(shù)，g是當(dāng)前迭代次數(shù)，Gmax是最大進化次數(shù)。

4)根據(jù)模型的約束條件，判斷種群中個體的可行性，刪除種群中不滿足約束條件的個體，通過隨機生成的方法，補充染色體，使其總數(shù)保持為N，形成新的種群。

步驟4 終止。累計循環(huán)計算的次數(shù)，如果次數(shù)小于預(yù)先設(shè)定的迭代次數(shù)，轉(zhuǎn)步驟2；否則，終止計算，轉(zhuǎn)步驟5。

3 算例分析

結(jié)合本文設(shè)計的模型，通過以下算例對其進行驗證。

算例1 設(shè)某地區(qū)因地震災(zāi)害，出現(xiàn)5個受災(zāi)點需要救援，現(xiàn)有8個資源供應(yīng)點，需求點Dj(j=1,2,3,4,5)的物資需求量分別為D1=3 000，D2=1 800，D3=2 200，D4=2 000，D5=2 500，每個需求點需要獲得物資的目標(biāo)時間tj=1 h (j=1,2,3,4,5)，供應(yīng)點Si(i=1,2,3,4,5,6,7,8)現(xiàn)有物資量分別為S1=800，S2=1 500，S3=1 300，S4=800，S5=1 600，S6=1 400，S7=1 500，S8=1 100，供應(yīng)點Si到需求點Dj的距離如表1，供應(yīng)點Si為需求點Dj提供資源的單位成本如表2，供應(yīng)點Si與需求點Dj之間各路段的道路暢通程度如表3。

表1 算例1中供應(yīng)點到需求點的距離lij km

表2 算例1中供應(yīng)點為需求點提供資源的單位成本cij 元

根據(jù)上述算法，初始可行解的染色體為P=[0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 0 1 0 0 1 | 0 800 0 0 0 1 500 0 0 0 0 0 0 1 300 0 0 0 0 0 0 800 0 0 0 0 1 600 0 0 900 500 0 0 0 0 1 500 0 0 1 000 0 0 100]，此時，目標(biāo)函數(shù)Z1=0.05,目標(biāo)函數(shù)Z2=9 534 356(元)。

一般遺傳算法種群大小的取值范圍是20～100，種群取值較小時，會降低種群的多樣性，可能會引起早熟現(xiàn)象，種群較大時，會降低運行效率，本文設(shè)置種群大小N=100；交叉概率一般應(yīng)取較大值，但若取值較大的話，會破壞種群中的優(yōu)良模式，若取值較小，產(chǎn)生新個體的速度較慢，一般取值范圍是0.4～0.99，本文取交叉概率pc=0.8；變異概率的一般取值范圍是0.000 1～0.1，取值較大雖能產(chǎn)生較多的新個體，但也可能破壞掉很多較好的模式，取值太小的話，變異操作產(chǎn)生新個體的能力和抑制早熟現(xiàn)象的能力就較差[16]，本文變異概率pm=0.05，迭代次數(shù)為1 000。利用Matlab軟件工具編程求解算例，其結(jié)果如表4～5所示，目標(biāo)函數(shù)Z1=0.000 133 7,目標(biāo)函數(shù)Z2=10 370 889(元)。

表3 算例1中供應(yīng)點到需求點各路段的道路暢通程度αij

表4 算例1中由并列選擇遺傳算法得到的供應(yīng)點與需求點的0- 1狀態(tài)變量值xij

表5 算例1中由并列選擇遺傳算法得到的供應(yīng)點為需求點提供的資源量nij

此外，采用標(biāo)準(zhǔn)粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法對該算例在同一臺計算機上進行計算。其結(jié)果如表6～7所示，目標(biāo)函數(shù)Z1=0.002 186 3,目標(biāo)函數(shù)Z2=10 918 259(元)。與PSO相比，并列選擇遺傳算法的方差減小了93.88%，成本減少了5%。

算例中：需求點D1由于距離供應(yīng)點較遠(yuǎn)，突發(fā)事件發(fā)生之初，供應(yīng)點現(xiàn)有的資源量無法同時滿足所有需求點，初始可行解中為需求點D1提供的資源量較少，這有悖于科學(xué)規(guī)劃、公平合理的宗旨，不利于社會和諧。出于現(xiàn)實意義的考慮，為距離較遠(yuǎn)的需求點提供救援雖然會增加成本但也是必需的。運用本文設(shè)計的模型生成的資源調(diào)度方案(如表4～5所示)可使所有需求點的資源滿足程度方差趨近于0，即公平性趨近最大化；與此同時也可使成本的增加量控制在可接受范圍內(nèi)，從而使得調(diào)度總成本最小。

表6 算例1中由PSO算法得到的供應(yīng)點與需求點的0- 1狀態(tài)變量值xij

表7 算例1中由PSO算法得到的供應(yīng)點為需求點提供的資源量nij

算例2 再考慮8個受災(zāi)需求點，5個資源供應(yīng)點的情形，需求點Dj(j=1,2,3,4,5,6,7,8)的物資需求量分別為D1=2 000，D2=1 500，D3=1 800，D4=1 000，D5=1 200，D6=1 700，D7=2 200，D8=1 600，每個需求點需要獲得物資的目標(biāo)時間tj=1h(j=1,2,3,4,5,6,7,8)，供應(yīng)點Si(i=1,2,3,4,5)現(xiàn)有物資量分別為S1=1 500，S2=2 600，S3=1 800，S4=2 800，S5=2 500，供應(yīng)點Si到需求點Dj的距離如表8，供應(yīng)點Si為需求點Dj提供資源的單位成本如表9，供應(yīng)點Si與需求點Dj之間各路段的道路暢通程度如表10。

表8 算例2中供應(yīng)點到需求點的距離lij km

采用本文設(shè)置的并列選擇遺傳算法求解(算法參數(shù)設(shè)置與算例1相同)，其結(jié)果如表11～12所示，目標(biāo)函數(shù)Z1=0.000 148 7,目標(biāo)函數(shù)Z2=9 258 380(元)。

此外，采用文獻[15]中設(shè)計的兩階段啟發(fā)式算法對該算例進行計算。其結(jié)果如表13～14所示，目標(biāo)函數(shù)Z1=0.001 47,目標(biāo)函數(shù)Z2=9 272 364(元)。與兩階段啟發(fā)式算法相比，并列選擇遺傳算法的方差減小了89.88%，成本減少了0.15%。

表9 算例2中供應(yīng)點為需求點提供資源的單位成本cij 元

表10 算例2中供應(yīng)點到需求點各路段的道路暢通程度αij

表11 算例2中由并列選擇遺傳算法得到的供應(yīng)點與需求點的0- 1狀態(tài)變量值xij

表12 算例2中由并列選擇遺傳算法得到的供應(yīng)點為需求點提供的資源量nij

表13 算例2中由兩階段啟發(fā)式算法得到的供應(yīng)點與需求點的0- 1狀態(tài)變量值xij

算例1和算例2的計算結(jié)果均可表明：采用本文設(shè)置的并列選擇遺傳算法，可使得所有需求點的資源滿足程度的方差更小(即公平性更大)、調(diào)度總成本更低，計算結(jié)果更優(yōu)。

表14 算例2中由兩階段啟發(fā)式算法得到的供應(yīng)點為需求點提供的資源量nij

4 結(jié)語

本文從現(xiàn)實角度出發(fā)解決多資源供應(yīng)點與多救援需求點之間的鐵路應(yīng)急資源調(diào)度問題，結(jié)合“軟時間窗”的概念，將公平性最大和調(diào)度總成本最小作為優(yōu)化目標(biāo)，以所有需求點的資源滿足程度的方差來衡量救援的公平性，建立多需求點與多供應(yīng)點間的數(shù)學(xué)模型，運用并列選擇遺傳算法求解，并設(shè)計了算例。該算例結(jié)果表明：1)該模型有很強的實用性，在鐵路突發(fā)事件發(fā)生之初、總資源量不足時，有效避免了距離較遠(yuǎn)的受災(zāi)點獲得的資源量較少甚至沒有的情況。2)本文中模型所選用的并列選擇遺傳算法計算效率高，對該問題的求解有很強的適應(yīng)性。3)本文所設(shè)計的模型與方法可為鐵路應(yīng)急資源調(diào)度提供有價值的決策支持，對于鐵路應(yīng)急指揮工作有很強的借鑒意義。此外，在將來研究中將增加對于鐵路突發(fā)事件發(fā)生之初的實際資源需求量快速測算的研究，使模型更加完善。