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

发布时间：2017-11-07 15:32

  本文关键词：求解大规模CVRP问题的快速贪婪算法

  更多相关文章： 能力约束车辆路径问题 贪婪算法 K-d树 Held Karp模型

【摘要】：为求解大规模具有能力约束的车辆路径问题(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。
【作者单位】： 大连理工大学系统工程研究所;
【基金】：国家自然科学基金重大课题资助项目(70890080,70890083) 教育部博士点基金资助项目(20100041110024)
【分类号】：C931.6
【正文快照】： 0引言车辆路径问题(Vehicle Routing Problem,VRP)是典型的组合优化难题[1],该问题根据所考虑实际因素的不同可分为不同类型,其中考虑车辆能力约束的车辆路径问题(Capacitated Vehicle Routing Problem,CVRP)是最为常见的形式之一[2,3]。由于CVRP属于NP-Hard问题,所以目前启发

【参考文献】

中国期刊全文数据库 前5条

1 张建勇;李军;;具有模糊旅行时间的VRP的一种混合遗传算法[J];管理工程学报;2006年04期

2 吴斌;钱存华;董敏;谢庆红;;具有同时集送货需求车辆路径问题的混沌量子进化算法研究[J];控制与决策;2010年03期

3 张军;唐加福;潘震东;孔媛;;分散搜索算法求解带货物权重的车辆路径问题[J];系统工程学报;2010年01期

4 赵燕伟;彭典军;张景玲;吴斌;;有能力约束车辆路径问题的量子进化算法[J];系统工程理论与实践;2009年02期

5 张燕;周支立;翟斌;;集货送货一体化的物流配送车辆路线问题的标号算法[J];运筹与管理;2007年03期

【共引文献】

中国期刊全文数据库 前10条

1 汪安静;龚本刚;;基于C-W算法的汽车零部件循环取货车辆路径优化研究[J];安徽工程科技学院学报(自然科学版);2010年02期

2 李明;;蚁群算法在土地利用结构优化模型中的应用[J];安徽农业科学;2011年14期

3 杨瑞臣;郝海燕;;改进的蚁群算法在物流配送路径问题求解中的应用[J];承德石油高等专科学校学报;2009年02期

4 王翊;范兴刚;王万良;姚晓敏;;基于混合量子进化算法的高效节能无线传感器网络路由算法[J];传感技术学报;2011年02期

5 石丽红;范厚明;翟志伟;王桂琳;;城市医疗废弃物回收处理流程及车行路径优化[J];大连海事大学学报;2010年03期

6 石兆旭;魏连雨;;有容量限制路径选择优化问题的混合蚂蚁算法[J];道路交通与安全;2005年06期

7 杨文超;胡祥培;王征;;顾客时间窗变化的物流配送问题干扰管理方法研究[J];大连理工大学学报;2012年02期

8 陈美军;张志胜;史金飞;;基于自适应多态蚁群算法的多约束车辆路径问题[J];东南大学学报(自然科学版);2008年01期

9 李委委;;一种解决VRP问题的混合蚁群算法研究[J];电脑知识与技术;2012年08期

10 孙改平;郭海文;;信息素动态更新的改进蚁群算法[J];福建电脑;2010年01期

中国重要会议论文全文数据库 前8条

1 黄辉;屠乃威;马天牧;郑秉霖;柴天佑;;基于VRP的模铸组炉问题模型及其蚁群算法[A];2009中国控制与决策会议论文集（3）[C];2009年

2 蒋忠中;盛莹;汪定伟;袁媛;;物流配送路径优化的双目标模糊规划模型与算法研究[A];中国企业运筹学学术交流大会论文集[C];2008年

3 黄红星;钟一文;黄习培;;挖掘最大频繁项集的二进制蚁群优化算法[A];第四届中国智能计算大会论文集[C];2010年

4 师凯;蔡延光;邹谷山;王涛;;运输调度问题的蚁群算法研究[A];04'中国企业自动化和信息化建设论坛暨中南六省区自动化学会学术年会专辑[C];2004年

5 陆琳;谭清美;;模糊信息动态车辆调度优化问题研究[A];第八届中国管理科学学术年会论文集[C];2006年

6 陈美军;张志胜;史金飞;;MDVRPMC问题的智能多态蚁群算法研究[A];2007第三届中国智能交通年会论文集[C];2007年

7 Chunhua Meng;Hongguo Wang;Zengzhen Shao;Yanhui Ding;;Heuristic Optimization Algorithms for Solving MRMPT[A];2013年中国智能自动化学术会议论文集（第二分册）[C];2013年

8 饶卫振;金淳;蒙秋男;;城区低碳物流配送问题模型及求解策略[A];社会经济发展转型与系统工程——中国系统工程学会第17届学术年会论文集[C];2012年

中国博士学位论文全文数据库 前10条

1 孙丽君;物流配送干扰管理问题的知识表示与建模方法[D];大连理工大学;2011年

2 郑俊丽;船舶分段制造车间的模块空间调度模型及算法[D];上海交通大学;2011年

3 葛显龙;面向云配送模式的车辆调度问题及算法研究[D];重庆大学;2011年

4 王君;不确定因素下车辆路径问题建模及优化方法研究[D];天津大学;2012年

5 石丽红;城市医疗废弃物回收处理模式及其网络研究[D];大连海事大学;2011年

6 丁秋雷;物流配送地址变化的干扰管理模型及其求解方法[D];大连理工大学;2011年

7 张琴;基于混沌理论和蚁群算法的多水源供水系统优化调度研究[D];浙江大学;2011年

8 牛云云;求解计算困难问题的膜计算模型与算法研究[D];华中科技大学;2012年

9 胡小兵;蚁群优化原理、理论及其应用研究[D];重庆大学;2004年

10 戴锡;车辆路线问题的二阶段启发式算法及其在现代物流配送中的应用[D];复旦大学;2004年

中国硕士学位论文全文数据库 前10条

1 邵晓路;蚁群群体智能网络可视化试验平台研制[D];浙江理工大学;2010年

2 吴明明;汽车供应物流循环取货车辆路径问题研究[D];吉林大学;2011年

3 叶创鑫;物流配送的路径优化与行程时间预测[D];暨南大学;2011年

4 田宇;基于系统仿真模拟退火算法的VRPTW研究[D];河北工程大学;2011年

5 李朝辉;连续域蚁群算法的改进研究及在参数估计中的应用[D];中南大学;2011年

6 李小龙;电子表面贴装生产线的集成优化方法[D];华南理工大学;2011年

7 邓生杰;2x2快速矩阵乘法问题的完全求解[D];华南理工大学;2011年

8 李振;基于小生境粒子群算法的同时取货送货车辆路径问题研究[D];山东大学;2011年

9 潘振;基于3PL循环取货的供应商自主管理库存系统研发[D];西南交通大学;2011年

10 朱文婷;基于不确定时间的车辆路径问题研究[D];西南交通大学;2011年

【二级参考文献】

中国期刊全文数据库 前10条

1 李军;有时间窗的车辆路线安排问题的启发式算法[J];系统工程;1996年05期

2 肖健梅,黄有方,李军军,王锡淮;基于离散微粒群优化的物流配送车辆路径问题[J];系统工程;2005年04期

3 张建勇,李军,郭耀煌;模糊需求信息条件下的实时动态车辆调度问题研究[J];管理工程学报;2004年04期

4 张建勇,李军;模糊车辆路径问题的一种混合遗传算法[J];管理工程学报;2005年02期

5 张建勇,李军,郭耀煌;具有模糊预约时间的VRP混合遗传算法[J];管理科学学报;2005年03期

6 潘震东;唐加福;韩毅;;带货物权重的车辆路径问题及遗传算法[J];管理科学学报;2007年03期

7 赵燕伟,吴斌,蒋丽,董红召,王万良;车辆路径问题的双种群遗传算法求解方法[J];计算机集成制造系统-CIMS;2004年03期

8 龙磊;陈秋双;华彦宁;徐亚;;具有同时集送货需求的车辆路径问题的自适应混合遗传算法[J];计算机集成制造系统;2008年03期

9 王宇平;李英华;;求解TSP的量子遗传算法[J];计算机学报;2007年05期

10 陈萍;黄厚宽;董兴业;;求解卸装一体化的车辆路径问题的混合启发式算法[J];计算机学报;2008年04期

【相似文献】

中国硕士学位论文全文数据库 前1条

1 崔海波;基于流程的组织结构设计关键问题研究[D];国防科学技术大学;2007年

，

本文编号：1153028