请求解析OR-Tools中PATH_CHEAPEST_ARC与GLOBAL_CHEAPEST_ARC的差异

核心逻辑拆解 #

PATH_CHEAPEST_ARC #

• 采用局部延伸式贪心：从设定的路线起始节点出发，每一步仅关注当前路径的最后一个节点，选择与它相连的成本最低的未访问节点，将其加入路径末尾，重复该过程直至所有节点都被纳入路径。
• 扩展到VRP场景时，会按车辆顺序依次用该逻辑生成各自的初始路径，每辆车的路径都是从起始点开始逐步延伸的连续链。

GLOBAL_CHEAPEST_ARC #

• 采用全局配对式贪心：完全不考虑当前路径的状态，每次在所有未建立连接的节点对中，筛选出成本最低的弧（路段），将这两个节点连接起来，重复操作直到所有节点都被整合进若干子路径中，最后再根据车辆数量拆分、调整这些子路径以符合VRP要求。

关键差异对比 #

• 决策范围不同：PATH_CHEAPEST_ARC是"走一步看一步"的局部最优，每一步只聚焦当前路径末端的邻居节点；GLOBAL_CHEAPEST_ARC则是全局视角，每次在所有未连接节点对里选成本最低的路段。
• 初始路径形态不同：PATH_CHEAPEST_ARC生成的是连续的单链（多车辆时为多条独立单链）；GLOBAL_CHEAPEST_ARC会先形成多个分散的子路径，后续再进行整合分配。
• 成本与效率权衡不同：PATH_CHEAPEST_ARC计算速度更快，每一步仅需计算当前节点的邻居成本；GLOBAL_CHEAPEST_ARC初始解的整体路段成本可能更低，但节点数量较多时，每次遍历所有节点对的计算量更大，且后续需要额外步骤整合子路径。
• VRP适配场景不同：PATH_CHEAPEST_ARC更适合车辆数量少、路径连续性要求高的场景；GLOBAL_CHEAPEST_ARC在节点规模大、车辆资源充足的场景下，能先锁定全局最低成本的路段组合，后续调整空间更大。

内容的提问来源于stack exchange，提问作者vawrom