网络化关键基础设施维修计划、调度与路径联合动态优化研究

The economic development and social well-being of modern societies are highly dependent on networked critical infrastructures, such as power transmission, telecommunications and transportation. These infrastructures need to continuously operate without any breaks. However, their operation is threatened by components aging and wearing, as well as natural disasters and intentional attacks. Thus, it is necessary to timely and effectively maintain them to ensure their reliability. Their components are known to be geographically distributed with future states highly uncertain. To deal with these characteristics, this proposed research will develop dynamic maintenance optimization models, solved by approximate dynamic programming algorithms, to make decisions under uncertainty. To address the transportation problem caused by the geographical distribution of infrastructure components, we will jointly optimize maintenance planning, workforce scheduling and routing. We will also combine robust optimization and approximate dynamic programming to solve for the maintenance plan that is optimal under the worst-case disruption. The proposed research can make significant theoretical and practical contributions in the area of dynamic maintenance decision making under uncertainty for complex systems, joint optimization of multiple decision makings and ensuring the reliability of a system’s continuous operation threatened by multiple risks.

电力、通讯、交通等网络化关键基础设施对促进经济发展、保障人们的幸福生活和增强社会稳定具有至关重要的作用。因此，对它们进行及时有效的维修以保障其可靠性是非常有必要的。这些关键基础设施具有持续运行无间断、地域分布广泛、未来状态高度不确定等特点，并且除了老化、磨损等因素，还受到自然灾害与蓄意破坏的威胁。本研究拟构建动态维修优化模型，并开发近似动态规划算法予以求解，以解决不确定条件下的关键基础设施维修计划优化问题；进行维修计划、维修队伍调度与路径的联合动态优化，以解决地域分布广泛带来的维修计划执行中的维修队伍交通问题，保证计划切实可行；融合鲁棒优化与近似动态规划以求解在最坏破坏情景发生时依然最优的维修计划。课题对解决复杂系统不确定环境下的动态维修决策问题，以及多种决策的联合优化问题，保障系统在多种风险因素下持续运行的可靠性具有重要的理论与实际意义。

本课题主要研究了电力、通讯、交通等关键基础设施的维修优化问题，以有效利用有限资源对其进行维修，保障其持续无间断运行的可靠性。开展维修优化的重要前提是高效的可靠性计算。然而，这些关键基础设施可靠性的计算是典型的NP-hard问题。为解决此问题，我们开发了近似算法，通过寻找可能会共边但具有串并联结构的最小路集实现了对其可靠性的高效近似计算。在此基础上，我们开发了网络化关键基础设施选择性维修优化方法，以解决其可靠性因老化、磨损等因素而持续降低的问题。该方法同时兼顾了维修工作执行过程中对可靠性的影响以及维修工作完成后对可靠性的提升，从而能够有力保障关键基础设施持续无间断运行的可靠性。.为解决关键基础设施所面临的未来状态高度不确定的问题，本课题开发了随机动态规划方法，为未来每一种可能的状态均找到近似最优的维修方案。为应对求解中的“维数灾难”难题，我们开发了近似动态规划算法，利用决策后状态向量将逆向递推转换为前向递推，有力提高了计算效率。接着，我们开发了维修计划与维修人员路径联合优化方法，以解决网络化关键基础设施含组件地域分布广泛的问题，在制定维修计划时即考虑后续维修人员最优交通路径的问题，从而获得切实可行的最优维修计划。.除了老化、磨损等内生风险外，关键基础设施还可能遭受自然灾害与蓄意破坏等外生风险的破坏。为应对此问题，我们研究了关键基础设施灾前维修资源配置优化、关联结构优化、灾后修复优化、载荷重分配优化等问题，以最大化其韧性。在灾后修复优化中，我们研究了多只维修队伍协同优化的问题。我们还将灾前的保护和灾后的修复及载荷重分配联合优化，进一步提高了关键基础设施韧性。针对自然灾害在发生区域、破坏程度等方面存在的不确定性，我们构建了基于拉格朗日松弛的两阶段随机混合线性整数规划方法。该方法能够充分考虑各可能场景对关键基础设施韧性的影响，有效解决不确定性问题。