研究算法大规模动态车辆路径理由优化策略

论文导读：
摘要：随着因特网络、电子技术和信息技术的进展,电子商务(Electronic Commerce, EC)、全球定位体系(Global Positioning System, GPS)、智能交通体系(Intelpgence Transport System, ITS)和全球移动通讯体系(Global System of Mobile communication, G)得到了越来越广泛的运用。当前,通过借助这些技术工具,在物流配送的历程中,物流企业能够便捷的获取到在线顾客、交通情况、车队情况等实时配送信息。由于事先的配送案例在新信息出现后可能变的次优甚至不可行,所从如何根据实时动态信息不断的合理调整车辆配送路线,已成为当代物流配送企业提高竞争力的关键因素。另外,如今顾客需求特点呈少批量多批次的进展走势,并且随着物流配送企业间的合作逐渐加强,配送中的顾客数量规模也越来越大。由此,在这两方面的背景下,大规模动态车辆路径不足随之产生。求解大规模动态车辆路径不足要求算法能够不断的合并实时信息,快速的求解得到新的车辆配送行驶路径计划,这要求算法的求解速度非常快。然而当前算法大多是为求解静态车辆路径不足设计,由此导致当前算法的特征是求解质量非常精确,但求解速度不够理想,所从,直接采取当前算法难于有效的求解大规模动态车辆路径不足。本探讨针对大规模动态车辆路径不足特点,提出了相应的优化办法。首先将大规模动态车辆路径不足转化为一系列的经典静态车辆路径不足；然后提出一个速度非常快且能确保求解质量较为满意的改善贪婪算法,用于在出现实时信息后快速的求解得到初始满意案例；最后设计了混合大邻域算法,用于继续优化改善贪婪算法的求解案例,直到下一条实时信息出现。具体探讨工作如下：(1)大规模动态车辆路径不足分析及求解思路探讨。首先界定了本论文探讨的大规模动态车辆路径不足所属的类型,并通过分析大规模动态车辆路径不足发现,在配送历程中出现新顾客、老顾客取消订单、交通中断和配送车辆抛锚等不同类型动态事件后,重新决策生成新的配送案例,等价于一个静态的多车型开放式车辆路径不足；然后,从正在执行配送任务车辆位置作为虚拟顾客的模式,将多车型开放式车辆路径不足转化为经典的静态车辆路径不足,由此求解大规模动态车辆路径不足,等价于求解一系列经典静态车辆路径不足；最后,基于经典车辆路径不足模型,提出了大规模动态车辆路径不足的模型极为求解思路。(2)求解车辆路径不足的改善贪婪算法探讨。首先,基于贪婪算法的思想,提出求解车辆路径不足的贪婪算法规则,通过分析和求解算例发现,该算法求解规则简洁但求解质量和求解速度均不够理想；然后,分别基于Held Karp模型和K-D Tree区域分割法提出了改善贪婪算法的求解质量和速度两个对策,原始贪婪算法结合提出的两个对策以而得到改善贪婪算法;最后,分析改善贪婪算法的复杂度发现仅为O(nlogn),并且采取改善贪婪算法求解了当前世界上最大的24个车辆路径不足标准算例,其平均求解质量在10%之内。(3)基于复杂网络论述的混合大邻域算法设计。首先提出了采取复杂网络分析算法解空间结构的办法,并分析了常用的几种k-opt算法的解空间结构发现,优秀算法的解空间结构类似于小世界网络；然后,从该探讨成果为论述依据,设计了一个混合大邻域算法,使其算法解空间的结构更类似于小世界网络,以而具有更好的算法性能,并且设计了执行该算法的数据结构从进一步提升其执行速度减少内存需求；最后,采取改善贪婪算法与混合大邻域算法联合利用的模式求解了众多算例,并与当前经典算法进行了对比发现这种求解模式的综合性能非常具有竞争力。本优化办法的主要贡献是,由于提出的改善贪婪算法的速度非常快速,能够在每次出现新的配送信息后以全局的角度重新优化得到最新的执行案例,并且使用提出的混合大邻域算法可从不断继续优化当前的执行案例。相对于目前通过局部调整当前案例处理新信息从减少当前配送计划变动程度的模式,本优化办法为求解大规模动态车辆路径不足提供了一种新的办法和求解思路。关键词：动态车辆路径不足论文改善贪婪算法论文混合大邻域算法论文复杂网络论文算法性能评价论文
本论文由www.7ctime.com,需要可从关系人员哦。论文导读：1285.4算例求解分析128-1375.4.196个动态车辆路径不足算例求解128-1315.4.2模拟实时配送数据的算例设计与求解131-1375.5本办法的其他运用137-1385.6本章小结138-1396总结与展望139-1426.1论文的主要创新性成果139-1406.2展望140-142参考文献142-159附录AAppMVODM估计MVODM准确性159-163附录B作者与DidS.Johnso
摘要4-6
Abstract6-11
1 绪论11-31

1.1 不足的提出与探讨的作用11-12

1.1 不足的提出11-12

1.2 探讨作用12

1.2 国内外相关探讨综述12-27

1.2.1 车辆路径不足描述及分类12-15

1.2.2 求解静态车辆路径不足的算法探讨近况15-21

1.2.3 求解动态车辆路径不足的算法探讨近况21-25

1.2.4 复杂网络运用探讨近况25

1.2.5 国内外相关探讨小节25-27

1.3 本论文的探讨内容与篇章结构27-31

1.3.1 探讨内容27

1.3.2 技术路线图27-28

1.3.3 篇章结构28-31

2 大规模动态不足分析及求解思路31-49

2.1 探讨的不足类型31-32

2.2 不足的定义32-35

2.3 不足分析与转化35-41

2.4 DC模型41-43

2.5 大规模D-DC模型43-46

2.6 大规模D-DC求解思路46-48

2.7 本章小节48-49

3 求解DC改善贪婪算法49-83

3.1 求解DC贪婪算法49-52

3.

1.1 贪婪算法规则49-50

3.

1.2 贪婪算法复杂度分析50

3.

1.3 算法性能的评估指标50-51

3.

1.4 贪婪算法的性能评估51-52

3.2 基于Held-Karp模型的改善质量对策52-68
3.

2.1 Held Karp模型52-53

3.

2.2 Held Karp模型在DC中的有效性53-56

3.

2.3 贪婪算法的求解质量与距离矩阵方差联系56-57

3.

2.4 距离矩阵方差最小化办法57-63

3.

2.5 距离矩阵方差最小化近似计算办法63-65

3.

2.6 距离矩阵方差最小化效果数据分析65-67

3.

2.7 DC-GR结合距离矩阵方差最小化办法性能67-68

3.3 基于K-D Tree办法的提速对策68-73

3.1 K-D Tree办法68-71

3.2 K-D Tree在DC-GR中的运用71-73

3.4 改善贪婪算法的步骤73-74

3.5 改善贪婪算法的复杂度分析74

3.6 算例求解分析74-82

3.6.1 求解说明75

3.6.2 求解结果75-79

3.6.3 DC-IMGR参数设定79-80

3.6.4 DC-IMGR性能评估80-82

3.7 本章小结82-83

4 求解DC混合大邻域算法83-120

4.1 主要元启发式算法简述83-90

4.

1.1 主要元启发式算法求解步骤83-86

4.

1.2 主要元启发式算法特征总结86-87

4.

1.3 元启发式算法中主要操作规则87-90

4.2 基于复杂网络的k-opt算法解空间表示90-93
4.

2.1 相关符号表示90

4.

2.2 复杂网络论述分析解邻域空间的可行性90-92

4.

2.3 复杂网络论述表示解空间的办法92-93

4.3 基于复杂网络论述的k-opt算法解空间分析办法93-109
4.

3.1 可行解对应节点标号计算办法93-95

4.

3.2 k-opt算法的邻域解空间分析95-100

4.

3.3 复杂网络的基本结构指标100-102

4.

3.4 实例分析102-109

4.4 混合大邻域算法109-113

4.1 混合大邻域算法规则设计109-112

4.2 混合大邻域算法复杂度分析112-113

4.5 混合大邻域算法执行的数据结构对策113-117

4.5.1 减少内存需求对策113

4.5.2 可行解存储模式对策113-117

4.6 算例求解分析117-119

4.7 本章小结119-120

5 运用体系及标准算例设计120-139

5.1 运用环境描述120-123

5.2 实时物流配送调度体系123-125

5.3 动态车辆路径不足算例设计125-128

5.4 算例求解分析128-137

5.

4.1 96个动态车辆路径不足算例求解128-131

5.

4.2 模拟实时配送数据的算例设计与求解131-137

5.5 本办法的其他运用137-138

5.6 本章小结138-139

6 总结与展望139-142

6.1 论文的主要创新性成果139-140

6.2 展望140-142

参考文献142-159
附录A AppMVODM估计MVODM准确性159-163
附录B 作者与Did S.Johnson教授的交流论文导读：资料163-164攻读博士学位期间发表学术论文状况164-165攻读博士学位期间参与项目状况165-166致谢166-167作者介绍167-168上一页123
资料163-164
攻读博士学位期间发表学术论文状况164-165
攻读博士学位期间参与项目状况165-166
致谢166-167
作者介绍167-168