摘要

本文提出了一种名为 UDC 的统一神经分治框架，用于解决大规模组合优化问题。该框架采用了一种新的基于强化学习的训练方法 DCR，以缓解次优分割策略的负面影响。UDC 利用高效的图神经网络进行全局分割，并使用固定长度的子路径求解器来解决子问题，在 10 个具有代表性的大规模组合优化问题上取得了显著的性能提升。

原理

UDC 框架遵循神经分治方法的一般框架，通过两个不同的阶段解决组合优化问题：分割阶段和征服阶段。在分割阶段，UDC 利用图神经网络生成初始解，并通过分割策略将问题分解为多个子问题。在征服阶段，UDC 利用构造性求解器来解决这些子问题，并通过合并子解来得到最终解。

流程

1. 分割阶段：UDC 首先构建一个稀疏图来表示问题实例，然后利用各向异性图神经网络（AGNN）生成热度图。基于热度图，UDC 利用分割策略生成初始解。
2. 征服阶段：UDC 首先根据初始解生成待解决的子问题和相应的约束。然后，UDC 利用构造性求解器来解决这些子问题，并通过合并子解来得到最终解。

应用

UDC 框架在大规模组合优化问题上具有广泛的应用前景，可应用于物流配送、车辆路径规划、任务分配等领域。此外，UDC 框架还可以与其他技术结合，如强化学习、深度学习等，以进一步提高其性能和应用范围。