基于蚁群优化算法的集装箱装载问题求解

论文摘要

集装箱装载问题（Container Loading Problem, CLP）是物流配送的重要环节,其方案的优劣对整个物流系统的效率以及运输成本有着重大的影响,但CLP是一个具有复杂约束条件的组合优化问题,在理论上属于NP-hard问题,需要设计性能良好的算法进行求解。蚁群优化算法（ACO）是一种新兴的智能优化算法,特别适合求解困难的组合优化问题。在旅行商、车辆调度等问题中得到广泛的应用,取得良好的效果。因此,本文尝试采用蚁群优化算法进行求解CLP。设计了基于食物量分配的多种群二元蚁群优化算法（FMPBACO）,算法中根据食物量决定种群中蚂蚁的数量以及种群的生灭,种群之间通过信息素混合相互学习。同时分析了算法的复杂度,并应用在0/1多背包问题,通过SAC-94 Suite测试集的求解表明算法具有良好的性能。针对CLP的特点,定义了空间三叉树,对可利用空间采用三叉树划分策略。针对弱异类集装箱装载问题,设计了一种结合启发式规则的混合FMPBACO进行求解,算法中先利用FMPBACO确定预备装入货物集,再用启发式规则决定货物的装入优先级顺序,同时分析了算法的复杂度。通过两个弱异类实例的测试,表明算法得到的装载方案有较高的空间利用率。针对强异类集装箱装载问题,设计了一种混合蚁群算法。算法中搜索空间分为货物摆放的优先序列和货物摆放的状态两部分;引入体积大的货物优先放入的启发式规则;将蚂蚁搜索得到的序列与历史最优序列进行交叉,取三者最优序列作为该蚂蚁的搜索路径;在更新信息素时,采取两种挥发系数更新信息素以避免信息素过快饱和,同时分析了算法的复杂度。通过三个强异类实例的测试,表明算法得到的装载方案也有较高的空间利用率。

论文目录

• 摘要
• Abstract
• 引言
• 1 绪论
• 1.1 背景
• 1.2 集装箱装载问题概述
• 1.3 切割与布局问题概述
• 1.3.1 切割与布局问题
• 1.3.2 切割与布局问题常用算法
• 1.4 选题的潜在意义
• 1.5 内容提要
• 2 集装箱装载问题算法综述
• 2.1 集装箱装载问题数学模型
• 2.2 集装箱装载问题算法综述
• 2.2.1 启发式算法
• 2.2.2 智能优化算法
• 2.2.2.1 遗传算法
• 2.2.2.2 模拟退火算法
• 2.2.2.3 禁忌搜索算法
• 2.3 本章小结
• 3 蚁群算法
• 3.1 蚁群的抽象
• 3.2 基本蚁群算法的机制原理
• 3.3 基本蚁群优化算法的模型
• 3.4 基本蚁群算法的实现步骤
• 3.5 基本蚁群算法复杂度的分析
• 3.6 蚁群算法的优缺点
• 3.7 蚁群优化算法研究现状
• 3.7.1 蚁群优化算法改进
• 3.7.2 蚁群优化算法收敛性研究
• 3.7.3 蚁群优化算法应用研究现状
• 3.8 本章小结
• 4 基于食物量分配的多种群二元蚁群优化算法
• 4.1 二元蚁群算法
• 4.2 FMPBACO 算法描述
• 4.3 0/1 多背包问题求解
• 4.4 本章小结
• 5 弱异类集装箱装载问题求解
• 5.1 空间三叉树定义与装载策略
• 5.1.1 空间三叉树定义
• 5.1.2 装载策略
• 5.2 目标函数及约束条件
• 5.3 算法描述
• 5.3.1 预备装入货物集的选择
• 5.3.2 启发式装箱规则
• 5.3.3 混合FMPBACO 算法步骤
• 5.3.4 算法时间复杂度分析
• 5.4 实例测试
• 5.5 本章小结
• 6 强异类集装箱装载问题求解
• 6.1 编码和解码
• 6.2 算法描述
• 6.2.1 序列选择
• 6.2.2 交叉操作
• 6.2.3 信息素更新
• 6.2.4 算法步骤
• 6.2.5 算法时间复杂度分析
• 6.3 实例测试
• 6.4 本章小结
• 7 结论
• 7.1 总结
• 7.2 研究展望
• 参考文献
• 在学研究成果
• 致谢