求解大规模CVRP问题的快速贪婪算法  

An Efficient Greedy Heuristic for Solving Large-scale Capacitated Vehicle Routing Problem

作　　者：饶卫振[1] 金淳[1] 

机构地区：[1]大连理工大学系统工程研究所,辽宁大连116024

出　　处：《管理工程学报》2014年第2期45-54,共10页Journal of Industrial Engineering and Engineering Management

基　　金：国家自然科学基金重大课题资助项目(70890080;70890083);教育部博士点基金资助项目(20100041110024)

摘　　要：为求解大规模具有能力约束的车辆路径问题(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。The Vehicle Routing Problem （VRP） was introduced by Dantzig and Ramser in 1959.VRP calls for the determination of the optimal set of routes to be performed by a fleet of vehicles to serve a given set of customers.VRP is one of the most studied combinatorial optimization problems.Hundreds of heuristics have been developed.However,all existing heuristics have complexity larger than O （n2）,which can lead to the incapability of solving very large-scale VRP in short time.Therefore,we propose an improved greedy heuristic with complexity O （nlogn） for solving large-scale Capacitated Vehicle Routing Problem （CVRP）,which is a classic version of VRP.This paper can be divided into five sections.In Sections 1,we define CVRP and present a new model for CVRP.Section 2 introduces Greedy heuristic （GR）,K-d tree and Held Karp model.GR is a classic construction heuristic for solving combinational optimization problems,but it hasn＇t been applied to solving CVRP.A greedy heuristic for solving CVRP （CVRP-GR） based on the traditional GR is proposed in Section 3.However,CVRP-GR has complexity O （n2 logn） and is not efficient enough.In addition,CVRP-GR cannot generate solutions with good quality because it adds very long edges into solution.Two enhancements for improving the speed and solution quality of CVRP-GR are presented by using K-d tree and Held Karp model,respectively.Consequently,CVRP-GR is combined with two enhancements results in an improved CVRP-GR （CVRP-IMGR）.We have proved that CVRP-IMGR has only complexity O （nlogn）,which is very efficient,and can solve large-scale CVRP instances in short time.Furthermore,the detail steps of CVRP-IMGR are presented in the last part of Section 3.In order to evaluate the performance of CVRP-IMGR,we solve 24 largest CVRP instances by using CVRP-GR,CVRP-IMGR and Savings that is the best-known heuristic for solving CVRP,in Section 4 of this paper.The computational results show that CVRP-IMGR is much more efficient than CVRP-GR and Savings,because the later

关 键 词：能力约束车辆路径问题 贪婪算法 K-D树 HELD Karp模型 

分 类 号：F502[经济管理—产业经济]