论文部分内容阅读
物流是社会经济生活中的重要组成部分,逐渐向现代物流系统方向发展。运输路线智能设计是现代物流系统的关键,要求在较短时间内提供高质量的车辆路径方案。通常将其建模为车辆路径问题。物流车辆路径优化具有“NP难”特性,其计算时间随着问题规则呈现阶乘性增长。在中小规模的车辆路径问题上,当前研究已经取得较好的效果,发展多种现代启发式方法,获得高质量的车辆路径方案。日益加快的城市化进程促进消费需求的爆发,路径优化问题的规模变得十分庞大,求解大规模物流车辆路径优化问题是当前研究的难点。从空间角度看,车辆路径问题中的典型要素均具有空间属性。车辆路径优化包含多个空间相关的子问题：路径优化、多仓库的服务区域划分等。针对三个典型车辆路径问题,本论文提出基于Voronoi图启发式策略,发展大规模车辆路径问题的高效算法。本论文的主要工作包括以下四个部分：1.针对大规模容量限制车辆路径问题,提出基于Voronoi邻近的启发式优化方法。大规模车辆路径问题是计算密集性的,优化关键是利用有限的计算能力搜索最应该被搜索的解空间。在平面Voronoi图的基础上,本论文定义K环、Voronoi邻居,提出基于、Voronoi邻近聚类的创建算法,并将局部搜索限制在在K环Voronoi邻居内,利用Voronoi长边引导搜索,提出保持Voronoi邻近性的启发式优化算法。利用大规模容量限制车辆路径标准问题集和真实物流问题进行算法测试与比较,结果表明本文算法的优于当前现代启发式算法。2.针对大规模多仓库车辆路径问题,提出了基于双层Voronoi图的启发式优化方法。多仓库之间存在空间竞争与写作,其难点在于客户点分割和路径优化之间的均衡。基于Voronoi图的分割和邻近特性,本论文提出双层Voronoi图模型,上层、Voronoi图源于仓库点集,在仓库间进行客户点分割；下层Voronoi图源于客户点集,精简局部搜索范围；在上层、Voronoi边附近进行仓库间客户点的交换。利用大规模多仓库车辆路径标准问题集和北京市模拟物流问题进行试验,结果表明本文算法能在较短时间内提供高质量的解。3.针对大规模附带时间窗的多仓库车辆路径问题,提出基于双层时空Voronoi图的启发式方法。附带时间窗的车辆路径优化同时在空间维度和时间维度的约束,进一步加剧了问题的复杂性。本论文在时空统一坐标系下表达附带时间窗的仓库和客户点,建立双层时空Voronoi图,利用时空Voronoi邻近加快局部搜索效率。利用大规模附带时间窗的多仓库车辆路径标准问题集和长三角的模拟物流问题进行试验,实验结果表明本文算法能够在18304.6秒内求解16000个客户点的附带时间窗的多仓库车辆路径问题。4.分析并验证基于Voronoi图的车辆路径优化方法有效性。本论文统计多种大规模车辆路径问题中的K环、Voronoi邻居的数量规律,分析基于Voronoi邻近的局部搜索算法的时间复杂度。利用高质量的车辆路径方案进行Voronoi邻近分析,发现Voronoi短路段在高质量方案中占有显著优势。实验结果证明基于Voronoi图进行大规模车辆路径优化的正确性。