论文部分内容阅读
物流配送车辆路径优化问题(Vehicle Routing Problem, VRP)已经被证明属于NP-Hard问题。传统的研究在模型建立上比较单一,没有对求解模型的算法进行深入探索并且在算法选择方面也没有进行细致的比较研究。因此,本文针对这三个方面对VRP数学建模,算法研究以及算法性能比较进行探讨,取得了以下研究成果:1.针对目前没有公认的多目标优化算法比较标准以及算法选择流程,本文提出了精度、时间、解决问题个数相结合的三维算法比较方法。首次,将精度作为算法比较的一个重要方面,得到了算法比较三维模型,同时,给出了可行的算法选择流程,并开发了算法选择软件。2.建立了静态多目标VRP模型,利用算法选择软件选出了合适的算法—NSGAⅡ。收集整理了美国密西根州的配送中心的数据,用NSGAⅡ求解已建立的静态多目标VRP模型,从收敛速率、Pareto面和Pareto投影三个方面分析了算法的有效性和可行性。3.为了克服NSGAⅡ算法早熟收敛和对初始群体依赖性的缺点,按照算法融合的思想,将经典算法与现代NSGAⅡ算法进行融合,提出了贪心NSGAⅡ、分支定界NSGAⅡ和Or-opt NSGAⅡ三种改进算法,以美国密西根州配送中心为实例,验证了三种算法的有效性和可行性。4.以经典遗传算法为参照,以美国密西根州配送中心的大规模(498个配送点)和小规模(30个配送点)VRP为实例,从收敛速率、收敛时间、最优值和非支配个体百分比四个方面对NSGAⅡ及其三种改进算法的性能进行了比较研究,得到了静态多目标VRP模型算法分析简表。5.利用仿真方法研究了交通拥挤对配送网络的影响,得到路口拥挤与准时到达折线图并基于此折线图提出了多目标VRP两阶段模型。同样,在动态多目标VRP模型上对NSGAⅡ及其三种算法的性能进行了研究探讨,得到了动态多目标VRP模型算法分析简表,与静态多目标VRP模型算法分析简表一起,成为多目标VRP两阶段模型的算法分析简表。