NGBB：用图神经网络加速车辆路径问题的精确求解

NGBB项目将图神经网络（GNN）与分支定界算法结合，通过模仿强分支决策来加速带容量约束车辆路径问题（CVRP）的精确求解，在保持最优性保证的同时显著减少搜索树规模，为物流优化领域提供高效智能解决方案。

车辆路径问题（VRP）是物流核心优化难题，属NP-hard问题，解空间随客户数量指数增长。传统精确算法保证最优但耗时，近似算法快却无最优性保证。分支定界是经典精确框架，分而治之求解；强分支策略能减小搜索树但计算昂贵，需临时评估候选变量。

NGBB（Neural Graph Branch-and-Bound）将GNN与分支定界结合针对CVRP。核心是用GNN模仿强分支决策：将CVRP建模为图（客户点为节点、距离为边），GNN通过消息传递学习嵌入，快速选最优分支方向，替代传统强分支的昂贵计算，同时保持最优性保证。

NGBB特点：

1. 动态优化：支持动态CVRP，应对需求变化、实时订单；
2. 最优性保证：基于分支定界框架，获数学最优解；
3. 搜索树缩减：智能分支选择显著减少节点访问量；
4. 适用广泛：可用于配送调度、服务路线规划、垃圾回收优化等场景。

NGBB挑战：

1. 泛化性：模型对未见过的问题规模/特征性能可能下降；
2. 训练数据：强分支样本获取耗时；
3. 预测可靠性：次优决策可能增加搜索树规模，需回退传统方法策略。未来需提升泛化能力、优化训练数据获取。

NGBB代表组合优化与机器学习融合前沿，用数据驱动增强传统算法，兼顾理论保证与性能提升。随物流效率需求提升及新模式兴起，这类智能优化技术将发挥重要作用，为研究者和工程师提供深度学习与运筹学结合的参考。