蚁群算法在物流系统中的应用研究

论文摘要

人们生活的现代社会是由计算机信息网络、电话通信网络、物流分派网络、运输服务网络等等各种网络组成的一个复杂的网络系统。随着研究对象的日益复杂化,一些传统的基于精确模型的确定性优化算法在解决具体问题时都遇到了极大的困难,一些学者从生物的生活习性中受到启发,提出了许多仿生类启发式智能优化算法。蚁群优化算法ACO(Ant ColonyOptimization)则是其中一种,特别适合于解决一些组合优化问题。该算法由Dorigo等人于20世纪90年代初提出以来,至今已引起越来越多人们的注意而发展出许多后续对其改进的算法,并且在很多领域得到了广泛的应用。由于蚁群优化算法是模拟蚂蚁觅食的习性,采用的是分布式并行计算机制,具有较强的鲁棒性并易与其他方法结合的特点,但也和其他进化算法一样存在计算量大、搜索时间长、易陷入局部最优的突出缺陷,针对算法的固有缺陷,后续很多学者对蚁群算法进行了改进。本文对蚁群算法及其在物流系统优化中的应用进行了研究,其主要研究内容如下:在物流系统优化两类难题中,提出用蚁群算法来求解配送中心选址的实际问题,针对该类组合优化问题,设计了一个改进算法,充分利用蚁群算法的并行机制和正反馈机制,引入局部更新规则增强正反馈作用,加快搜索速度,在全局更新中增加本轮最优路径上信息浓度,并在迭代后期引入动态平滑信息素轨迹机制,增大那些低信息轨迹被选择的概率,增强算法的搜索能力,通过对实例问题的求解,验证了改进算法的有效性,找到了最优解组合。针对第二类问题的TSP模型实质和蚁群算法在解决该类问题中的固有不足,本文提出了一种具有奖罚机制的分组蚁群算法。即对蚂蚁进行分组,利用蚂蚁组之间合作和组内蚂蚁相遇合作思想,采用全局与局部更新规则和改进MMAS策略,并引入奖罚机制对信息素进行更新。仿真实验数据表明改进后的算法避免了算法停滞而陷入局部最优的现象,加快了搜索速度,找到的解也较优,取得了算法时间和优化性能之间的平衡,提高了算法的性能。在物流系统供应链网络优化中出现的需寻求最优斯点或其组合来构造斯坦纳最短树的问题,传统的算法难以解决此类NP难题,本文探讨了蚁群算法的求解方法,用改进后蚁群算法结合MST算法的模式来解决,实例验证它是有效的。

论文目录

• 摘要
• ABSTRACT
• 第1章 引言
• 1.1 选题研究背景及意义
• 1.1.1 选题背景
• 1.1.2 研究意义
• 1.2 蚁群算法国内外研究与发展
• 1.2.1 蚁群算法国外研究状况
• 1.2.2 蚁群算法国内研究状况
• 1.2.3 蚂蚁系统及其发展
• 1.2.4 小结
• 1.3 论文的主要工作与组织结构
• 第2章 蚁群算法与网络优化算法
• 2.1 基本蚁群算法（ACO）
• 2.1.1 ACO优化机理
• 2.1.2 ACO优化模型
• 2.1.3 复杂度分析及性能评价指标
• 2.2 网络图算法
• 2.2.1 图的遍历搜索、最短路径与流的算法
• 2.2.2 最小代价生成树
• 2.2.3 斯坦纳树
• 2.3 几种主要的元启发式进化算法
• 2.3.1 遗传算法
• 2.3.2 人工神经网络
• 2.3.3 禁忌搜索算法
• 2.3.4 粒子群算法
• 2.4 蚁群算法的优势、特点及应用
• 第3章 物流系统中选址与路径寻优问题的蚁群算法求解
• 3.1 物流概述及物流系统
• 3.2 物流实践中需要解决的问题
• 3.3 选址问题
• 3.3.1 数学模型描述
• 3.3.2 蚁群算法设计
• 3.4 算例分析
• 3.5 路径寻优问题
• 3.6 传统算法、ACO、本文改进算法比较
• 3.6.1 传统算法与 ACO
• 3.6.2 本文改进算法
• 3.7 实验比较
• 3.8 本章小结
• 第4章 物流系统中斯坦纳最短树问题的蚁群算法应用
• 4.1 供应链网络中的斯坦纳树
• 4.1.1 问题的提出
• 4.1.2 引入斯坦纳树
• 4.2 斯坦纳最短树的蚁群算法求解
• 4.2.1 SMT求解模式
• 4.2.2 算法设计
• 4.3 算例分析
• 4.4 本章小结
• 第5章 总结
• 5.1 论文的总结
• 5.2 不足及后续展望
• 致谢
• 参考文献
• 附录
• 攻读学位期间的研究成果