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

• 作者: 刘民 吴晓冰 吴澄 祝崇隽
• 来源期刊: 清华大学学报(自然科学版)
• 学科: 数学
• 关键词: 复杂度 迭代次数 分布函数 上界 CVRP 2-OPT
• 年，卷（期）: 2002,（9）
• 所属期刊栏目: 自动化
• 页码范围: 1218-1221
• 页数: 4页
• 分类号: O223
• 字数: 4535字
• 语种: 中文
• DOI: 10.3321/j.issn:1000-0054.2002.09.023

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	吴澄	清华大学自动化系	125	4840	34.0	67.0
2	刘民	清华大学自动化系	54	1195	17.0	33.0
3	祝崇隽	清华大学自动化系	3	355	3.0	3.0
4	吴晓冰	中兴通讯有限公司上海二所	1	12	1.0	1.0