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