考慮公平性的面向多災點需求應急資源調度

杜雪靈，孟學雷，楊 貝，湯 霖

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

0 引言

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

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

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

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

1 多目標應急資源調度模型

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

圖1 物資供應點與救援需求點的調度關系示意圖

1.1 模型假設

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

1.2 模型基礎

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

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

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

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

nij表示供應點Si為需求點Dj所提供的資源量。

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

lij表示供應點Si到需求點Dj的距離。

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

v表示車輛在路段上的目標行駛速度。

tj表示需求點Dj需要獲得資源的目標時間。

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

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

1.3 模型建立

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

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

綜合考慮前文對問題的分析，本文設計建立以救援公平性最大和調度總成本最小為目標的應急資源調度模型：

(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)

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

2 算法設計

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

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

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

具體求解過程如下。

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

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

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

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

(10)

其中fi為群體中第i個個體的適應度函數(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]內的隨機數(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是當前迭代次數(shù)，Gmax是最大進化次數(shù)。

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

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

3 算例分析

結合本文設計的模型，通過以下算例對其進行驗證。

算例1 設某地區(qū)因地震災害，出現(xiàn)5個受災點需要救援，現(xiàn)有8個資源供應點，需求點Dj(j=1,2,3,4,5)的物資需求量分別為D1=3 000，D2=1 800，D3=2 200，D4=2 000，D5=2 500，每個需求點需要獲得物資的目標時間tj=1 h (j=1,2,3,4,5)，供應點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，供應點Si到需求點Dj的距離如表1，供應點Si為需求點Dj提供資源的單位成本如表2，供應點Si與需求點Dj之間各路段的道路暢通程度如表3。

表1 算例1中供應點到需求點的距離lij km

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

根據上述算法，初始可行解的染色體為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]，此時，目標函數(shù)Z1=0.05,目標函數(shù)Z2=9 534 356(元)。

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

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

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

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

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

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

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

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

算例2 再考慮8個受災需求點，5個資源供應點的情形，需求點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，每個需求點需要獲得物資的目標時間tj=1h(j=1,2,3,4,5,6,7,8)，供應點Si(i=1,2,3,4,5)現(xiàn)有物資量分別為S1=1 500，S2=2 600，S3=1 800，S4=2 800，S5=2 500，供應點Si到需求點Dj的距離如表8，供應點Si為需求點Dj提供資源的單位成本如表9，供應點Si與需求點Dj之間各路段的道路暢通程度如表10。

表8 算例2中供應點到需求點的距離lij km

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

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

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

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

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

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

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

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

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

4 結語

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