运输优化问题中常见启发式算法比较与研究

发布时间：2018-07-24 21:51

【摘要】：运输优化问题涉及面广,种类繁多,精确求解难度高,难有统一的方法求解。但由于问题原型多数属于大型生产问题,解的精确性微小差异可能会带来巨大的经济,人力,物力等资源的耗费,能够在可接受的时间范围内找到满意解,无论是从理论上或是工作中都是显得很有必要。本文结合常见启发式算法特点,应用到运输优化问题的大量实例,选取出三种相对成熟的算法：遗传算法、模拟退火算法、蚁群算法,以运输优化模型特点为依托,做出收敛性比较,合理拓展的理论基础的验证,并在此基础上提出了关于启发式算法“高效性”的个人观点,以及算法性能指标的确定。文章最后结合多种模型,以“高效性”原则为指导,以实验结果为依据,基本证实启发式算法能够有效的应用到大型运输优化问题中,在快速合理的前提下给出较为满意的结果。本论文所做原创性工作如下：借助三种常用启发式算法收敛性条件分析,提出“存优策略”和与经典算法结合的合理思路,甚至是对启发式算法合理的使用优化条件的可行性做出分析。设计出带有宽度约束的船闸优化模型,提出驼峰三级减速的优化模型的建模思想,对于经典问题Hamilton问题(以及TSP问题)做出了相应的研究工作,并结合启发式算法研究成果,做出了算法分析。提出启发式算法“高效性”的基本原则,在以往追求算法适用性强的观点,做出合理补充。定义了启发式算法性能指标,重点研究与经典算法不同的收敛精度相关性能指标的确定,及合理性的分析。本论文是在前人的辛勤汗水工作基础上,结合自身所学以及擅长,大胆设想小心求证,对启发式算法以往对比只从实验结果比较的现实情况做出了突破,从比较新颖的观点多启发式算法做出比较与分析。
[Abstract]:The problem of transportation optimization involves a wide range, a wide variety, difficult to accurately solve, and difficult to solve a unified method. However, because most of the prototype problems are large production problems, the small difference in accuracy of solutions may bring huge economic, human, material and other resources to find satisfactory solutions within an acceptable time range. It is necessary in both theory and work. This paper combines the characteristics of common heuristic algorithms and applies to a large number of examples of transportation optimization problems, and selects three relatively mature algorithms: genetic algorithm, simulated annealing algorithm, ant colony algorithm, based on the special point of transportation optimization model, make the theory of convergence and rational expansion. On the basis of this, a personal view on the "efficiency" of the heuristic algorithm and the determination of the performance index of the algorithm are proposed. At the end of the paper, the paper combines many models, guided by the principle of "high efficiency", and based on the experimental results, and basically proves that the heuristic algorithm can be effectively applied to the problem of large-scale transportation optimization. Satisfactory results are obtained under the premise of fast and reasonable.
The original work of this paper is as follows:
With the help of the convergence condition analysis of three common heuristic algorithms, the "survival strategy" and the rational idea of combining with the classical algorithm are put forward, and even the feasibility of the optimal conditions for the rational use of the heuristic algorithm is analyzed.
The optimization model of ship lock with width constraint is designed, the modeling idea of the optimization model of hump three stage deceleration is put forward. The research work on the classic problem Hamilton (and TSP problem) is made, and the algorithm analysis is made with the research results of the heuristic algorithm.
The basic principle of heuristic algorithm "high efficiency" is put forward, which makes reasonable supplement in the past in pursuit of the applicability of the algorithm.
The performance index of heuristic algorithm is defined, and the determination of the convergence accuracy and related performance indicators and the analysis of rationality are mainly studied.
This paper is based on the work of the predecessors' hard work and sweat work, combined with his own learning and good, bold assumption of careful proof, the heuristic algorithm in the past comparison only from the experimental results compared with the actual situation made a breakthrough, from a relatively new point of view of the heuristic algorithm to make a comparison and analysis.
【学位授予单位】：西南交通大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：U116

【参考文献】