集装箱装载问题的启发式优化算法

《集装箱装载问题的启发式优化算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第13卷第3期山东交通学院学报Vol.13No.32005年9月JOURNALOFSHANDONGJIAOTONGUNIVERSITYSep.2005集装箱装载问题的启发式优化算法陈建岭(山东交通学院交通工程系,山东济南250023)摘要:集装箱装载是个多约束的复杂组合优化问题,属于NP-Hard问题,其精确求解是很困难的,一般多用启发式方法来近似解。针对背包型集装箱装载问题提出了一种启发式算法,该算法采用了新的“砌墙”机制和货物组对策略,通过递归寻优得到解。通过实例说明该算法具有较好的有效性和实用性。关键词:集装箱

2、装载;背包;启发式算法中图分类号:U492.3文献标识码:A文章编号:1672-0032(2005)03-0053-04所谓集装箱装载问题是指如何将货物按某种方式装入集装箱,从而最大限度地提高集装箱的空间能力。集装箱装载问题可以划分为不同的分支。Dyckhoff将集装箱装载问题分为3/B/O和3/V/I,也即单集装箱和多集装箱的装载。Bortfeldt则根据货物的差异,将装载的盒子(货物)分为同类、弱异类、强异类,同类是指盒子都相同的情况,弱异类指盒子的种类比较少的情况,而强异类指盒子的种类很多的情[1]况。根据目标

3、函数和约束条件的差异,集装箱装载问题可以概括为几种变化形式:条状装载,其目标函数为货物装载后占用集装箱的长度为最小;背包形式装载,其目标函数为集装箱的空间利用率最大;同箱型多箱装载,其目标函数为所用的集装箱数量最少;多箱型多箱装载,其目标函数为集装箱的运输成本最小。从本质上讲,集装箱装载问题属于三维空间剪裁与装填问题,该类问题被认为是NP-Hard问题,难[2-5]于精确求解,目前多用启发式方法寻找近似最优解,本文针对背包型集装箱装载问题提出了一种启发式算法,经算例验证取得了较好的效果。1问题描述本文叙述的问题属于将

4、给定的一些矩形盒子装入给定大小的集装箱从而使集装箱的空间利用率最大之情形,也即背包型集装箱装载问题。为便于研究,做如下假定:1)集装箱的长、宽、高分别代表笛卡尔坐标系的X,Y,Z轴方向,坐标原点位于前端左下角(集装箱门在后部),如图1所示。2)货物装在长方体的盒子内,盒子本身的挤压变形可以忽略。3)货物放置方向必须与坐标轴平行或正交,货物不能交迭放置,不得悬置于集装箱的尺寸范围,不同类型货物可以相邻摆放。4)货物可以正交旋转。5)假设每个货物图1集装箱坐标系代表的利润与其体积相当。基于以上假设,可以得到该背包问题的数

5、学模型n∑wihidixii=1maxF=,V(1)nst.∑wihidixi

6、,装箱2启发式算法[6]对于集装箱装载问题,货物的装填方式比较经典的是“砌墙”方式,即将集装箱沿长度方向(也即X坐标轴方向)构建一系列具有不同厚度的货物“层”。本算法依然采用这种方式,不过对于每个货物“层”将其划分为一系列的垂直或水平的货物“条”,从而将每个货物“条”的装填转化为求解容量等于货物“条”长度的背包问题。对于货物层厚度和货物条宽度,采用了一种新的有限枚举机制,另外为了保证货物层表面的平整性采取了货物合并策略以减少空间碎片产生。2.1选择货物“层”厚度和货物“条”宽度货物层厚度和货物带宽度的选择对于集装箱空

7、间利用率有很大的影响,理想的情况就是考虑所有可能的层厚和带宽,但是这样所需运算量非常巨大。为了降低运算的复杂性,该算法采用了层厚和带宽有限枚举策略,即对于每个搜索节点只考虑其一部分子节点。对于每个节点只考虑M1个货物“层”厚度和M2个货物“条”宽度,算法的运算性能依赖于这些选择尺寸是否适宜。因此,考虑以下方法:1)从未装填货物中选择出现频率最大的尺寸,这种选择具有较大可能得到规则的货物“层”。2)选择出现频率递增的最大尺寸,每次从剩余货物选择尺寸最大的货物使其出现频次大于上一个被选的货物的出现频率。对于每个搜索节点找

8、出M1个层厚度及M2个带宽,就可以应用求解背包问题的方法进行货物“条”的配装。2.2货物组对方法通过货物组对可以得到较为规则的货物层,减少空间碎片,改善空间利用率。其步骤如下:首先,调整货物尺寸使dj