时间敏感选项依赖下的基础设施恢复决策研究

任爱俊， 田 军， 冯耕中

(西安交通大学 管理学院，陕西 西安 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)与完全分散决策环境相比，在信息共享决策环境下独立决策能够获得显著的恢复效能改进。然而，部分基础设施改进自身累积恢复效能的同时，可能会导致整体累积恢复效能发生劣化，因此，实践当中，在信息共享决策环境下，各基础设施享有相对独立决策权的同时，需要有更高层次的权威组织辅之以适当的调控，保证整体累积恢复效能得到持续优化。进一步研究可以考虑，在信息共享决策环境下，分析累积恢复效能的改进水平与信息共享轮次之间的关系，以及基础设施规模与累积恢复效能改进之间的关系，以为实践人员提供决策参考。