带有中途设施的有限容量单车辆覆盖巡回问题的分解方法

《Computers & Operations Research》：Decomposition method for a capacitated single-vehicle covering tour problem with intermediate facilities

　　

我们考虑一个带有中间处置设施的废物收集问题，以适应更小但更可持续的车辆的使用，这些车辆的容量小于传统的废物收集卡车。优化问题在于确定放置收集点的位置以及访问这些位置的容量受限收集车辆的路径。我们首先提出了一个利用路网稀疏性的混合整数线性规划模型。为了解决实际问题实例，我们提出一种解决方案，将问题分解为选择位置的集合覆盖问题和确定路径并对集合覆盖解进行定价的带中间设施的容量受限车辆路径问题。我们应用列生成来解决这个路径问题，并提出一种新颖的集合覆盖问题方法，利用问题属性通过图论方法高效地找到集合覆盖。我们将我们的方法与先前工作中提出的集合构造方法以及使用最先进的商业求解器直接求解混合整数线性规划模型进行了比较。基于真实数据生成的实例的计算实验证实了我们问题的难度，并显示了所开发的分解方法在最佳解决方案数量和到最佳解决方案的平均差距方面的优越性能。

在本文中，我们研究一个涉及比传统收集卡车更小但更可持续车辆的废物收集问题。这类车辆在独栋住宅区或街道狭窄的市中心可以高效运行。然而，由于容量和行驶速度有限，需要安装中间处置设施以避免长途前往最终处置设施。由于所有车辆都是相同的，在我们的设置中，我们认为只使用一辆车，但它可以进行任意次数的旅行。因此，我们将问题建模为带中间设施的容量受限单车覆盖旅行问题 (CCTP-IF)，这是路网上的多车容量受限覆盖旅行问题 (Cm-CTP-R; Fischer 等，2023) 的一个变体。它是在设计更高效和可持续的不可回收废物收集系统的背景下引入的。给定带有车辆仓库、放置收集点的候选位置和一组中间设施的路网，我们在本文中解决的决策包括选择居民必须放置垃圾袋的收集点位置以及确定容量受限车辆的路径。车辆执行恰好一次轮转，从仓库出发并返回，访问选定的地点收集废物，并根据其容量要求随时在中间设施卸载。它总是在中间设施进行最后一次卸载后结束轮转，以便空车返回车辆仓库。每栋住宅楼产生一定量的废物，只有在该建筑给定（合理）步行距离内的候选地点才被认为适合居民放置垃圾袋。因此，对于每栋建筑，必须至少选择一个合格的收集点。如果在解决方案中为某栋建筑选择了几个这样的地点，我们假设该建筑的所有居民总是会选择最近的一个来放置垃圾。在我们的研究基于的案例中，大型传统垃圾车随后将废物从中间设施运往最终处置点，但这部分过程不在本研究考虑范围内。

图 1 说明了瑞士某市政当局一小部分街道网络上的 CCTP-IF。在此示例中，所有街道都是双向的。所有圆圈都是候选收集点，位于路网上，加粗的被认为与相关住宅楼距离为 0（它们被添加以保证至少有一个收集点位于每栋建筑的最大步行距离内）。方块代表中间设施，三角形是车辆仓库。图 1(b) 显示了一个解决方案示例，最大步行距离为 100 米。在此解决方案中，车辆从仓库出发，访问最远的选定收集点，收集废物，并在途中停在另一个点。然后它在最远的中间设施卸载。在返回途中，它服务另一个收集点，并在返回仓库之前在最近的中间设施处置剩余的废物。注意，所有住宅楼节点都位于至少一个选定收集点（绿色）的 100 米范围内。

本文的贡献如下：
1. 我们引入并建模了 Cm-CTP-R (Fischer 等，2023) 的一个包含中间设施的新变体。为了处理源自真实数据的大型实例 (Fischer 等，2023)，我们开发了一种解决方案，将问题分解为其构建的原子问题：集合覆盖问题 (SCP) 和带中间设施的容量受限车辆路径问题 (CVRP-IF)。我们还提供了广泛的计算结果来展示这种方法的优势。
2. 利用路网结构，我们提出了一种新的启发式算法来解决 SCP，基于在弦图中寻找最小团覆盖已知是多项式时间复杂度这一事实 (Golumbic, 2004)。
3. 我们证明对于 CVRP-IF，使用动态规划和 ng-path 概念 (Baldacci 等，2011) 解决带资源约束的最短路径问题 (SPPRC) 在路网上比在完全网络上更高效。

本文其余部分组织如下：第 2 节简要介绍了与我们的问题相关的研究。第 3 节正式定义了问题。第 4 节提出了基于路网的混合整数线性规划模型。第 5 节介绍了分解方法的一般思路，第 6 节提出了集合覆盖问题的图论方法，第 7 节描述了带中间设施的容量受限车辆路径问题的列生成方法。第 8 节报告了计算实验，第 9 节给出了一些结论性意见。

章节摘要
相关工作
Fischer 等 (2023) 引入的 Cm-CTP-R 与多车覆盖旅行问题 (m-CTP; Hachicha 等，2000) 密切相关，在其中设计最多 m 条车辆路径，这些路径从仓库出发并返回，总长度最小，使得需要覆盖的节点位于旅行节点（即车辆访问的节点）的预设距离内。定义附加约束来限制任何路径的节点数量和长度。Cm-CTP-R 被建模为

问题定义
在本节中，我们使用 Fischer 等 (2023) 中引入的符号和建模假设正式定义 CCTP-IF。给定一个有向强连通图 G=(V∪W,A)，具有两个节点集 V 和 W，以及代表路网的弧集 A。W 是有正需求的节点集，V 包括代表候选位置、中间设施和道路交叉口的节点，后者提供路网精细表示而不是

基于路网的模型
我们扩展了 Fischer 等 (2023) 中提出的基于路网的模型，其中为每个路段引入了决策变量 (Letchford 等，2013)。设 M={1,…,m} 为 m 条路径的集合，其中 m 定义了基于车辆容量 Q 可执行路径数量的上界。设 Vfacσ=Vfac∪{σ} 为可用的中间设施和仓库的集合。设 xll′k 为一个整数变量，表示在第

分解方法
为了解决源自真实数据的大型实例，我们提出一种将 CCTP-IF 分解为集合覆盖问题和带中间设施的容量受限车辆路径问题的解决方案。在我们的背景下，集合覆盖问题具有可以利用的特殊结构。我们通过为集合覆盖问题引入一种新颖的方法来实现这一点，该方法由在需求节点可步行子图的交集图中寻找最小团覆盖组成 (第 6 节)。该方法返回一个集合覆盖 Vsel，定义了一个带中间设施的容量受限车辆路径问题实例，该实例由列

集合覆盖问题 (SCP)
集合覆盖问题通过一种新颖的最小团覆盖方法解决，该方法受益于路网结构和底层图的属性。在本文余下部分，我们将此方法称为团方法。

带中间设施的容量受限车辆路径问题 (CVRP-IF)
本节描述了在提出的分解方法 (第 5 节) 中用于解决带中间设施的容量受限车辆路径问题的列生成方法。列生成是一种通过迭代向模型添加变量来解决大量变量问题的技术 (Dantzig 和 Wolfe, 1960)。对于带中间设施的容量受限单车覆盖旅行问题，这是一个有前途的策略，因为带有中间设施的小车辆的路径往往比 Cm-CTP-R 中考虑的路径更短。给定一个集合覆盖

计算实验
在本节中，我们展示了计算实验的结果。解决方案已用 Java 实现。为了解决混合整数线性规划和受限主问题，我们通过其 Java API 使用了 Gurobi 9.5.2 MIP 求解器。实例在一台配有 Intel(R) Xeon(R) Gold 6148 CPU @ 2.40 GHz 处理器和 32 GB 内存的计算机上进行了测试，运行在 Linux 系统下，并设置了 12 小时的时间限制，除非另有说明。

结论
在本文中，我们建模了带中间设施的容量受限单车覆盖旅行问题，其灵感来自于带有中间处置设施的废物收集问题，以适应更小车型的使用。它是 Fischer 等 (2023) 引入的路网上的多车容量受限覆盖旅行问题的一个变体，而后者本身与多车覆盖旅行问题密切相关。我们扩展了他们提出的基于路网的混合整数线性规划模型，并开发了一种将问题分解为集合覆盖问题和带中间设施的容量受限车辆路径问题的解决方案，以处理源自真实数据更大的实例

CRediT 作者贡献声明
Vera Fischer: 写作 – 审阅与编辑，写作 – 原稿，可视化，验证，方法论，调查，形式分析，数据管理，概念化。Antoine Legrain: 写作 – 审阅与编辑，验证，监督，方法论。Patrick Munroe: 写作 – 审阅与编辑，验证，软件，数据管理。David Schindl: 写作 – 审阅与编辑，验证，监督，方法论。

致谢
作者们衷心感谢 Innosuisse 在 36157.1 IP-EE 资助下的支持。他们还感谢 Hasler 基金会支持在加拿大蒙特利尔的研究停留，并高度重视 Schwendimann AG 在实施实践实验和提供相关数据方面的参与。

Vera Fischer|Antoine Legrain|Patrick Munroe|David Schindl
弗里堡大学，瑞士弗里堡