基于遗传算法的带时间窗车辆路径优化问题研究

摘要

车辆路径问题(Vehicle Routing Problem,VRP)是物流配送过程中的关键问题之一,随着物流配送行业竞争日益激烈和客户对物流配送时效性要求越来越高,对车辆路径问题的研究,尤其是对带时间窗车辆路径问题(Vehicle RoutingProblem With Time Windows,VRPTW)的研究,不仅可以帮助运输企业提高服务水平,为客户提供快捷、准时、安全、舒适的服务,而且有助于企业节约运输成本,提高车辆利用效率,缩短生产周期,加速资金周转,实现资源的合理配置,汲取“第三利润源泉”的财富,因此研究带时间窗车辆路径问题具有重要的现实意义。
　　 本文正是基于以上背景对带时间窗的车辆路径优化问题进行了相关研究。论文从旅行商问题出发,通过分析带时间窗车辆路径优化问题的基本理论,对可用于求解VRPTW的各种优化算法进行了对比,确定了遗传算法作为本文VRPTW求解算法。在此基础上,考虑配送距离、配送及时性以及配送车辆数对配送成本的影响,构建了以配送总成本最小化为目标的带有惩罚函数的VRPTW优化模型,并设计了适合于该模型求解的染色体编码方式以及遗传算子等。最后,应用算例进行了仿真试验,利用MATLAB软件分别计算出基于改进遗传算法和基本遗传算法的最优目标函数值与最优配送路径方案,通过对试验结果的对比分析,验证了本文所建模型及求解算法的合理性和有效性。
　　 图21幅,表8个,参考文献67篇。

目录

文摘

英文文摘

致谢

1 绪论

1.1 研究背景及意义

1.2 国内外研究现状

1.2.1 国外研究现状

1.2.2 国内研究现状

1.3 本文的研究方法及主要内容

1.4 本章小结

2 车辆路径问题概述

2.1 旅行商问题(TSP)

2.2 车辆路径问题(VRP)

2.2.1 车辆路径问题的描述

2.2.2 车辆路径问题的组成要素

2.2.3 车辆路径问题的数学模型

2.2.4 车辆路径问题的分类

2.3 带时间窗的车辆路径问题(VRPTW)

2.3.1 时间窗的概念及描述

2.3.2 时间窗的分类

2.4 本章小结

3 带时间窗车辆路径问题求解算法研究

3.1 精确算法

3.2 启发式算法

3.2.1 传统启发式算法

3.2.1 现代启发式算法

3.3 遗传算法

3.3.1 遗传算法基本思想

3.3.2 遗传算法相关概念

3.3.3 遗传算法工作流程

3.3.4 遗传算法特点

3.4 常用算法概括与比较

3.5 本章小结

4 VRPTW模型构建与算法设计

4.1 VRPTW模型构建

4.1.1 问题描述

4.1.2 基本假设

4.1.3 惩罚函数

4.1.4 参变量定义

4.1.5 数学模型

4.2 遗传算法设计

4.2.1 编码与解码

4.2.2 初始群体

4.2.3 选择算子

4.2.4 交叉算子

4.2.5 变异算子

4.2.6 适应度函数

4.2.7 终止进化规则

4.3 本章小结

5 算例分析

5.1 算例说明

5.2 试验数据

5.3 试验参数设定

5.4 算法实现主要步骤

5.5 试验结果分析

5.6 本章小结

6 总结及展望

6.1 全文总结

6.2 研究展望

参考文献

附录A:试验数据C204

作者简历

学位论文数据集