基于时空聚类的车辆路径分析与优化

论文摘要

近年来，作为“第三利润源”，物流的研究及应用已经引起了政府、工商企业以及学术界的高度重视。随着经济的发展和市场竞争的日益激烈，配送中心所覆盖区域的顾客规模越来越大，生产企业或零售企业对供货商或第三方物流提供商配送时间的要求越来越高。然而，物流配送中的不确定性为配送车辆路径的分析和优化带来了很大的挑战。通过分析不难发现，这些不确定性因素均具有较强的时空分布特征。因此，在研究中综合考虑时间因素和空间因素是非常必要的。而现有研究中，时空一体化分析方法在物流中的应用仍然没有得到充分的重视。本文的研究目的即采用物流与智能交通、时间地理学理论相结合的方法，研究物流配送业务的时空分布特点，引入时空距离的度量方法，为车辆路径问题提供分析和优化的方法和工具。本文借鉴目前求解VRPTW的诸多成功经验，改进了传统两阶段算法的求解框架，利用Solomon经典的I1插入算法构造可行初始解，然后对顾客点进行时空聚类，最终利用可变邻域搜索（VNS）算法对路径进行改进。基于时空距离对客户点进行聚类，可以降低改进阶段空间搜索的范围，使改进更具有针对性。在顾客点聚类分区阶段，我们设计了时空距离的度量方法，令其代替空间距离作为判断两个顾客点相近性的依据。在初始路径改进阶段，我们提出了2-opt、relocate、exchange等多种邻域结构和改进算子，有效改进了解的质量，并使得算法更适用于解决大规模VRP问题。最后，在通过C++编程实现改进两阶段算法之后，以Gehring&Homberger标准问题集的算例作为模型标准数据，验证了本文提出的算法在解决VRP特别是大规模VRPTW方面的有效性和实用性。文中算法实现了在求解过程中同时考虑时间因素和空间因素，搜索时间较短且求解性能较优，能够满足实际应用的需要，而引入时空聚类的理念并利用时空一体化分析方法对车辆路径规划进行分析、诊断和优化，为求解车辆路径问题提供了一个新的研究视角。

论文目录

• 摘要
• Abstract
• 主要符号对照表
• 第1章 引言
• 1.1. 选题背景及意义
• 1.1.1. 选题背景
• 1.1.2. 选题意义
• 1.2. 本文工作
• 1.2.1. 研究支持
• 1.2.2. 研究内容
• 1.2.3. 论文安排
• 1.3. 本章小结
• 第2章 相关理论研究与文献综述
• 2.1. 车辆路径问题
• 2.1.1. 定义及分类
• 2.1.2. 求解算法
• 2.1.3. 大规模 VRP 问题
• 2.1.4. 可变邻域搜索算法
• 2.2. 考虑时间和空间特征的 VRP
• 2.2.1. 单独考虑时间和空间特征
• 2.2.2. 综合考虑时间和空间特征
• 2.3. 聚类分析
• 2.3.1. 聚类分析概述
• 2.3.2. 主要聚类算法
• 2.3.3. K-means 聚类算法
• 2.4. 本章小结
• 第3章 算法的设计与实现
• 3.1. 算法整体框架
• 3.2. 初始路径构建阶段
• 3.3. 顾客点聚类分区阶段
• 3.3.1. 时空路径
• 3.3.2. 时空距离的度量
• 3.3.3. 基于聚类的遗传算法求解方法
• 3.4. 局部搜索改进阶段
• 3.4.1. 算法原理及实现
• 3.4.2. 改进算子
• 3.5. 本章小结
• 第4章 算例结果分析
• 4.1. 实验测试问题
• 4.2. 算法性能分析
• 4.3. 算法时间比较
• 4.4. 本章小结
• 第5章 总结与展望
• 5.1. 论文工作总结
• 5.2. 主要创新点
• 5.3. 未来研究展望
• 参考文献
• 致谢
• 个人简历、在学期间发表的学术论文与研究成果