利用机器学习改进列生成算法求解多集装箱装载问题

论文摘要

将各种尺寸数量的箱子全部装载到不同尺寸的集装箱中,并使得总运输成本最小的问题叫做成本最小化的多箱型多集装箱装载问题(MCLCMP)。包括多集装箱装载问题(MCLP)在内的许多组合优化问题都可以被描述为集合覆盖模型。由于其复杂性,决策过程往往分为两个阶段:第一阶段忽略子决策细节,粗略估计全局决策;第二阶段考虑所有细节,生成完整的方案。此类问题通常使用列生成(CG)技术进行求解,CG的有效性在很大程度上取决于定价子问题的解决效率。我们的CG策略是:1.对定价子问题进行松弛变换;2.训练机器学习模型以预测松弛变换与其真实解决方案之间的差异;3.根据预测将松弛变换转化为真实解决方案。每个企业的产品规格不同、运营数据具有独特性,而机器学习可以挖掘数据背后的信息,因此本文通过机器学习从累积的历史运营数据中提取有价值的信息,来提高CG对MCLP的有效性。为第一阶段的全局决策分配更多时间,使它能够更快速地锁定高质量的解空间,最终提高优化算法的整体性能。同时改进后的优化算法在应用于具体企业时能达到更高的效能,这是传统的优化算法无法做到的。

论文目录

• 摘要
• abstract
• 第一章 绪论
•   1.1 研究背景
•   1.2 论文研究意义
•   1.3 利用机器学习提升优化算法的研究综述
•   1.4 研究内容及论文框架
• 第二章 原型列生成算法
•   2.1 集装箱装载问题
•   2.2 集合覆盖模型
•   2.3 列生成技术
•   2.4 原型列生成算法
•   2.5 利用机器学习对原型列生成算法改进思路
•   2.6 本章小结
• 第三章 利用机器学习求解预测子问题
•   3.1 定义预测子问题
•   3.2 数据特征项
•   3.3 数据生成
•   3.4 机器学习模型
•   3.5 模型交叉检验
•   3.6 本章小结
• 第四章 利用机器学习改进原型列生成算法的实现
•   4.1 改进后算法的整体框架
•   4.2 具体改进步骤
•   4.3 本章小结
• 第五章 求解多箱型多集装箱问题
•   5.1 实验来源
•   5.2 实验环境与参数设置
•   5.3 交叉检验
•   5.4 算法各改进的评估
•   5.5 实验结果
•   5.6 本章小结
• 结论与启示
• 参考文献
• 攻读硕士学位期间取得的研究成果
• 致谢
• 附件

文章来源

类型: 硕士论文

作者: 马宇彤

导师: 朱文斌

关键词: 多集装箱装载问题,原型列生成,机器学习,集合覆盖模型

来源: 华南理工大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 华南理工大学

分类号: TP181;O225

DOI: 10.27151/d.cnki.ghnlu.2019.003293

总页数: 88

文件大小: 3363K

下载量: 159