随机需求车辆路径问题的混合遗传算法研究

摘要

随机需求车辆路径问题(Vehicle Routing Problems with StochasticDemands，VRPSD)是车辆路径问题(Vehicle Routing Problem，VRP)的一个重要分支，由于其具有很强的现实意义，所以成为物流管理领域研究的热点。如何在顾客需求随机的情况下，合理安排车辆行驶路径，以实现运输时间最短、成本最低等目标，这是多年来随机需求车辆路径问题研究的难点。本文通过引入决策者风险偏好改进了VRPSD模型并设计了混合遗传算法求解VRPSD，最后通过随机需求车辆路径问题算例进行了验证和对比，证明了本文算法的有效性并确定了使随机需求车辆路径问题目标值最优的决策者风险偏好值。本文的具体研究工作如下:
　　(1)随机需求车辆路径问题的构建。在分析了目前VRPSD模型的基础上，本文在客户需求随机的情况下考虑了决策者风险偏好对VRPSD目标值的影响。本文采用机会约束策略建立了VRPSD模型，将决策者风险偏好引入到模型中，决策者风险偏好在模型寻优的过程中起到重要作用。
　　（2基于混合遗传算法求解随机需求车辆路径问题研究。设计了混合遗传算法求解VRPSD，先用“最近邻域和插入混合”算法结合随机生成方法产生随机需求车辆路径问题的初始种群，提高了初始种群的质量，再利用遗传算法进行全局搜索，求得随机需求车辆路径问题的解。
　　(3)混合遗传算法求解随机需求车辆路径问题的算例验证。通过C语言对本文提出的混合遗传算法算法编程，利用本文提出混合遗传算法求解随机需求车辆路径问题算例，确定了决策者的最佳风险偏好值，并通过对比实验证明了本文混合遗传算法求解VRPSD的有效性。
　　本文研究了决策者风险偏好对随VRPSD求解的影响并确定了使优化目标最小的决策者风险偏好值，设计了高效的混合遗传算法对VRPSD进行求解，为求解VRPSD和发展遗传混合算法提供了有用的价值。其研究成果不仅对于车辆路径问题的实际应用具有指导意义，而且决策者风险偏好值的研究还能为物流配送调度系统提供决策支持。

目录

声明

摘要

1 绪论

1．1 选题背景及研究意义

1．1．1 选题背景

1．1．2 研究意义

1．2 国内外相关研究综述

1．2．1 随机需求车辆路径问题国内外研究进展

1．2．2 混合算法求解车辆路径问题的研究进展

1．2．3 国内外研究综述小结

1．3 本文研究的思路与主要内容

2 随机需求车辆路径问题模型的分析及构建

2．1 随机需求车辆路径问题模型分析

2．1．1 随机需求车辆路径问题的描述及特征

2．1．2 随机需求车辆路径问题预回路确定策略

2．1．3 路径期望长度的计算

2．2 随机需求车辆路径问题模型的构建

2．2．1 车辆路径问题的描述及模型

2．2．2 随机车辆路径问题的界定

2．2．3 符号说明

2．2．4 随机需求车辆路径问题模型的构建

2．3 本章小结

3 求解随机需求车辆路径问题的混合遗传算法研究

3．1 混合遗传算法介绍

3．1．1 混合遗传算法基本思想

3．1．2 混合遗传算法中的基本算法介绍

3．1．3 混合遗传算法的步骤

3．2 混合遗传算法的优势

3．3 混合遗传算法的设计

3．4 本章小结

4 算例验证及分析

4．1 算例介绍

4．2 确定主观偏好值Cr*

4．3 混合遗传算法求解随机需求车辆路径问题的数值实验

4．4 本章小结

5 总结与展望

5．1 主要创新点

5．2 进一步研究方向

参考文献

附录

攻读硕士学位期间发表学术论文情况

致谢