论文部分内容阅读
车辆路径规划问题(Vehicle Routing Problem,VRP)是现代物流配送过程中的关键环节,而且其在众多领域中都有广泛的应用,因此它的提出引起了不同学科的专家和物流管理者的极大重视,目前VRP已经成为研究的热点。但是如何找到一种高效的算法使其在较短的时间内找到比较满意的全局解仍然是研究的重点。本文主要从以下几个方面进行阐述。(1)详细介绍和比较分析了国内外求解VRP问题的研究现状和求解方法,重点阐述了基本蚁群算法(Ant System,AS)的工作原理、数学模型和实现旅行商问题(Traveling Salesman Problem,TSP)的求解过程,剖析了蚁群算法的复杂度、特征以及重要参数的设置对算法性能的影响情况。但是,如何在蚁群算法求解TSP问题的基础上把其改造成适合求解VRP问题的算法是本文研究的主要内容,而从此问题出发可以有两个不同的方向:直接法和转化法。(2)本文首先从直接法出发提出了两种改进蚁群算法的技术。技术方案一(简称ImproAS_VRP_ACSTSP)是先运用初步改造好的蚁群算法得到一个VRP可行解,然后在这个解的基础上分多段运用蚁群TSP算法以对该VRP解进行改善。技术方案二(简称OutsideAdvancedAS_InsideACSTSP)不仅对蚁群算法进行了充分的完善而且采用了两次蚁群算法,外部的蚁群算法只是为了得到多种不同的分组方案,而内部的蚁群算法则是为该分组规划出较短路线并指导蚂蚁按此路线行走。然后又从转化法出发提出了一种新型改进技术方案三(简称MutationSweep_ACSTSP),它是在之前顺序扫描算法的基础上增加了变异操作,并将变异算子用于扫描过程中,既可保证得到VRP解依旧是可行的又可使不同的分组之间距离较接近,这样就可得到多个较合理的分组,然后在每个分组内部实现路内次序的再优化,最后就可以得到VRP问题的最优解。(3)利用Matlab在VRPLIB数据集上进行仿真测试,记录三种改进算法找到的最优目标函数值及运行时间,比较和分析得到的仿真结果,验证和评价这些改进技术方案的合理性和有效性。