车辆路径问题及其智能算法的研究

发布时间：2018-11-16 15:02

【摘要】：随着经济全球化的快速扩张以及信息化产业的扶摇直上,物流作为新兴服务业,广阔的前景和增值功能有目共睹,正在全球范围内有着飞跃性的进步。在物流诸多环节中,降低运输成本、提高运输效率有助于加速物流业的发展。因此,作为运输的核心问题的车辆路径问题得到了充足的研究,并取得了丰富的研究成果。它通过组织、优化货物的运输线路,在满足一定的约束前提下,以最低的运输费用、最短的运输距离、最少的运输时间等为目标,将货物送达目的地。本文基于对车辆路径问题的数学模型,结合之前学者采用各种算法进行的丰富研究,设计了改进的粒子群算法应用于车辆路径问题,以及用遗传算法求解同时供货和取货任务的随机车辆路径问题。本文所做工作如下： (1)简要介绍了车辆路径问题的研究进程与现状,以及研究意义,介绍了车辆路径问题的数学模型、精确算法、启发式算法和智能优化算法等。 (2)概要介绍了遗传算法优胜劣汰、粒子群算法群体趋优的基本思想、算法步骤流程以及在各领域的应用。 (3)主要研究用粒子群算法求解有能力约束的车辆路径问题,由于粒子速度受到前一次速度的影响,进而影响算法的搜索能力,本文针对粒子群算法中惯性权重的选择,采用线性与非线性结合的取值方式。实验结果表明,改进后,搜索最优解的成功率得到提高,全局搜索能力有所进步,并且计算精度也得到改善。而对于较大规模的车辆路径问题,采用粒子群算法与遗传算法相结合的方案,引入遗传算法特有的交叉算子的思想。实验结果显示,改进后,较好的避免了早熟收敛,同时提高了收敛速度与精度。 (4)针对同时供货和取货任务的随机车辆路径问题,由于信息的不确定性,考虑到使用不依赖于具体的问题的遗传算法进行求解,结合问题采用自然数编码的方式,并对算法中选择算子进行改进,保证保存最优个体,并对基本案例进行了测试,得到良好的结果。
[Abstract]:With the rapid expansion of economic globalization and information industry, logistics, as a new service industry, has broad prospects and value-added functions, and is making great progress in the world. In many aspects of logistics, reducing transportation cost and improving transportation efficiency are helpful to accelerate the development of logistics industry. Therefore, the vehicle routing problem, which is the core problem of transportation, has been fully studied, and a lot of research results have been obtained. Through organizing and optimizing the transportation line of goods, it can reach the destination with the aim of the lowest transportation cost, the shortest transportation distance and the least transportation time, under the premise of satisfying certain constraints. In this paper, based on the mathematical model of vehicle routing problem, combined with the abundant research of previous scholars using various algorithms, an improved particle swarm optimization algorithm is designed to apply to the vehicle routing problem. Genetic algorithm is used to solve the stochastic vehicle routing problem. The work of this paper is as follows: (1) the research process and current situation of the vehicle routing problem are briefly introduced. The mathematical model, exact algorithm, heuristic algorithm and intelligent optimization algorithm of the vehicle routing problem are introduced. (2) the basic ideas of genetic algorithm (GA), particle swarm optimization (PSO) and its application in various fields are briefly introduced. (3) Particle Swarm Optimization (PSO) algorithm is mainly used to solve the vehicle routing problem with capacity constraints. Because the particle velocity is affected by the previous velocity, and then the search ability of the algorithm is affected, this paper aims at the choice of inertia weight in PSO. A combination of linear and nonlinear values is adopted. The experimental results show that the success rate of searching the optimal solution is improved, the global search ability is improved, and the computational accuracy is improved. For the large scale vehicle routing problem, particle swarm optimization (PSO) combined with genetic algorithm (GA) is adopted, and the idea of crossover operator which is unique to GA is introduced. The experimental results show that the improved method can avoid premature convergence and improve the speed and precision of convergence. (4) for the random vehicle routing problem with both supply and delivery tasks, considering the uncertainty of information, considering the use of genetic algorithm which does not depend on the specific problem, the method of natural number coding is used to solve the problem. The selection operator in the algorithm is improved to ensure the preservation of the optimal individual, and the basic cases are tested and good results are obtained.
【学位授予单位】：安徽理工大学
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TP18

【参考文献】