求解VRP问题的改进和声搜索算法的研究

发布时间：2018-04-13 22:39

本文选题：车辆路径问题 + 和声搜索算法　；参考：《浙江师范大学》2015年硕士论文

【摘要】：物流有企业“第三利润源泉”之称。在现代商业发展环境中,如何优化物流系统,降低物流成本已经成为企业要考虑的重要问题。车辆路径问题(Vehicle routing problem, VRP)是物流配送中的核心问题,合理安排配送车辆的路径对企业降低运营成本,提高服务质量有着重要意义。车辆路径问题是典型的NP难解问题,大多用启发式算法求解。和声搜索算法是一种新颖的启发式算法,最近几年得到了迅速发展,但是新提出的新和声算法在求解车辆路径问题方面研究并不充分。本文研究了基于和声搜索算法求解车辆路径问题的方法,并且提出了有效的改进方法。主要研究内容包括：(1)研究了和声算法、多种改进的和声搜索算法,在原算法的基础上,加入了2-opt算子,应用到VRP问题求解中,实验表明和声搜索算法能求得较高质量的可行解。(2)对带有容量限制的车辆路径问题(CVRP),提出了一种改进的全局最优和声搜索算法。该算法采用自然数编码,在新和声的生成过程中,增加了和声约束,避免了不可行解的生成,并利用2-opt算子对新的和声进行了优化,从而压缩了搜索空间,提高了算法效率。实验表明改进后的算法提高了搜索效率。(3)针对和声搜索算法容易陷入局部最优以及自然数编码不便于结合其他算法等问题,提出了萤火虫和声搜索算法(FGHS)来求解CVRP。算法采用了实数编码,在新解生成过程中,引入了萤火虫算法的更新公式,利用萤火虫的仿生特性改进和声搜索算法的音调调节,使算法不易陷入局部最优；提出了一种和声库重置方法,在算法陷入局部最优时,利用混沌扰动系统增加和声记忆库中解的多样性来帮助算法跳出局部最优,同时用局部搜索来增强寻优能力。
[Abstract]:Logistics has the enterprise "the third profit source" said.In the modern commercial development environment, how to optimize the logistics system and reduce the logistics cost has become an important issue for enterprises to consider.Vehicle routing problem (VRP) is the core problem in logistics distribution. It is of great significance for enterprises to reduce operation cost and improve service quality by reasonably arranging vehicle routing.Vehicle routing problem is a typical NP-hard problem, which is mostly solved by heuristic algorithm.Harmony search algorithm is a new heuristic algorithm, which has been developed rapidly in recent years. However, the new harmonic algorithm is not enough to solve the vehicle routing problem.In this paper, the method of solving vehicle routing problem based on harmony search algorithm is studied, and an effective improvement method is proposed.The main research contents include: (1) the harmonic algorithm is studied, and many improved harmonic search algorithms are studied. Based on the original algorithm, the 2-opt operator is added to solve the VRP problem.Experiments show that the harmonic search algorithm can obtain a high quality feasible solution. (2) for the vehicle routing problem with capacity constraints, an improved global optimal harmonic search algorithm is proposed.The algorithm uses natural number coding. In the process of generating new harmony, it adds harmony constraints, avoids the generation of infeasible solutions, and optimizes the new harmony by using 2-opt operator, thus compressing the search space and improving the efficiency of the algorithm.Experiments show that the improved algorithm improves the search efficiency. (3) aiming at the problems that harmony search algorithm is easy to fall into local optimum and natural number coding is not easy to combine with other algorithms, a firefly harmonic search algorithm (FGHS) is proposed to solve CVRPs.In the process of generating the new solution, the update formula of the firefly algorithm is introduced, and the tone adjustment of the harmonic search algorithm is improved by using the bionic characteristic of the firefly, which makes the algorithm difficult to fall into local optimum.In this paper, a harmonic sound bank reset method is proposed. When the algorithm falls into a local optimum, the chaos disturbance system is used to increase the diversity of the solution in the harmonic memory bank to help the algorithm jump out of the local optimum, and the local search is used to enhance the searching ability.
【学位授予单位】：浙江师范大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：F259.23;TP301.6

【参考文献】