2.2　网络恢复决策优化问题研究

交通网络受到的物理损害需要借助外界的恢复措施才能得到恢复，因此，学者们往往将弹复性、成本、时间及一些相关变量作为目标函数或约束条件建立模型，研究交通网络恢复决策优化问题。传统的网络恢复决策研究主要可以归纳为选择问题（Selection Problem）和排程问题（Scheduling Problem）两大方向。除此之外，还有一些学者开始研究选择与排程集成问题（Integrated Selection and Scheduling Problem）。

2.2.1　选择问题

交通网络恢复的选择问题是在成本约束下，确定最优的待恢复路段组合，或最优的预防措施、恢复措施组合，其本质上属于一种配置优化问题。例如，Chen和Miller-Hooks建立了一个随机混合整数规划模型，利用蒙特卡洛模拟、Benders分解和列生成法来求解该模型，寻找灾害发生不确定性环境和固定预算下恢复措施的最优配置，使得多式联运网络的弹复性最大化。在他们研究的基础上，Miller-Hooks等人增加对预控措施的考虑，分别针对机场跑道和滑行道网络、货物运输网络、城市交通-电力耦合系统，提出了在不确定性环境和固定预算下同时考虑预防措施和恢复措施的优化配置模型。还有一些学者对交通网络应急资源布局选址的研究也属于配置优化问题，其目的是为了灾后尽快恢复交通网络的基本能力。

由于交通网络结构自身的特点，对交通网络优化问题的研究需要基于图论、网络流理论等理论方法，使得选择问题这一配置优化问题也可以被归结为网络设计问题（Network Design Problem）。因此，根据决策周期的不同，又可以分为单周期网络设计问题（Single-period Network Design Problem）和多周期网络设计问题（Multi-period Network Design Problem）两类。

1. 单周期网络设计问题

单周期网络设计问题将决策周期视为一个整体，关注的是周期结束时的最终网络结构及该结构的性能。自1973年Morlok首次提出定量的交通网络设计问题后，该问题得到了诸多研究。尤其是相对比较简单的单周期网络设计问题，也被用于研究交通网络恢复问题。比如，李斌等人建立了基于连通可靠性的灾后应急阶段路网重建模型，并利用灵敏度分析的方法求解此模型，以便确定灾后应急阶段需要优先重建的关键路段。Liu等人研究固定预算下如何在需要翻新的公路桥梁间做出选择，以便提高整个交通网络的弹复性和稳健性。作者建立两阶段随机规划模型，优化系统损失的均值，并建立了相应的求解算法。程杰等人以网络整体效率为优化目标，考虑在随机和目的攻击下的交通网络级联失效效应对交通状况的影响，并建立了相应的城市道路网络修复策略双层优化模型。花丙威等人提出了路网脆弱性评价指标，并在此基础上构建了路网修复的双层规划模型，以便决策灾后短暂修复阶段需要修复哪些关键路段。Zhang和Wang结合网络拓扑结构、冗余水平、流量模式、网络元件的结构可靠性、网络功能，提出了一个基于弹复性的网络性能指标，并以最大化该指标为目标建立了公路网络改造项目优化模型。Zhang等人分别针对恢复过程中的确定和不确定环境，建立了带弹复性指标约束条件的网络设计优化模型，决策变量是指事故后哪些受损边需要恢复，目标函数是指恢复成本最小化。

2. 多周期网络设计问题

在实际生活中，交通网络等基础设置的投资建设往往工期较长，时间跨度甚至长达十几年，这期间的网络结构及其变化就变得至关重要。只关注最终网络结构可能会使决策效果发生较大偏差。因此，现实需求使得学者和从业者开始逐渐关注多周期网络设计问题，也称为递增网络设计问题（Incremental Network Design Problem）。这类问题将决策周期视为多周期，其一般形式是寻求各周期的综合最优设计决策，以使网络在所有周期上的累积性能最优。Baxter等人和Kalinowski等人分别研究了考虑最短路和最大流的情况下，每一个周期内网络只增加一条边的多周期网络设计问题。他们研究了这类问题的复杂性，证明即使是这类问题的最简单形式也是NP-hard。因此，在求解多周期网络设计问题时，部分学者虽然采用如分支切割法之类的精确算法，但考虑到这类问题固有的复杂性，这类精确算法往往只适用于求解小规模的网络问题，更多的研究往往采用近似算法或启发式算法。

多周期网络设计问题在交通规划领域已经得到广泛研究，研究涉及高速公路网络、铁路网络、城市道路网络、多式联运网络等多种交通网络，以及考虑需求不确定性、成本回收、交通枢纽选址、交通网络健康成本等诸多因素的多周期网络设计问题。

交通网络等重大基础设施灾后恢复或重建也具备多周期特点，因此，一些学者也将多周期网络设计问题应用于这些领域的研究。例如，陈艳艳等人根据生命线网络系统的网络特性和震后应急修复的特点，以控制地震引发的损失为目标，提出了震害快速检测的原则及应急修复的分步优化策略。谢秉磊等人建立了灾后恢复阶段多期路网重建规划的双层模型，上层模型是以工程总效益最大为目标建立多期工程效益模型，下层模型是基于出行时间可靠性的用户均衡配流模型。Kiyota等人研究了高速公路的多阶段重建优化问题，他们建立了一个考虑公路重建时封闭策略的动态规划模型，使各周期的累计总效用最大。Matisziw等人综合考虑系统成本最小化和网络流最大化，提出了一个基础设施网络恢复策略的多周期多目标优化方法。Ye和Ukkusuri用网络性能恢复率度量弹复性，并提出了交通网络多阶段重建计划优化模型，使交通网络的弹复性在给定成本和流量约束下最大化。卢志刚等人针对灾后配电网故障抢修需优先保证重要负荷供电的实际情况，建立了含分布式电源的配电网灾后多小队分阶段抢修策略的优化模型。

多周期网络设计问题在解决选择问题时通常只考虑成本约束而不考虑资源约束，假设每个周期选出的路段均可以同时开工维修，并在该周期内完成维修工程，在下个周期投入使用。因此，多周期网络设计问题仅仅确定了选出的路段可以安排在哪个周期进行维修，并没有根据资源约束对该周期内的维修工程进行排程。进一步地，在Hosseininasab等人的研究中，路段的维修可以是跨多个周期的，但他们假设每个周期内所有路段维修同时开工，这意味着仍然没有考虑资源约束，没有对每个周期内的维修工程进行排程。

如前所述，交通网络优化问题与通信网络、输电网络等其他基础设施网络研究的重要不同之处在于，当进行交通网络的分析、设计和优化时，需要考虑出行者对网络优化决策的行为反应，才能使决策模型更加贴近现实情况。因此，上述所有选择问题研究又可以分为如下两类。

（1）不考虑网络用户的行为：这类研究一般因为研究对象、研究问题的特殊性，或者出于简化问题便于研究的考虑，在建模过程中没有考虑网络用户的行为反应。

（2）考虑网络用户的行为：这类研究往往采用双层模型，上层模型解决交通网络优化决策问题，下层模型研究网络用户对上层决策的行为反应。这类问题求解难度更大，但对现实问题也更具指导意义。

表2.3列出了本节介绍的选择问题文献分类。

2.2.2　排程问题

交通网络恢复的排程问题往往需要考虑资源约束，在给定资源（一般表现为可同时开工修复的路段的数量）的情况下，研究待修复路段的最佳修复时序排列。交通网络恢复的排程问题研究一般分为如下几个方向。

1. 基于设定的重要性指标进行排序

这类研究是排程问题研究中最基础的一类，主要思路就是根据路段（或节点）的各类重要性指标来进行排序维修。因此，如何设置合理的路段重要性指标，以便全面合理地反应路段修复后对整个网络性能的提升贡献，是研究的重点。例如，王伟研究了突发事件下铁路网的修复问题，通过以节点或边被修复后对网络性能的贡献来识别铁路网系统中的关键节点或关键边的方法，进而给出铁路物理网的修复时序方案。姬利娟选用网络效率和最大连通子图的连通度两个指标来衡量网络修复的有效性，在此基础上对危险品运输网络的修复目标进行排序。周振宇研究级联失效对城市道路交通网络的影响，建立了节点失效、节点修复效果的评价指标，然后依据失效节点修复后路网阻塞程度指标对节点重要度进行排序，并根据此排序顺序修复失效节点。

弹复性作为衡量恢复效果的重要指标，也常被用来评价恢复策略的优劣，以便决策者在备选的恢复策略中做出选择。还有一些学者提出了一些基于弹复性的其他度量指标，据此评价给定恢复策略的优劣。比如，Barker等人和Baroud等人提出了两个基于弹复性的网络边的重要性度量指标，可以根据边的重要性排序来制定恢复策略。

这类研究存在一定的局限性。首先，根据路段（或节点）的各类重要性指标来进行排序维修的方法缺乏对问题的系统性认识。例如，如果当前最重要的网络恢复目标是优先保证修复一条最短路段，那么决策者应该考虑的就是如何确定一条最适合的最短路段，也就是一组路段，如果仅仅按照路段自身的重要性排序，那么优先修复的路段可能属于不同的最短路，反而耽误了最短路段的修复。其次，给定的候选恢复策略可能并没有包含最佳策略。

2. 基于车间作业调度问题（Job Shop Scheduling Problem，JSSP）思路的研究

这类问题主要针对灾后恢复重建问题，从车间作业调度问题的角度出发，将交通网络恢复排程问题中的资源和待修复路段分别视为车间作业调度问题中的加工机器和代加工零件，研究如何根据实际约束情况，将待修复路段分配给各个工程队及各路段在对应工程队的维修顺序，以取得最佳的恢复效果（如恢复时间最短、恢复成本最小、网络性能最好、系统弹复性最大等）。

Arimura等人将恢复可达性作为优化目标，研究了考虑多个工程队分工合作情况下的公路网络维修排程问题，并详细列出了求解该问题的遗传算法设计。Furuta等人考虑了地震灾害后的各种不确定性，提出了一个改进的考虑不确定性的遗传算法（GACU），以便对地震灾后生命线系统的恢复排程做出最优调度决策。Cicekci等人提出了两种贪婪调度算法来恢复受损的生命线网络，一种算法用于分配多个异构工程师，并为修复独立损坏的元件制订计划；另一种算法用于考虑网络约束的单个工程师的修复计划。这两种算法都使用效益增益率作为指标来决定下一步应该修复哪个元件，由谁来修复。Lertworawanich建立了预算和资源未知情况下的高速公路网络恢复顺序决策动态模型，该模型的主要目标是使断开网络的出行需求损失最小化，一旦网络变为连通的，模型的第二个目标最小化网络运行时间。Bocchini和Frangopol建立了震后桥梁修复策略优化模型，以每座桥梁开始修复的时间和每座桥梁的修复速度（代表分配给每座桥梁的修复资金）为决策变量，以最大化交通网络弹复性、最小化修复时间和修复成本为目标，寻求最优的修复策略。Zhang等人提出了两个基于弹复性的恢复策略评价指标，即总恢复时间和恢复曲线的倾斜程度。用这两个指标分别度量网络恢复的速度和效率，然后以这两个指标为目标，考虑资源约束，建立优化模型，求解公路—桥梁网络灾后的最佳恢复时序。

除了维修资源约束，Vugrin等人考虑了同一路段上可能存在的不同维修任务和维修方式，建立了一个双层规划模型来寻求灾后交通网络的最优恢复时序，模型上层通过优化交通网络弹复性求解最优恢复策略，模型下层求解相应决策下的网络流问题。Hackl等人同时考虑资源和可选择的恢复措施的约束，以最小化恢复成本（包括直接成本和由于网络提供的服务不足而产生的间接费用）为目标建立了恢复时序优化模型，并用模拟退火算法求解该模型。

3. 基于车辆路径问题（Vehicle Routing Problem，VRP）思路的研究

这类问题主要针对灾后应急救援阶段，该阶段交通网络的主要功能是为救援队伍、应急物资配送、灾区群众疏散提供安全高效的救援路径，基本不用考虑社会日常出行需求，公路修复工作以疏通受灾点与救灾中心等之间的道路为主要任务。因此，这部分研究往往从车辆路径的角度出发，将救灾中心、受灾点、工程队分别视为车辆路径问题中的配送中心、客户、车队，研究如何根据实际约束情况，合理规划各工程队的维修路径，以便取得最佳的恢复效果。

Chen和Tzeng针对地震后公路网络抢修的多工程队调度问题，构建了模糊多目标模型，并使用了不对称的交通指派技术来衡量重建排程的效率。Feng和Wang考虑资源和时间的约束，以最大化公路修复长度和营救人员数量、最小化救援人员风险为目标，建立了高速公路震后应急修复调度模型。针对地震后公路抢修时间的不确定性，王福圣将抢修时间视为模糊变量，建立了公路紧急抢修的模糊多场站车辆路径模型，并设计了算法对模型进行求解。Tang等人利用稳健性和期望优化概念，结合时空网络（Time-space Network）方法，建立了考虑通行时间和维修时间不确定的工程队抢修线路调度模型。霍建顺等人考虑震后的不确定性，建立了基于抢修时间模糊的受损公路抢修线路调度模型，并以汶川地震为例，对所建模型和算法进行验证。Yan和Shih利用蚁群系统（Ant Colony System，ACS）算法，结合阈值接受技术，开发了一种基于ACS的混合算法，能够有效地解决公路抢修时空网络问题。考虑到应急物资配送、灾民疏散等交通流分布会随着路网抢修工作而改变，李双琳和郑斌以最大化路网抢修累积绩效为目标，建立了动态交通流下的震后路网抢修排程优化模型，并设计了一种混合遗传算法对模型进行求解。

另外，应急物资配送、灾区群众疏散等工作也是灾后应急救援阶段面临的重要工作，由于时间紧迫，这些工作往往需要和应急道路疏通工作同步进行。因此，也有不少学者将应急道路抢修与应急救援阶段面临的应急物资配送、废墟清理、紧急救援及疏散问题相结合，研究联合优化问题。

与选择问题类似，上述所有排程问题研究也可以按照是否考虑网络用户的行为划分为两类。不过，由于应急救援阶段以应急物资配送、救援疏散为主要任务，这类任务集中且可控，用户日常出行可以忽略。因此，基于车辆路径问题思路的研究基本都不考虑用户的行为。表2.4列出了本节介绍的排程问题相关文献的分类情况。

2.2.3　选择与排程集成问题

选择与排程集成问题的研究重点是根据某个恢复阶段的特点（如成本预算、资源预算、工期不确定性等）和该阶段优先保证的恢复目标，同时解决该阶段的选择问题和维修排程问题。选择与排程集成问题与多周期网络设计问题的相同之处在于，两者均考虑了恢复决策在恢复过程中所产生的效果，而不仅仅只关注最终的网络结构；不同之处在于，选择与排程集成问题考虑了每个恢复阶段的资源约束，即不能同时修复选出的待修复网络元件，需要根据资源约束对工作任务进行排程。因此，选择与排程集成问题难度更大，而目前有关该问题的研究相对较少。

Nurre等人采用网络最大流作为网络性能指标，研究了基础设施网络恢复的选择与排程集成问题；并基于最大流问题的特点，开发了一种启发式作业安排规则来解决该选择与排程集成问题。Cavdaroglu等人考虑当今社会基础设施间大量存在的相互依赖关系，将上述问题拓展到相依基础设施系统（Interdependent Infrastructure Systems），研究了它们灾后联合恢复的选择与排程集成问题。Almoghathawi等人也研究了相依基础设施网络恢复的选择与排程集成问题，他们考虑了不同的事故场景，以及时间和资源的约束，提出了一种基于弹复性的多目标恢复模型。该模型旨在使相依基础设施网络的弹复性最大化，同时最小化与恢复过程相关的总成本。Nurre和Sharkey研究了选择与排程集成问题的复杂性，他们考虑分别采用最大流、最小成本流、最短路、最小生成树作为网络性能的选择与排程集成问题，证明这些问题都是NP-hard问题；并提出了一种新的启发式调度规则算法框架，该框架根据不同边的集合在网络中的相互作用来确定选择决策和排程决策。Sun和Sharkey重点分析了上述调度规则的近似因子，证明了近似保证是基于网络中的弧数和调度环境中的机器数。Nurre和Sharkey考虑网络元件维修开始时间不确定的情况，研究了实时优化环境下的基础设施网络恢复的选择与排程集成问题。在该环境下，决策者一开始无法获知全部的网络元件维修开始时间，而是随着时间的推移逐步获知的。Alvarez-Miranda和Pereira将网络选择与排程集成问题归结为一个两阶段稳健优化模型，并给出了求解该模型的精确算法，模型第一个阶段的决策与经典的网络设计问题相对应，第二个阶段的决策与不确定性下的网络建设排程问题相对应。

上述这些选择与排程集成问题研究都是关于一般性基础设施系统或者抽象网络的，多以最大流或最短路段等作为网络性能，网络流的传输遵循系统调度不需要考虑网络用户的自主选择行为，因此并不适用于交通网络的研究。Li等人研究了交通网络应急恢复阶段恢复策略优化问题，并建立了一个双层模型。上层模型解决交通网络应急恢复阶段的选择与排程集成问题，以便最大化交通网络弹复性；下层模型用带时间序列的用户均衡配流模型来刻画上层决策下的用户路径选择行为。该模型也考虑了恢复策略在恢复过程中的效果和交通网络用户的选择行为，能够有效地帮助决策者同时确定应急恢复阶段需要优先恢复的关键路段及其恢复时序。