混合禁忌搜索算法在配送车辆调度问题中的研究和应用

摘要

车辆调度问题是管理科学的一个重要研究课题,在物流配送中有着广泛的应用背景,对于企业降低成本、提高效率起到重要的作用。带时间窗的车辆调度问题(Vehicle Routing Problem with Time Windows,VRPTW)正是基于这样的实际背景提出的组合优化问题,属于NP(Nondeterministic Polynomial)难题。VRPTW寻求在满足顾客的时间窗和车辆的容量约束的条件下,使总的代价最小的一组车辆路线。
　　本文以VRPTW为研究对象,着重于禁忌搜索算法研究。禁忌搜索算法是对局部邻域算法扩展后的一种全局寻优算法。针对初始解的优劣对禁忌搜索算法的结果影响较大的特点,设计了新的初始解的产生方法。一是对标准禁忌搜索算法进行改进,产生了多个初始解,使邻域的搜索范围更广;二是将聚类算法引入到VRP问题中,把聚类结果作为禁忌搜索算法的初始解,再利用禁忌搜索算法迭代生成最优解,此方法适于求解客户点分布较为集中的大规模VRP问题。
　　通过对软时间窗车辆调度问题建立模型,进行实例研究,并对solomon的经典数据集进行数值实验,计算结果显示算法能够在合理时间内求得满意解,证明了本文所提出的算法优化车辆调度问题的有效性和可行性。

目录

封面

声明

中文摘要

英文摘要

目录

第一章 绪论

§1.1 研究背景

§1.2 课题研究的目的和意义

§1.3 问题的提出

§1.4 国内外研究现状

§1.5 论文完成的工作及论文框架

第二章 车辆调度问题的描述与模型建立

§2.1 车辆调度问题的基本问题描述

§2.3 本章小结

第三章 车辆调度问题的算法研究

§3.1 VRPTW问题的研究方法

§3.2 禁忌搜索算法理论

§3.3 组合优化和算法复杂性

§3.4 本章小结

第四章 混合禁忌搜索算法在VRPTW中的应用

§4.1 禁忌搜索算法的具体实现技术

§4.2 禁忌搜索算法的改进

§4.3 聚类算法在VRP问题中的应用

§4.4 混合禁忌搜索算法流程及特点

第五章 算例分析及实证研究

§5.1 算例分析

§5.2 实证研究

§5.3 本章小结

第六章 结论及展望

§6.1 结论

§6.2 展望

参考文献

附录 算法核心代码

致谢

作者在攻读硕士期间的主要研究成果