基于改进遗传算法的带软时间窗车辆路径问题的研究

摘要

中国物流与采购联合会数据显示2014年我国社会物流总成本占GDP的比重约为16.6％，这一数据高于全球平均水平约5个百分点。第三产业统计年鉴的数据显示近20年来运输成本在物流总成本中所占的比重均超过了50％。上述数据表明车辆路径问题是影响我国物流总成本偏高的一个重要因素。在实际的运输过程中，由于客户规模一般较大，很难做到使每一个客户都达到最满意的结果，故软时间窗车辆路径问题(Vehicle Routing Problem with Soft TimeWindow, VRPSTW)更加贴近实际运输情况。另外VRPSTW会充分考虑每一个节点上的客户满意度问题。因此研究VRPSTW无论是在提高顾客满意度方面还是在缩减物流成本方面都在物流运输中起着最为重要的作用。
　　遗传算法(Genetic Algorithm，GA)是求解VRPSTW时应用更广泛、性能表现更为优越的。但是该算法也存在早熟问题、易收敛到局部最优解的问题和求解精度有待进一步提高的问题。为此本文采取了以下措施来解决这些问题:引入最佳种群规模的计算方法;采用随机生成方式来产生初始种群;采用自适应机制来确定交叉概率和变异概率;采取基于排序法的随机竞争选择和最佳保留相结合的选择策略;引入小生境操作技术的交叉算子A;采用局部爬山变异算子。为了使整个算法能更好的解决VRPSTW，本文做了如下工作，首先综合考虑了顾客的满意度、物流公司的费用支出、顾客的特殊要求等因素后，对目标函数进行了权重的设置以及对约束条件进行了罚函数等方面的处理。其次除了对遗传算子的改进外，还对编码解码、种群初始化方法、控制参数的设置以及终止条件的确定等方面进行了适度的调整工作。最后为测算改进算法的有效性，针对同一数据集进行了全方位多角度的对比分析工作，力求使后续分析工作更具有说服力。
　　针对GA求解VRPSTW时所表现出的种种不足，本文做出相应改进调整方案后。对solomon标准库中C101数据集的100个节点进行测试，以验证改进方案的合理性。在大量的测算过程中，算法并没有出现早熟现象和收敛到局部最优解的情况，最长的平均计算时间为90.63秒，在可接受的范围内。对选择算子、交叉算子和变异算子做出改进后，分别有了7.68％、9.22％、4.67％的优化。这些数据充分说明了文中求解VRPSTW时对GA所做的种种改进是较为合理的。

目录

声明

摘要

第一章 绪论

1．1 研究背景和意义

1．2 国内外研究现状

1．2．1 问题描述

1．2．2 国外研究现状

1．2．3 国内研究现状

1．3 VRPSTW研究中目前存在的问题

1．4 研究的主要内容及组织结构

1．5 本章小结

第二章 带软时间窗车辆路径问题和遗传算法的研究概述

2．1 车辆路径问题概述

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

2．1．2 车辆路径问题的分类

2．1．3 车辆路径问题的约束

2．1．4 车辆路径问题的优化目标

2．2 带时间窗车辆路径问题

2．2．1 带时间窗车辆路径问题的概述

2．2．2 带时间窗车辆路径问题的分类

2．2．3 求解VRPTW的常用方法

2．3 基于遗传算法的概述

2．3．1 遗传算法

2．3．2 遗传算法的优点

2．3．3 遗传算法的缺点

2．3．4 遗传算法的步骤

2．4 本章小结

第三章 VRPSTW多目标优化模型的构建

3．1 问题描述

3．2 参变量的定义

3．3 多目标函数的构建

3．4 约束条件的构建

3．5 约束条件的处理

3．6 本章小结

第四章 VRPSTW的改进遗传算法

4．1 遗传算法的编码和解码

4．2 种群初始化及适应度函数的构建

4．2．1 种群初始化

4．2．2 适应度函数的构建

4．3 选择算子的改进

4．4 交叉算子的改进

4．5 变异算子的改进

4．6 控制参数的设置及终止条件的确定

4．6．1 设置控制参数

4．6．2 确定终止条件

4．7 本章小结

第五章 算法测试和性能比较

5．1 Solomon标准库简介

5．2 算法的实现

5．2．1 算法流程图

5．2．2 算法程序设计

5．3 实例测验及结果分析

5．3．1 不同选择算子的测试

5．3．2 不同交叉算子的测试

5．3．3 不同变异算子的测试

5．3．4 软硬时间窗的测试

5．3．5 不同算法的测试

5．4 本章小结

第六章 总结与展望

6．1 全文总结

6．2 论文的不足之处与展望

6．2．1 论文的不足之处

6．2．2 展望

参考文献

发表论文和参加科研情况说明

附录

致谢