论文摘要
装箱问题是一个经典的组合优化问题，受到众多学者的关注，在过去曾经被广泛的研究，并且早已在实际生产、生活中显示出重要的应用价值。但是在实际生产和运输过程中，各种装箱问题常常要比经典的装箱问题更复杂一些，常常带有一些其他的约束，增加了问题的难度。这篇文章中我们将探讨两个装箱问题的变形-在颜色约束为2和任意颜色约束下染色装箱问题的箱子数目极小化。我们的装箱问题源于网络中的实际应用和一些生产运输的需要。比如在网络数据传输中，我们需要将数据封装为数据包进行发送。在这些应用中，每种物品代表不同的来自单一用户（或者单一任务）的数据。通过极小化箱子的使用数目，我们可以增加网络的使用效率。本文中我们考虑极小化箱子颜色数差问题的对偶问题及其子问题。我们考虑在有颜色约束的情况下极小化箱子数量，讨论了颜色约束为2的染色装箱问题，证明其是NP完全的，给出一个线性的近似算法，并证明他的近似比为4／3。最后我们讨论了颜色约束为任意的情况，并给出一个启发式算法。
论文目录
相关论文文献
- [1].考虑货物冲突关系的二维装箱问题研究[J]. 宁波大学学报(理工版) 2020(02)
- [2].圆形装箱问题[J]. 城市环境设计 2020(03)
- [3].箱有长宽高 万物可装箱[J]. 中小学数学(初中版) 2020(Z2)
- [4].基于图着色模型的冲突装箱问题启发式算法[J]. 运筹与管理 2013(05)
- [5].基于混合模拟退火算法的多约束装箱问题研究[J]. 无线互联科技 2019(23)
- [6].面向梯形箱子的三维装箱问题算法研究[J]. 微型机与应用 2015(09)
- [7].三维货物装箱问题的研究进展[J]. 铁道科学与工程学报 2015(05)
- [8].三维装箱问题的启发式算法[J]. 物流技术 2012(03)
- [9].模拟退火算法在装箱问题中的应用[J]. 电脑知识与技术 2010(05)
- [10].一种尺寸可变的装箱问题的在线近似算法[J]. 许昌学院学报 2010(05)
- [11].基于遗传算法的港口装箱问题的研究[J]. 电脑知识与技术 2009(36)
- [12].一种尺寸可变的装箱问题的在线近似算法[J]. 科技创新导报 2008(04)
- [13].摆放约束的二维装箱研究[J]. 装备制造技术 2020(07)
- [14].二维一刀切装箱问题的两阶段启发式算法[J]. 计算机集成制造系统 2012(09)
- [15].二维离线非旋转装箱问题的一个混合算法[J]. 计算机工程与应用 2011(07)
- [16].运用混合人工鱼群算法求解装箱问题[J]. 延安职业技术学院学报 2009(03)
- [17].基于混合遗传算法的多品种货物装箱问题研究[J]. 包装与食品机械 2020(03)
- [18].基于禁忌搜索算法的二维装箱问题研究[J]. 山西能源学院学报 2017(03)
- [19].基于“5块”法的二种货物二维装箱优化模型构建与实例[J]. 宁波工程学院学报 2019(02)
- [20].装箱问题在物流领域的研究回顾与分析——基于美国科学情报研究所科研数据库(Web of Science,1989～2018)的科学计量分析[J]. 科技促进发展 2019(07)
- [21].基于启发式拟人算法的三维装箱问题求解[J]. 物流技术 2013(05)
- [22].求解三维装箱问题的多层启发式搜索算法[J]. 计算机学报 2012(12)
- [23].多约束三维装箱问题的混合遗传算法[J]. 现代计算机(专业版) 2011(Z1)
- [24].二维矩形条带装箱问题的底部左齐择优匹配算法[J]. 软件学报 2009(06)
- [25].三维装箱问题的智能启发式算法[J]. 中南林业科技大学学报 2009(03)
- [26].关于染色装箱问题的一个近似算法[J]. 科技信息 2009(28)
- [27].二维装箱问题非线性规划模型和算法[J]. 大连理工大学学报 2008(02)
- [28].平面二维装箱问题“5块法”规划解法[J]. 宁波工程学院学报 2018(03)
- [29].带冲突关系装箱问题的启发式求解算法[J]. 运筹与管理 2015(02)
- [30].三维装箱问题的模型与改进遗传算法[J]. 数学的实践与认识 2010(02)