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

被引：1

作者：

祝崇隽

刘民

吴澄

吴晓冰

机构：

[1] 清华大学自动化系

[2] 中兴通讯有限公司上海二所

来源：

清华大学学报(自然科学版) | 2002年 / 09期

关键词：

复杂度; 迭代次数; 分布函数; 上界; CVRP; 2-OPT;

D O I：

10.16511/j.cnki.qhdxxb.2002.09.022

中图分类号：

O221 [规划论（数学规划）];

学科分类号：

摘要：

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

引用

页码：1218 / 1221

页数：4