CAJ | 학술논문

为求解大规模具有能力约束的车辆路径问题（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.
위구해대규모구유능력약속적차량로경문제（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.
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 two heuristics have complexity O （n2logn）.For all 24 instances,CVRP-IMGR and Savings have better solutions than CVRP-GR.Moreover,CVRP-IMGR generates better solutions than Savings in 18 out 24 instances.The relation between parameters in CVRP-IMGR and performance of CVRP-IMGR is also discussed in Section 4.In the last section,we draw the conclusion that （1） two enhancements based on K-d tree and Held Karp model are very efficient and effective; （2） CVRP-GR involving two enhancements can result in CVRP-IMGR that has only complexity O （nlogn） ; and （3）CVRP-IMGR is able to generate better solutions than classic construction heuristic savings.Future researches may want to apply CVRP-IMGR to solving VRP that requires short response time,e.g.dynamical VRP （DVRP）.