4. VRP求解算法概览

车辆路径问题（VRP）是典型的NP-hard组合优化问题。随着客户规模从几十个增长到上千个，单一算法很难在所有场景下都表现良好。理解精确算法、启发式算法与元启发式算法各自的能力边界，是后续建模与求解选型的基础。本节不追求罗列算法细节，而是围绕“什么问题该用什么算法、算法在什么条件下会失效”这条主线展开。

三类算法的本质差异

精确算法以数学规划为基础，追求在有限时间内证明最优解。分支定界（Branch and Bound）通过对解空间的分支与剪枝，配合下界估计逐步排除劣解；分支定价（Branch and Price）则把列生成嵌入分支框架，适合处理车辆数多、路径组合爆炸的集合划分模型。它们的共同点是：只要运行足够久，理论上能给出最优解与最优性间隙，但计算时间随规模呈指数增长。

启发式算法不保证最优，但追求在可接受时间内得到高质量可行解。构造启发式（如节约算法Clarke-Wright、最近邻、扫描法）从空解出发逐步插入客户，速度快、实现简单，常作为初始解生成器；改进启发式（如2-opt、Or-opt、 relocate、交换邻域）在已有解上做局部调整，通过邻域搜索降低总成本。二者通常组合使用：先构造，再改进。

元启发式算法在局部搜索之上引入更高层的策略以跳出局部最优。遗传算法通过种群交叉变异保持多样性；蚁群算法利用信息素正反馈逐步强化优质路径；禁忌搜索用禁忌表记录近期移动，避免循环并接受劣解以探索更广区域。它们适合中大规模、约束复杂的场景，但参数敏感、结果具有随机性，需要多次运行评估稳定性。

性能边界从哪里来

精确算法的瓶颈在于下界质量与分支规模。以分支定界为例，若下界松弛过松，剪枝效率低，搜索树迅速膨胀；分支定价虽然通过列生成缓解了变量爆炸，但每次迭代都要解定价子问题（通常是带资源约束的最短路），规模上去后单次迭代成本也很高。工程经验上，带容量约束的CVRP在客户数约50以内、约束不太复杂时，精确算法尚可在合理时间内给出最优或接近最优解；超过100后往往需要借助启发式提供上界、并设置时间上限接受最优性间隙。

启发式的边界在于邻域结构与陷入局部最优。节约算法在客户分布较均匀、容量约束不紧时表现稳定，但遇到时间窗、多车型等复杂约束时，构造规则需要大幅改造。2-opt等改进算子对路径内部交叉有效，却难以处理跨路径的客户迁移，因此常需组合多种邻域。它们真正的价值在于“快”：几百个客户也能在秒级给出可行解，适合作为元启发式的初始解或实时调度中的快速响应方案。

元启发式的边界在于参数与评价预算。遗传算法的种群规模、交叉变异率，蚁群的信息素挥发系数，禁忌搜索的禁忌长度与候选集大小，都会显著影响结果。它们通常需要成百上千次迭代，单次评价又要计算完整路径成本，因此大规模场景下必须控制评价次数或采用增量计算。另一个常被忽视的点是随机性：同一组参数多次运行结果可能相差几个百分点，工程上应固定随机种子做对比，并报告多次运行的均值与最差值，而不是只挑最好的一次。

一个选型示例

假设某配送中心有1辆车、容量约束、80个客户，要求2小时内给出方案。此时精确算法可能因时间不足而无法收敛，建议先用节约算法构造初始解，再用2-opt与relocate组合改进，若仍有时间余量，可启动禁忌搜索在改进解上继续优化，并设置评价次数上限。若客户数降到30且允许4小时计算，则可尝试分支定价，以启发式解作为初始上界加速剪枝。这个例子说明：算法选型不是按“先进程度”排序，而是按规模、时限、质量要求三者共同决定。

常见误区

• 把元启发式当作万能解：在客户数很少时，它可能比精确算法更慢且无法证明最优。
• 只用一次运行结果下结论：随机算法的单次结果不足以代表其真实水平。
• 忽视约束改造成本：构造启发式在标准CVRP上有效，加入时间窗后往往需要重新设计插入准则。
• 不设时间上限：精确算法在难例上可能长时间无进展，工程中应设置间隙阈值或时间预算。