原文传递
遗传算法在带时间窗的车辆路径问题中的应用
| 论文题名： | 遗传算法在带时间窗的车辆路径问题中的应用 |
| 关键词： | 车辆路径问题;遗传算法;时间窗;交叉算子;惩罚函数 |
| 摘要： | 经济的发展使得物流成为了一门重要的产业,车辆路径问题(VRP, Vehicle Routing Problem)是物流中最重要的一部分,引起了学者与企业管理者的高度重视。由于消费者对配送时间的要求越加严格,因而对带时间窗的车辆路径问题(VRPTW, Vehicle Routing Problem with Time Windows)的研究具有重要的现实意义。 本文针对基本遗传算法的不足作了一系列的改进,并用C语言进行了编程实现。用程序对具体的带时间窗的车辆路径问题实例进行求解,证实了本文改进算法的有效性。 本文的主要工作包括: (1)建立了有惩罚函数的VRPTW的数学模型。设置惩罚函数,对车辆提前到达或延后到达加以惩罚,根据客户不同的服务要求,设置了两类惩罚函数,一类是线性函数,一类是二次函数,其中二次函数的模型更符合实际,因为当配送车辆提前或延后送达的时间较小时对顾客的满意度不会有太大的影响,而当提前或延后的时间较大时则会严重降低客户的满意度。 (2)提出了一种新的交叉算子。新交叉算子将已寻优的部分路径段(优良基因段)作为一个整体,交叉后不会破坏优良的基因段。此外,比较了交叉前后的染色体适应度的变化,若交叉后的染色体更差则保留交叉前的染色体。通过与其他交叉算子如顺序交叉、部分匹配交叉(PMX)算子的求解效率作比较,证实了该新交叉算子的科学合理性。 (3)对遗传算法的选择操作进行了改进,引出了一种优化的轮盘赌选择方法,并保留了每次迭代时的最优个体。采用这种改进后的选择算子提高了适应度较高个体被选择的概率,从而加速算法的收敛。 (4)将改进的遗传算法用C语言编程实现,用此程序去求解车辆路径问题。与基本遗传算法的运算结果进行比较,本文的算法具有较好的效果。在所需配送车辆数量小的同时,能更好的满足客户对配送时间的要求,从而降低了运输成本。 |
| 作者： | 詹孝龙 |
| 专业： | 计算机技术 |
| 导师： | 胡中栋 |
| 授予学位： | 硕士 |
| 授予学位单位： | 江西理工大学 |
| 学位年度： | 2014 |
| 正文语种： | 中文 |
检索历史
应用推荐
