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

《运输优化问题中常见启发式算法比较与研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、西南交通大学硕士研究生学位论文第1页第1章绪论1．1研究背景及意义1．1．1研究背景运输行业是国民经济重要的产业部门。运输优化问题中的模型多具有规模大，约束形式复杂，研究难度极大的基本情况，运用传统的最优化理论只能在特定的范围给出最优解，而大部分情况都很难在合理时间给出合适的解。这需要我们研究能在可接受时间内得到满意解的方案，而这恰恰是启发式算法的特点。启发式算法从提出至今时间不长，却因为其对复杂系统具有算法编制相对简单，处理问速度快的独特优点，在大型优化问题或是没有针对算法的优化问题中，显得格外抢眼。同时，启发式算法对于一些非线性约束或是目标函数的问题，它所要做的只是合理找到变量与变量之间的

2、迭代关系，而非约束条件或是目标函数的关系，这是相对容易的。但是启发式算法研究时间不长，各种启发式算法的孤立使用，也使得它们内在关系与特点不容易被看清。本文针对这些原因，结合大量关于算法的改进措施，以及运输优化模型的特点，讨论了关于算法本身的相关问题，以及运用到运输优化特定问题中的设计方案。1．1．2研究意义启发式算法作为现代优化计算方法，提出时间不长，就算法本身而言，还有很多值得优化和改进的理论基础，对于应用到各种特定模型的具体设计中，因仁者见仁智者见智，也难有统一的设计方案，这使得同一种算法思想编制的算法，收敛精度和收敛速度差异很大，在解决实际大型优化问题中所带来的经济、时间等资源的影响是无

3、可法估量的。运输优化问题大多属于大型优化问题，其实用性非常高，能够有效的得到更优化的结果带来的效应很显著，本论文从以上指导方针出发，即作出了算法的优化与综合，又联系实际引入常见运输优化问题的特定算法设计讨论，不论在理论研究还是实际应用都是具有一定的价值。1．2国内外研究现状1．2．1有关算法的研究现状自启发式算法提出至今，不仅大量的新算法在涌现，对于算法在实际问题中的应用也有非常丰富的研究成果。其中：Hopfield0,21(20世纪80年代)将人工神经网络成功地应用在组合优化问题，McClelland和Rumelhart。构造的多层反馈学习算法成功地解决了单隐含层认知网络的西南交通大学硕士研

4、究生学位论文第2页“异或”问题及其他的识别问题。Gloved4】(1986)首次提出禁忌搜索这一概念，进而形成一套完整的算法。成功运用到组合优化问题Itll5,61。邢文UIItn(1993)将模拟退火算法应用于Jobshop排序问题，算是我国早一批将启发式算法引入应用的研究人员。余春峰【8l(1998)关于遗传算法编码理论，做出十进制遗传算法的理论分析以及应用。张远福，时连强[91(2002)将启发式算法应用至运输优化问题——车流径路问题中。阿库林尼契夫【1o】(2000)有数学方法在铁路中的应用一作品，集成了很多铁路方向的问题应用现代数学手段的处理方式。我校学者彭其渊，闫海峰【111(20

5、05)将集装箱运输组织中的问题，用了多种现代式启发算法及改进算法进行详细研究，罗列出众多铁路运输组织模型，对学者今后的研究极具有参考价值。启发式算法在铁路运输中的研究远不仅此，几乎每年都有上百篇高质量的相关论文，在此由于篇幅与位置的安排，很难将其一一罗列，在之后的内容，还会进行介绍。1．2．2其他方向的研究现状关于模型的建立，算法收敛性的探讨，相关指标的制定等一系列研究，均是参考了大量的建模材料【12】、Markov性分析‘131、数学分析㈣、数值分析【15】、逼近论、高等代数‘161、离散数学【18】的相关文献并结合作者本身的原创性思考所建立，为了查阅文献的方便，会在相关章节分别给出。本文正

6、是有如此坚实的基础，为文章做出正确引路，才能做到一点微不足道的贡献。1．3主要研究内容及技术路线1．3．1主要研究内容本文的研究内容主要包括以下几部分：(1)绪论介绍本文的研究背景、研究意义，分析国内外相关资料与研究文献，对国内外的相关研究成果进行分析，介绍论文主要研究内容及技术路线。(2)模型与算法本章从总体介绍了算法与复杂优化问题的关系，介绍了领域，问题复杂性等概念为后文的叙述，做好铺垫工作。(3)三种常见的启发式算法介绍初步引入本文主要研究的三种启发式算法：模拟退火算法、遗传算法、蚁群算法的原理与流程，并对相关参数进行分析，对操作设计也进行了介绍。为后文进行算法西南交通大学硕士研究生学位

7、论文第3页的比较与分析做好铺垫。(4)三种算法的比较与分析对三种算法的收敛性，适用性，改进方向做出了比较与分析，提出了启发式算法“高效性”的界定，并研究了性能指标的合理设置。(5)启发式算法在运输优化问题中的相关问题讨论给出了常见的运输优化问题模型，并设计了带有宽度的船闸优化模型，简诉了驼峰三级减速优化模型的建模思想，将上文研究内容引入几个具有代表性的问题中，设计算法，对于能得到相关参数的问题，给