基于混合遗传算法的快递车辆路径优化问题的研究

摘要

车辆路径问题（简称VRP问题）是快递物流配送过程中的关键性环节之一，同时也是组合优化问题中典型的 NP-hard问题。针对遗传算法处理大规模数据时表现出的搜索性能下降、早熟收敛等现象，将杂乱无章的大规模客户数据首先运用分解协调算法进行处理，将数据划分成为多个独立的有序小规模客户群后，在每个客户群内运用遗传算法确定每辆快递服务车辆的服务对象，从而获得具有参考价值的调度方案。本文的主要研究内容如下：
　　（1）考虑到组合优化问题的特点，建立车辆路径数学模型时，基于时间窗划分依据以及违背规则时相应的惩罚措施，以配送时间最短、配送成本消耗最小为目标，在快递服务车辆的行程过程中，混合了硬时间窗和软时间窗两者的时间窗要求规则，建立混合时间窗车辆路径模型。
　　（2）针对传统遗传算法求解高维度数据的车辆路径问题时容易出现效率低、早熟等现象，提出一种新的混合遗传算法：首先，将杂乱无章的大规模客户数据，依据分解协调算法的关联预测法，将客户群划分成多个独立的不同的小规模的客户群；然后，在每个数据群内运用遗传算法求解每辆快递服务车辆的服务序列，来高效率的求解车辆路径调度问题模型。仿真实验表明，所提出的混合遗传算法比传统遗传算法在寻找最优解和运算效率方面均有较大的提升。
　　（3）为了进一步验证混合遗传算法的可用性，针对某物流中心的实际快递配送服务，将所提算法进一步应用于物流中心每辆快递车辆的服务配送路线设定这一应用场景中，并与已有的混合遗传启发式算法、量子蚁群算法进行了多次实验比较、分析得到，本文的混合遗传算法在求解服务车辆的平均配送时间、寻优效率等性能指标上相对于上述两种算法均有提升，能够为物流中心提供有价值的调度指导方案。

目录

1绪论

1.1选题背景

1.2研究意义

1.3车辆路径问题研究现状

1.4技术路线

1.5论文主要研究内容

1.6论文的组织结构

2车辆路径问题模型的建立与分析

2.1车辆路径问题概述

2.2车辆路径问题分类

2.3时间窗概念与分类

2.4带时间窗的车辆路径问题模型设计

2.5本章小结

3遗传算法理论研究

3.1遗传算法研究现状

3.2遗传算法操作算子

3.3遗传算法流程

3.4本章小结

4分解协调算法理论研究

4.1分解协调算法研究现状

4.2分解协调原理及优越性

4.3关联预测法原理

4.4关联预测法算法推导

4.5本章小结

5车辆路径问题的混合遗传算法设计

5.1混合遗传算法原理及优越性

5.2混合遗传算法流程

5.3混合遗传算法设计

5.4混合遗传算法性能仿真实验

5.5本章小结

6混合遗传算法在车辆路径问题的应用实现

6.1车辆路径问题应用场景分析

6.2车辆路径调度问题实验数据采集与分析

6.3仿真实验结果分析

6.4本章小结

总结与展望

总结

展望

参考文献

致谢

攻读学位期间发表的学术论文

声明