基于改进贪心算法动态车辆路径问题分析,这是一篇与贪心论文范文相关的免费优秀学术论文范文资料,为你的论文写作提供参考。
贪心论文参考文献：
摘 要：针对移动电子商务下的动态车辆路径问题,在贪心算法的基础上,结合K-d tree方法和Held-Karp模型对贪心算法进行改进,对移动电子商务环境下的动态车辆路径问题进行案例分析,并验证该算法的有效性.
关键词：移动电子商务；动态车辆路径问题；改进贪心算法；案例分析
中图分类号：O22 文献识别码：A 文章编号：1001-828X（2017）001-000-01
一、引言
移动电子商务环境下取货车辆调度问题的实质就是动态车辆路径问题（DVRP）.目前对于DVRP问题的解决方法主要包括两类,一是采用判断准则将新出现的顾客添加到已经制定的路线中.二是采用优化算法从全局最优角度出发.但是目前上述算法不能实现全局系统最优,且实时性不强.
二、理论概述
1.贪心算法
贪心算法求解DVRP的过程是将任意两节点构成的边按边长升序排列有（Cn2等于n（n-1）/2条边）,从最短边开始依次添加合法边至当前路径中,直到添加完所有合法边,形成每条路径的两端点都和配送中心节点O连接形成Hamilton回路为止
2. K-d tree方法
K-d tree方法即k维空间二叉搜寻树,是一种分割k（本文k等于2）维数据空间的数据结构,主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）.其原理是将系统中n个点所在k维空间进行分割,将分割后的区域视为二叉树的节点,将整个区域用二叉树表示.
3.Held-Karp模型
Held和Karp在1970年提出了经典的Held-Karp模型,用于求解旅行商问题的最优解下界.该模型的原理是使用一个实数向量η等于（η1,η2,等ηn）改造距离矩阵的模型.
4.改進贪心算法的步骤
对改进贪心算法的整个过程分步骤说明：（1）读取DVRP问题和第i个新出现的顾客；（2）设置t和α两个参数；（3）根据顾客和配送中心的坐标信息、t建立K-d tree；（4）根据坐标信息和α计算向量η；（5）根据K-d tree和Held-Karp 模型改造后距离矩阵,计算每个节点i对应的最邻近节点j,并将边（i,j）和对应长度rij+ηi+ηj存至Heap,且按边长升序排列；（6）提取Heap中的第一条最短边,假设为（x,y）；（7）判断添加边（x,y）至当前路径是否满足判断合法边的4条规则,满足执行（9）否则执行（8）；（8）更新Heap数组,保证每个可连接节点和最邻近节点形成的边均在Heap中,然后执行（6）；（9）添加边（x,y）至当前路径中；（10）确定是否还有合法边存在,如果有则执行（8）；否则将形成的m条路径的端点分别和配送中心连接得到最终解,结束程序.
三、算例说明和求解
本文以Li等人在2005年提出了12个n为560～1200的算例为数据基础,算例名称最后的数量表示顾客数量,动态程度φ分别为0.25、0.50、0.75、1.00.求解质量和求解时间如表1.
改进贪心算法在求解质量方面优于已知最优解,求解时间较短.求解最大的算例DVRP-1200,φ等于1.00时,顾客出现的平均时间间隔为24.00s,计算耗时仅为10.35s,能满足对于算法时间的要求.
四、结语
本文结合K-d tree法和Held-Karp模型提高求解质量策略,提出了移动电子商务环境下动态车辆路径问题的改进贪心算法,对12个标准算例求解验证了该模型和算法能在合理的时间内求解DVRP问题.
参考文献：
[1]易云飞,董文永,林晓东.求解带软时间窗车辆路径问题的改进伊藤算法及其收敛性分析[J].电子学报,2015,04：658-664.
[2]Li FY, Golden B, Wasil Edward. Very large-scale vehicle routing：new test problems, algorithms, and results [J]. Computers and Operations Research,2005, 32 （5）：1165-1179.
作者简介：李珊珊（1991-）,女,汉族,山东德州人,山东科技大学矿业和安全工程学院硕士研究生,系统理论专业.
结论：关于对不知道怎么写贪心论文范文课题研究的大学硕士、相关本科毕业论文告诫人不要贪心的句子论文开题报告范文和文献综述及职称论文的作为参考文献资料下载。
基于改进遗传算法农产品配送路径优化
[摘要]以第三方物流企业为视角，在保证配送质量最高的情况下，将配送成本最低作为优化目标，构建多目标农产品配送路径优化模型。针对此类NP问题，结合。
多车场一体化集货送货车辆路径问题混合遗传算法
摘 要：为满足电子商务客户多样化和个性化的需求，建立多车场一体化装卸混合车辆调度模型。针对模型的特点，采用混合遗传算法求解。即利用模拟退火算法。
分车收发车辆路径问题三个式算法之比较
摘要：车辆路径问题已经出现了很多的变种．在这些扩展的VRP问题当中，分车收发车辆路径问题就是其中之一本文针对这一问题在已有的模型上加以改进，并且。
需求可分车辆路径问题模型和算法
摘要：需求可分的车辆路径问题（sDVRP）无论是从运输距离还是派车数量上，都可进一步优化传统的车辆路径问题。为了降低sDVRP的求解难度，本文在。