混合遗传算法在配送车辆调度问题中的应用

摘要

随着我国市场经济的逐步完善,企业之间的竞争日益加剧,竞争手段也不断转换,由最初的质量到目前的价格、渠道、服务向未来的供应链的竞争发展.现代物流理论在市场竞争中的应用使得这一竞争形式成为未来企业关注的焦点.然而在现代化的物流体系中,目前物流配送的薄弱环节正日益暴露出来并亟待解决.如何有效地进行车辆调度,降低企业的运输成本,从而在满足顾客日益多变的需求同时,给企业带来利润,引起了广大企业决策者和研究者的兴趣.遗传算法是一种自适应随机搜索算法,它采用解的种群作为工作单元,模仿生物进化的适者生存原则指导搜索并改进目标.但是由于遗传算法在搜索过程中容易陷入局部最优,以及初始种群对算法的效果有较大的影响,所以用单纯的遗传算法解决车辆调度问题通常不能取得较好的结果.本文基于Sweep算法和Cheapest Insertion算法的启发式算法用于构造遗传算法的初始种群,并构造一种较好的变异算子,从而改善种群的初始化和搜索过程,得到较好的调度方案.本文通过对带有硬时间窗的车辆调度问题进行实例计算,计算结果表明了这种混合遗传算法解决此类问题的有效性.综上所述,这种基于Sweep算法、Cheapest Insertion算法种群初始化和IOPT变异算子的混合遗传算法是解决带有时间窗车辆调度问题的新方法,该算法能够在合理的时间内求得满意解,是解决此类大规模组合优化问题的一个新途径.

目录

文摘

英文文摘

独创性声明及学位论文版权使用授权书

1绪论

1.1课题背景

1.2研究的目的和意义

1.3问题的提出

1.4国内外研究现状

1.5论文的主要工作和框架结构

2遗传算法

2.1遗传算法的基本思想

2.2遗传算法的特点

2.3遗传算法的基本流程

2.4遗传算法与组合优化

3带有时间窗的车辆调度问题

3.1一般车辆调度问题(VRP)的基本概念和分类

3.2带有时间窗的车辆调度问题(VRPTW)

3.3车辆调度问题的求解方法

4遗传算法的种群初始化方法研究

4.1算法的基本思想和原理

4.2基于Sweep和Cheapest Insertion算法的初始化流程

4.3初始化的实例结果

5混合遗传算法在带有时间窗车辆调度问题中的应用研究

5.1混合遗传算法在VRPTW中的应用

5.2配送系统中VRPTW的数学模型

5.3染色体编码与解码操作

5.4选择适应度函数

5.5种群初始化

5.6遗传算子设计

5.7算法流程

6应用实例及结果分析

6.1实验数据

6.2结果分析

7总结与展望

7.1全文总结

7.2有待改进之处

致 谢

参考文献

附录1攻读硕士学位期间发表的论文及参加的课题研究

附录2 R102数据