管理工程学报
管理工程學報
관리공정학보
JOURNAL OF INDUSTRIAL ENGINEERING AND ENGINEERING MANAGEMENT
2014年
2期
45-54
,共10页
能力约束车辆路径问题%贪婪算法%K-d树%Held Karp模型
能力約束車輛路徑問題%貪婪算法%K-d樹%Held Karp模型
능력약속차량로경문제%탐람산법%K-d수%Held Karp모형
Capacitated vehicle routing problem%Greedy heuristic%K-d tree%Held Karp model
为求解大规模具有能力约束的车辆路径问题(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.
위구해대규모구유능력약속적차량로경문제(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.
