基于聚类的车辆线路优化算法研究

论文摘要

物流配送中的车辆线路优化问题（VRP,Vehicle Routing Problem）是近几十年来学术界的一个研究热点。如何针对车辆路径问题的特点,构造运算简单、性能优异的启发式算法,对降低物流系统成本具有十分重要的意义。由于目前已有算法无法有效解决实际中大规模物流配送问题,本文针对大规模VRP问题的特点,提出了“先聚类,再分派,后排程”的三阶段求解算法。首先,利用改进的基于密度的聚类算法（DBSCAN,Density Based SpatialClustering of Applications with Noise）对客户点进行分区聚类,生成一些虚拟客户,将大规模问题转化为小规模问题;然后,在第一阶段聚类的基础上,以生成的虚拟客户集合作为输入,采用Clark-Wright节约里程算法进行车辆分派;最后,将车辆服务的虚拟客户重新转化为实际客户,将问题变为若干个小规模的旅行商问题（TSP,Traveling Salesman Problem）,采用蚁群算法或最邻近点算法对每辆车安排最优的客户访问次序。为验证算法的有效性,本文进行了大量的仿真试验。试验主要包括两部分:对标准试验库（benchmark）的测试和山西某市烟草配送中心实际线路优化问题的求解。一方面,在对标准试验库A集部分算例的试验中,探讨了算法相关参数值选择问题,而且试验获得的所有结果与最优解的偏差均在3%-7%之间,验证了算法的可行性;另一方面,本算法在27分钟内成功地解决了有4642个客户点的大规模车辆线路优化实际问题,在求解质量和运行时间方面都体现出本算法的高效性。最后,本文对基于聚类的车辆线路优化算法在解决大规模实际问题的应用前景进行了展望,并给出了进一步的研究方向。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 第一章 绪论
• 1.1 研究背景
• 1.2 VRP问题文献综述
• 1.2.1 车辆线路优化问题
• 1.2.2 VRP模型
• 1.2.3 模型分类
• 1.2.4 问题特点
• 1.2.5 车辆路径问题的研究现状
• 1.3 问题的提出
• 1.4 研究目的和意义
• 1.5 论文章节安排
• 第二章 相关理论
• 2.1 图论中的网络模型
• 2.1.1 相关概念
• 2.1.2 网络的表示
• 2.2 Clark-Wright节约里程算法
• 2.3 蚁群算法
• 2.4 聚类算法
• 2.5 本章小结
• 第三章 基于聚类的车辆线路优化算法
• 3.1 大规模车辆线路优化问题
• 3.1.1 大规模车辆线路优化问题的特点
• 3.1.2 大规模车辆线路优化问题研究综述
• 3.1.3 大规模车辆线路优化问题的简化策略
• 3.2 基于聚类的车辆线路优化算法
• 3.2.1 算法基本思想
• 3.2.2 算法描述
• 3.2.3 改进基于密度的客户聚类算法
• 3.3 本章小结
• 第四章 仿真试验与分析
• 4.1 标准试验库测试
• 4.1.1 参数分析
• 4.1.2 算例测试结果
• 4.2 大规模烟草配送车辆线路优化试验
• 4.2.1 试验数据
• 4.2.2 试验结果
• 4.3 本章小结
• 第五章 总结和展望
• 5.1 论文工作总结
• 5.2 下一步研究展望
• 参考文献
• 致谢
• 攻读硕士学位期间发表论文
• 学位论文评阅及答辩情况表