一种求解多目标车辆路径问题的遗传算法研究

发布时间：2018-04-22 02:22

本文选题：车辆路径问题 + 多目标优化问题　；参考：《东北大学》2014年硕士论文

【摘要】：车辆路径问题(Vehicle routing problem, VRP)是一个经典的运筹学问题,它是指若干个客户各自有着不同的货物需求,若干个配送中心向客户提供货物,由车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。VRP问题在科学和工程应用领域具有非常广泛的应用,很多实际的物流运输问题都可以转化成各种VRP问题来进行解决。由于VRP已经被证明是NP难的,所以对于大规模VRP问题往往考虑利用各种智能优化算法来进行求解。随着经济的发展、科学技术的进步以及人们需求的日益多元化,越来越多实际应用问题往往需要考虑多个优化目标,多目标优化正在成为近年来运筹学领域一个研究热点。需要注意的是目前关于多目标VRP问题的研究文献并不多,在很多方面尤其是求解算法设计方面亟需开展进一步深入的研究。本文采纳系统工程的思想,利用运筹学、进化计算等领域的相关研究成果,设计和开发一种能够有效求解多目标VRP问题的遗传算法(Genetic algorithm,GA)。本文的主要内容可以归纳如下几个方面：(1)相关工作综述部分。主要介绍了VRP问题及求解算法、多目标优化理论与方法等方面的研究工作。(2)问题建模部分。在给出一般VRP以及带有时间窗约束VRP问题数学模型的基础上,建立一个以最小化配送成本和最大化客户满意度为目标函数的多目标VRP问题的数学模型。(3)算法设计部分。研究一般VRP问题的求解算法,考虑到编码和解码是求解VRP问题的GA设计中所面临的主要挑战,对三种不同编码方法的有效性进行对比仿真实验。在上述研究结论的基础上,通过结合一种经典多目标进化算法(MOEA/D)的相关思想,提出一种能够求解多目标VRP问题的新型多目标GA算法。(4)仿真实验部分。利用一组根据VRPLIB中标准测试问题构造的多目标VRP问题,对所提出的多目标GA算法进行仿真实验以检验其性能。此外,还在仿真实验中分析所提出的算法中关键参数及算子对算法性能的影响。(5)结论部分。对本文研究的主要工作进行总结,指出存在的不足之处,并对下一步的研究工作进行展望。
[Abstract]:Vehicle routing problem (VRP) is a classic operational research problem. It means that several customers have different goods needs, several distribution centers provide goods to customers, and the team is responsible for distributing goods and organizing proper traffic route. The goal is to make customers meet the needs and can be certain. Under the constraints, the.VRP problem, such as the shortest path, the least cost, and the least time consuming, has a very wide application in the field of science and engineering applications. Many practical logistics and transportation problems can be transformed into various VRP problems to be solved. Because VRP has been proved to be difficult for NP, so the problem of large-scale VRP problem is bound to With the development of economy, the progress of science and technology and the increasing diversity of people's needs, more and more practical applications often need to consider multiple optimization targets. Multi objective optimization is becoming a hot topic in the field of operational research in recent years. There are few research literatures on the multi-objective VRP problem, and in many aspects, especially the design of solving algorithms, we need to carry out further research. This paper adopts the idea of system engineering, and designs and develops a genetic algorithm (Ge), which can effectively solve the multi-objective VRP problem by using the related research results in the fields of operational research, evolutionary computation and so on. Netic algorithm, GA). The main contents of this paper can be summed up as follows: (1) a summary of the related work. It mainly introduces the research work of the VRP problem and the solving algorithm, the theory and method of multi-objective optimization. (2) the modeling part of the problem is based on the mathematical model of the general VRP and the VRP problem with time window constraints. In order to minimize the cost of distribution and maximize customer satisfaction as the objective function, a mathematical model for the multiobjective VRP problem is established. (3) the algorithm design part. The algorithm of solving the general VRP problem is studied. The main challenge in the GA design for solving the VRP problem is the encoding and decoding, and the effectiveness of the three different coding methods is given. On the basis of the above conclusions, a new multi-objective GA algorithm which can solve the multi-objective VRP problem is proposed on the basis of the relevant ideas of a classical multi-objective evolutionary algorithm (MOEA/D). (4) the simulation experiment part. A set of multi-objective VRP problems which are constructed according to the standard test problem in VRPLIB is proposed. The multi objective GA algorithm is simulated to test its performance. In addition, the influence of the key parameters and operators in the proposed algorithm on the performance of the algorithm is also analyzed. (5) conclusion part. The main work of this paper is summarized, the shortcomings of the existing research are pointed out, and the next step of the research work is prospected.

【学位授予单位】：东北大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U116.2;TP18

【参考文献】