两阶段随机优化的共识固定方法——应用于随机奖励收集旅行商问题

《TRANSPORTATION RESEARCH PART E-LOGISTICS AND TRANSPORTATION REVIEW》：Consensus fixing for two-stage stochastic optimization – applied to stochastic prize collecting TSP

　　

研究人员考虑两阶段随机优化问题（two-stage stochastic optimization problems），其中第一阶段和第二阶段问题都可能包含二元变量（binary variables）。提出了一种基于共识固定（consensus fixing）的高度并行启发式方法：使用变邻域搜索启发式方法（Variable Neighborhood Search heuristic, VNS）为每个场景独立求解问题。然后，场景尝试就固定单个第一阶段变量达成共识，使用各种评分函数和选择函数。交替求解独立场景和变量固定的过程重复进行，直到所有第一阶段变量被固定。由于所有第二阶段问题独立，该框架非常适合并行实现。该通用框架在两个阶段随机奖励收集旅行商问题（two-stage stochastic prize collecting traveling salesman problem, TPTSP）上进行了测试。第一阶段客户（订阅客户）需要每天服务，而第二阶段客户（按需客户）每天波动。计算结果显示，对于包含最多500个第一阶段客户和500个第二阶段客户、最多128个场景的实例，可以在几分钟内获得高质量解，且求解时间随场景数量扩展良好。

在交通运输与物流领域，许多优化问题面临不确定性，如客户需求、行驶时间波动。经典处理方法包括随机优化（Stochastic Optimization, SOP）和鲁棒优化（Robust Optimization, ROP），常采用场景采样方法（Sample Average Approximation）。两阶段随机优化问题（Two-Stage Stochastic Optimization Problems）中，第一阶段决策先行，第二阶段参数依场景揭示，目标为最小化期望成本。现有方法（如整数L形方法、分支定价、渐进对冲等）在扩展性上存在局限，尤其当问题规模和场景数量增长时，算法复杂度高、实现困难。因此，研究人员旨在开发一种快速、可并行、易于实现的启发式框架，能随场景数量高效扩展，同时保持解质量。本文提出共识固定（Consensus Fixing, CF）元启发式，并应用于随机奖励收集旅行商问题（Two-Stage Stochastic Prize Collecting Traveling Salesman Problem, TPTSP），研究成果发表于《Transportation Research Part E: Logistics and Transportation Review》。

研究人员为开展研究所用的关键技术方法（不超过250字）：
（1）共识固定（CF）启发式框架，基于场景分解，每个场景独立求解后，通过评分函数（后悔值、多数、阈值、组合）和缩放因子（均匀、机会约束、无产者线性/二次、精英线性/二次等）达成第一阶段变量共识；（2）变邻域搜索（Variable Neighborhood Search, VNS）求解每个场景的确定性奖励收集旅行商问题，结合模拟退火接受准则，利用四个邻域（节点删除、节点插入、节点移动、交叉边）；（3）破坏性贪婪启发式初始化VNS，先构建巨环再移除节点；（4）并行实现：每个场景独立线程，使用pthread_create/pthread_join。实验实例随机生成，客户点均匀分布于1000×1000矩形区域，利润范围[0,120]，距离取欧几里得整数。

研究结果：
**5.1 示例说明（An illustrative example）**
通过6场景实例展示解路径：算法能访问高利润客户（深蓝节点），优先固定低利润节点或位于偏远区域的节点，高利润且位于中心区域的节点后固定，体现“安全”与“不确定”决策顺序。
**5.2 参数调优（Parameter tuning）**
针对模拟退火参数（初始温度T₀、冷却率α）和迭代次数I_max进行调优实验（10随机实例，n_max=128，|S|=16），确定最优组合：T₀=200、α=0.95、I_max=100k，此时解质量与计算时间平衡最佳。
**5.3 评分函数与缩放因子（Score value and scaling factor）**
比较四种评分函数和八种缩放因子（各10实例），发现优化期望值z_E时，后悔值（regret）评分函数与均匀（unif）缩放因子表现最佳；优化鲁棒值z_R时，pquad缩放因子最优。
**5.4 贪婪启发式（Greedy heuristic）**
评估破坏性贪婪启发式（用于VNS初始化），结果显示对n_max≥400的大规模实例（|S|=16），贪婪解与VNS解相对偏差约5%，表明可快速获得高质量初始解。
**5.5 共识成本（Cost of consensus）**
通过比较独立求解（上界）与固定第一阶段变量后的解，发现中等规模实例（n_max100-200）差距约10-17%，大规模实例缩小至5-6%，证实CF启发式性能良好。
**5.6 运行时间分析（Running time analysis）**
扩展场景数从1至16（n_max=128），计算时间（墙上时间）随场景数增加仅增长约50%（考虑超频后约14.6%），表明算法具有良好扩展性。在64核CPU上扩展至128场景时，时间增长更平缓。
**5.7 增加场景数时的解质量（Solution quality when increasing the number of scenarios）**
随着场景数增加，z_E从1场景下降后，在12场景后略有回升，表明更多场景可能提供更多自由度；z_R则持续缓慢下降。相对偏差分析表明3场景后z_E偏差<2%，而z_R需20场景以上才低于5%。
**5.8 解验证（Validation of solutions）**
固定第一阶段解后在全部32场景上评估，发现少于8场景时z_E被高估（偏差>20%），8场景后解质量接近；z_R需超过10场景偏差<10%，超过20场景偏差<2%。
**5.9 增加客户数（Increasing the number of customers）**
当n_max从100增至500（|S|=16），z_E快速增长，计算时间适度增加（约500秒，5次重启），CPU利用率达88.3%，证明算法适用于动态环境。
**5.10 搜索进程（Search progress）**
观察目标函数随固定变量数变化：前半段略有上升（因多数固定操作起多样化作用），后半段下降；对比1M与100k迭代，更多迭代改善有限，说明CF节省时间而不显著影响解质量。
**5.11 固定多个变量（Fixing several variables）**
每次迭代固定k个变量可缩短运行时间约k倍，但解质量轻微下降（k=10时下降约2%），与减少VNS迭代次数的效果相当。

总结讨论部分：研究人员认为，CF启发式对于两阶段随机优化问题具有巨大潜力，易于实现且扩展性好，可基于现有确定性求解器构建随机版本。对于TPTSP，后悔值评分函数与均匀缩放因子适用于期望值优化，pquad缩放因子适用于鲁棒优化。有趣发现是12-20场景时z_E被低估，但仅8场景即可获得高质量第一阶段决策；鲁棒优化需至少10场景才能使偏差小于10%。CF还提供变量固定顺序，反映决策的“确定”与“灵活”程度，支持多阶段决策。

研究结论翻译（原文Conclusion部分）：
元启发式方法对于两阶段随机优化问题具有巨大潜力，有助于解决大规模现实不确定性规划问题。所提出的CF启发式简单易实现，且随场景数量扩展良好。此外，CF使得能够利用现有确定性问题的先进求解器（启发式或精确），确保实现便捷且解质量较高。尽管本文仅展示了奖励收集旅行商问题的计算结果，但整体原则普遍适用于运输、物流与规划领域的诸多问题。对于共识固定启发式，发现后悔值评分函数在研究的奖励收集旅行商问题中表现最佳；优化期望值z_E时均匀缩放因子最优，优化鲁棒值z_R时pquad缩放因子最优。虽然本文使用VNS作为底层启发式，但任何优秀启发式均可替代。CF启发式允许对场景数进行大规模测试，有一个有趣发现：在TPTSP中，12至20场景导致期望值z_E相较于32以上场景被低估，但仅8场景即可获得高质量第一阶段决策。使用鲁棒优化z_R为目标时，至少需要10场景才能将偏差控制在10%以内，且此可能仍被低估。最后，CF不仅求解SOP，还提供第一阶段变量固定顺序：早期决策较为“确定”，晚期决策较为“灵活”，这为支持更好决策提供了有价值信息。