推文作者：祝心怡，香港理工大学在读博士生，研究方向: 多式联运，客货共运
编者按
本文介绍了具有随机客户和需求的一致性车辆路径问题（ConVRP）。为描述问题的随机性特征，本文建立了基于场景的两阶段随机规划数学模型，并引入了branch-and-cut和Benders分解算法来解决SAA方法中的样本问题。
1.引言
本文的问题设置包括车辆路径问题（VRP）的两个重要特征：一致性（Groër 等人，2009 年）和不确定性（Gendreau 等人，2016 年）。首先，一致性被定义为某些解随时间推移保持相对稳定的程度。在当今竞争激烈的商业环境中，随着企业寻求提供个性化服务，这一特点显得尤为重要。从承运商的角度看，可以尝试通过有限数量的司机访问每位客户来促进一致性。这有助于定制服务，可能提高客户满意度和公司收入。从司机的角度来看，定期访问相对稳定的一组客户有可能提高配送操作的效率，因为司机会熟悉某个区域、小型道路网络的状况和有限的客户群体。因此，一致性对于建立信任以及提升客户服务非常重要。其次，关键数据在方案规划阶段存在不确定性，这给决策过程带来了挑战。在计划阶段，使用点预测往往会导致执行阶段表现不佳，这进一步凸显了将不确定性纳入运营计划的重要性。
2.模型构建
本文在两阶段随机规划的背景下，研究具有随机客户和需求的一致车辆路由问题（ConVRP)。考虑一组潜在客户，一组容量为的同质车辆，用集合表示。车辆停靠在节点 0 表示的仓库，所有路线都从该仓库出发并返回。本文假设每辆车都与一名司机相关联。节点集代表所有可能的位置。代表所有场景的有限集合，场景中嵌入了两个不确定变量的联合实现：客户存在随机变量定义了场景中是否存在顾客；随机变量代表现有客户的需求。每个场景发生的概率由给定。问题定义在完全无向图上，其中是边集。考虑到一致性，让 𝐷 > 0 作为参数，表示在第一阶段分配给每个客户的不同司机的最大数量。
在问题的第一阶段，必须确定司机对客户的分配。在第二阶段选择客户，并根据随机变量的实现情况设计路线。在这一阶段，除了路线成本外，还会因未服务的客户而产生惩罚项。为了确保计划访问的司机一致性，第一阶段的分配在第二阶段的所有场景中保持不变。其中，给每个客户的不同司机的目标最大数量提前指定。然而，允许违反这一目标，并在目标函数中进行处罚，使得模型的灵活性较高。该问题的模型如下所示：
模型的目标是最大限度减少第一阶段违反一致性惩罚的总和，加上预期的第二阶段成本，即所有情况下的路线成本和不为潜在客户服务的惩罚总和。其中，
为0-1变量，当且仅当客户𝑖被分配到车辆𝑘时值为1；
为0-1变量，当且仅当至少有一名客户被分配到车辆𝑘时值为1；
为连续变量，衡量客户 𝑖 违反驾驶员一致性目标的程度；
为0-1变量，当且仅当客户𝑖在场景中被车辆𝑘访问时值为1；
为整数变量，表示车辆𝑘在场景中访问边的次数。
约束(2)反映了在第一阶段将客户分配给超过 𝐷 名司机时违反一致性目标的情况。约束(3)确保客户在每个情景中最多被一辆车访问一次。约束(4)保证分配给客户的车辆的流量守恒。约束(5)确保在每个情景中，每辆车在与仓库相邻的客户节点最多有两个。这些约束确保每辆车在每个情景中最多只使用一条路线。约束(6)将第一阶段的分配与第二阶段的路径变量联系起来，确保客户的访问只能由预先分配的司机进行。约束(7)保证车辆容量的满足，而约束(8)是子回路消除约束。约束(9)在至少有一个客户分配给车辆时激活变量。最后，决策变量的定义域由约束(10)–(15)确定。
3.算法设计
3.1 SAA
两阶段随机规划，尤其是两个阶段都包含整数变量的规划，求解起来非常困难。随着情景集 𝛺 的增大，这种难度也会显著增加。因此，本文采用SAA对问题进行求解，在此不做赘述。一般来说，SAA 的性能取决于参数选择（样本问题大小|𝑁|和重复次数 𝑀）以及解决样本问题的方法。一方面，较小的|𝑁|值会导致问题更易解决，而较大的样本可能会在评估大量情景集 𝛺 时使得第一阶段决策，产生潜在更好的解决方案。另一方面，在理想情况下，可以每次复制中使用有效的精确方法来优化解决样本问题。然而，即使是场景集较小的样本问题也可能很难求解，因此可以采用精确方算法的早期停止标准或使用启发式算法。
3.2 Branch-and-cut (BC)
本文的Branch-and-cut（BC）算法指的是在模型中，动态添加子回路消除约束(8)。具体来说，在BC中本文使用精确分离算法，该算法基于分支定界解的支持图上最小 𝑠 − 𝑡 割问题的解。在树的任何节点上，令和分别表示车辆流量和访问变量的解。本文为为每个情景和车辆构建一个无向支持图，为图中每个且的节点创建一个节点。每条边的权重（其中）设置为。
本文为构建图中的每个客户节点解决最小𝑠 − 𝑡 割问题，将节点设为源节点𝑠，设为汇节点𝑡。如果最小割的容量小于2，则会识别出违反子回路消除约束的情况。求解时，通过使用包含源节点𝑠的分区，检查每个场景和相对应车辆的子回路消除约束，如果发现违反了约束，则将其添加到模型中。为了对子回路消除约束进行定义，选择。本文使用Concorde求解器中的算法解决最小割问题，在树的根节点处分离子回路消除约束，以改进模型的线性松弛，并在每次找到整数解时进行分离。
为了进一步提高BC算法的性能，作者添加了两组对称性约束（SBC）：
约束（16）规定，只有当车辆被使用时，车辆才能被使用。约束条件只针对单一场景，因为如果对多个场景添加这些约束条件，可能会去除最优解。约束 (17) 根据车辆的综合分配情况，对车辆进行排序，只有当一辆index较小的车辆也被分配给客户时，车辆𝑘才能被分配给客户。作者还添加了约束 (18)，即optimality cuts（OCs），使得每个客户至少分配给一名司机：
3.3 Benders分解 (BD)
在BD算法中，利用原问题的结构将其划分为主问题和一系列子问题，子问题通常比原问题更易解决。当应用于随机规划问题时，该方法通常被称为 L 型方法：当固定了第一阶段的解时，可以将|𝛺|个子问题分开并独立求解。本文的主问题，放松了VRP部分的复杂约束（3）-（8），转化成了分配问题，如下所示：
其中是一个辅助变量，用于刻画场景下第二阶段的最优值。Optimality cuts 为子问题增加了界，确保不会低估第二阶段的成本。对于主问题来说，我们在每个场景下有相对应的子问题：
BD算法是以branch-and-check方式执行的，主问题只需要求解一次，Benders cuts即时生成。使用BC算法求解主问题时，每当找到一个整数可行解时，求解子问题验证解的可行性。当给定当前的主问题的候选解时和子问题的最优解时，如果有，那么低估了场景下第二阶段的最优解。在这种情况下会加入下方的optimality cut，确保当主问题的解是时，变量将取值为
这些cut可能很弱，不利于BD方法的性能。因此，作者尝试利用初始cuts来加强初始主问题，提高BD算法的效率。约束（32）为每个子问题的成本设定了一个下界：
该下界相当于对到达客户的最小旅行成本与未服务成本取小。求解过程中，会对所有子问题评估，即使早期会违反约束(31)。通过将子问题解与第一阶段解相结合，能找到原问题的可行解。
4.数值实验
4.1 解法对比
在本节中，作者比较了BC算法和BD算法作为独立方法的性能，以及使用 BC 和 BD 解决样本问题的 SAA 算法（分别为 SAA-BC 和 SAA-BD）的性能，如表1所示。
在表 1 中，作者按出现概率列出了不同方法的以下统计数据：(i) 找到最优解的数量；(ii) 找到最优解的平均总成本；(iii) 每种方法找到的最优解与所有方法同时找到的最优解的平均Gap；(iv) 平均总时间（秒）；(v) 找到最优解的平均时间（秒）。当客户出现的概率增加时，很难证明解的最优性。不过，在BC算法证明最优解的大多数情况下，两种 SAA 方法都能找到最优解，同时所有方法都能在所有情况下找到可行解。从总成本和平均Gap值中可以看出，平均而言，SAA-BC 找到了质量最好的解决方案，在所有客户出现概率上都明显优于其他方法。
4.2 保持一致性的成本
本节旨在评估在一致性的成本。在确定性 ConVRP 文献中，一致性可以在不牺牲标准运营指标（如总旅行成本）的情况下得到改善，本文旨在验证这一观点在随机情况下是否有效。为此，我们将随机规划的解（通过 SAA-BC 生成）与两种不同方法生成的解进行了比较。
4.2.1 忽略一致性要求
第一种方法是完全忽略一致性要求，即在原模型中忽略约束（2）。作者将这种情况称为 “解耦方法”，即将原模型转化成可按场景分离的随机规划。应用该方法，可以评估所得到的解的一致性，并将其与原始随机规划的一致性进行比较。表 4 按客户出现概率，列出了原随机规划和解耦方法的数据。从表中可以看出，解耦方法的总成本较高，而成本差异主要来自一致性惩罚，特别是在客户出现概率为 80% 的情况下，违规水平比原随机规划高出四倍多。同时，在使用解耦方法时，由于目标函数仅考虑路线成本和未服务客户成本之间的权衡，因此路径成本略有下降。因此，在解耦方法中，不服务客户并不是一个有利可图的选择，所有客户都会被访问，因此会使用更多的车辆。该结果凸显了在随机ConVRP中，将不服务客户作为备用选项的灵活性。
4.2.2 设置较高的一致性目标
在第二种情况下，本文研究了考虑更高一致性目标值的效果。为此，我们使用 SAA-BC 方法求解了实例，考虑了 𝐷 = 2 和 𝐷 = 3的情况，并与𝐷 = 1 时得到的结果进行了比较，如表5所示。结果表明，考虑更宽松的一致性目标所增加的灵活性，可使解的成本更低。成本的降低是通过减少未服务的客户数量和偏离一致性目标的程度来实现的。平均来看，这些解会使用更多的车辆。当设置 𝐷 > 1 时，路径成本几乎等于总成本，这可能是由于目标宽松时，一致性成本和运营成本之间的权衡降低了。在这种情况下，可以简化为场景问题的单独优化，目标是降低路径成本和未服务客户的成本。
4.3 模型选择的观点
通过比较随机规划的解与两种期望值（EV）方法，可以对随机解的价值（VSS）进行评估。在第一个EV问题中，没有采用基于场景的随机规划，而是使用了单一场景，即随机变量取其相应的期望值，同时考虑需求和客户出现的不确定性。第二个EV问题只考虑需求的不确定性。然后，通过求解原问题，将其第一阶段的决策固定为相应 EV 问题解的值，来评估使用EV和EV2问题解的期望成本（分别为 EEV 和 EEV2），结果如表6所示。结果表明，如果忽略不确定性，成本会显著增加。然而，成本增加的程度取决于处理不确定性的方式。随着客户出现概率的增加，随机解的值也会增加。
5.结论
本文介绍并研究了考虑随机客户和需求的一致性车辆路径问题，采用基于场景的两阶段随机规划方法进行研究。第一阶段为规划阶段，包括为客户分配司机，这些分配在第二阶段保持不变。第二阶段在实现随机变量后，模型定义了哪辆车将访问哪些客户，以及车辆将按照选定的分配路线行驶。问题中设定了一致性目标，即分配给每个客户的司机数量上限，对违反一致性目标的行为进行惩罚。
参考文献：
Groër, C., Golden, B., Wasil, E., 2009. The consistent vehicle routing problem. Manuf. Serv. Oper. Manag. 11 (4), 630–643.
Gendreau, M., Jabali, O., Rei, W., 2016. 50Th anniversary invited article-future research directions in stochastic vehicle routing. Transp. Sci. 50 (4), 1163–1173.
Alvarez, A. , Jans, R. , & Mannering, F. ，2024. The consistent vehicle routing problem with stochastic customers and demands. Transport Res B-meth. 186.
微信公众号后台回复
加群：加入全球华人OR|AI|DS社区硕博微信学术群
资料：免费获得大量运筹学相关学习资料
人才库：加入运筹精英人才库，获得独家职位推荐
电子书：免费获取平台小编独家创作的优化理论、运筹实践和数据科学电子书，持续更新中ing...
加入我们：加入「运筹OR帷幄」，参与内容创作平台运营
知识星球：加入「运筹OR帷幄」数据算法社区，免费参与每周「领读计划」、「行业inTalk」、「OR会客厅」等直播活动，与数百位签约大V进行在线交流
文章须知
推文作者：祝心怡，香港理工大学在读博士生
责任编辑：江镕行
微信编辑：疑疑
文章由『运筹OR帷幄』原创发布
如需转载请在公众号后台获取转载须知
关注我们
FOLLOW US
