遗传算法在带时间窗的车辆路径问题中的应用

摘要

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

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪 论

1.1 研究背景及意义

1.2 本文主要内容与结构

第二章 车辆路径问题概述

2.1 车辆路径问题描述

2.2 车辆路径问题的研究现状

第三章 遗传算法概述

3.1 遗传算法的理论基础

3.2 遗传算法的具体流程

3.3 遗传算法的特性

3.4 遗传算法存在的问题

第四章 遗传算法求解带软时间窗的车辆路径问题

4.1 带时间窗的车辆路径问题的概念

4.2 遗传算法求解带软时间窗的车辆路径问题的步骤

第五章 算例分析及实现

5.1 算例说明

5.2 实验分析

第六章 总结与展望

6.1 工作总结

6.2 研究展望

参考文献