| 针对CVRP的2-OPT算法的时间复杂度均值分析 |
| |
| 引用本文： | 祝崇隽,刘民,吴澄,吴晓冰.针对CVRP的2-OPT算法的时间复杂度均值分析[J].清华大学学报(自然科学版),2002,42(9):1218-1221. |
| |
| 作者姓名： | 祝崇隽 刘民 吴澄 吴晓冰 |
| |
| 作者单位： | 1. 清华大学,自动化系,北京,100084
2. 中兴通讯有限公司上海二所,上海,200233 |
| |
| 基金项目： | 国家自然科学基金资助项目 (60 0 0 40 10 )，国家“八六三”高科技项目 |
| |
| 摘 要： | 分析了需求不可分割带能力约束的车辆路径问题(CVRP)的 2 - OPT算法计算时间的平均复杂度。利用需求分布独立于客户的空间分布的特点 ,将车辆路径问题 (VRP)转化为多旅行商 (MTSP)问题 ,并通过分析 MTSP进行 2 -OPT操作的可行性条件 ,建立起该算法运行所需的迭代次数的分布函数 ,进而求得平均运算时间复杂度的上界。该文为有效评价针对 VRP的 2 - OPT算法 ,提供了理论依据 ,并为VRP领域的启发式算法的复杂度分析 ,提供了一种新思路。
|
| 关 键 词： | 复杂度 迭代次数 分布函数 上界 CVRP 2-OPT |
| 文章编号： | 1000-0054(2002)09-1218-04 |
| 修稿时间： | 2001年2月28日 |
Complexity analysis for run time of 2-OPT algorithm for CVRP |
| |
| ZHU Chongjun,LIU Min,WU Cheng,WU Xiaobing.Complexity analysis for run time of 2-OPT algorithm for CVRP[J].Journal of Tsinghua University(Science and Technology),2002,42(9):1218-1221. |
| |
| Authors: | ZHU Chongjun LIU Min WU Cheng WU Xiaobing |
| |
| Institution: | ZHU Chongjun~1,LIU Min~1,WU Cheng~1,WU Xiaobing~2 |
| |
| Abstract: | The complexity of the 2 -OPT algorithm for the capacitated vehicle routing problem (CVRP) was analyzed in this paper. Since the demand distribution is independent of location distribution, the vehicle routing problem (VRP) was transformed into a Multiple Traveling Salesman Problem (MTSP) to avoid demand constraints. The feasibility conditions for the use of 2 -OPT with MTSP were used to determine the distribution of the iteration numbers and the upper bound of the expected algorithm run time. The algorithm provides a powerful method to evaluate the 2 -OPT for the CVRP and a new way to analyze heuristic algorithms for VRP. |
| |
| Keywords: | complexity iteration number distribution function upper bound capacitated vehicle routing problem (CVRP) 2 -OPT |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
