《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：A consensus fixing based heuristic for liner shipping network design with stochastic demands
编辑推荐：
为了满足海运业的可持续发展目标，需要设计能够有效利用船舶运力并适应集装箱需求波动的航线网络。针对季节性需求变化带来的不确定性，研究人员研究了两阶段随机班轮航运网络设计问题（Liner Shipping Network Design Problem, LSNDP
为了满足海运业的可持续发展目标，需要设计能够有效利用船舶运力并适应集装箱需求波动的航线网络。针对季节性需求变化带来的不确定性，研究人员研究了两阶段随机班轮航运网络设计问题（Liner Shipping Network Design Problem, LSNDP）。在该问题中，第一阶段决策定义网络结构，第二阶段决策在不同需求场景下对集装箱进行路径规划。研究人员提出了首个能够处理真实规模LINER-LIB实例的通用求解方法，该方法能够解决包含多达202个港口和9615个需求商品的随机LSNDP实例。所提出的方法引入了一种新颖的基于种群的元启发式算法，该算法采用了共识固定（Consensus Fixing）策略。具体而言，对于每个场景并行地在第一阶段决策上使用自适应大邻域搜索（Adaptive Large Neighbourhood Search, ALNS）框架进行求解，而第二阶段流决策则使用快速列生成（Column Generation, CG）进行评估。各个场景在迭代过程中尝试就固定某个第一阶段决策达成共识，这一过程基于各种评分和缩放函数。为了处理第一阶段决策空间的复杂性，研究人员在应用共识固定时引入了一种松弛的决策表示。这使得该框架能够方便地扩展到非二元问题，并生成一个具有优选共同特征的结构化解决方案种群，该种群由专门的种群管理机制提供支持。计算实验表明，该方法能够在合理的时间内找到高质量的解决方案，与确定性基线相比，实现了高达20%至30%的改进。研究结果还揭示了随机规划的价值是依赖于具体实例的：灵活的网络结构能从中获得显著收益，而单枢纽实例由于其有限的路由适应性，从随机优化中获得的优势微乎其微。
论文解读
研究背景与意义
随着全球贸易的不断深化，班轮航运作为供应链的重要支柱，面临着日益严峻的可持续发展挑战。在实际运营中，集装箱需求的季节性波动给航线网络的规划带来了极大的不确定性。传统的确定性班轮航运网络设计问题（LSNDP）往往假设需求是固定的，这导致在面对实际波动时，设计出的网络可能因缺乏韧性而导致运营成本激增或交付率下降。因此，如何在战略层面设计出既能高效利用船舶资源，又能适应需求不确定性的航线网络，成为了学术界和产业界亟待解决的问题。本研究针对这一痛点，探索了在两阶段随机优化框架下求解LSNDP的方法，旨在通过更科学的数学建模与算法设计，提升海运物流系统的抗风险能力与经济效益。
关键技术方法
为实现上述目标，研究人员开发了一套融合多种先进优化技术的混合求解框架。首先，针对需求的不确定性，研究构建了基于离散场景的两阶段随机规划模型，将决策分为不可调整的第一阶段网络设计和可随场景变化的第二阶段集装箱流规划。其次，在算法层面，核心创新在于引入了共识固定（Consensus Fixing）机制。该方法采用基于种群的元启发式策略，为每个需求场景并行维护一个解。各场景独立利用自适应大邻域搜索（ALNS）优化网络结构，并利用快速列生成（CG）精确评估集装箱流成本。在迭代间隙，通过跨场景的评分与缩放机制，识别并固定那些对多个场景均至关重要的网络决策变量，从而引导所有场景的解向一个共同的、具备全局鲁棒性的网络结构收敛。此外，研究还对ALNS进行了定制化扩展，增加了专门的破坏与修复算子以及动态种群管理策略，以应对共识固定带来的复杂约束。在数据方面，研究基于标准的LINER-LIB基准测试集，并通过截断正态分布生成了多组随机需求场景以模拟现实波动。
研究结果
引言与文献综述
研究开篇阐述了LSNDP在现实运营中的复杂性，指出其兼具网络设计（NP-hard）和多商品流（MCFP）的双重属性。通过详尽的文献回顾，研究人员梳理了LSNDP模型的发展历程，从基础的循环航线到包含转运、运输时间限制和航速优化的综合模型。在求解方法方面，研究指出了现有算法的四大流派：统一模型法、两阶段法、候选路径子集法和骨干流法。针对不确定性，文献回顾强调了现有研究多集中于运营层面的调度调整，而在战略层面的网络设计随机优化（SOP）研究相对匮乏，且现有方法在处理大规模整数决策时面临可扩展性瓶颈。这为本文提出的共识固定启发式算法奠定了理论基础。
问题描述与模型构建
研究人员将带不确定需求的LSNDP（LSNDP-UD）严格定义为一个两阶段随机优化问题。第一阶段为网络设计，决定哪些航线被纳入网络，目标是最小化运营成本；第二阶段为流量分配，决定集装箱如何在不同场景中通过网络从起点运往终点，目标是最大化收入。研究给出了详细的数学模型，包含了港口节点集、弧集、商品集、场景集等关键要素，并定义了相应的决策变量，如二进制变量yr表示航线r是否被选中，连续变量m_{ij}^{sk}和z_s^k分别表示场景s下商品k在弧(i,j)上的流量和实际交付量。模型的目标函数是最大化所有场景下期望利润或最差场景利润的加权和，并受到船舶容量、船队可用性、流量守恒等约束。
求解方法
求解方法是本研究的重点。共识固定启发式算法的流程如下：首先，为每个场景并行初始化一个网络解。随后，进入主循环，每个场景独立运行ALNS改进其网络解，并通过列生成精确计算该网络下的集装箱流成本。接着，进入共识步骤，计算每个网络决策变量（如两港口间是否存在航段）的极性（Polarity），即各场景对该变量取0或1的评分差异。评分机制包括多数投票、利用率和后悔值（Regret）三种。缩放因子则根据场景的目标函数值进行排序加权，如精英制、平民制或线性缩放。具有最大极性的变量被固定，并传递给所有场景。此过程重复直至达到时间限制或固定变量比例阈值。最后，从所有场景的解中评选出在测试集上表现最优的一个作为最终方案。
计算实验
研究通过大量的计算实验验证了所提方法的有效性。实验在包含7个不同规模和拓扑结构的LINER-LIB实例上进行。结果表明，共识固定启发式算法在所有实例上均能稳定运行。与基于期望需求值（EEV）的确定性基线相比，该方法在期望案例和worst-case案例中均取得了显著提升，平均改进幅度可达20%至30%。特别是在Mediterranean和AsiaEurope等多枢纽复杂网络中，性能提升尤为明显。然而，对于WAF这类单枢纽网络，由于结构过于刚性，缺乏替代路径，随机优化的收益非常有限甚至为负。此外，研究还探讨了允许0-fix决策的影响，发现其不仅未带来额外收益，反而因浪费计算资源排除冗余变量而降低了求解效率。在敏感性分析中，无论需求变异系数如何变化，共识固定方法均表现出较强的鲁棒性。在与另一种随机流方法（SCFM）的对比中，共识固定不仅在区域依赖的需求分布上表现更优，即便在未针对该分布训练的“未知”场景下，依然展现出卓越的泛化能力。
讨论与结论
研究人员在讨论中指出，共识固定启发式算法成功地将两阶段随机优化应用于大规模的LSNDP，证明了其在处理复杂整数决策时的巨大潜力。研究结论明确了随机规划的价值高度依赖于网络拓扑结构：灵活的、多枢纽的网络能够从随机优化中获得巨大的风险抵御收益，而结构僵化的单枢纽网络则难以受益。该研究不仅为海运物流提供了一套高效的决策支持工具，更重要的是，它拓展了共识固定框架的应用边界，证明了其作为一种通用随机优化求解范式的可行性与优越性。未来，该方法有望被推广至其他面临不确定性的组合优化问题中，为学术界提供更多验证与比较的基准。
