求解大规模VCVRP问题的快速动态规划算法

发布时间：2017-08-05 13:25

  本文关键词：求解大规模VCVRP问题的快速动态规划算法

  更多相关文章： 车辆路径问题 VCVRP问题 动态规划 组合优化 快速算法 启发式算法

【摘要】：车辆路径问题是一类典型的组合优化问题,大部分研究都只考虑车辆能力固定的情形,实际中受货物形状特性及客户需求变化,车辆的能力是受限变化的,针对能力受限变化的车辆路径问题(varied capacitated vehicle routing problem,VCVRP),基于动态规划理论,提出一种求解大规模VCVRP问题的快速动态规划算法.该算法以传统的最佳适应降序算法(best fit decreasing,BFD)和最小生成树(minimum spanning tree,MST)算法为基础,引入K步回溯,短途优先原则,实现了VCVRP中的货物装箱问题和路由选择问题的近似解耦.同时给出了该算法的优化目标车辆旅程的理论上界,短途优先原则的局部最小的理论分析与证明.最后以乘用车物流运输案例为背景,给出了计算实例,并从算法参数与算例规模多个角度进行求解质量与算法性能的分析.
【作者单位】： 国防科学技术大学信息系统与管理学院国防采办与体系工程管理教研室;国防科学技术大学信息系统与管理学院C4ISR国防科技重点实验室;
【关键词】： 车辆路径问题 VCVRP问题 动态规划 组合优化 快速算法 启发式算法
【基金】：国家自然科学基金(71201168)~~
【分类号】：O221.3
【正文快照】： (1.国防科学技术大学信息系统与管理学院国防采办与体系工程管理教研室,长沙410073;2.国防科学技术大学信息系统与管理学院C4ISR国防科技重点实验室,长沙410073)Fast dynamic programming algorithm for the large scale VCVRPproblemZHANG Pengle1,XIAO Kaiming2,FU Chunxiao

【相似文献】

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

1 李菲;肖洪祥;;基于神经动态规划算法的最优路径选择[J];桂林工学院学报;2009年01期

2 罗宗俊;;高维0-1瓶颈问题的动态规划算法[J];数值计算与计算机应用;2013年01期

3 周静;;运用动态规划算法解决最大价值路线图问题[J];硅谷;2013年15期

4 李乐园;林诒勋;;电力网调度时间表问题的动态规划算法[J];河南科学;1988年02期

5 徐绪松;工序问题的动态规划算法[J];武汉大学学报(自然科学版);1994年05期

6 赵钰;徐涛;陈红军;;炮兵营火力分配的二阶动态规划算法[J];四川兵工学报;2009年09期

7 陈捷;;基于动态规划算法的最值问题分析[J];电脑与信息技术;2013年06期

8 廖慧芬;邵小兵;;动态规划算法的原理及应用[J];中国科技信息;2005年21期

9 刘莹;;改进的动态规划算法在最优航线选择中的应用[J];邵阳学院学报(自然科学版);2007年01期

10 王雪瑞;秦勤;李建;;Possible Winner问题参数算法研究及核心化[J];湘潭大学自然科学学报;2012年04期

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

1 顾文彬;高梅国;;基于改进动态规划算法的雷达微弱目标检测[A];中国航空学会信号与信息处理专业全国第八届学术会议论文集[C];2004年

2 唐玲娜;唐雪飞;叶昌伟;;动态规划算法正序实现及其改进[A];2008'中国信息技术与应用学术论坛论文集（二）[C];2008年

中国重要报纸全文数据库 前1条

1 PALADIN;动态规划算法设计[N];电脑报;2003年

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

1 许虎;基于动态规划算法的网瘾戒除辅助活动规划系统的研究与实现[D];东北大学;2013年

2 刘昭;基于DP算法插电式柴电混合动力汽车控制策略研究[D];重庆交通大学;2015年

3 李强;动态规划算法时间效率优化策略研究[D];中南民族大学;2015年

4 丁伟军;结合近似动态规划算法的串行生产系统风险管理研究[D];清华大学;2011年

5 张玉斌;迭代动态规划算法及并行化研究[D];中国石油大学;2008年

6 吴涛;动态规划算法应用及其在时间效率上的优化[D];南京理工大学;2008年

7 李前兴;工业过程迭代动态规划算法研究[D];浙江大学;2011年

8 农健恒;同尺寸物品装箱的动态规划算法[D];广西大学;2014年

9 杜君;MPP环境中面向动态规划算法的混合并行系统的研究[D];天津大学;2014年

10 杨再新;高频雷达运动目标多帧检测技术研究[D];哈尔滨工业大学;2014年

，

本文编号：625134