论文部分内容阅读
物流配送是物流活动中直接与消费者相连的环节。在物流的各项成本中,配送成本占了很大的比例,而车辆路径优化的合理与否直接影响配送成本。因此,采用科学、合理的方法解决车辆路径优化问题,是物流配送中非常重要的一个环节。本课题以现代物流配送环节中的车辆路径问题为研究对象,结合实际物流配送中配送中心多、问题规模大、约束条件多、复杂性高等问题,提出一种基于“集群第一,路线第二”的路径生成策略。该策略首先使用改进的K-Means聚类算法实现客户的配送区域的自动划分,将大规模的VRP简化成小规模的VRP,降低计算量,提高求解速度;其次使用改进的PFIH算法和变邻域搜索(VNS)算法相结合的混合启发式算法求解配送区域内车辆路径优化问题。基于上述策略,本文的主要工作如下:(1)物流配送区域及客户的聚类分析。分析影响配送过程的主要因素,以减少求解复杂性为目标,采用改进的K-Means算法实现客户配送区域的自动划分。(2)带时间窗约束的车辆路径问题数学模型的构建和初始可行车辆配送路线的求解。在实现对客户点配送区域划分的基础上,使用一种改进的PFIH算法求解配送区域内车辆初始可行路径,得到备选的车辆路径方案集合。(3)路线改进和路线优化。为提高生成的车辆路径的效率和质量,在所得到的备选车辆路径集合中,基于Voronoi多边形邻域相似信息的性质,使用变邻域搜索算法的操作对备选方案进行路径改进与路线优化,得到较优解。(4)烟草物流配送原型系统的实现。基于本文提出的车辆路径生成策略,设计并实现了一个烟草物流配送车辆路径生成原型系统。实验结果表明,本文的车辆路径生成策略既能获取较优的车辆配送路线,同时也具有较好的实时性,能满足实际应用需求。