组合装箱问题模型与算法研究

《组合装箱问题模型与算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学硕士学位论文组合装箱问题模型与算法研究硕士研究生：江瀑学号：1120209391导师：陈峰副教授申请学位：工学硕士学科：工业工程所在单位：机械与动力工程学院答辩日期：2015年2月授予学位单位：上海交通大学DissertationSubmittedtoShanghaiJiaoTongUniversityfortheDegreeofMasterResearchonModelingandAlgorithmforCombinatorialBinPackingProblemCandidate：JIANGPuStudentID:1120209391S

2、upervisor：AssociateProf.CHENFengAcademicDegreeAppliedfor：MasterofEngineeringSpeciality：IndustrialEngineeringAffiliation：SchoolofMechanicalEngineeringDateofDefence：February,2015Degree-Conferring-Institution：ShanghaiJiaoTongUniversity上海交通大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研

3、究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的研宄做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：>〇(^年>月4日上海交通大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

4、保密□，在_年解密后适用本授权书。本学位论文属于不保密Z(请在以上方框内打“V”）学位论文作者签名：ivi指导教师签名:日期：>〇^年>月Z日日期：>心年>月4日上海交通大学硕士学位论文组合装箱问题模型与算法研究摘要本文研究近年新提出的汽车物流组合装箱问题。该问题在国内汽车物流领域实际存在，并且伴随着中国汽车工业的迅速发展，凸显出来，对物流运输公司造成了很大的困扰。因此，针对性的解决该问题具有非常重要的现实意义。通过研究该问题，提出有效的解决方案，并应用到实践中，对于汽车物流来说，能够非常有效的降低成本并且提高效率。首先，本文在研究其他经典装箱问题的基

5、础上，将组合装箱调研与实践中遇到的目标需求与操作要求进行分析与整理，将其转化为问题的目标与约束，形成完整的问题描述，并且建立混合整数规划模型。其次，为了快速、有效的求解该问题模型，本文设计了两种算法，一种是基于分枝定界思想的精确求解算法，针对本文所研究的问题以及模型，分别给出了分枝定界算法的分枝策略、上界、下界、搜索模式和支配规则,并且给出了详细的算法流程。另一种算法则是基于贪婪思想的启发式算法。本文详尽介绍了贪婪算法的基本思想以及算法流程。I摘要最后，通过数值实验验证所提出模型与算法的有效性。本文使用ILOGCPLEX优化工具和设计的算法对模型进行求

6、解，进行数值实验，通过比较一些指标，分析实验结果来对模型的有效性以及设计的算法的高效性进行验证。同时，对组合装箱调度的实际数据进行实例验证，通过与实际人工调度的结果比较待装载商品车完成数量以及高紧急程度的商品车的完成比例，证明建立的模型以及算法较人工调度的优势，从而验证了实际应用价值。本文通过构建数学模型、设计有效算法，为组合装箱问题提供了高效的、智能化的解决方案。通过数值实验表明，本文研究成果可直接应用于实践活动，对组合优化的理论与方法的发展具有一定的推动作用。关键词：混合整数规划模型、组合装箱问题、分枝定界、贪婪算法II上海交通大学硕士学位论文Re

7、searchonModelingandAlgorithmforCombinatorialBinPackingProblemAbstractThispaperfocusesonnewcombinatorialbinpackingproblemrecently.Thisproblemisarealprobleminautomobilelogistics.WiththedevelopmentofChinaautomobileindustry,thisproblemhasaseriousimpactinlogisticscompanies.So,doingre

8、searchintothisproblemandprovidingsolutionscancu