作者：饶卫振 金淳能力约束车辆路径问题贪婪算法heldkarp模型
摘要：为求解大规模具有能力约束的车辆路径问题（Capacitated Vehicle Routing Problem,CVRP）,提出了一种快速改进贪婪算法CVRP-IMGR.基于贪婪算法思想设计了求解CVRP问题的贪婪算法CVRP-GR,在此基础上进一步采用K-d tree法和Held Karp模型改进了CVRP-GR的求解速度和求解质量,从而得到CVRP-IMGR.CVRP-IMGR的复杂度可以达到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.
注：因版权方要求，不能公开全文，如需全文，请咨询杂志社
