時間敏感選項依賴下的基礎設施恢復決策研究

任愛俊， 田 軍， 馮耕中

(西安交通大學 管理學院，陜西 西安 710049)

0 引言

隨著時代步伐的不斷前進，基礎設施之間的關聯也越來越緊密，這就導致突發事件引起基礎設施損毀后相互之間會形成恢復依賴。在2008年中國南方雪災應急過程中，人民日報等媒體大規模報道了通訊、電力、化石能源、交通、供水、排水等基礎設施之間形成的恢復依賴，(例如：通訊設施恢復依賴于電網恢復供電，或者備用發電機能夠持續供電；電力恢復依賴于交通恢復來運輸線路修復設備和材料，同時依賴于電煤恢復供給；備用發電機持續運行依賴于燃油加注；燃油加注任務執行決策又依賴于電力恢復情況；電煤供給恢復依賴于鐵路恢復運行)，這些基礎設施恢復任務之間存在的依賴關系導致恢復決策非常復雜，以至于黨中央及各級政府領導人親臨一線協調各個基礎設施之間的恢復決策[1,2]。在此之后的汶川“5·12”大地震、天津港“8·12”大爆炸、2016年南方洪水等突發事件應急過程中，均有關于基礎設施之間恢復依賴的大量報道，為此，國務院提出了提升突發事件后基礎設施系統恢復決策科學化水平的要求[3]。恢復依賴會導致一個基礎設施的恢復受制于其他基礎設施的恢復過程，通過延遲開始時間或者降低恢復效率影響整體恢復進度，并且這種影響會產生級聯效應，因此，要快速有效的將基礎設施恢復到正常運行狀態，以控制突發事件對社會產生的影響，制定合理的恢復決策非常重要，這是快速恢復基礎設施系統服務和降低社會損失的關鍵。基礎設施網絡恢復過程主要包含兩個決策階段[4]：(1)確定需要修復或者臨時安裝組件的集合，該階段決定恢復工作完成后基礎設施的網絡拓撲結構，即設計決策階段；(2)指派任務到工作組，并安排工作組完成任務，即調度決策階段。

關于基礎設施恢復，國內研究主要集中于恢復調度決策問題，小部分研究關注于設計決策問題。袁媛,樊治平,劉洋[5]針對基礎設施網絡中多個節點失效的應急搶修問題，構建了以節點失效損失最小為目標的搶修隊伍派遣優化模型。張雷,馬璐,元昌安[6]提出了以應急救援效率最大化、物資消耗最小化為目標的最短時限應急救援多目標指派模型。林振智,文福拴,周浩[7]提出了一種基于復雜網絡社團結構理論的恢復子系統劃分算法，根據各個子系統分裂出來的先后次序進而確定子系統之間同步并列的先后恢復次序，以基礎設施為中心給出了一種調度決策方法。代穎,馬祖軍,朱道立等[8]考慮突發事件后的基礎設施恢復資源調度問題，構建了一個基于機會約束規劃的多目標模糊優化模型。劉亞杰,陳森,徐鳳麟[9]研究了突發事件后路網修復的資源調度問題，提出了一種非確定性應急資源調度規劃模型，該模型解決的實際上仍然是以路網累積恢復效能最大化為目標的資源調度路徑決策問題。張玲,王晶,張敏[10]研究了應急響應期間資源配置網絡的設計問題，以資源配置效率最大化為目標建立了應急資源配置網絡的混合整數規劃模型，該模型實際上相當于給出了交通基礎設施恢復設計決策模型。潘芳,仲偉俊[11]考慮突發事件后迅速恢復應急救援公路線網問題，借鑒網絡堵塞流中最小飽和流的基本理論和方法，提出了最小運力最優恢復模型，該模型本質上也是解決恢復設計決策問題，但是，研究中設定為流制定路線后沿路線的所有節點必須修復，沒有考慮節點潛在的冗余和選擇問題。上述模型都是將基礎設施作為獨立節點進行分析，對于恢復依賴國內學術界主要采用定性方法進行研究。

國外研究已經逐漸將恢復依賴納入了基礎設施網絡恢復的建模范圍。Xu、Guikema和Davidson等[12]提出了一個考慮網絡節點間依賴約束的電力網絡恢復調度隨機整數規劃模型，該模型以恢復時間最短為目標，并且假定所有損毀節點必須全部修復。Yan和Shih[13]考慮運輸配送和道路搶修之間的恢復依賴關系，構建了一個多物資的混合整數規劃模型，目標是最小化失效路段修復時間與資源供給時間的加權和。Lee、Mitchell和Wallace等[14]基于網絡流理論開發了一個相互依賴基礎設施系統分層網絡(ILN)模型，該模型能夠用于度量由于基礎設施損毀導致的服務斷供，并且也可以用于決定為了恢復全部基礎設施服務需要安裝或者修復的組件集合，然而，并沒有給出基礎設施組件修復的調度決策規則。Matisziw、Murray和Grubesic[15]考慮了在有限資源條件下恢復過程中相互依賴基礎設施節點的資源分配問題，并且提出了以最小化服務損失和最大化流為目標的規劃方法，從基礎設施角度來考慮的話，該方法給出的是一個恢復設計方法，因為計算結果給出了恢復節點集合。Gong、Lee和Mitchell等[16]聚焦于在給定存在恢復依賴的安裝和修復組件集合條件下指派任務到工作組的規則，提供了一個包含任務遲延和最大完工時間在內的多目標規劃Benders分解算法。

上述決策模型全部聚焦于決策的單一階段：或者僅考慮設計決策，或者僅考慮調度決策。由于兩個問題目標性質的差別，評估度量標準存在潛在沖突，設計決策的評估標準常常是成本，而調度決策的度量標準常常是完成恢復的耗時，這意味著，設計階段為了降低成本，可能導致恢復過程耗時極度增加，換言之，基礎公共服務不會得到高效率的恢復，這完全不符合應急恢復基本準則，所以，按照順序依次獨立進行這樣的兩個決策階段存在重大缺陷。Cavdaroglu、Hammel和Mitchell等[4]以及Nurre、Cavdaroglu和Mitchell等[17]分別建立了包含恢復設計和調度決策的集成模型，然而，都沒有考慮不同恢復依賴關系類型的差別，并且假設基礎設施恢復完全處于一種集中式決策場景。Sharkey、Nurre和Nguyen等[18]通過研究基礎設施的恢復過程給出了恢復相互依賴的概念界定，并且將其劃分為傳統優先依賴、效率優先依賴、選項優先依賴和時間敏感選項依賴四類，該研究發現對于不同恢復依賴關系類型，在時間約束、流約束及任務指派約束等方面均存在重大差別，因此，為了改進決策質量，有必要進一步深入分析相應的恢復設計和調度決策方法。

突發事件發生后，大多數情形具備的特征是：(1)損毀組件存在首選和備選恢復方案；(2)由于恢復工作時效性要求較高，如果在某個時間點采用首選方案無法達成目標就需要啟用備選方案。這樣的特征基本符合Sharkey[18]定義的時間敏感選項恢復相互依賴類型，因此，本文基于網絡流理論，在已有恢復設計與調度決策模型基礎之上，深入分析了時間敏感選項類型依賴下基礎設施恢復過程中的約束關系，構建了時間敏感選項依賴恢復設計與調度決策模型；然后，根據基礎設施之間協作水平的差別，識別了基礎設施網絡恢復的三種決策環境，同時，給出了該模型在三種決策環境下的應用方法；最后，利用真實基礎設施數據集在三種決策環境下對模型進行了測試分析。

1 設計與調度決策模型

1.1 問題描述

Sharkey[18]將時間敏感選項類型的恢復依賴定義為：如果在基礎設施m中的一個恢復任務在特定期限內無法完成，另一個在基礎設施n中的恢復任務必須完成。該類恢復依賴的一個典型例子是無線網絡通信塔供電情境：在突發事件后，如果通信塔的備用發電機耗盡燃料之前，電力基礎設施無法恢復，就需要完成備用發電機的燃料加注任務。圖1給出了基礎設施網絡及時間敏感選項恢復依賴示例。在示例中，變電站、無線基站、加油站、交通設施之間存在服務供給關系，其中變電站出現故障，變壓器i對無線基站中信號塔j的電力供給中斷，無線基站啟用備用發電機供電，然而，備用發電機在燃料耗盡之前，如果電力無法恢復，則需要完成燃料加注任務，否則不需要執行燃料加注任務。

基礎設施恢復過程中的時間敏感選項類型恢復依賴問題可以描述為：每個基礎設施可以通過一個ILN網絡表示，每個網絡包含節點和弧兩類組件；節點組件分為供給、需求和傳輸三種類型，供給節點是服務流的源頭，生產一定的服務；需求節點消費一定的服務，需要服務流供給以維持正常運行；傳輸節點是服務流由供給節點到需求節點的中轉站，既不生產服務也不消費服務；服務對應網絡中的流，并且通過網絡中的弧從供給節點向需求節點流動；突發事件發生后，至少有兩個需要恢復運行的基礎設施m和n，基礎設施n中節點j恢復運行依賴于基礎設施m中節點i恢復對j的服務供給，即基礎設施n中節點j恢復運行依賴于節點i通過弧(i,j)向節點j供給服務，當且僅當節點i在指定截止期限內無法完成對j的服務供給，基礎設施n需要在指定截止期限完成通過安裝臨時節點向節點j供給服務的任務。將恢復節點i對節點j服務供給的任務稱為優選任務，通過安裝臨時節點向節點j供給服務的任務稱為備選任務。目標是在恢復周期內最大化累積恢復效能，即最小化基礎設施系統累積服務損失，需要解決的問題是給出修復或者臨時安裝組件的集合，然后，將組件恢復任務指派工作組，并確定每個工作組完成指派任務的時間。

圖1 基礎設施網絡及時間敏感選項恢復依賴示例

1.2 假設條件

為了聚焦于核心問題，基于實際情況做了如下簡化假設：

(1)基礎設施之間存在的依賴全部為線性關系。盡管電力、通信等基礎設施根據物理法則運行，然而，Nurre、Cavdaroglu和Mitchell等[17]發現線性模型能夠對這類基礎設施恢復決策提供良好的近似表示。

(2)一項恢復任務一旦開始執行則必須在一個連續時間段內完成。

(3)在整個恢復過程中正常運行組件對于全部基礎設施都可見。

(4)基礎設施網絡中僅包含單商品流。然而，通過向模型中的變量和參數添加一個商品索引便可以處理存在多商品流的基礎設施，擴展方法參見文獻[14]。

(5)將基礎設施中遭到破壞的組件以弧表示，這個假設條件不失一般性，因為如果一個節點i遭到破壞，可以使用標準網絡擴充法將節點i以兩個節點i′和i″以及弧(i′,i″)表示，所有原本進入i的入弧轉而從i′進入，所有從i離開的出弧轉而從i″輸出。

(6)每個工作組一次只處理一條弧的恢復任務。

(7)相互依賴關系全部發生在子基礎設施的節點處，即，如果一段弧存在輸入相互依賴，則可以將該弧分成兩段，中間帶有一個節點。

(8)恢復設計與調度決策占用恢復過程的耗時可忽略不計。

(9)各組件的恢復耗時對于任一工作組均相同。

1.3 符號及意義

M-基礎設施的集合；

Vm,+-基礎設施m中供給節點的集合；

Vm,=-基礎設施m中傳輸節點的集合；

Vm,--基礎設施m中需求節點的集合；

Em-基礎設施m中未損毀弧的集合；

δm,+(i)-基礎設施m中進入節點i的弧集合；

δm,-(i)-基礎設施m中離開節點i的弧集合；

wm-基礎設施m在網絡中的權重；

T-恢復過程中的時間周期集合；

Km-在基礎設施m中工作組的集合；

TSO-對于?(j,n)∈TSO，基礎設施n中的節點j無法通過完成優選任務恢復需求供應的話，則通過完成備選任務恢復需求供應；

1.4 混合整數規劃模型

本研究使用時間索引規劃確定一個工作組完成一項恢復任務的時間點，每個索引單位增量對應一個恢復周期，在每個時間周期都需要決定各個基礎設施系統中通過弧的流量，目的是評估整個相互依賴基礎設施網絡的累積恢復效能，并確定相關基礎設施的恢復決策。基礎設施系統屬于生命線系統，突發事件后效能的恢復程度無法用經濟方式進行準確估量，因此，采用需求節點的服務滿足比例來表達基礎設施的累積恢復程度。時間敏感選項依賴條件下集成恢復設計與調度決策問題的混合整數規劃模型如下：

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

(19)

(20)

(21)

(22)

(23)

2 恢復決策環境

根據相互依賴基礎設施恢復期間的協作水平差異，從而產生了不同的決策環境，按照協作緊密程度的不同，研究中主要考慮三種決策環境，即完全中心化決策環境、完全分散決策環境和信息共享決策環境。

2.1 完全中心化決策環境

完全中心化決策環境是基礎設施系統恢復的理想情況，在該決策環境下存在唯一的決策中心，該決策中心控制所有的資源，對相互依賴基礎設施網絡中所有基礎設施的恢復設計與調度進行統一決策。為了最大化累積恢復效能，可以通過直接求解模型得到設計與調度決策，因此，從理論上來說，中心化決策環境可以獲得最高的決策效率和最大的累積恢復效能，在研究中該決策環境的計算結果將會作為其他決策環境的參照。然而，從實踐角度來說，由于各基礎設施之間的現實利益沖突和決策偏好差異，一般不存在該決策環境。

2.2 完全分散決策環境

當t達到恢復周期的結束，每個基礎設施的恢復決策已經完全確定，并且所有t時刻的全部變量值已知，然后將這些變量作為定值帶入模型目標函數，從而可以評估相應決策的累積恢復效能。

2.3 信息共享決策環境

在恢復工作起始階段，所有基礎設施獨立決策各自的恢復設計與調度方案，然后向其他基礎設施公布，因此，接下來每個基礎設施掌握了關于其他基礎設施的最新計劃，并且能夠通過求解模型公式更新恢復設計和調度決策。此時，各個基礎設施恢復決策依據的信息并不一定是其他基礎設施實際執行的決策方案，恢復信息的公布和決策方案的優化更新可能持續多輪迭代。

3 模型測試

3.1 案例描述

基于高德地圖提供的API通過編程方式獲取了廣州市基礎設施網絡的一個子集，表1提供了該子集的統計描述信息。電力基礎設施包含變電站、換流站、開關站等；通信基礎設施包括基站、數據中心、中心機房等；交通基礎設施包括高架橋、隧道、車站、停車場、交通信號等；供水基礎設施包括自來水廠、加壓站、水塔等；排水基礎設施包括污水處理廠、泵站、截流設施、檢查井、污水井等；化石能源基礎設施包括加油站、氣源站、調壓站、加氣站、氣化站等。表2提供了基礎設施之間的需求供給關系數量。

表1 基礎設施基本信息

表2 基礎設施之間的需求供給關系數量

表3 各場景下損毀組件數量

3.2 計算與分析

研究中分別考慮了Km=3和Km=6兩種情況下，當T=30時的恢復設計與調度決策過程。根據混合整數規劃模型目標函數，在整個恢復過程中用0到1之間的百分比評估累積恢復效能，這一評估提供了實際恢復水平與理想恢復上限的一個比較。基于筆記本電腦上運行IBM ILOG CPLEX Optimization Studio 12.6求解混合整數規劃模型，進行了時間敏感選項類型恢復依賴的基礎設施恢復設計與調度決策模型測試，并比較分析了三種決策環境下的累積恢復效能差異。

在中心化決策條件下，通過直接求解模型就能夠獲得最優恢復決策，并且代表了基礎設施網絡從突發事件中恢復的最高累積效能。對于完全分散決策環境中恢復決策依賴父節點的基礎設施，父節點組件完成恢復之前，自身無法進行調度決策，在每個恢復周期t，各個基礎設施依據父節點恢復情況優化自身恢復決策，直至所有基礎設施全部恢復或者達到恢復截止期限。

在信息共享決策環境下，每個基礎設施會基于所依賴基礎設施聲明的恢復決策優化自身的恢復設計與調度決策。每輪信息共享包括：(1)各個基礎設施聲明自身的恢復決策；(2)各個基礎設施基于所依賴基礎設施的恢復決策優化自身的恢復設計與調度決策。在計算分析過程當中，允許信息共享進行任何輪次，關注點在于是否達到穩定解，即兩輪之間沒有任何基礎設施變更恢復決策。在測試中，結果在7輪之后只有六個實例中的兩個達到了穩定解。考慮不同的信息共享輪次，Cum(l)表示1輪后的累積恢復效能，依次類推。表4提供了各個決策環境下基礎設施的累積恢復效能。

根據表4的比較結果，對時間敏感選項類型恢復依賴，集中式決策環境下累積恢復效能最高，比完全分散決策高出了19.7%到47.4%，比信息共享決策環境下迭代7輪后的累積恢復效能高出了2.7%到16.6%；信息共享決策環境下累積恢復效能次之，迭代1輪后的累積恢復效能比完全分散決策環境高出了4.3%到7.2%，迭代7輪后的累積恢復效能比完全分散決策環境高出了15%到26.4%。如果將集中式決策環境與完全分散決策環境下的累積恢復效能差值作為基數，信息共享決策環境下迭代7輪后的累積恢復效能改進了52.6%到82.3%。從計算結果可以看到，信息共享決策環境比完全分散決策環境產生了一個重要的改進，因此，在各個基礎設施獨立決策時，對于時間敏感選項類型恢復依賴，恢復設計與調度決策能夠通過信息共享取得顯著的改進。這一改進表明當突發事件引起大范圍損毀時，在恢復過程中應急管理人員有必要實現跨基礎設施的溝通與交流。

表5提供了信息共享決策環境下累積恢復效能隨迭代輪次增加呈現出的變化。由測試結果數據可知，只有小規模場景分別當Km=3和Km=6時各自經過4輪和7輪信息共享之后恢復決策取得穩定解，總體來看隨著迭代輪次的增加，累積恢復效能出現了收斂趨勢。然而，在迭代過程中，累積恢復效能出現了一些波動，這是由于基礎設施在以一種利己的方式調整決策過程，雖然部分基礎設施改進了自身累積恢復效能，但是，延遲了權重較大基礎設施的恢復時間，從而導致總體累積恢復效能發生劣化。在實踐當中，突發事件后基礎設施恢復工作需要迅速開展，信息共享的輪次需要盡可能小，因此，在相互依賴基礎設施恢復活動中，可以不要求相互依賴基礎設施的恢復決策構成穩定解，針對信息共享環境的傳統“停止規則”需要通過輪次確定。迭代停止規則可以是在連續的兩輪之間沒有基礎設施調整自身的恢復決策或者迭代輪次達到限定次數。

表4 各個決策環境下累積恢復效能

表5 信息共享決策環境下累積恢復效能隨迭代輪次增加呈現出的變化

4 結論

本文研究了突發事件后基礎設施恢復過程中存在時間敏感選項恢復依賴的恢復設計與調度決策問題。基于網絡流理論，深入分析了基礎設施恢復過程中時間敏感選項恢復依賴的特征與決策約束，在此基礎之上提出了恢復設計與調度決策混合整數規劃模型。該模型可以用于開發時間敏感選項類型依賴下的基礎設施恢復設計與調度決策，也可以用于度量相互依賴基礎設施系統恢復期內指定時間的累積恢復效能。根據基礎設施恢復過程中相互之間協作水平的差別，識別了完全集中化、信息共享和完全分散三種決策環境，同時，給出了該模型在三種決策環境下的應用方法。通過真實數據測試發現：

(1)模型在解決實際問題時具備可行性；

(2)在完全中心化決策環境下能夠獲得最優的決策結果，信息共享環境次之，完全分散決策環境最差；

(3)與完全分散決策環境相比，在信息共享決策環境下獨立決策能夠獲得顯著的恢復效能改進。然而，部分基礎設施改進自身累積恢復效能的同時，可能會導致整體累積恢復效能發生劣化，因此，實踐當中，在信息共享決策環境下，各基礎設施享有相對獨立決策權的同時，需要有更高層次的權威組織輔之以適當的調控，保證整體累積恢復效能得到持續優化。進一步研究可以考慮，在信息共享決策環境下，分析累積恢復效能的改進水平與信息共享輪次之間的關系，以及基礎設施規模與累積恢復效能改進之間的關系，以為實踐人員提供決策參考。