通过协同划分优化构建稳健可行的路径

# 1 引言 来源：https://arxiv.org/html/2607.03694 \\OneAndAHalfSpacedXII\\EquationsNumberedThrough\\TheoremsNumberedThrough\\ECRepeatTheorems\\MANUSCRIPTNO \\RUNAUTHOR Karaahmetoglu 和 Kim \\RUNTITLE 协作分区优化 \\TITLE 通过协作分区优化实现鲁棒的可行路径构建 \\ARTICLEAUTHORS\\AUTHOR Oguzhan Karaahmetoglu\\AFF电气与计算机工程系，卡内基梅隆大学，\\EMAILokaraahm@cmu\.edu \\AUTHOR Hyong Kim\\AFF电气与计算机工程系，卡内基梅隆大学，\\EMAILkim@ece\.cmu\.edu \\ABSTRACT 大规模容量受限车辆路径问题（CVRP）通常通过将客户划分为更小的路径子问题来求解，这些子问题可以独立优化。虽然这大大降低了计算复杂度，但独立构建的路径解决方案可能导致部分客户需求未被满足，即使车队其他部分有足够的资源。我们提出了协作路径构建器（CoRC），这是一个路径规划框架，允许独立求解的子问题在优化过程中交换客户和车辆，而不是仅依赖固定分区或后续的全局重优化阶段。在AGS基准实例和包含多达20万个客户的合成实例上进行的计算实验，将CoRC与独立路径规划、路径后全局重优化以及最先进的端到端路径框架进行了比较。在所有评估的分区策略中，CoRC一致地构建了可行的路径解决方案，而其他基于分区的方法则未能做到。此外，对于评估的端到端路径框架在相同计算预算下未能产生解决方案的问题实例，CoRC依然有效。这些结果表明，路径子问题之间的协作为大规模可行路径构建提供了一种鲁棒且可扩展的方法。 \\KEYWORDS 车辆路径问题，容量受限车辆路径问题，大规模优化，优化 我们考虑同质化(Dantzig 和 Ramser1959 (https://arxiv.org/html/2607.03694#bib.bib53))和异质化车队的容量受限车辆路径问题（CVRP）(Goldenet al.1984 (https://arxiv.org/html/2607.03694#bib.bib54), Toth 和 Vigo2014 (https://arxiv.org/html/2607.03694#bib.bib1))。给定一组已知需求的客户和一支由容量受限车辆组成的车队，目标是在不违反车辆容量约束的情况下，构建访问所有客户的顺序路径，同时最小化总路径成本。CVRP是交通运输和物流领域的基本优化问题之一，应用包括货物配送(Crainic 和 Laporte1997 (https://arxiv.org/html/2607.03694#bib.bib50))、包裹及最后一公里配送(Boysenet al.2020 (https://arxiv.org/html/2607.03694#bib.bib51))、人道主义物流(Campbellet al.2008 (https://arxiv.org/html/2607.03694#bib.bib52))以及城市服务运营，如垃圾收集和街道维护(Yamínet al.2024 (https://arxiv.org/html/2607.03694#bib.bib47), Anily 和 Federgruen1993 (https://arxiv.org/html/2607.03694#bib.bib49))。CVRP是NP难的(Lenstra 和 Rinnooy Kan1981 (https://arxiv.org/html/2607.03694#bib.bib8))。因此，文献中发展了广泛的精确算法、启发式算法、元启发式算法和分解技术，以获得高质量的路径解决方案(Gillett 和 Miller1974 (https://arxiv.org/html/2607.03694#bib.bib14), Clarke 和 Wright1964 (https://arxiv.org/html/2607.03694#bib.bib59), Pisinger 和 Ropke2018 (https://arxiv.org/html/2607.03694#bib.bib58))。其中，基于分解的方法已成为现代车辆路径启发式算法的重要组成部分，特别是在大规模路径实例中(Santiniet al.2023 (https://arxiv.org/html/2607.03694#bib.bib17))。一个突出的分解范式是“先聚类后路径”（CFRS）框架(Gillett 和 Miller1974 (https://arxiv.org/html/2607.03694#bib.bib14), Jingjinget al.2022 (https://arxiv.org/html/2607.03694#bib.bib23))。在该框架中，原始路径实例被划分为多个路径子问题，每个子问题由一组客户和分配的一组车辆组成。每个子问题因此定义了一个更小的CVRP，可以随后独立求解。因此，对每个子问题应用路径算法来构建局部车辆路径(Kerscher 和 Minner2024 (https://arxiv.org/html/2607.03694#bib.bib32), Pisinger 和 Ropke2018 (https://arxiv.org/html/2607.03694#bib.bib58))。最后，将所有子问题获得的路径合并，得到原始大规模实例的解决方案。这种分区与路径的分离自然引出一个问题：在分解完成后如何执行路径规划。为此，我们在下一小节讨论针对这一范式的现有方法。 ### 1\.1 先前工作 早期的CFRS方法主要侧重于几何分区。代表性例子包括扫描算法(Gillett 和 Miller1974 (https://arxiv.org/html/2607.03694#bib.bib14))和基于质心的聚类方法(Abdellaouiet al.2024 (https://arxiv.org/html/2607.03694#bib.bib20))，这些方法根据客户的空间位置进行划分，然后在每个分区内独立构建路径。许多后续方法继续基于几何分区原则，同时提出替代的聚类过程(Cakiret al.2015 (https://arxiv.org/html/2607.03694#bib.bib55), Gaonet al.2025 (https://arxiv.org/html/2607.03694#bib.bib57))。后续工作将额外的操作信息纳入分区阶段。这些方法不仅依赖客户位置，在构建分区时还考虑客户需求、车辆容量或与路径相关的工作量度量等因素(Alesianiet al.2022 (https://arxiv.org/html/2607.03694#bib.bib10), Linfatiet al.2022 (https://arxiv.org/html/2607.03694#bib.bib24), Jingjinget al.2022 (https://arxiv.org/html/2607.03694#bib.bib23))。最近，基于学习的方法通过强化学习、神经组合优化和大语言模型，使用优化反馈来指导分解决策(Liet al.2022 (https://arxiv.org/html/2607.03694#bib.bib11), Chin 和 Schiffer2026 (https://arxiv.org/html/2607.03694#bib.bib25), Da Roset al.2026 (https://arxiv.org/html/2607.03694#bib.bib27), Xiuet al.2026 (https://arxiv.org/html/2607.03694#bib.bib28), Thindet al.2025 (https://arxiv.org/html/2607.03694#bib.bib29))。这些现代方法通过经验风险最小化来估计策略，从而利用历史数据中的模式进行扩展(Vapnik1991 (https://arxiv.org/html/2607.03694#bib.bib60))。分解构建完成后，最常见的路径策略是独立求解每个路径子问题，然后将得到的路径组合成完整解决方案(Gillett 和 Miller1974 (https://arxiv.org/html/2607.03694#bib.bib14), Battarraet al.2014 (https://arxiv.org/html/2607.03694#bib.bib43))。在此策略下，每个聚类使用仅分配给该子问题的客户和车辆，通过路径求解器进行处理。另一系列研究在独立生成的路径合并后，执行额外的优化阶段(Kerscher 和 Minner2024 (https://arxiv.org/html/2607.03694#bib.bib32))。这些方法应用全局改进过程，如自适应大邻域搜索(Ropke 和 Pisinger2006 (https://arxiv.org/html/2607.03694#bib.bib62))或“分解-路径-改进”策略，来优化合并后的路径解决方案。通过将合并的路径规划与客户和车辆分配相结合进行优化，这些方法提供了改进独立路径构建所得解决方案的额外机会。这旨在降低路径成本或纳入在独立路径阶段仍未服务的客户。现有路径范式要么在路径构建过程中保持初始分解不变，要么仅通过后续的全局重优化阶段引入协调。然而，路径构建本身会产生初始分解中不可用的优化信息，包括未服务需求、未使用车辆以及剩余车辆容量。这些数量表征了每个子问题的当前路径状态，并可能指示在路径过程完成之前修订客户和车辆分配的机会。受此观察的启发，我们研究了路径阶段的一种替代组织方式。我们不将协调限制在初始分解或推迟到后续的全局优化阶段，而是在路径构建过程中引入一个中间协作阶段。在此方案中，路径子问题交换其局部路径结果的摘要，从而在最终解决方案组装之前实现客户转移、车辆转移和分区合并。由于协作机制作用于现有初始分解之上，它与几何、操作和基于学习的分区方法是互补的。 ## 2 问题定义 我们的方法建立在经典CVRP及其在“先聚类后路径”框架下的分解基础之上。因此，我们首先阐述底层路径问题，然后定义相应的分解，最后引入一个动态扩展，允许路径子问题在路径过程中进行交互。参见图注(a)容量受限车辆路径问题公式。参见图注(b)静态先聚类后路径（CFRS）公式。参见图注(c)具有当前解的动态CFRS公式。图1：所提出公式的数学演进。(a) CVRP公式，定义路径和路径解决方案。(b) 传统CFRS公式，其中固定分解P\\mathcal\{P\}导致独立的路径子问题，其当前解S\\mathcal\{S\}被组合成全局解。(c) 动态CFRS公式，其中分解和当前解通过重新分配操作在优化步骤中演变，同时保留未受影响的当前路径。### 2\.1 不可分割需求的容量受限车辆路径问题 在本节中，我们介绍本文中使用的公式和符号，以及CVRP的目标和约束。图1(a) (https://arxiv.org/html/2607.03694#S2.F1.sf1) 展示了一个简单案例。令CC表示客户集合，MM表示车辆集合，L=C∪\{0\}L=C\\cup\\\{0\\\}表示包括车场在内的所有位置集合。每个客户c∈Cc\\in C有需求dcd\_\{c\}，每辆车m∈Mm\\in M有容量QmQ\_\{m\}，位置i,j∈Li,j\\in L之间的旅行成本由tijt\_\{ij\}给出。 ###### 定义2.1 (路径) 车辆m∈Mm\\in M的路径是一个有序位置序列Rm=\(0,vm\(1\),...,vm\(lm\),0\),R\_\{m\}=\(0,v\_\{m\}^\{\(1\)\},\\ldots,v\_\{m\}^\{\(l\_\{m\}\)\},0\),其中lml\_\{m\}是车辆mm的路径长度，vi∈Cv\_\{i\}\\in C是被车辆mm访问的不同客户，路径从车场开始并结束，并且沿路径服务的总需求不超过车辆容量，∑c∈Rmdc≤Qm\\sum\_\{c\\in R\_\{m\}\}d\_\{c\}\\leq Q\_\{m\}。 ###### 定义2.2 (路径解决方案) 路径解决方案是一个路径集合S=\{Rm\}m∈MS=\\\{R\_\{m\}\\\}\_\{m\\in M\}，包含车队中每辆车至多一条路径。在本文中，我们区分几种类型的路径解决方案。 ###### 定义2.3 (解的相关术语) 令SS表示一个路径解决方案。 - •*可行解*满足优化模型的所有路径约束，但可能留下部分客户需求未被服务。 - •*完整解*是一个可行解，其中每位客户都得到服务。为了适应可用车辆资源不足以服务所有客户需求的路径实例，或尚未构建完整解的中间优化阶段，我们允许客户暂时未被服务。令xijmx\_\{ijm\}为二进制变量，表示车辆mm是否经过弧(i,j)(i,j)；令zcmz\_\{cm\}为二进制变量，表示客户cc是否分配给车辆mm；令ycy\_\{c\}表示客户cc是否仍未被服务。我们考虑以下目标函数： min∑m∈M∑i∈L∑j∈Ltijxijm\+ρ∑c∈Cdcyc,\\min\\sum\_\{m\\in M\}\\sum\_\{i\\in L\}\\sum\_\{j\\in L\}t\_\{ij\}x\_\{ijm\}\+\\rho\\sum\_\{c\\in C\}d\_\{c\}y\_\{c\},\(1\)其中ρ∈R\+\\rho\\in\\mathbb\{R\}^\{\+\}是与未服务需求相关的惩罚系数。目标函数在最小化总旅行成本的同时，对未服务的客户需求进行惩罚。路径解决方案受标准的分配、流量守恒和车辆容量约束(Laporte2009 (https://arxiv.org/html/2607.03694#bib.bib7))。每位客户要么被访问恰好一次，要么保持未服务状态， ∑m∈M∑j∈Lxcjm\+yc=1,∀c∈C\.\\sum\_\{m\\in M\}\\sum\_\{j\\in L\}x\_\{cjm\}\+y\_\{c\}=1,\\qquad\\forall c\\in C\.\(2\) 流量守恒要求每辆进入客户位置的车辆也必须离开该位置， ∑j∈Lxijm=∑j∈Lxjim,∀i∈C,m∈M\.\\sum\_\{j\\in L\}x\_\{ijm\}=\\sum\_\{j\\in L\}x\_\{jim\},\\qquad\\forall i\\in C,\\;m\\in M\.\(3\) 车辆容量通过 ∑c∈Cdczcm≤Qm,∀m∈M\.\\sum\_\{c\\in C\}d\_\{c\}z\_\{cm\}\\leq Q\_\{m\},\\qquad\\forall m\\in M\.\(4\) 强制执行。其他路径约束，包括车场连通性、子路径消除和二进制域限制，遵循标准CVRP公式，为简洁起见此处省略。 ### 2\.2 先聚类后路径公式 接下来，我们形式化本文中使用的先聚类后路径（CFRS）框架。我们从传统的静态公式开始，其中分解在路径构建过程中保持不变。然后，我们扩展该公式，允许客户和车辆分配在连续的优化轮次中演变，为后续章节开发的协作路径方法提供数学基础。 #### 2\.2\.1 静态公式 先聚类后路径（CFRS）分解将CVRP实例划分为一组更小的路径子问题，如图1(b) (https://arxiv.org/html/2607.03694#S2.F1.sf2)所示。令 P=\{\(C1,M1\),\(C2,M2\),...,\(CK,MK\)\}\\mathcal\{P\}=\\left\\\{\(C\_\{1\},M\_\{1\}\),\(C\_\{2\},M\_\{2\}\),\\dots,\(C\_\{K\},M\_\{K\}\)\\right\\\}\(5\)表示客户集CC和车辆集MM的一个分解，其中每个路径子问题由一个客户子集Ck⊆CC\_\{k\}\\subseteq C和一个关联的车辆子集Mk⊆MM\_\{k\}\\subseteq M组成。客户和车辆分配形成不相交的分区， Ci∩Cj\\displaystyle C\_\{i\}\\cap C\_\{j\}=∅,\\displaystyle=\\emptyset,∀i≠j,\\displaystyle\\forall i\\neq j,\(6\)⋃k=1KCk\\displaystyle\\bigcup\_\{k=1\}^\{K\}C\_\{k\}=C,\\displaystyle=C,\(7\)Mi∩Mj\\displaystyle M\_\{i\}\\cap M\_\{j\}=∅,\\displaystyle=\\emptyset,∀i≠j,\\displaystyle\\forall i\\neq j,\(8\)⋃k=1KMk\\displaystyle\\bigcup\_\{k=1\}^\{K\}M\_\{k\}=M\.\\displaystyle=M\.\(9\) 每个分区定义一个独立的路径子问题Xk=\(Ck,Mk\)X\_\{k\}=\(C\_\{k\},M\_\{k\}\)，该子问题使用路径过程求解 Sk=σ\(Xk\)=\{Rm\}m∈Mk,S\_\{k\}=\\sigma\(X\_\{k\}\)=\\\{R\_\{m\}\\\}\_\{m\\in M\_\{k\}\},\(10\)其中SkS\_\{k\}d