在项目持续时间不确定的情况下，用于南极研究的综合随机项目选择与调度方法

《Computers & Industrial Engineering》：Integrated stochastic project selection and scheduling for antarctic research under uncertain project durations

　　摘要
我们研究了随机研究项目选择与调度问题（SRPSAP），这一问题的提出是受到南极实地考察活动的启发。规划者在不确定性消除之前必须选择一个研究项目组合，并为每个情景制定出符合优先级、时间窗口、稀缺可再生资源以及站点间转移时间要求的可行多站点调度计划。我们将SRPSAP视为一个两阶段随机混合整数编程问题，旨在最大化预期净利润，并开发了四种解决方法：（i）使用商业求解器直接求解；（ii）整数L形分解（IL-S）；（iii）结合模拟退火的混合IL-S（IL-S+SA）；（iv）针对整个随机问题的模拟退火（SA-SP）。列表调度程序明确处理资源分配和转移，并提供快速的可行性检查。在36个反映南极实际物流情况的合成实例上，我们比较了各种方法的解决质量和运行时间。精确方法往往需要过多的计算资源。IL-S在平均差距上表现优异，并能提供有用的界限，而SA-SP通常是最快的方法，但重复运行时结果的稳定性较差。在某些情况下（例如，预测范围较短或站点较少时），混合IL-S+SA能减少差距；而随着站点数量和资源类型的增加，单独使用IL-S更为稳定。这些结果表明，明确建模不确定性并将分解与可扩展的元启发式算法结合使用，可以为极地作业制定出实用且高价值的计划。我们发布了一套可复制的实例，并讨论了扩展到多目标风险控制、相关不确定性以及更复杂的海空物流方面的可能性。

引言
在南极进行科学项目的规划和执行是一个复杂的优化挑战，因为需要在研究活动的高科学价值与极地地区严苛的物流和环境限制之间取得平衡。南极在调节全球气候、海洋环流和生态过程方面起着基础性作用，因此对该大陆的持续研究对于理解全球环境变化至关重要（Kennicutt等人，2015年）。然而，极端的偏远性、有限的运输能力和不可预测的天气条件给项目执行带来了显著的不确定性，经常影响项目持续时间和资源可用性（Kennicutt等人，2014年）。这些独特条件意味着研究规划不能依赖确定性调度，而是需要采用能够明确纳入活动持续时间不确定性和稀缺资源分配的优化方法。本研究探讨了多站点南极站点的随机研究项目选择与调度问题（SRPSAP），该问题扩展了随机项目组合和调度模型，以适应活动持续时间不确定的多站点南极作业。问题要求决策者在第一阶段根据项目的预期科学和经济价值选择项目，然后在第二阶段确定如何在多个站点之间安排这些项目。模型考虑了优先关系、有限的可再生和不可再生资源、严格的时间窗口以及站点间资源转移的可能性，转移时间进一步限制了调度的可行性。与确定性模型不同，SRPSAP明确考虑了环境变化因素，如风暴、冰况和操作延误，从而产生了项目完成时间各异的复杂情景（Vega-Hidalgo等人，2026年）。因此，该问题被构建为一个两阶段随机混合整数编程模型，其中第一阶段的二进制选择决策与第二阶段的情景依赖调度子问题相结合。这项工作直接建立在Vega-Hidalgo等人（2026年）提出的确定性多站点南极站点研究项目选择与调度问题（RPSAP）的基础上，并在结构上进行了重要扩展。在确定性模型中，项目选择和调度是为活动持续时间的一个具体实现定义的；相比之下，SRPSAP引入了依赖情景的项目持续时间以及一个两阶段随机结构，第一阶段的项目选择决策必须通过第二阶段的补救调度在多个情景中保持可行性。这种转变不仅改变了不确定性的表示方式，也改变了决策逻辑，因为现在必须根据项目在多个操作实现中的预期表现和可行性来评估选择方案。SRPSAP处于两个成熟研究领域的交叉点：随机项目组合选择问题（SPPSP）和随机资源受限项目调度问题（SRCPSP）（Habibi等人，2025年）。SPPSP通常考虑项目成本、收入或成功概率的不确定性，并在预算或风险约束下最大化预期组合价值；然而，它们通常通过预算或截止日期等替代指标来表示时间和资源影响，而不是通过明确的活动级调度（Nascimento等人，2025年）。相比之下，SRCPSP文献强调在不确定性下调度优先级可行的活动，同时考虑资源限制。尽管文献中存在相关的综合方法，但很少有研究同时结合项目选择、详细的多站点调度、站点间转移和依赖情景的补救措施。

解决SRPSAP在计算上具有挑战性，因为它将第一阶段的二进制组合决策与第二阶段的情景依赖调度子问题结合在一起，而后者本身是RCPSP的变体。每个情景都需要构建尊重时间窗口、资源容量和站点间转移延迟的优先级可行调度，从而显著增加了组合复杂性（Bigler等人，2024年）。此外，可能的情景数量随着不确定性的增加而增加，导致随机规划中众所周知的“维度灾难”（Li & Womer，2015年）。标准商业求解器可以优化处理小规模实例，但随着项目数量、站点数量和情景数量的增加，其扩展性较差（Dashti等人，2025年）。即使是像整数L形分解这样的分解方法，在子问题调度计算密集时也会遇到收敛困难（Fu等人，2024年）。这些限制突显了需要制定结合精确方法和启发式/元启发式技术的定制化解决方案策略，以实现解决方案质量和可扩展性。

在这种计算要求高的环境中，仅在建模项目持续时间上的不确定性是一个有意图且合理的选择。在南极作业中，活动持续时间是最直接受到环境变化影响的参数：风暴、海冰状况和物流中断会以难以在规划阶段预见的方式延长或压缩野外工作窗口（Kennicutt等人，2014年）。关键的是，持续时间不确定性会贯穿决策过程的两个阶段。在第一阶段，一个在预期持续时间下看起来有利可图的项目可能在不利的情景下变得不可行或导致损失，从而影响最终选择的项目组合。在第二阶段，持续时间的具体情况决定了所选项目是否能在所有站点的时间窗口和资源限制内得到合理调度。其他参数（如资源可用性、转移时间和项目收入）被视为确定性的，不是因为它们被完全知道，而是因为将不确定性集中在持续时间上可以使模型隔离并分析核心规划挑战，同时保持计算可行性。将随机结构扩展到其他参数是未来工作的自然方向。为了解决SRPSAP，我们提出了一个由四种互补策略支持的两阶段随机编程模型。首先，使用最先进的商业求解器解决随机模型，为小规模实例建立最优基准。其次，我们开发了一种适应SRPSAP结构的整数L形分解方法。第三，我们探索了一种结合模拟退火的混合分解方法，以提高随机补救评估的可扩展性。最后，我们提出了一种专为SRPSAP量身定制的独立模拟退火元启发式算法，为大规模情况下不实用精确方法提供高质量的近似解决方案。这些方法共同提供了一种平衡策略，将精确优化与启发式灵活性结合起来，以提高可扩展性和鲁棒性。

通过36个模拟南极物流情况（其中活动持续时间不确定）的计算实验，证明了所提方法的有效性。对四种方法的比较分析揭示了准确性和可扩展性之间的权衡。虽然精确方法为小规模问题提供了基准，但混合和元启发式策略在几秒钟内就能接近最优性能，为大规模问题提供了实际优势。这些结果突显了本研究的主要贡献：
（i）为SRPSAP开发了一种两阶段随机模型，将Vega-Hidalgo等人（2026年）的确定性RPSAP扩展为连接第一阶段项目选择决策与第二阶段多个南极站点情景依赖调度的方法。
（ii）开发了一种适应SRPSAP结构的整数L形分解方法。
（iii）探索了一种结合模拟退火的混合分解策略，用于随机补救评估。
（iv）构建了一个可复制的测试平台，用于支持在极端和资源受限环境中分析规划权衡。

总的来说，这些贡献丰富了多站点环境中集成随机项目选择与调度的方法论工具包，并为南极研究规划提供了决策支持。除了方法论上的进步之外，所提出的框架还为负责规划南极研究项目的决策者提供了直接价值。通过明确建模项目持续时间、资源流动性和站点间转移的不确定性，该方法使规划者能够优先考虑预期科学回报最高的项目，同时遵守操作可行性。该框架还支持资源前置和应急规划，使物流管理者能够在各种情景下评估科学价值与风险暴露之间的权衡。从政策角度来看，结果为在不同项目间分配有限的预算和运输能力提供了指导，确保在极端环境条件下实现关键研究目标。更广泛地说，这些方法可以应用于其他高风险环境，如海洋能源、灾害响应或远程探索。这样，本研究不仅为优化文献做出了贡献，还为管理者在极端环境中实现 resilient 和科学高效的运营提供了可操作的见解。

本文的其余部分组织如下：第2节回顾相关工作；第3节正式定义随机优化模型；第4节介绍解决方法；第5节报告计算实验结果；第6节讨论实验结果；第7节总结了贡献、管理意义和未来研究的方向。

文献综述
本研究解决的问题与项目评估和调度领域中的三个成熟研究方向密切相关。随机项目组合选择问题（SPPSP）关注在成本、收益或成功概率等未来结果不确定的情况下选择哪些项目进行，通常旨在在控制风险的同时最大化预期价值。随机资源受限项目调度问题（SRCPSP）则关注在活动持续时间不确定的情况下，如何在多个南极研究站点之间分配稀缺的异质资源。

问题描述
SRPSAP模型捕捉了在多个南极研究站点之间分配稀缺异质资源的挑战，同时考虑了操作限制和不确定的活动持续时间，这些持续时间由多个情景表示。它结合了随机项目组合选择和资源受限调度的元素，适用于地理分布的环境，其中项目选择和调度可行性取决于特定情景的实现。

整数L形方法
首先，我们将介绍Laporte和Louveaux（1993年）提出的整数L形方法。这种方法依赖于Benders分解（Benders，1962年）和分支剪枝技术（Padberg和Rinaldi，1991年），以解决决策变量的非整数性。

计算实验和结果
本节展示了第3节中随机模型测试的结果以及第4节中算法的结果。具体来说，我们比较了四种解决SRPSAP的方法：
• CS：使用商业求解器解决随机模型。
• IL-S：使用整数L形方法解决随机模型，用LBSA-SP生成初始可行解，然后使用商业求解器处理每个情景中的CP和子问题。
• IL-S+SA：使用整数L形方法解决随机模型，然后使用模拟退火来改进随机补救评估的可扩展性。

讨论
计算结果突出显示了速度和鲁棒性之间的重要权衡，这需要仔细解释。当考虑每个实例的最佳差距重复次数时，SA-SP在大多数组中实现了最低的平均相对差距，并且这些最佳差距重复次数均在100秒内完成，最快情况下比单独使用IL-S快68倍。然而，这种总体性能掩盖了运行间的显著变异性：表6显示，单个SA-SP重复次数……

结论
本研究开发了一个全面的随机编程框架，用于在存在重大操作不确定性的情况下选择和调度南极站点上的科学研究项目。其贡献有四方面：首先，它引入了一个两阶段随机模型，将第一阶段的项目选择与第二阶段的情景依赖调度联系起来，以最大化预期科学收益；其次，它提出了一种基于整数L形分解的精确分解方法；第三，它探索了一种结合模拟退火的混合分解策略；第四，它构建了一个可复制的测试平台，用于支持在极端和资源受限环境中分析规划权衡。

CRediT作者贡献声明
Mauricio Vega-Hidalgo：撰写——原始草案、可视化、软件、方法学、资金获取、形式分析、概念化。
Lorenna Pradenas：撰写——审阅与编辑、监督、概念化。维克托·帕拉达（Victor Parada）：负责撰写、审稿与编辑工作以及数据验证；赫克托·坎塞拉（Héctor Cancela）：负责监督工作及理论框架的构建。
未引用的参考文献：Artigues, 2017; Ma et al., 2019; Ma et al., 2019; de Nascimento et al., 2025; SAT, 1959。

利益冲突声明
作者声明：他们不存在任何可能影响本文研究结果的已知财务利益或个人关系。

致谢
本研究由智利国家科学技术研究院（ANID）下属的人力资源与国家博士培养项目（Subdirección de Capital Humano/Doctorado Nacional/2021）资助，项目编号为21210451。
参与研究的团队成员包括：毛里西奥·维加-伊达尔戈（Mauricio Vega-Hidalgo）、洛雷娜·普拉德纳斯（Lorena Pradenas）、维克托·帕拉达（Víctor Parada）和赫克托·坎塞拉（Héctor Cancela），他们均来自智利康塞普西翁大学（Universidad de Concepción）的工业工程系，地址为Edmundo Larenas 219号，康塞普西翁市。