《Operations Research Perspectives》：A heuristic for Capacitated Facility Location Problems under multi-uncertainty
编辑推荐：
容量受限设施选址问题（Capacitated Facility Location Problem，CFLP）在多重不确定性下面临严峻挑战。本文提出了一种多目标随机优化模型（CFLP-MU），用于协调总期望成本与服务满意度之间的权衡，从而增强供应链韧性。鉴于该问
容量受限设施选址问题（Capacitated Facility Location Problem，CFLP）在多重不确定性下面临严峻挑战。本文提出了一种多目标随机优化模型（CFLP-MU），用于协调总期望成本与服务满意度之间的权衡，从而增强供应链韧性。鉴于该问题的计算复杂性，研究人员开发了一种融合遗传算法（Genetic Algorithm，GA）与模拟退火（Simulated Annealing，SA）的新型启发式方法，即DSAA-Hybrid NSGA-II。该算法集成了确定性热启动（Deterministic Warm Start，DWS）、动态样本平均近似（Dynamic Sample Average Approximation，DSAA）、重点客户容量预留（VIP）及反馈驱动智能修复（Feedback-driven Smart Repair，FSR）四种核心机制。研究结果表明：相比基准多目标进化算法（Multi-Objective Evolutionary Algorithms，MOEAs），DSAA-Hybrid NSGA-II在收敛效率与Pareto前沿质量方面均表现更优；弹性容量选项能够有效替代静态物理冗余；灾后恢复投入相比单纯增加设施密度可带来更高的边际收益。数值实验证实随机优化在高惩罚不确定性条件下具有显著的经济价值，模型消融研究验证了各机制的结构必要性，跨尺度测试则证明该算法具有良好的可扩展性。该模型为供应链风险管理中的设施选址决策提供了稳健的决策支持工具。
多不确定性下的容量受限设施选址问题研究：模型构建与算法设计
**1. 研究背景与问题提出**
设施选址问题（Facility Location Problem，FLP）作为运筹学（Operations Research）的基础研究领域，为供应链管理中的战略性长期决策提供了理论 foundation 与方法论支撑。在实际生产场景中，设施通常具有较长的生命周期，且各参数在此期间会发生变化，这使得设施选址决策必须兼顾效率与可靠性。当考虑容量限制时，容量受限设施选址问题（Capacitated Facility Location Problem，CFLP）应运而生，其核心在于为有限容量的多个设施分配客户需求，以最小化总成本。既有CFLP研究主要集中于单目标优化，通常仅以总成本作为唯一优化准则，少有研究同时优化成本与服务两个维度，而多目标方法能够更准确地反映实际生产过程的复杂性。
在供应链管理中，参数的可变性引入了诸多不确定性，亟需在选址决策中予以系统考虑。现有文献对不确定性下的设施选址问题已有一定探索，涵盖需求不确定性、设施中断风险及容量可用性等维度。然而，尽管近期模型已整合双重不确定源，但在多目标框架下同时考虑需求波动、设施中断风险与容量可用性不确定性的研究仍较为匮乏。这一研究缺口为提出更综合的CFLP多不确定性建模方法提供了契机。为弥合上述缺口，本研究的主要目标是构建并求解多不确定性下的容量受限设施选址问题（CFLP-MU），提出一种多目标随机模型，以平衡总期望成本与服务满意度，从而增强供应链韧性，并开发高效的求解算法以应对该问题的计算复杂性。
**2. 研究方法与技术路径**
研究人员首先建立了一个两阶段多目标随机规划模型，第一阶段在不确定性显现前做出设施开设与主动强化等战略决策，第二阶段则根据不确定性参数的实现进行容量扩展水平选择、正常运输与应急调配等运营决策。模型以最小化总期望成本与最大化服务满意度（Service Satisfaction Ratio，SSR）为双目标。在求解算法设计上，由于CFLP及其扩展问题属于NP-hard，且模型为混合整数线性规划（Mixed-Integer Linear Programming，MILP），随着设施数、客户数与中断场景数的增加，搜索空间呈指数级增长。为此，研究人员提出了DSAA-Hybrid NSGA-II算法，该算法以非支配排序遗传算法II（Non-dominated Sorting Genetic Algorithm II，NSGA-II）为基本框架，融合了四种核心机制：确定性热启动、动态样本平均近似、重点客户容量预留、反馈驱动智能修复。实验采用随机生成的小型、中型和大型三种规模实例，以精确求解器（ε-约束方法）生成参考Pareto前沿作为基准，并使用超体积（Hypervolume，HV）与反世代距离（Inverted Generational Distance，IGD）两项标准指标评估算法性能。此外，构造了需求分布与中断相关性各异的替代不确定环境以检验模型的鲁棒性。
**3. 研究结果与分析**
**3.1 算法性能评估与消融实验。**在小型实例上，与精确MIP求解器相比，DSAA-Hybrid NSGA-II在5.7秒内获得了精确算法85%的超体积（0.7270对0.8555），IGD仅为0.1028，表明其能够以极低计算开销生成近似最优解。与基准NSGA-II相比，所提算法HV提升17.9%，IGD从0.1608降至0.1028，且计算时间更短。MOEA/D与SPEA2则表现出严重的早熟收敛现象。消融实验结果表明，重点客户逻辑对于保证100%的VIP服务满意度不可或缺；动态样本平均近似机制在保证解质量的同时将运行时间从224.3秒降至110.0秒；确定性热启动与反馈驱动智能修复分别在初始收敛与搜索空间缩减方面发挥作用。
**3.2 参数敏感性分析。**重点客户参数敏感性分析显示，惩罚乘数达到10.0倍基线水平时方能强制执行绝对优先级服务，实现100%的VIP满意度，同时总成本上升18.47%，这代表了韧性的现实代价。服务衰减函数敏感性分析表明，线性衰减模型与阶跃衰减模型之间的Jaccard相似度高达90.18%，核心战略选址拓扑对函数形式具有高度鲁棒性，但线性模型更能反映实际物流并防止低估真实韧性成本。全局参考服务半径的敏感性分析证实基线设定实现了全局连通性与惩罚梯度严格性之间的最优平衡。在替代随机环境（正态需求分布与空间相关中断）下，模型展现出稳定的性能，负的随机解价值（Value of the Stochastic Solution，VSS）与低完美信息期望价值（Expected Value of Perfect Information，EVPI）验证了随机规划策略的有效性。
**3.3 中型基准实例的Pareto优化与敏感性分析。**Pareto前沿分析表明，提高恢复能力系数（α）可产生更具成本效益的权衡；随着服务满意度接近90%，边际成本急剧上升，说明追求近乎完美的可靠性需要不成比例的高额投资。九组敏感性分析结果显示，需求短缺惩罚系数（uj）是基础设施策略的主导驱动因素：高惩罚条件下系统采取极端稳健姿态，设施开设率达100%，SSR约94%；低惩罚条件下系统维持稀疏网络，设施开设率约65.5%至72.5%，SSR降至53.8%至56.6%。较高的恢复能力允许系统以更低的单位成本实现更高的服务满意度，证实弹性运营能力可以替代部分结构性冗余。
**3.4 战略拓扑与成本构成分析。**网络拓扑揭示了系统明显偏好利用扩展设施提供弹性容量而非单纯增加设施数量，分配链接按邻近性组织为局部集群。成本结构分解显示，随着惩罚系数上升，支出从惩罚项转向基础设施投资，扩展成本的急剧增加表明系统高度依赖弹性容量应对需求激增与中断事件。较高的恢复能力可有效抵消维持过量基线的数学必要性。
**3.5 运营弹性与扩展动态分析。**场景稳健性分析表明，中断事件下最低服务满意度仍保持在80%目标阈值以上，而扩展场景作为稳定性基线，服务满意度保持在约90%水平。扩展层级热图揭示了系统对高层级容量（第三层级）的显著依赖，该现象由高惩罚参数与重点客户严格服务保证共同驱动，同时也证实模型能正确识别并放弃结构性不具竞争力的设施节点。
**3.6 反事实分析与网络韧性评估。**对五个活跃设施进行定向中断模拟的结果显示，网络平均成本增加0.15%，SSR下降5.01%。关键骨干节点的失效导致严重成本上升，而关闭部分边缘节点虽能带来轻微成本降低，却引发不成比例的SSR下降，证实基线方案已处于Pareto最优边界。
**3.7 模型消融实验。**禁用容量扩展机制导致成本灾难性上升至1.5×1011量级，证实弹性扩展缓冲不可或缺；禁用灾后应急恢复能力使Pareto前沿显著下移至劣势区域；禁用未满足需求惩罚则导致无法生成高服务水平（>70%）的可行解。实验结果证明了各机制在CFLP-MU模型中的结构必要性。
**3.8 跨尺度可扩展性分析。**平均VSS从小型实例的?10.45%上升至大型实例的?2.66%，表明随着网络规模增大，忽略不确定性将导致更严重的损失。EVPI在中等规模达到峰值16.82%，随后在大型规模骤降至2.52%，反映出鲁棒性饱和效应：当系统建立足够的后备容量应对严重惩罚时，完美信息的经济价值趋近于零。
**4. 讨论与结论**
讨论部分指出，运营韧性与弹性容量选项可有效替代静态物理冗余，分层扩展选项的引入使系统能够在不承担高额固定成本的情况下建立应对需求激增的缓冲机制。在实践中，当短缺惩罚较高时随机规划尤为重要，而对灾后恢复能力的投资相比单纯增加设施密度可带来更高的边际收益。研究结论部分翻译如下：本研究提出了CFLP-MU模型以支持供应链风险管理决策，同时应对客户需求、容量可用性与设施中断方面的不确定性，并利用战略性容量扩展选项来缓解这些风险。通过整合这些关键因素，该模型为在复杂不确定性下最小化设施成本与最大化服务覆盖质量提供了稳健的战略决策方案。研究人员开发的DSAA-Hybrid NSGA-II框架在收敛效率与Pareto解质量方面均优于基准MOEAs，成功在计算效率与解结构质量之间取得平衡，生成了成本与服务可靠性之间多样化的权衡方案。跨尺度测试证实该方法具有良好的可扩展性，且随着网络复杂性的增长，随机规划的必要性愈发凸显。未来研究将聚焦于两个扩展方向：将容量扩展选项建模为实物期权以更精确地捕捉其不确定性下的财务价值，以及以部分退化状态替代二元中断假设以实现更精细的韧性评估。
