求解vrp问题的改进和声搜索算法的分析

《求解vrp问题的改进和声搜索算法的分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据l绪论联网呈现飞速发展的趋势，深入研究VRP问题不仅有重要的科学理论意义，同时具有巨大的经济效益。VRP是一类NPhard的网络和组合优化问题，只有一些规模较小的问题(不超过30个客户)可以通过精确算法计算出最优解。对更大规模的VRP问题，解空间的范围就超过了精确解法的计算能力，要在有限的计算资源和计算时问下求得最优解，几乎是不可能的。对这种规模的车辆路径问题，比较好的方法是使用一种启发式算法。启发式算法在求解VRP时虽然牺牲了一些求解精度，却大大提高了解决问题的速度。目前，常用来解决车辆路径问题的启

2、发式算法主要有遗传算法，粒子群算法，禁忌搜索等。其中和声搜索算法作为一种比较新的全局优化启发式算法，在实践中已经取得了比遗传算法，粒子群算法等更好的结果，因此受到越来越多学者的重视。为了提高我国企业物流的配送优化能力，降低货物的流通成本，本文在国内外现有的研究工作的基础上，对和声搜索算法进行了深入的研究，提出了改进和声搜索算法CVRP求解算法。与用基本和声算法求解VRP相比，求解精度和速度均大大提高，相比较其他启发式算法，改进的和声算法也有着明显优势。1．2国内外7RP问题的研究VRP问题可以描述为：一定数量

3、的客户，各自有不同数量的物流需求，配送中心根据客户的需求，规划车队行车路线，在满足一定的约束的条件下，达到诸如路程最短、成本最小、耗费时间最短等目标。VRP问题最初由Danting和Ramser于1959年提出。经过几十年的发展，出现了许多分支，包括：带时间窗车辆路径问题、多配送中心车辆路径问题、容量限制车辆路径问题、基于站点的车辆路径问题、开放式车辆路径问题、同时取送货车辆路径问题等。国外对车辆路径问题的研究开展的较早，具有代表性的工作主要包括：Heung．SukHwang等人在对带时间窗车辆路径问题(VR

4、PTw)的研究中，将原本只用于求解旅行商问题(TSP)的模型应用在求解VRP问题上，并通过改良遗传算法的突变、复制的方式和亲代的选择方法，创新地提出了一种求解VRP问题改进的遗传算法。实验结果表明，采用的改进算法结果要优于原有求解方法，而且该方法对不同规模的问题也有较强的适应性。Chiang和Russell提出了基于模拟退火(SimulateAnnealing，SA)结合禁忌搜索的3万方数据1绪论方法来求解VRP，利用了TS中禁忌列表来提高SA的寻优能力，同时算法评估了在Solomon测试集上的表现，实验结果

5、比仅采用一种启发式算法更好，证明了混合式启发算法有着明显的优势，值得继续深入探讨。Yoshiike，Takefuji等人提出了一种新颖的方法。该算法求解VRP的过程为两个阶段，其中第一个阶段用最大的神经元VRP模型简化问题，便于分组。YingjieZhong，MichaelH．Cole等人使用带引导的局部搜索算法来求解带时间窗车辆路径问题，这种方法的一个缺陷是求解过程会有违反时间窗约束的情况发生，所以又融入了分组规划法，同时引入2-opt算子，1-move算子，交换算子等。经过改进后，算法可以在约束条件范围内

6、求得较高质量的解。此外，Desaulniers、Hong和Park、Toth和Vigo、Baker和Sheasby等人使用了其他算法来求解VRP，例如，通过神经网络，数学规划等方法来解决VRP。国内研究VRP问题起步于20世纪90年代初。我国学者普遍使用启发式算法，以提高求解效率，并适用于不同类型的VRP的，研究取得了显著的成果：罗敏华研究了用蚁群算法求解带容量限制的VRP。算法模拟了蚂蚁的觅食过程，用蚂蚁的信息素来构筑车辆行驶的路径，同时用节约算法提高初始解的质量。作者用蚁群算法解决了同时限制载重和行驶距离

7、的车辆路径问题(DCvI冲)，针对蚂蚁的数量如何影响寻优过程这个问题，作者经过研究表明较少的蚂蚁可以达到同样的效果。王佳容等人利用人工神经网络(舢州)和时间分割、禁忌搜索相结合的方法来解决软时间窗车辆调度问题。为了使更多的时间服务较早和较晚的客户可以有最优的分群，该方法根据客户需求所在的位置，通过自组织神经网络构建网格地图，将用户分群，同时检查的时间窗口每一组客户距离仓库的远近。结果表明，该方法对解决带时间窗车辆路径问题是有效的。肖鹏等人改进了遗传算法的编码方式并构造了一种伪克隆遗传算法，在其中采用了一种等位

8、基因换位算子，实验表明在解决客户数目较少的VRP时效果明显。王正彬等人研究了现实中的物流运输过程，对VRP模型进行了改进，在其中增加了车辆运输的限制条件，并用启发式算法进行了求解。1．3和声搜索算法的研究现状和声搜索算法(harmonysearchalgorithm，HS)是韩国学者Geem在2001年提出的一种4万方数据1绪论新颖的元启发算法【3】，算法的灵感来自于音乐家自然演奏过程中寻求一个更好