在灾害管理场景中提升响应能力：评估用于分配技术团队和恢复蜂窝通信功能的算法 Ozcan Dimez, Alper Camci, Tankut Acarman

《Symmetry》：Response Improvement During Disaster Management Scenarios: Evaluation of Algorithms to Assign Technical Teams and to Reactivate Cellular Communication Ozcan Dimez, Alper Camci and Tankut Acarman

　　摘要：应对自然灾害是一项时间紧迫且复杂的任务，需要快速的协调能力和分析技能。自然灾害的应对措施必须迅速实施，资源也需要被高效、有效地利用。自动化系统可以显著减少人为决策错误，提高响应速度，并降低运营成本。本研究提出了一种自动化系统，该系统利用实时移动网络数据来优化团队部署和协调，以修复基站故障并重新部署核心节点受损或拥堵的蜂窝通信网络。研究采用了从优化算法到快速启发式算法的各种方法，用于在自然灾害发生时自动分配技术团队处理故障。这些算法在多目标分配性能方面接受了评估和测试，同时考虑了各种约束条件。研究使用了从基站记录的真实故障数据作为评估依据。评估指标包括平均分配的故障数量、分配效率、自动化分配系统的平均延迟以及技术团队前往基站的行驶距离。为了在自然灾害发生时立即维持协调性和恢复能力，必须重新部署蜂窝通信系统。研究结果表明，通过将位于邻近城市的技术团队立即调度到位，并通过将技术团队的行驶距离最小化到几公里的范围，可以确保新到达的故障得到高优先级的自动处理。与以往的研究相比，本研究通过使用破坏性地震事件后的真实故障数据，并采用电信运营商使用的性能指标，填补了某些空白。

1. 引言
自然灾害、基础设施故障和紧急情况给公共机构和私营部门组织带来了紧迫的、多维度的、复杂的决策挑战。灾害区域内的通信网络中断、信息流动延迟以及技术团队之间的缺乏协调，都会大幅降低应对措施的有效性。在战术性现场操作中，这一问题尤为关键，因为需要同时管理众多变量，这往往导致资源分配不当和损失增加。本研究的核心焦点是提出了一种自动化分配系统。该系统用于评估和测试用于应对地震灾害的分配算法。它处理来自各种来源的数据，特别是基于位置的故障信息和技术团队信息，以及由此得出的故障优先级，从而提高整体响应效果。所提出的程序替代或支持了人工决策过程，确保在紧急情况下资源得到快速和最优的分配。

自然灾害管理包括四个基本阶段：减灾、准备、响应和恢复。减灾阶段涉及长期管理活动，旨在预防或减轻自然灾害可能造成的后果。准备阶段包括规划、培训和基础设施开发，以确保对潜在自然灾害的抵御能力。响应阶段指的是在灾害发生时采取的立即行动，以尽量减少人员和财产的损失。最后，恢复阶段包括灾后重建和恢复工作，以恢复正常生活条件。有效实施自然灾害管理流程在减少灾难影响方面起着关键作用[1]。在调查[1]中，列出了每个灾害管理阶段应用的人工智能（AI）方法。数据可用性被指为准确预测的挑战，计算复杂性受数据规模的影响，数据多样性则对危机期间的处理、管理和决策构成了挑战。研究得出结论，用于自然灾害管理的方法和程序需要具有可解释性和可重复性。

本文提出了一个概念性的决策支持系统（DSS）框架，以便有效整合志愿者参与应急响应规划。该框架包含四个层次：用于整合输入的数据管理层；作为处理核心的分析层；用户界面层；以及决策层。分析层包括用于任务分配和资源分配的优化模型。然而，研究并未展示应急响应规划的具体用例和优化方法，这凸显了现有方法中的不足[2]。

在[3]中，回顾了在自然灾害和疫情期间使用机器学习（ML）算法来高效运作应急服务并最大化利用现有资源的情况。灾害发生后，ML算法被用于确定疏散路线、分类人群情况，并利用物联网（IoT）传感器、基于Android的智能手机集成传感器和无人机（UAV）传感器来预防人群灾难。在[4]中，研究了利用地理信息系统（GIS）和遥感（RS）的AI应用在自然灾害管理中的应用。展示了使用卷积神经网络（CNN）对受损建筑和区域进行分类和绘图的方法。电信基础设施和电信服务被提及为应用领域。

在[5]中，为了危机管理和应急协调，还使用了社交媒体平台和帖子。研究指出，利用社交媒体数据应对危机是有必要的，但现有研究仅使用了X（前身为Twitter）的社交媒体数据集，需要增加原始帖子的数量以更好地理解灾害情况并提高预测准确性。在[6]中，利用包含时间和位置信息的社交媒体数据来分析和分类紧急情况，以便协调资源分配。提取了与紧急情况相关的关键词，并利用帖子提供的时空信息来确定灾害发生的时间和位置。深度学习和BERT模型在召回率方面分别达到了0.8972和0.9808。涉及时空信息的社交媒体数据被用来分析受自然灾害影响公众的情绪和需求。通过将强化学习、自然语言处理和游戏化集成到平台中，AI得到了改进；一些资源如水、食物、医疗援助、避难所和电力被作为灾害响应进行分配，同时完善政策并考虑公众的情绪[7]。然而，使用社交媒体信息进行灾害管理具有挑战性，因为用户可能会传播错误信息，这些信息可能不可信。信息质量，尤其是帖子内容可能因表情符号和不相关字符等因素而较差，这使得从社交媒体提取的信息在灾害管理中难以使用[8]。

[9]中对建模关键基础设施系统间相互依赖性的方法进行了全面回顾。研究表明，极端灾害发生时，这些相互依赖性会导致脆弱性，从而引发连锁故障，严重延迟或阻止响应活动[10]。大数据来源的激增和数据分析技术的快速进步为AI应用在估算灾害相关损失和恢复成本方面的更广泛采用铺平了道路。然而，数据收集和记录过程的标准化不足可能导致经济影响预测的显著差异。在[11]中开发了地震风险数字孪生（SRDT）平台，用于地震管理。该平台可以通过多种数据（包括地理空间数据、结构数据、人口数据和实时传感器数据）来开展灾害管理的所有阶段。AI以类似的方式被整合到SRDT灾害管理中[12]。

在应急管理和恢复操作中，志愿者的组织和协调往往至关重要[13]。有效和及时的志愿者资源管理可以增强社区和组织应对自然灾害、流行病和其他紧急情况的能力[14,15]。虽然志愿者的涌入是有益的，但也带来了重大的管理挑战，需要精心设计的规划模型来确保其潜力得到有效利用[16,17]。将志愿者、技术现场团队和公共机构动态整合到系统中，要求DSS在准实时基础上运行。在[18]中提出了一种集成的DSS架构，其中包含了基于AI的事件检测、数据融合和任务匹配模块。

在[19]中，为 humanitarian 组织的志愿者管理模型适配了一种双标准整数规划模型。为了将个体或志愿者团队分配到任务中，引入了成本函数来表示总短缺成本和不愿意的任务分配数量，同时考虑了志愿者的任务偏好。专家根据扩展信念规则基础（EBRB）方法对志愿者的参数（如自我满意度、经验、同行认可度和合作精神）进行了分类。构建了一个满意度评估模型，基于救援恢复任务与志愿者之间的双向匹配。为了提高志愿者提供的灾害响应效果，使用数据包络分析（DEA）和差分进化（DE）算法对匹配过程进行了验证和优化[20]。

在[21]中，通过众包确定了救援物资的优先级。在考虑紧急需求优先级和资源最大使用限制的情况下，提出了成本函数。根据灾害发生后几小时内伤势的严重程度对需求进行了优先级排序。遗传算法被用来寻找最优解。假设地形较为起伏，定义了当地支持机构的地理位置，使用了数值数据进行分析。通过考虑十个案例来提高实际应用中的效果[22]。在[22]中，提出了利用博弈论在自然灾害管理中分配和分配资源的方法。灾害发生时，参与者为争夺有限资源而竞争。引入了成本函数，并通过纯策略纳什均衡（PSNE）确定了资源分配策略。案例研究用于验证所提出的方法。

在[23]中，资源作为应对自然灾害的分配和最佳使用对于维持幸存者和恢复基础设施功能至关重要。资源规划、组织管理能力、资源支持能力和信息处理能力构成了运营能力[23]。使用分析层次过程（Analytic Hierarchy Process）提出了一个评估指标，以评估中国和韩国的运营能力因素和指标。还计算了全球权重，快速响应和资源分配能力被认为是对运营能力影响最大的因素。

当电信基础设施的核心节点因灾害破坏或通信流量拥堵而无法正常工作时，提出了高通量卫星系统作为蜂窝通信的替代方案，用于覆盖大面积区域[24]。在[25]中，对包括洪水、飓风、冬季风暴、海啸、地震、火灾和雷暴在内的可能自然灾害对电信网络的影响进行了分类。地震具有突然性，会导致电力故障，并通过振动损坏核心节点。通过混合设计方差分析（ANOVA）分析了严重冬季风暴期间和之后的无线流量和短信服务（SMS）模式。研究表明，风暴期间语音通话分钟数和短信数量增加，风暴过后恢复到日常使用水平[25]。

本研究的动机源于2023年2月6日发生的地震灾害。这次地震影响了十一个城市，矩震级为7.8级，影响了土耳其南部和中部以及叙利亚北部和西部，覆盖面积约为35万平方公里，几乎相当于德国的面积，影响了约1400万人，占土耳其人口的16%。所有生活方面的可持续性都受到了严重影响；例如，地震对农业和食品行业的严重影响在[26]中进行了分析。来自电信运营商的移动网络数据显示，手动派遣的技术团队直到第二天才到达灾害区域，以修复基站故障并重新部署蜂窝通信。在第三天，运营效率得到了保证。这种延迟凸显了手动协调的局限性，以及自动化和数据驱动系统的必要性。本文提出的方法填补了现有文献中的空白，介绍了一个自动化的自然灾害响应系统，并对相关算法进行了全面分析。所采用的算法要么具有受时间变化约束的多目标成本函数，要么采用启发式方法。由于警报数量不断增加，且受灾害破坏影响的技术团队数量有限，多目标问题变得难以解决。对分配算法进行了系统评估，并使用在自然灾害极端条件下记录的真实警报数据集对其响应性能进行了比较。与以往的研究（例如[2,5,18]）相比，本研究通过使用破坏性地震后记录的真实警报数据，采用了多目标优化方法以及电信运营商使用的性能指标，填补了特定空白。总体而言，该方案呈现出一种自上而下、适合现场操作的架构，具有自主性、高效性和有效性。此外，所提出的方法使用真实数据集进行了测试，初步结果得到了专业技术人员的验证。

在本研究中，评估和测试了多种算法，包括自适应匈牙利算法（Adaptive Hungarian Algorithm）、混合整数线性规划（Mixed-Integer Linear Programming, MILP）、最小成本流问题（Minimum-Cost Flow Problem, MCFP）、约束编程-可满足性（Constraint Programming–Satisfiability, CP-SAT）、后悔启发式（Regret Heuristic）、遗传算法（Genetic Algorithm）和贪心最近邻算法（Greedy Nearest-Neighbor Algorithm），以评估它们在分配技术团队修复因地震故障的基站警报任务中的性能。数据来源于多个时空维度，包括蜂窝网络分析、应用程序工作流程和基站警报信息，以及技术团队的可用性。该系统实现了自动化，以减少对自然灾害的响应时间，并根据基站位置和连接用户数量定义的优先级约束，将技术团队分配到警报位置，同时确保最小化旅行距离。通过多目标优化，选择相对旅行距离最小的技术团队来处理警报，同时优先处理高优先级警报。因此，通过快速高效地重新部署移动通信服务，增强了对应急灾害的响应能力。

本研究的贡献如下：
(i) 选定的算法涵盖了从精确优化到快速启发式方法的整个范围。这些算法被用于应对自然灾害，并通过关键性能指标进行比较，如基于优先级的警报分配率、技术团队与警报之间的相对旅行距离以及算法的响应时间。实施了一个实际程序，当警报数量超过技术团队数量时，通过将未分配的警报修复任务转移到下一个时间窗口来确保警报分配的连续性。
(ii) 域知识函数：加权成本函数结合了测地距离、警报优先级和地理集群完整性，以最小化响应时间和总旅行距离。
(iii) 在地震影响区域的站点优先级和干预优化：本研究利用了哈塔伊地区电信运营商基础设施的全面数据，结合2023年的地震事件。数据集包括所有站点的警报记录、它们作为紧急集结中心的指定、在服务关键基础设施站点中的作用以及它们的运营关键性级别。根据连接到每个基站的手机用户数量生成热图或变化情况。同时，收集了要部署到受灾地区的技术团队的位置数据。利用这个多维数据集，系统地对警报进行分类，根据计算出的优先级进行排序，并与可用的技术现场团队资源匹配。实验场景表明，这种程序能够及时有效地分配基站警报，替代了传统的手动监控和决策方式。

本文的结构如下：引言部分介绍了研究的动机、文献回顾和贡献。第二部分详细解释了自然灾害的数据集，并阐述了流程图和方法论。展示了利用位置信息和警报优先级融合警报和技术团队的流程图。采用分配算法来应对自然灾害，给出了它们的公式，包括自然响应多目标和约束条件的制定。第三部分提出了实验研究，评估和测试了分配算法的性能。根据不同数量的技术团队，使用性能指标比较了算法的性能，以分析对地震灾害响应的改进情况。最后给出了研究的一些结论。

为了应对地震灾害并确保灾区的蜂窝通信，需要分配技术团队来修复无法正常工作的基站并消除警报信号。控制和指挥（C&C）中心收集警报信号，然后将警报分配给技术团队，以响应这些警报并使受损或因异常运行条件而拥堵的基站恢复正常运行。由于受地震影响地区的本地技术团队可能因通信故障或自身受伤而无法到达，因此会从地震区域外部（如邻近城市部署的团队）调派技术团队来修复基站警报。这些救援技术团队被命令前往地震灾区。

所提出的系统处理来自不同来源的数据，特别是基于位置的警报和技术团队信息。利用警报的优先级来提高整体分配性能。测试场景使用了在其他数据集中记录的技术团队位置信息。图1展示了所提出的自动化分配系统的流程图。地震发生时，会触发分配技术团队的过程。例如，触发信号可能来自区域地震海啸监测中心，以启动这一灾害响应程序。流程图分为两个分支：第一个分支收集因地震破坏效应而产生的基站警报，确定警报优先级，并按5分钟的时间间隔分组警报，包括警报类型、位置和用户数量以计算其优先级。这些警报会被缓存，直到被分配给技术团队。第二个分支是通过数据库提取技术团队的位置和可用性。通过移动应用程序或其他互联网消息工具发送通知来确定技术团队的可用性。在地震周边选择技术团队，并可以扩展覆盖范围以分配更多技术团队。然后，在后端服务器中使用开放路线服务（Open Route Service, ORS）和道路数字地图数据，应用ORS提供的路由来计算团队i与警报j之间的相对距离。通过多目标优化算法，在满足约束条件的情况下，将技术团队分配给警报，同时最小化其成本函数。当警报未被分配给技术团队时，它会被放入待分配列表中，在下一个5分钟的时间间隔内继续等待分配。

2. 技术团队对基站警报的分配作为应对地震灾害的措施
为了应对地震灾害并确保灾区的蜂窝通信，需要分配技术团队来修复无法正常工作的基站并消除警报信号。控制和指挥（C&C）中心收集警报信号，然后将警报分配给技术团队，以响应这些警报并使受损或因异常运行条件而拥堵的基站恢复正常运行。由于受地震影响地区的本地技术团队可能因通信故障或自身受伤而无法到达，因此会从地震区域外部（如邻近城市部署的团队）调派技术团队来修复基站警报。这些救援技术团队被命令前往地震灾区。

所提出的系统处理来自不同来源的数据，特别是基于位置的警报和技术团队信息。利用警报的优先级来提高整体分配性能。测试场景使用了在其他数据集中记录和更新的技术团队位置信息。图1展示了所提出的自动化分配系统的流程图。地震发生时，会触发分配技术团队的过程。例如，触发信号可能来自区域地震海啸监测中心，以启动这一灾害响应程序。流程图有两个分支：第一个分支收集因地震破坏效应而产生的基站警报，确定警报优先级，并按5分钟的时间间隔分组警报，包括警报类型、位置和用户数量以计算其优先级。这些警报会被缓存，直到被分配给技术团队。第二个分支是通过数据库提取技术团队的位置和可用性。通过移动应用程序或其他互联网消息工具发送通知来确定技术团队的可用性。在地震周边选择技术团队，可以扩展覆盖范围以分配更多技术团队。然后，在后端服务器中使用开放路线服务（ORS）和道路数字地图数据，应用ORS提供的路由来计算团队i与警报j之间的相对距离。通过多目标优化算法，在满足约束条件的情况下将技术团队分配给警报，同时最小化其成本函数。当警报未被分配给技术团队时，它会被放入待分配列表中，在下一个5分钟的时间间隔内继续等待分配。

2.1. 数据集
数据集由蜂窝通信基站报告的故障和运行故障原因的警报组成，始于2023年2月6日发生在土耳其的地震。该数据集涵盖了11个受影响的城市，包括城市和郊区地区。它代表了一个大规模的灾害场景，涉及广泛地理区域内众多基站的同时发生警报。在24小时内，数据集包含了来自不同省份和现场位置的5500个警报。数据集捕捉了单日内生成的警报，24小时被划分为5分钟的时间间隔（共288个时间组），以模拟时间流动，即00:00到00:05、23:55到23:59。使用5分钟时间间隔的理由是一些警报是由基站站点故障或部分站点故障引起的。这类临时警报通常在5分钟内得到解决，因此不需要分配技术团队。在24小时内的总共10,570个警报中，有5,070个警报在5分钟内自行修复。因此，使用5分钟的时间间隔来累积警报。

2.2. 灾害场景下算法的实现
为了评估和测试，选择了一系列算法，涵盖了从精确优化到快速启发式方法的整个范围。自适应匈牙利算法（Adaptive Hungarian Algorithm）因其对5分钟时间间隔内动态快照的最优性而被选中，用于分配技术团队处理警报。其优先级加权能力在成本矩阵中赋予了较高的权重，该权重会定期计算[27,28]。自适应匈牙利算法生成动态响应。混合整数线性规划（MILP）被选为基准测试的性能基线。MILP通过确保二进制分配决策和线性约束来呈现多目标和约束条件。MILP算法适用于规划和模拟目的，即离线使用[29,30]。最小成本流问题（MCFP）类似于MILP，但它具有网络流结构。MCFP流模型能够高效地为线性分配结构计算最优解，适用于约束条件有限的大规模实例[31,32]。约束编程-可满足性（CP-SAT）模型使用二进制变量和分配约束构建。当分配问题必须结合复杂的逻辑或组合约束并在给定时间内满足约束时，CP-SAT特别有效[33,34]。当计算资源极其有限且问题复杂性较低时，后悔启发式算法（Regret Heuristic Algorithm）是可行的[35,36]。与基本的贪心最近邻算法（Greedy Nearest-Neighbor）相比，它有显著改进。遗传算法（Genetic Algorithm）是一种适用于复杂非凸目标的强大元启发式方法。当精确模型速度过慢时，它是另一种选择，但需要调整且不保证最优解[37,38]。贪心最近邻算法是一种实时基线方法。贪心启发式算法反复在所有可行对中选择成本最低的技术团队-警报对。尽管它在计算上成本低廉且适用于实时调度，但在全局效果上可能不佳[39,40]。

在本研究中，采用了多种算法来评估它们在分配技术团队处理警报方面的性能，作为受约束的多目标优化问题。目标是在可用团队和警报的集合中，根据最小相对旅行距离分配技术团队；最大化警报的分配率，确保所有警报都被分配给技术团队；最后，优先处理高优先级的警报。采用算法的成本函数和约束条件以满足多目标要求。必须将一组技术团队分配给具有优先级和空间位置的警报集合。表示在5分钟时间间隔内可用的技术团队集合，表示在前一个时间间隔内发生的警报集合。由于警报是由地震效应引起的，因此需要分配的警报数量超过了可以同时部署的可用团队数量；(1)自适应匈牙利算法是经典匈牙利算法的扩展，它动态调整成本矩阵以处理多目标和时变约束。分配对（团队i，警报j）的成本函数由以下公式得出：(1)其中表示对（团队i，警报j）之间的相对距离，是组合优先级，是分配率，和是自适应的正权重值，这些权重值根据最小化行驶距离、最大化技术团队对高优先级警报的分配率进行迭代调整[41]。该算法解决了标准的分配成本函数：(2)二进制决策变量定义为：(3)MILP是一个精确的数学模型，其中多目标问题被表述为使用正权重值的单一目标：(4)每个技术团队最多只能分配给一个警报，每个警报最多只能被一个技术团队分配：(5)其中二进制决策变量由(3)给出。(3)MCFP在流网络上对分配问题进行建模。该算法创建了一个二分图：源节点连接到所有技术团队节点，容量=1，成本=0；技术团队连接到警报节点，容量=1，成本函数由以下公式给出：(6)任务节点连接到汇节点，容量=1，成本=0。从到的总流量受到流量守恒和容量约束的限制，其中是二进制决策变量。(4)CP-SAT模型是一种使用布尔逻辑和有限域变量的声明性方法。CP-SAT是一种现代的完全求解器，结合了约束编程、基于满足性的搜索和线性规划（LP）的思想。它主要用于具有离散约束的调度和分配问题。其目标是通过表示组合优先级、分配率和所有技术团队对警报（团队i，警报j）之间相对距离的加权和来最大化函数：(8)其中，和是自适应权重。约束与MILP定义中的相同，如下所示：(5)遗憾启发式算法是一种建设性的、类似贪婪的启发式方法，它考虑了未做出最佳分配的成本。对于每个未分配的技术团队，它计算：(9)这种表述代表了未分配最高优先级警报任务的机会成本。算法首先将具有最大遗憾的技术团队分配给最高优先级的警报，然后更新并重复这一过程。优先级通过定义(10)来整合。(6)遗传算法是一种基于种群的元启发式方法，受到自然选择的启发。它是一种基于种群的元启发式方法，通过选择、交叉和变异来进化候选分配。针对地震和技术团队对警报的分配问题，典型的分配编码、适应度函数以及选择、交叉、变异和进化阶段如下所示：染色体被定义为。每个基因代表分配给警报i的团队。算法通过这些变量来最小化适应度函数：(11)其中表示分配率的总和，表示行驶距离的总和，是总优先级，和是正权重值。基于种群的元启发式方法执行如下：选择：选择父染色体（例如，锦标赛选择）。交叉：结合父染色体以产生后代（例如，有序交叉—OX—以保持排列的有效性）。变异：随机交换两个基因或突变一个片段。进化：迭代选择、交叉和变异以创建新世代，保留最适合的个体。(7)贪婪最近邻算法是一种简单的启发式方法，它基于最近距离（或最低“有效成本”）进行分配。对于自然灾害响应，它优先考虑高优先级，而不仅仅是相对距离。对于警报-技术团队分配，通过以下公式定义得分：(12)算法步骤如下：重复选择所有警报，直到它们被分配给一个技术团队。找到技术团队和警报之间的未分配对，给出最高得分。将技术团队分配给警报。标记两者都已分配。所选算法涵盖了从精确优化到快速启发式的范围。贪婪最近邻和遗憾启发式提供了适合时间紧迫响应的快速解决方案，但不能保证最优性。匈牙利算法能够高效地为线性分配结构计算最优解，并且非常适合具有有限约束的大规模实例。MILP和MCFP模型提供了最大的建模灵活性，可以捕捉真实的灾难响应需求，但计算工作量增加。CP-SAT能够快速提供可行解决方案，并且它被应用于从具有复杂规则和附加约束的调度到紧急响应用例的测试中。当问题结构或规模使得精确方法不切实际时，遗传算法提供了灵活的替代方案。这些方法共同使得使用在自然灾害极端操作条件下记录的真实警报数据集来系统评估灾难响应性能成为可能。3. 实验研究使用2023年2月11日的数据集进行实验。来自非常广泛地理区域的众多基站同时发生了警报。数据集包含5500个警报。除了真实的警报和现场数据集外，测试场景还使用了技术团队的位置数据。数据集包含了全天发生的警报。时间线通过将24小时的一天划分为5分钟的子组（288组）来模拟，例如00:00和00:05、23:55和23:59等。位置数据包括分布在国家内随机选定位置的642个技术团队，以便评估和测试技术团队分配方法的性能。技术团队从地震区之外选出，并被要求修复地震影响区域的基站警报。在后台服务器中使用开放路线服务（ORS）来计算给定警报位置与可用技术团队位置之间的相对距离[42]。对（团队i，警报j）之间的相对距离是数字道路地图匹配的距离，它表示候选技术团队到达给定警报位置所需的行驶距离，确保导航的最佳路线。分配率定义为分配给技术团队的警报数量与需要分配的总警报数量之比。一个警报在技术团队修复之前被视为已分配，而在分配给技术团队之前被视为未分配。警报可以在其发生后的第一个5分钟子组内被分配，或者该警报可以被推迟到下一个5分钟子组。警报的总数等于已分配的警报数量和未分配的警报数量，新到达的警报在图2中绘制，被推迟的警报在图3中绘制。分配率的范围是[0, 1]。图2. 累计警报与分配。图3. 未分配和被推迟警报的时间响应。优先级被计算出来，并作为多目标成本添加到总体成本中，由(1)至(12)给出，以奖励选择具有更高优先级的基站和警报。第一个优先级项与基站的位置有关。当基站的天线范围覆盖责任关键和安全关键点（如灾难和紧急管理救援单位、机场、医院、政府建筑等）时，该基站会被优先考虑。显然，这些优先级的基站在灾难和危机管理的初始阶段必须能够正常运行。数据集中将优先级作为配置参数分配给基站。第二个优先级项与连接到基站的订阅者数量有关。技术团队的分配优先级确保拥有更多移动通信订阅者的基站能够正常运行。它在一天结束时计算，即00:00，作为前一天与当天连接到同一基站的订阅者数量之间的差异，即热图，考虑了该区域内所有基站的订阅者数量差异。这个优先级值是基站位置和每个基站的订阅者数量的加权平均值，如下所示：pj = α.x + (1 ? α).z (13)其中x表示给每个基站位置分配的优先级值，z表示订阅者数量之间的差异，α是权重值，范围在[0, 1]之间，由专家技术操作员选择为α = 0.7。图2中用蓝色绘制了随时间累积的警报数量。截至2月11日00:00，警报数量在增加。使用自适应匈牙利算法、MILP、MCFP、CP-SAT、遗憾启发式算法和贪婪最近邻算法将警报分配给技术团队。评估并比较了技术团队对警报的分配性能。所有算法都将警报分配给技术团队，最终达到警报的总数，即5500个。图3绘制并比较了未分配警报的数量，说明了算法将技术团队分配给即将到来的警报的能力。初始时间（即00:00）时，未分配的警报数量为零，因为可用的技术团队数量多于初始5分钟时间窗口内的警报数量。比较了未分配和被推迟到即将到来的5分钟时间间隔的警报的算法结果。与图4中绘制的分配率响应一致，MILP和MCMF算法在优化分配率目标方面表现更好，更成功地减少了未分配警报的数量。自适应匈牙利算法利用其加权能力，充分减少了未分配的警报数量。作为实时算法，贪婪最近邻算法在初始阶段同时最小化了成本。随着新警报的到来，需要分配的警报总数增加，基于贪婪的方法由于无法优化团队分配而无法最小化未分配的警报数量。但其性能在减少未分配警报方面是足够的。CP-SAT、遗憾启发式和遗传算法在未分配警报数量方面达到了最高水平。它们不能保证最优性或成本最小化，但它们在第二天中午之前通过空间索引和成本函数的最优解（分别由(8)、(9)和(11)给出）分配了所有累积的警报。图4. 累计分配率。图4中绘制并比较了随时间变化的累计分配比率。MILP和MCMF的时间响应分别用绿色和红色绘制，它们在约束条件下使用多目标解决方案实现了高分配率。在整个分配过程中，它们的最优解决方案最大化了分配率响应。在初始阶段以及随着警报的累积，累计响应率有所下降，但与其他算法相比，它们的最优解决方案在提高分配率方面表现更好。贪婪最近邻算法作为快速基线算法，通过其在分配过程初期选择最小成本的能力，展示了最高的分配率。随着新警报的到来和警报的累积，它无法保证最优性，与MILP和MCMF相比。自适应匈牙利算法用橙色绘制，它权衡了分配率的最大化，并响应了即将到来的警报。其累计分配率响应显示出下降，由于警报数量的增加和计算成本的增加，在初始阶段导致性能下降。CP-SAT通过紫色曲线展示了累积响应率的提升，这是需要最大化的目标，但其分配响应性能相较于MILP、MCMF、自适应匈牙利算法和贪婪最近邻算法表现较差。遗憾启发式算法由于技术团队与警报分配之间的复杂性，在其他算法中实现了最低的分配率性能。遗憾启发式方法在灾难响应过程中面临更复杂的响应条件，这受到不断增加的警报数量和可用技术团队数量减少的影响。遗传算法作为一种强大的元启发式解决方案，由于无法保证最优解，因此在实现多个目标中的警报分配率最大化方面表现不佳。另一个成本目标是最小化技术团队位置与警报位置之间的相对距离。图5比较了每个警报的平均响应时间。自适应匈牙利算法通过在其多目标成本矩阵中显著惩罚旅行距离成本（公式（1）来体现其优先级权重，从而优于其他算法。相反，尽管贪婪最近邻算法在分配率响应方面表现良好，但它无法进行多目标优化和最小化旅行成本，甚至会在较高的旅行距离下进行团队分配。采用贪婪方法时，由于所有技术团队已被分配并忙于处理警报修复任务，更多的警报会被转移到下一个时间窗口进行处理，从而导致更长的旅行时间和距离。贪婪最近邻方法无法优化团队分配。MILP和MCMF通过使用多目标和分配约束（公式（4）至（7）来最小化旅行距离成本，但与自适应匈牙利算法相比，它们会导致相对距离加倍。CP-SAT、遗憾启发式和遗传算法在分配时也能将旅行距离成本降至与MILP和MCMF相同的水平。遗憾算法在公式（10）中的优先级计算略微提高了分配性能。图5显示了技术团队的平均旅行时间。图6绘制并比较了每种算法下可用技术团队与警报之间的分配旅行距离数据。自适应匈牙利算法的平均分配距离是所有算法中最低的，其最大旅行距离值也低于其他算法。基于贪婪选择的最近邻算法导致了最长的旅行距离。尽管它提供了最低的旅行距离数据，但由于缺乏多目标优化能力，其旅行距离也是最长的。旅行距离数据下半部分的中位数高于自适应匈牙利算法数据的上半部分中位数，表明基于贪婪选择的团队分配并未涉及旅行距离的最小化。MILP、MCMF、CP-SAT、遗憾启发式和遗传算法的数据箱线图显示了相同的旅行距离中位数水平。遗憾算法数据集中的最小值非常接近旅行距离数据下半部分的中位数，表明其在公式（10）中的优先级整合有助于最小化旅行距离。MILP、MCMF、CP-SAT、遗憾启发式和遗传算法的数据中的最大旅行距离处于同一水平。CP-SAT和遗憾启发式在多目标优化方面与MILP和MCMF相同，都惩罚了相对距离成本。图6展示了旅行距离响应分布的比较。响应时间定义为警报发生到被技术团队处理之间的时间间隔。在自然灾害场景中，需要评估和测试分配算法的响应时间。图7绘制了每种算法的响应时间箱线图，以比较平均响应时间以及响应时间数据分布中的最小和最大响应时间。对于MILP和MCMF算法，响应时间的中位数接近数据下半部分的中位数（即第一四分位数Q1），但中位数也显著低于数据上半部分的中位数（即第三四分位数Q3），这表明随着分配问题复杂性的增加（由于可用团队数量减少和新到达及累积的警报数量增加），这两种算法也可能导致更长的响应时间。尽管CP-SAT的旅行距离成本最小化水平与MILP和MCMF相当，但其响应时间的变化较大。遗憾启发式和遗传算法的数据显示出非常相似的响应时间分布。贪婪最近邻算法的响应数据显示了其实时基线调度能力，但随着新警报到达率和警报累积率的增加，可用技术团队数量减少。基于人口的元启发式算法导致的最大响应时间高于自适应匈牙利、MILP和MCMF等多目标算法。自适应匈牙利算法的数据显示，其响应数据中的最小值接近数据下半部分的中位数，而数据上半部分的中位数和最大值与MILP和MCMF的数据相同。其中位数略高，表明自适应匈牙利算法需要更多时间来完成分配。图7比较了响应时间分布。为了应对自然灾害，需要根据最小相对距离和算法的最小响应时间将优先级较高的警报分配给技术团队。分配算法必须快速，并且应优先处理优先级较高的警报。作为测试场景，通过分配结果来评估算法的性能，包括那些组合优先级超过75%的警报，在60分钟内完成。在5500个警报的数据集中，组合优先级超过75%的警报总数为1195个。对于紧急响应评估，评估了优先级超过75%且算法响应时间少于60分钟的警报的分配算法性能。图8绘制了分配技术团队位置与警报位置之间的平均相对距离与完成时间的95%的关系。完成时间是通过将分配算法的响应时间、旅行时间以及技术团队到达基站后修复警报所用的平均时间相加计算得出的。图8比较了95%的警报修复时间与每次分配的平均距离。选择了响应时间少于60分钟的分配结果。如果响应时间超过60分钟，则这些分配结果不被包括在内也不进行比较。图8根据给定的紧急标准评估了分配响应。自适应匈牙利算法在60分钟内分配了54%的高优先级警报。在这些警报中，95%在1725分钟的完成时间内被处理，分配到的警报与技术团队初始位置之间的距离为36公里。MILP和MCMF算法在60分钟内完成了100%的高优先级警报的分配。95%的警报在1400分钟的完成时间内被处理，但分配到的警报与技术团队初始位置之间的距离增加了两倍以上，达到100公里，而自适应匈牙利算法仅为36公里。MILP和MCMF在给定约束条件下进行了多目标优化。更明显的是，自适应匈牙利算法在相同的旅行距离下分配了半数警报。自适应匈牙利算法具有更多的多目标优化能力，但在这种极端紧急响应场景中不如MILP和MCMF高效。CP-SAT和遗传算法分别在这类优先级下分配了98%和95.6%的警报。与MILP和MCMF相比，95%的警报在更长的时间内被处理。遗憾启发式算法在这类优先级下分配了57.3%的警报，但在最高服务时间内完成了95%的警报。贪婪最近邻算法的分配性能较差，因为它无法在约束条件下进行优化，导致分配的相对距离较长。此外，它在60分钟内为93.5%的此类优先级警报分配了团队，且警报修复完成时间与MILP和MCMF算法相当。技术团队数量不同，评估了选定分配算法的性能，并与地震灾难当天实际存在的642个技术团队的数量进行了比较。使用了7种不同的团队数量，即100、200、400、642（默认值）、800、1000和1200个团队，并随机生成和测试了每个团队的位置。由于随机化，每种团队数量的模拟场景重复了10次。图9显示，对于不同数量的团队，自适应匈牙利算法分配警报的速率高于其他算法。MILP、MCMF、遗憾启发式和遗传算法随着团队数量的增加而提高了分配率性能。贪婪最近邻算法的分配率随着团队数量的增加而线性增长。当团队数量低于500时，CP-SAT的分配率较低。当团队数量超过642时，所有算法的分配率均为100%。图9显示了分配率与技术团队数量增加的关系。在分配警报的同时，第二个目标是最小化技术团队初始位置与警报位置之间的相对距离。图10评估了不同团队数量下的情况。自适应匈牙利算法对技术团队数量的变化不敏感，并在最小化相对距离的同时分配警报。MILP、遗憾启发式、遗传算法和贪婪最近邻算法利用团队数量的增加带来了改进。由于无法优化，贪婪最近邻算法在其他算法中以最高的相对距离成本进行分配。其旅行距离最小化目标在所有团队数量下都表现不佳。CP-SAT没有表现出多目标优化能力，因为其响应时间变化较大且独立于团队数量。MCMF也对团队数量的增加不敏感，并且在相对距离较大的情况下仍能将技术团队分配给警报，但它能够在不同约束条件下实现多目标优化，并确保较低的旅行距离。图10显示了相对距离响应与技术团队数量增加的关系。图11测试并比较了每种算法对警报的响应时间与技术团队数量增加的关系。当团队数量低于500时，自适应匈牙利算法的响应时间低于两种多目标优化算法MILP和MCMF。当团队数量超过500时，贪婪最近邻算法不受团队数量增加的影响，能够在较短的响应时间内分配更多警报。在增加团队数量的同时，MILP、MCMF、自适应匈牙利算法和遗憾启发式算法都实现了响应时间的最小化，这些响应时间与团队数量的增加成反比，这表明了有更多团队可供分配给警报所带来的积极影响。遗憾启发式算法始终是最快的，而当技术团队数量超过800个时，自适应匈牙利算法的速度也会变得非常快。图11展示了响应时间与技术团队数量增加之间的关系。总体而言，根据图2至图8中绘制的响应情况，表1对7种警报团队分配方法在地震灾害响应中的性能进行了定性比较（这些方法采用了三目标优化）。表1总结了相对距离和响应时间的数据分布，并进行了定性比较。图9至图11中的可扩展性测试结果在表1中也进行了对比，以评估每种分配方法的可扩展性表现。

实验使用了一台配备Intel i7 13620H CPU（运行频率为4.6 GHz）和32 GB内存的笔记本电脑进行。操作系统为开源的Ubuntu 22.04，编程语言使用Python 3.14。MILP使用了Python的线性规划API，CP-SAT算法使用了CP-SAT求解器。Scikit-learn中的sklearn.neighbors模块用于最近邻算法，scipy.optimize包用于优化算法，其中的scipy.optimize.linear_sum_assignment函数用于自适应匈牙利算法中的二分图最小权重匹配。

**结论**
本文评估并测试了一系列从精确优化到快速启发式算法在地震灾害响应中的性能。通过性能指标对分配算法进行了全面评估，旨在实现自动化系统，以消除人为错误、提高速度并降低运营成本。首先且紧急的是，必须确保蜂窝通信的畅通。电信运营商必须首先到达并修复受损的基站基础设施。但由于受灾区域规模庞大以及需要分配给警报的技术团队位置分布的复杂性，人工操作员在立即分配技术团队、救援人员和志愿者时可能会遇到延迟和决策错误。传统方法依赖于手工操作。本文提出的自动化系统旨在消除人为错误、提高速度并降低运营成本。评估了一系列从精确优化到快速启发式算法的分配方法，并通过关键性能指标（如根据优先级分配警报的比率、技术团队初始位置与警报位置之间的相对行驶距离以及算法的响应时间）进行了比较。实际应用中使用了地震灾害响应期间记录的警报数据。

在灾害响应中，必须根据优先级立即分配警报。技术团队需要以最短的行驶距离和时间到达警报位置，这是分配技术团队的另一个目标，即选择与警报相对距离较近的团队。在紧急分配情况下（例如优先级较高的警报且要求算法响应时间小于60分钟），自适应匈牙利算法、MILP和MCFP能够确保较低的行驶距离和响应时间。这些多目标优化算法在满足约束条件的同时，提高了响应速度和相对距离的接近度。相比之下，CP-SAT和遗传算法虽然分配时间较长，但响应时间和服务效率尚可。遗憾启发式算法虽然考虑了警报的优先级，但无法最小化成本，其性能低于自适应匈牙利算法、MILP和MCFP。贪心最近邻算法在初始阶段能够实时将警报分配给技术团队，但由于其贪婪的选择方式，随着新警报的到来和技术团队数量的减少，长期性能较差，无法同时优化多个目标。作为案例研究，自适应匈牙利算法在60分钟内完成了54%的高优先级警报分配，分配后的警报与技术团队初始位置之间的距离为36公里。MILP和MCMF算法在60分钟内完成了100%的高优先级警报分配，但分配后的警报与技术团队初始位置之间的距离增加了两倍以上（分别为100公里和36公里）。CP-SAT和遗传算法分别完成了98%和95.6%的高优先级警报分配。遗憾启发式算法完成了57.3%的高优先级警报分配，但其中95%的警报在最长服务时间内得到响应。贪心最近邻算法由于无法在约束条件下进行优化，导致分配的相对距离较长。此外，虽然93.5%的高优先级警报在60分钟内得到响应和分配，但其修复时间与MILP和MCMF算法相当。尽管响应的警报数量较少，但由于贪婪的选择方式，修复时间较短。

所提出的自动化系统及其核心分配算法可以应用于其他自然灾害场景。紧急情况下需要将有限的资源（即蜂窝通信领域的技术团队）分配到警报位置。优先级排序对于首先满足紧急和关键责任点（如灾害和应急管理救援单位、机场、医院、政府建筑等）的需求至关重要。洪水、飓风、冬季风暴、海啸、地震、火灾和雷暴等自然灾害会破坏基础设施和住宅建筑，因此基于位置的决策方法可以借鉴本文提出的方法。该方法消除了手动协调的局限性，是传统手动监控和决策方式的替代方案。后端服务器使用了Open Route Service（ORS）提供的道路数字地图数据和路由信息来计算实际行驶时间。未来的研究和发展方向可以包括收集技术团队和志愿者关于受损建筑、封闭道路以及待救援人群位置的反馈信息。这些信息可以通过智能手机上的灾害响应移动应用程序捕捉并共享图像以及时间和位置信息来获取，从而优化所有救援团队的调度。