求解大规模CVRP问题的快速贪婪算法 |
| |
引用本文: | 饶卫振,金,淳.求解大规模CVRP问题的快速贪婪算法[J].管理工程学报,2014(2):45-54. |
| |
作者姓名: | 饶卫振 金 淳 |
| |
摘 要: | 为求解大规模具有能力约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP),提出了一种快速改进贪婪算法CVRP-IMGR。基于贪婪算法思想设计了求解CVRP问题的贪婪算法CVRP-GR,在此基础上进一步采用K-d tree法和Held Karp模型改进了CVRP-GR的求解速度和求解质量,从而得到CVRP-IMGR。CVRPIMGR的复杂度可以达到O(nlogn),能够快速求解大规模(顾客数量大于500)CVRP问题。为验证CVRP-IMGR的有效性,分别采用CVRP-GR、CVRP-IMGR和经典构建型算法Savings求解了当前24个最大规模的CVRP算例,结果表明:CVRP-IMGR的求解速度远快于复杂度为O(n2logn)的CVRP-GR和Savings;CVRP-IMGR对所有算例的求解质量优于CVRP-GR,并且对18个算例的求解质量优于Savings。
|
关 键 词: | 能力约束车辆路径问题 贪婪算法 K-d树 Held Karp模型 |
本文献已被 CNKI 等数据库收录! |
|