针对CVRP的2-OPT算法的时间复杂度均值分析

分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,建立起该算法运行所需的迭代次数的分布函数 ,进而求得平均运算时间复杂度的上界。该文为有效评价针对 VRP的 2 - OPT算法 ,提供了理论依据 ,并为VRP领域的启发式算法的复杂度分析 ,提供了一种新思路。