基于蚁群算法的铁路车辆路径问题研究

论文摘要

车辆路径问题是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究的一个热点问题。开放式车辆路径问题是另一种类型的车辆路径问题,有着广泛的应用前景。它与基本的车辆路径问题的主要区别是不要求车辆完成运输任务后必须返回原出发点。蚁群算法是一种新的仿生类算法,属于随机搜索算法,多年来的研究已显示出蚁群算法在求解复杂优化问题方面的优越性。蚁群算法也存在一些缺陷,如收敛速度慢,容易陷入局部最优解等。本文对带约束条件的开放式车辆路径问题从理论上进行研究,实现了铁路运输矢量图的分层显示,约束条件主要考虑了铁路运输网络的系统最优平衡,也就是全局最优,而并非仅仅是单个用户的路径寻优,使研究内容更具有实际应用价值。通过实验对比了蚁群算法和其它经典的人工智能算法后,发现无论是获得的解的质量还是迭代次数蚁群算法都明显优于其它人工智能算法,显示了其在解决复杂优化问题方面的竞争力。针对蚁群算法的缺点,很多学者提出了改进蚁群算法,本文分别编程实现了蚁群算法和典型的改进蚁群算法,通过实验观察到改进蚁群算法的性能明显提高,然后借鉴了某些改进蚁群算法的思想并与带约束条件的铁路VRP相结合对蚁群算法进行了新的改进,使其在求解问题时结果更好、速度更快。最后针对本文研究的实际问题,对蚁群算法中各参数的选取规则进行了归纳。实验表明用改进蚁群算法求解带约束条件的铁路VRP是有效的,这一成功尝试再次表明蚁群算法在优化领域具有强大竞争力。本文在研究中考虑了能获得系统最优平衡的约束条件,使研究内容更贴合铁路运输的实际,不仅具有理论研究意义也富有实际应用价值。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 选题背景和研究意义
• 1.2 国内外研究现状
• 1.3 本文的主要内容
• 第2章 VRP的提出及各类VRP的算法
• 2.1 VRP的提出
• 2.2 VRP的分类
• 2.3 求解VRP的算法
• 2.3.1 精确算法
• 2.3.2 人工智能算法
• 2.4 开放式车辆路径问题
• 第3章 基本蚁群算法及其实现
• 3.1 蚁群算法的提出
• 3.2 蚁群算法的基本原理
• 3.3 蚁群算法的应用
• 3.4 蚁群算法的特点
• 3.4.1 蚁群算法的优点
• 3.4.2 蚁群算法的缺点
• 3.5 蚁群算法模型
• 3.5.1 TSP问题
• 3.5.2 蚁群算法模型
• 3.6 蚁群算法与其它人工智能算法的比较
• 第4章 蚁群算法的改进及实现
• 4.1 蚁群算法的改进
• 4.1.1 带精英策略的蚁群算法
• 4.1.2 基于优化排序的蚁群算法
• 4.1.3 Ant-Q System
• 4.1.4 最大-最小蚁群算法
• 4.1.5 最优-最差蚁群算法
• 4.1.6 混合蚁群算法
• 4.2 编程实现典型改进蚁群算法及结果比较
• 4.2.1 三种模型的实验结果
• 4.2.2 基本蚁群算法与Ant-Q System、最大-最小蚁群算法、最优-最差蚁群算法的实验结果
• 第5章 改进蚁群算法求解带约束条件的铁路 VRP
• 5.1 VRP问题模型
• 5.2 图论基础即图的存储结构
• 5.3 铁路运输网络图的分层显示
• 5.4 蚁群算法设计
• 5.4.1 线路构造
• 5.4.2 信息素的更新
• 5.4.3 约束条件
• 5.5 实验与结果
• 5.6 算法中的参数选择
• 结论与展望
• 1、结论
• 2、展望
• 致谢
• 参考文献
• 附录
• 攻读硕士学位期间发表的论文及科研成果