现实约束条件下的集装箱多箱装载优化

《现实约束条件下的集装箱多箱装载优化》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、现实约束条件下的集装箱多箱装载优化１郭贝贝，靳志宏，李肇坤(大连海事大学交通运输管理学院,大连116026)摘要：针对现实约束条件下的复杂集装箱多箱装载优化问题，提出了一个全新的遗传算法与启发式算法相结合的交互式混合算法。该算法在维持较高的集装箱空间利用率的同时，满足了货物承载能力、集装箱重心稳性以及混载等现实约束。通过基准测试问题的数值实验，表明所提出算法产生的装箱方案优于基于MichaelElay算法的装箱方案。关键词：多箱装载问题；交互式算法；预分配策略；现实约束ResearchonMultipleContainersLoadingProblemWith

2、PracticalConstraintsGUOBeibei，JINZhihong，LIZhaokun(TransportManagementDepartment,DalianMaritimeUniversity,Dalian116026,China)Abstract:Thispaperfocusesonthecomplicatedmultiplecontainersloadingproblem(CMCLP).Bycombininggeneticandheuristicalgorithms,ahybridalgorithm,whichnotonlygenerat

3、esefficientloadingpatternsbutalsosatisfiessomepracticalconstraintssuchascargoesbearingcapacity,containerloadingstabilityandmixedloadingrestrictionetc,isputforwardtosolveCMCLP.NumericalexperimentsfromthebenchmarkproblemshaveshownthattheproposedalgorithmissuperiortoMichaelElay’salgori

4、thms.Keywords:MultipleContainerLoadingProblem;HybridAlgorithm;Pre-AllocationStrategy;PracticalConstraints0.引言装箱问题是一类复杂的组合优化问题，有很强的应用价值，在运输、调度、排产等领域有着广阔的应用前景。装箱问题即为物体在三维空间的摆放优化问题，按照使用容器数量来划分，装箱问题可以分为单箱装载问题和多箱装载问题。目前，国内外学者对单箱装载问题做了大量的研究.George和Robinson[1]采用构造型启发式算法来解决集装箱装载问题，在算法中他们首次给

5、出了“层”的概念；在Loh和Nee[2]的算法中，“层”以水平的形态出现，即由下而上完成装箱工作，为了构建平坦的截面，算法按货物的高度设置优先级别；DavidPisinger[3]针对背包装箱问题（假设货物的价值等于其体积），基于“层”设计了一种启发式算法，其基本思想是：将整个集装箱空间分成若干垂直的层，再将层分成若干水平或垂直的带，相应的以集装箱的宽或者高为背包能力、所有未装入物品为对象，按项目基金：国家自然科学基金资助项目（70572104）作者简介：郭贝贝(1985-),女，山东烟台人，硕士研究生，研究方向为物流工程与管理，（E-mail）gbb_74@

6、163.com;靳志宏(1963-)，男，辽宁沈阳人，日本名古屋工业大学博士，教授，博导，研究方向为优化技术与应用、生产与运作管理、物流与供应链管理，（E-mail）jin_zhi_hong@yahoo.com.cn;李肇坤(1980-)，男，山东郓城人，博士研究生，研究方向为物流系统规划与管理，（E-mail）lzkyxh@126.com;背包问题填充这些带，并最终获得全局最优解，其中，合适的层的深度和带宽通过分支定界法获得，在这个过程中包括了多种排序和选择的规则，这种方法集装箱的利用率较高，但货物稳定性很差，上层货物经常得不到下面货物的完全支撑；姜义东[4

7、]采用三叉树的数据结构来处理空间，该算法采用优先放置体积大的物体策略，每次都先把最大物体放入剩余空间虽然这样划分剩余空间会减少问题的复杂性，但是划分后的剩余空间比较“零碎”；靳志宏等[5]在启发式算法中引入空间分割与空间合并规则，有效地减少了狭长空间的产生，大大提高了集装箱的空间利用率。对于多箱装载问题，尤其是多约束条件的复杂多箱装载问题，研究的比较少，Ivancic[6]和Mohanty[7]针对单一种类容器的情况，提出了应用连续性策略的方法。这种策略一个很明显的缺陷是，大的或不易摆放的物品经常被留在最后摆放，从而导致最后使用的容器利用率很低；Michael

8、Eley[8]采用同时性策略，将单箱问