二维矩形装箱问题及其算法设计
发布时间:2017-11-25 06:10
本文关键词:二维矩形装箱问题及其算法设计
【摘要】:装箱问题是一类重要的组合优化问题,在众多行业中被广泛应用。如果我们对这类问题给出较好的装箱方案,它不仅有效地利用资源和节约成本,还会对各行业产生深远影响。装箱问题已被证明是NP-完备问题,具有很高的复杂性,因此有效的近似算法更多地被应用于求解装箱问题。 在本论文中,我们以二维矩形装箱问题为研究对象。受Lodi等人所设计的4-近似算法思想启发,我们在此算法基础上进行一些修正,即对摆放物品的条形箱子高度进行更细地划分和把物品划分为三类的情形。文中设计出解决二维矩形装箱问题的3-近似算法,并给出算法正确性证明、复杂性分析以及算法程序实现。
【学位授予单位】:云南大学
【学位级别】:硕士
【学位授予年份】:2015
【分类号】:O157
【共引文献】
中国期刊全文数据库 前10条
1 王波,高欣宝,刘保成,蔡军锋;基于提高运输能力的箱式包装设计[J];包装工程;2005年05期
2 李荣;;浅析解决装箱问题的三种启发式算法[J];福建电脑;2006年05期
3 王竹婷;邹乐;;基于层次聚类模型的矩形优化排样问题研究[J];重庆科技学院学报(自然科学版);2014年02期
4 程浩;刘心报;刘林;经怀明;;一种用遗传算法求解装箱问题的新编码方法[J];合肥工业大学学报(自然科学版);2006年02期
5 屈红文;;最小基数箱子覆盖问题[J];河南教育学院学报(自然科学版);2009年04期
6 王磊;马磊娟;;运用混合人工鱼群算法求解装箱问题[J];技术与市场;2009年07期
7 曹晶;郑巍;许e,
本文编号:1225031
本文链接:https://www.wllwen.com/kejilunwen/yysx/1225031.html