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

发布时间：2020-07-30 08:53

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

【相似文献】

相关期刊论文 前10条

1 李哲;夏立;吴正国;周卫平;;UPQC输出滤波器的优化设计[J];电力自动化设备;2011年07期

2 周海强;鞠平;宋忠鹏;金宇清;孙国强;;基于附加虚拟阻抗和蚁群优化算法的动态等效模型在线修正方法[J];中国电机工程学报;2011年19期

3 李慧;王来运;;基于混沌蚁群算法的电力短期负荷预测[J];北京信息科技大学学报(自然科学版);2011年04期

4 施雄华;陈根军;鞠平;张道农;;一种新的广义电力负荷模型及其工程应用[J];电力科学与技术学报;2011年02期

5 代启国;冀俊忠;刘椿年;;蚁群算法中基于知识引导的信息素控制策略[J];北京工业大学学报;2011年08期

6 ;[J];;年期

7 ;[J];;年期

8 ;[J];;年期

9 ;[J];;年期

10 ;[J];;年期

相关会议论文 前10条

1 熊伟清;魏平;;基于食物量分配的多种群二元蚁群优化算法[A];中国自动化学会控制理论专业委员会D卷[C];2011年

2 邓科;丛爽;;不同蚁群优化算法在C-TSP中的性能对比研究[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年

3 赵冬斌;易建强;;基于蚁群优化算法的机器人规划[A];第25届中国控制会议论文集（中册）[C];2006年

4 唐好选;曲毅;;蚁群优化算法在蛋白质构象预测问题中的应用[A];黑龙江省计算机学会2007年学术交流年会论文集[C];2007年

5 乔宗涛;谢军;谢明;;蚁群优化算法在无人机航路规划中的应用[A];中国航空学会控制与应用第十二届学术年会论文集[C];2006年

6 朱耀佳;吕勇哉;陈玉旺;潘常春;;蚁群优化方法在“炼钢-连铸-热轧”集成调度中的应用[A];中国计量协会冶金分会2007年会论文集[C];2007年

7 章小强;管霖;;基于蚁群算法的暂态稳定评估输入特征的识别[A];中国高等学校电力系统及其自动化专业第二十四届学术年会论文集（中册）[C];2008年

8 张伟;李守智;高峰;刘振山;;几种智能最优化算法的比较研究[A];第二十四届中国控制会议论文集（下册）[C];2005年

9 杨佳;许强;曹长修;;一种锅炉燃烧系统的新型优化算法[A];2007'仪表，自动化及先进集成技术大会论文集（二）[C];2007年

10 江珩;;强化集装箱安全管理 防止货车超偏载报警[A];2009年山东省科协学术年会胶济客运专线相关技术研讨会论文集[C];2009年

相关重要报纸文章 前10条

1 陈飞;张家港：进口牛皮集装箱 “毒气”屡屡超标[N];江苏法制报;2007年

2 沈湫莎;太仓港年吞吐百万集装箱[N];文汇报;2007年

3 尹建三 林国坚 张华坚;设备残损与包装密不可分[N];中国国门时报;2006年

4 杨朝春　侍晓宁;江苏口岸首次截获澳柪鲇琜N];中国国门时报;2007年

5 林若萍邋符传涛;当心熏蒸货物残毒带来安全隐患[N];中国国门时报;2008年

6 黄永卓;北海口岸化工贸易额创新高[N];中国化工报;2007年

7 罗敏;2008年图书市场聚焦“中国奇迹”[N];第一财经日报;2008年

8 陆军　　张强　　侍晓宁;狠抓进口木材检验检疫[N];中国国门时报;2005年

9 陈西艳;天津港见证我国集装箱运输升级[N];北方经济时报;2007年

10 吴荣光 漳关;移花接木 先行先试[N];闽南日报;2007年

相关博士学位论文 前10条

1 许瑞;基于蚁群优化算法的批调度问题研究[D];中国科学技术大学;2011年

2 李莉;柔性作业车间调度中的群智能优化算法研究[D];东北林业大学;2011年

3 庄晓东;多移动机器人运动控制策略的强化学习研究[D];中国海洋大学;2005年

4 燕忠;基于蚁群优化算法的若干问题的研究[D];东南大学;2005年

5 钟一文;智能优化方法及其应用研究[D];浙江大学;2005年

6 刘泓;交通仿真系统的并行计算、智能优化和混杂模型研究[D];浙江大学;2006年

7 李娜娜;仿生算法及其在专家分配问题中的应用[D];天津大学;2008年

8 薛俊芳;机电产品拆卸过程建模与规划研究[D];哈尔滨工程大学;2008年

9 白保存;考虑任务合成的成像卫星调度模型与优化算法研究[D];国防科学技术大学;2008年

10 龚毅光;汽车产品审核系统中人工智能技术的应用研究[D];南京航空航天大学;2009年

相关硕士学位论文 前10条

1 袁军良;基于蚁群优化算法的集装箱装载问题求解[D];宁波大学;2011年

2 李郭记;基于NCL的集装箱单箱装载优化研究[D];大连海事大学;2010年

3 王敏;基于蚁群优化算法的齿轮箱故障诊断研究[D];中北大学;2010年

4 张辉;基于蚁群算法的港口物流问题的研究[D];辽宁科技大学;2008年

5 李静宜;蚁群神经网络的研究及其应用[D];江苏科技大学;2010年

6 张泽彬;基于混合启发式蚁群优化算法在双层车辆路径问题的研究[D];广东工业大学;2012年

7 何雪海;蚁群优化算法及其应用研究[D];重庆大学;2011年

8 吴虎发;蚁群优化算法在求解最短路径问题中的研究与应用[D];安徽大学;2012年

9 付杰;基于GPU的并行蚁群优化算法的研究与实现[D];中国舰船研究院;2011年

10 刘好斌;蚁群优化算法的改进及其在TSP中的应用[D];重庆大学;2010年

本文编号：2775311