推文作者：
祝心怡，香港理工大学在读博士生
研究方向: 多式联运，客货共运
编者按
针对需求不确定性下的服务网络设计，本文提出了一种两阶段鲁棒优化方法。作者采用无概率不确定性集来描述潜在情景，并提出了列和约束生成法（C&CG）来精确求解鲁棒模型。数值结果表明，本文提出的算法在计算速度和求解质量方面均优于Benders分解，验证了模型的鲁棒性。
1.引言
服务网络设计（SND）解决的是战术规划问题，包括运输路线的设计和集运公司的货流分配（例如，Crainic，2000 年，2003 年）。SND 方案的主要目标是有效地利用车辆和司机等资产，以满足货物的运输需求。大多数有关 SND 的研究在战术规划阶段，并没有考虑不确定性，而是将其推迟到运营阶段。然而，货物运输服务依赖于需求、旅行时间和运输成本等不确定性因素。因此，在实践中，货代公司面临在信息有限的情况下，做出规划层和运营层的决策以满足需求不确定性的挑战。
本文在需求不确定条件下，为SND建立两阶段鲁棒优化（RO）模型。RO无需概率信息，通过不确定性集捕捉随机性，并能在不确定性集内部的任何扰动下，得出相对稳健的设计决策。具体来说，在第一阶段，模型在未知不确定参数的情况下，进行运输服务的规划决策；在第二阶段，基于已揭示的不确定性，进行货流分配和外包（outsourcing）决策。本文采用了C&CG作为求解方法，并对算法性能进行了详细分析。结果表明，C&CG比Benders分解法更有效。此外，本文还分析了鲁棒解的结构特性，并通过模型对比，证明了所提出的鲁棒优化模型的稳健性和灵活性。
2.问题描述和模型构建
2.1 问题描述
本文的研究基于 Lium 等人（2009 年）和 Bai 等人（2014 年）对 SND 问题的研究。网络被建模为时空网络，其中时间被离散为相同长度的时段，每个节点在每个时段都有一个副本。模型的目标是最小化总体固定成本和外包成本。由于与网络固定费用相比，流量成本被认为是最小的，因此被忽略。考虑一个有向图，每个货物有名义需求，需要从起点运输到终点。每个货物在到达起点，必须在前到达终点。固定成本与弧相关，用于提供货运服务。定义为在时间段到达车辆的出发时间段。决策变量定义如下：
:在时间段节点到节点的服务频率，且.
:在时间段节点到节点的货物流量，且.
:最佳货流中通过外包满足的货物的数量，且.
2.2 基本两阶段RO模型
本文引入多面体不确定性集（Polyhedral Uncertainty Set）。对于每个货物，区间表示不确定需求的范围。只有当实际需求量大于名义需求量时，解才会变得更差。由于本文的目标是为最差情况构建一个稳健的服务网络，因此在这些情况下可能不会出现负的需求偏差；本文处理的需求量只在和之间。文中使用来表示多面体不确定集，即，其中，是不确定性预算，取值范围在连续区间 。多面体不确定性集通过参数来调整方法的鲁棒性，以适应解的保守程度。如果同时，则的值代表同时偏离名义需求的最大不确定需求量。基本的两阶段鲁棒SND 问题表述为：
其中，optimal[RP] 表示第二阶段问题的最优目标值，记为 RP：
目标函数（1）旨在最大限度地降低不确定性集中最坏情况的总成本，包括第一阶段的网络设计成本和第二阶段的外包成本。约束（2）确保每个时期进入和离开每个节点的车辆数量相同，以满足流量平衡的要求。在第二阶段的目标函数（4）中，外包货量定义在集合中，其中通过 min 运算符确定成本最低的解。此外，在给定第一阶段决策的情况下，通过 max 运算符，确定产生最高追索成本的不确定方案。约束（5）限制总货流不超过网络容量。约束（6）是每件货物和每个节点，在每个时间段的流量平衡。约束（7）确保每件货物都能在交货截止日期前到达目的地。约束（3）、（8）和（9）定义了决策变量的范围。
2.3 拓展两阶段RO模型
单一的不确定性集可能过于粗糙，无法准确描述不确定性。针对这一问题，An 和 Zeng（2015 年）指出，基本 RO 模型可以通过利用多个不确定性集，以及分配给它们的不同权重来进行扩展，以捕捉各种随机情景。扩展后的 RO 模型可用于满足各种要求，具体如下：
其中表示第个不确定集以及相应的权重。扩展 RO 模型中使用的不确定性集总数为。
为了总结不同模型之间的区别和联系，文中的附录 A 提供了忽略需求不确定性的确定性模型；附录 B 提供了基于情景的 SP 模型，具体可参阅原文。
3.算法设计
由于 Zeng 和 Zhao（2013 年）开发的列和约束生成方法（C&CG）在处理两阶段鲁棒优化问题时表现良好，因此本文使用 C&CG 来求解模型。在求解主问题 (MP) 得到设计决策后，剩下的max-min子问题被求解，以确定最坏情况下的解。第二阶段子问题总是可行的，因为在不确定的情况下，可以通过外包满足未满足的需求。因此，本文通过子问题的对偶形式来求解第二阶段的 max-min 问题。本文选择基本两阶段 RO 模型来详细说明 C&CG 方法，扩展的 RO 模型只需稍加修改即可求解。本文还使用 Bender分解法作为算法对比。
3.1 第二阶段问题的对偶
为了将第二阶段模型重新表述为一个max-max问题，取内部最小化问题的对偶值，通过固定和即可得到：
文中分别为约束条件 (12)、(13) 和 (14) 设置了对偶变量。根据对偶理论，对偶问题被表述为：
让表示的可行域，为一个有界多面体。由于最优解是的一个极值点，可以等价地将该子问题转化为一个最大化问题，即，其形式为
是一个双线性项（bilinear）优化问题，是一个NP难问题。因此，本文通过分段线性函数和解的存在性的性质，将重新表述为混合整数规划问题（MIP），具体转换可参阅原文。原文证明了是一个0-1变量，因此双线性项可替换为，其中当时，，否则。转换后的MIP形式如下：
2.3 拓展两阶段RO模型
在每次迭代时，给定规划决策，通过求解得到最坏情况下的，然后得到追索变量和与此特定情况相关的相应约束，并将其添加到MP中。原始问题的上限和下限分别定义为 UB 和 LB。GAP 是 UB 和 LB 之间的相对差距。在 C&CG 算法过程中，首先提出需要迭代求解的MP：
C&CG 方法的框架如下：
（1）设定且。
（2）将的初始解设为任意值。
（3）求解得到最坏情况下的。得到追索变量和相应的(31)-(34)约束，并将这些约束加到MP中。
（4）迭代，直到满足终止条件：
(i)得到 MP 的最优解；将LB 设为 MP 的最优值;
(ii)求解得到最坏情况下的。更新上界：
(iii)如果 GAP 在的范围内，则算法终止；否则，更新并创建追索变量以及 (31)-(34) 中相应的约束条件。将它们添加到 MP 中，然后进入步骤 (i)。
对于扩展的 RO 模型，通过求解一个子问题来确定每个不确定性集合的最坏情况，其追索变量和相应的约束条件也被添加到 MP 中。在求解扩展 RO 模型时，MP 的目标函数如下：
其中是第个不确定集。C&CG 方法可以在有限的迭代次数内收敛到最优解，并高效地求解两阶段 RO 模型。相比之下，在Benders分解中，每次迭代时，只有一个携带第一阶段决策变量的切平面会被添加到 MP 中。相应的Benders cut为
4.数值实验
数值实验的目的有三个：（1）确定所提出的 C&CG 算法在考虑不确定需求的鲁棒性服务网络设计中的有效性和效率；（2）评估所提出的 RO 模型所获得的最优决策的鲁棒性和灵活性；（3）比较不同模型的结果并分析其特性。文章通过 Gurobi求解线性和混合整数模型，并且将 C&CG 方法和 Bender分解方法的时间限制都设定为7200s。具体参数可参见原文，结果如下：
表 2 显示，Benders分解法无法在规定时间内优化解决所有实例，并且Benders分解在规定时间内的平均Gap为 87.29%。相比之下，C&CG 方法可以高效地求解所有实例。此外，C&CG 方法所需的迭代次数要少得多。因此，C&CG 方法在计算时间和求解质量上都优于Bender分解法。
为了进一步展示 C&CG 方法的有效性和效率，作者使用了一个稍小的实例：该实例可以用Bender分解在有限时间内求解到最优，并绘制了 C&CG 和 BD 方法在迭代和时间上的收敛曲线。该实例包括六个货物和五个节点，重复了五个周期。在图 1 中，即使经过 400 次迭代，Bender分解方法的差距也在缓慢减小，甚至不为零；而 C&CG 方法仅经过两次迭代就以最优方式解决了该实例。在图 2 中，可以发现Benders分解需要 60,000 多秒才能最优解；而 C&CG 方法只需要 0.8 秒就能最优解 。
文章还对不确定性需求、不确定性预算水平等参数进行了灵敏度分析，并分析了确定性模型、随机性模型和鲁棒优化模型之间的解的结构差异，在此不做赘述。感兴趣的可参考原文。
5.结论
本文针对 SND 问题提出了一个两阶段鲁棒优化方案，以解决需求不确定性问题。文章使用不确定性集，来描述引入的鲁棒优化模型中可能出现的不确定情况，采用C&CG方法来高效求解鲁棒优化模型，使其达到最优。数值实验表明，该方法比Benders分解法更有效、更高效。文章还分析了鲁棒解的结构，该方案采用集运和路径共享，作为提供运营灵活性和对冲不确定性的手段。
参考文献
Zujian Wang, Mingyao Qi (2020) Robust Service Network Design Under Demand Uncertainty. Transportation Science 54(3):676-689.
Lium AG, Crainic TG, Wallace SW (2009) A study of demand stochasticity in service network design. Transportation Sci. 43(2): 144–157.
Bai R, Wallace SW, Li J, Chong YL (2014) Stochastic service network design with rerouting. Transportation Res. Part B: Methodological 60(1):50–65.
An Yu, Zeng B (2015) Exploring the modeling capacity of two-stage robust optimization: variants of robust unit commitment model. IEEE Trans. Power Systems 30(1):109–122.
Zeng B, Zhao L (2013) Solving two-stage robust optimization problems using a column-and-constraint generation method. Oper. Res. Lett. 41(5):457–461.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：祝心怡，香港理工大学在读博士生
责任编辑：江镕行
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
