《Kuwait Journal of Science》：Exact and heuristic methods for the risk-constrained cash-in-transit vehicle routing problem
编辑推荐：
摘要本文研究了风险约束的现金运输车辆路径问题（RCTVRP），其中每位客户由一辆车辆访问，收集预定金额的现金。与一条路径相关的风险定义为行驶距离与所运输现金金额的乘积。目标是最小化总行驶距离，同时确保每条路径上的风险不超过预定义的阈值。为了解决RCTVRP，研
摘要本文研究了风险约束的现金运输车辆路径问题（RCTVRP），其中每位客户由一辆车辆访问，收集预定金额的现金。与一条路径相关的风险定义为行驶距离与所运输现金金额的乘积。目标是最小化总行驶距离，同时确保每条路径上的风险不超过预定义的阈值。为了解决RCTVRP，研究人员提出了两种方法：一种精确的分支-切割-定价（BCP）算法，以及一种结合了迭代局部搜索、随机化可变邻域下降和集合划分模型的元启发式算法。在包含多达337个节点的基准实例上进行的计算实验表明，研究人员提出的精确方法和启发式方法在解的质量和计算时间方面均优于文献中现有的最佳方法。提出的精确方法在123个测试实例中，有87个获得最优解，而提出的启发式方法在138个实例中，有117个匹配或改进了已知的最佳解。
以下是根据您提供的论文原文撰写的解读文章：
**研究背景、问题与意义**
现金运输（CIT）行业负责在银行、自动取款机（ATM）、珠宝店等处理大量现金的商业场所之间安全运输现金及其他贵重资产。由于所运货物价值高昂，安全是核心关注点，现金运输作业面临抢劫和武装袭击等风险。为降低这些威胁，公司采用严格的安保协议，包括装甲车辆、实时追踪和受训人员。此外，优化现金运输路线不仅对增强安全性至关重要，也有助于降低运营成本和提高服务效率，使其成为一个具有重要实际意义的复杂物流问题。考虑到这些安全问题，现金运输行业的路线优化需要纳入风险因素的专门模型，这促使了Talarico等人（2015）提出风险约束的现金运输车辆路径问题（RCTVRP）。
RCTVRP的核心在于设计一组从中央仓库出发、访问给定数量客户的路线，同时最小化总行驶距离。每位客户必须被访问恰好一次，并在每次访问时收集预定金额的现金。与传统的车辆路径问题（VRP）不同，该问题假设车辆容量不是限制因素，但出于安全原因，禁止仅包含一条路线的解。为降低盗窃风险，RCTVRP为每条路线引入了一个与现金运输相关的风险度量，该风险随着行驶距离和携带现金金额的增加而增加。此风险受限于一个预定义的风险阈值，确保没有路线超过可接受的安全水平。尽管已有研究，但现有精确方法（如Pereira Silva等人（2020）提出的单商品流（OCF）模型）和启发式方法（如Radoji?i?等人（2018）提出的模糊贪婪随机自适应搜索程序（GRASP）与路径重连算法）在求解大规模实例时仍存在局限性，例如求解速度慢或无法保证解的质量。因此，开发更高效的RCTVRP求解方法对于提升现金运输操作的安全性和成本效益具有直接意义。
**主要研究内容与结论**
本研究针对RCTVRP，提出了两种创新的求解方法：一种精确的分支-切割-定价（BCP）算法和一种基于迭代局部搜索（ILS）的元启发式算法（ILS-SP）。通过在包含多达337个节点的138个基准实例上进行广泛计算实验，研究结果表明，所提出的BCP算法在求解质量和计算时间上均显著优于文献中现有的最佳精确方法（OCF模型），在123个测试实例中成功求解了87个最优解。同时，提出的ILS-SP启发式算法在所有138个实例上均展现出强大的性能，其平均差距和计算时间均优于现有最佳启发式方法（模糊GRASP），并且在117个实例中找到了与已知最佳解（BKS）相匹配或更优的解。该研究发表于《Kuwait Journal of Science》。
**关键技术与方法**
1. **分支-切割-定价（BCP）算法**：基于集合划分（SP）公式，通过求解一个带资源约束的最短路径问题（SPPRC）作为定价子问题来动态生成满足风险约束的路径变量。该方法集成了Sadykov和Vanderbeck（2021）的通用BCP框架、Sadykov等人（2021）的基于桶的标记算法、ng-path松弛、rank-1切割、自动对偶价格平滑稳定化、路径枚举技术和分层强分支等先进技术。
2. **迭代局部搜索-集合划分（ILS-SP）元启发式算法**：这是一种混合方法，结合了迭代局部搜索（ILS）、随机化可变邻域下降（RVND）和集合划分（SP）模型。在ILS框架内，采用多种经典邻域算子（如swap、shift、2-opt等）进行局部搜索，并通过扰动机制逃避局部最优。搜索过程中收集的路径被存储在一个池中，最终通过求解一个SP模型来全局优化组合这些路径，以得到最终解。
**研究结果**
**4. Proposed BCP algorithm（提出的BCP算法）**
通过基于集合划分公式的BCP算法，动态生成满足风险约束的路径变量。该算法将定价子问题建模为SPPRC，并采用前向和后向标记算法结合串联准则来生成可行路径。引入了ng-path松弛和rank-1切割等机制来加强界限，并采用多级强分支策略处理分数解。
**5. Proposed ILS algorithm（提出的ILS算法）**
提出的ILS-SP算法围绕ILS框架构建，集成了RVND进行局部搜索和SP模型进行解的精炼。初始解通过随机选择最佳并行插入（BPI）或Clarke and Wright节约算法（CW）生成。局部搜索阶段采用9种邻域（包括路线间和路线内），并在RVND框架下进行探索。扰动阶段通过随机应用多次swap或shift操作来逃离局部最优。最后，在搜索过程中收集的路径被用于构建和求解一个SP模型，以进行全局优化。
**6. Computational results（计算结果）**
通过大量计算实验验证了方法的有效性。
* **6.2. Comparison with the literature — exact approaches（与文献比较——精确方法）**：在包含123个实例的测试集上，提出的BCP算法在7200秒内最优求解了87个实例，平均计算时间为2295.4秒；而文献中最佳精确方法（OCF）仅求解了32个实例，平均计算时间为5170.1秒，表明BCP算法在求解数量和速度上均占优。
* **6.3. Results per instance — proposed exact approach（按实例结果——提出的精确方法）**：对V、O、S三个数据集进行了详细分析。BCP算法能最优求解几乎所有不超过101个节点的实例，但对于V数据集中72个节点的实例，由于客户需求高度异质且风险阈值（T）很大，导致定价子问题复杂，求解困难。S数据集中的实例因螺旋形空间布局，难度也相对较高。
* **6.4. Results of the proposed ILS approach（提出的ILS方法结果）**：在与现有最佳启发式方法（模糊GRASP）的对比中，ILS算法在所有数据集上均取得了更低的平均差距（Gap best和Gap avg）和更短的计算时间。例如，在V数据集（>72节点）上，ILS算法的平均最佳差距为0.2%，而文献方法为4.5%。在138个实例中，ILS算法在117个实例中找到的解与BKS一致。
**结论与讨论**
本文针对风险约束的现金运输车辆路径问题（RCTVRP），提出了两种求解方法：一种迭代局部搜索（ILS）算法和一种精确的分支-切割-定价（BCP）算法。在包含多达337个节点的123个基准实例上，BCP精确方法表现出色，在7200秒时间限制内最优求解了87个实例，而文献中的最佳方法仅能求解32个。对于启发式方法，ILS算法在所有138个测试实例上均产生了高质量的解，其平均差距和计算时间均优于现有最佳启发式算法，并且在117个实例中找到了与已知最佳解（BKS）相匹配的解。未来的研究方向是探索其他包含风险考量的VRP变体，并调整研究人员提出的方法以有效处理这些扩展问题。
