安多集装箱装载问题启发式算法研究及应用

　　安多集装箱装载问题启发式算法研究及应用安多集装箱装载问题启发式算法研究及应用 山东大学 硕士学位论文 安多集装箱装载问题启发式算法研究及应用 姓名:陈建岭 申请学位级别:硕士 专业:机械电子工程 指导教师:张强 20040510山东大学硕士学位论文 摘要 单元装载既是一种现代的运输理念又是扩大交易量和市场份额的有效客户响 应方式,在物流业有着重要的意义。本文试图从单元装载的角度系统地研究货物 装载问题。 本文首先阐述了单元装载的体系并提出了几点改进单元装载设计的策略,然 后重点研究了安多集装箱装载问题。安多集装箱既是一种典型的集装器具又兼具...

　　安多集装箱装载问题启发式算法研究及应用 姓名:陈建岭 申请学位级别:硕士 专业:机械电子工程 指导教师:张强 20040510山东大学硕士学位论文 摘要 单元装载既是一种现代的运输理念又是扩大交易量和市场份额的有效客户响 应方式,在物流业有着重要的意义。本文试图从单元装载的角度系统地研究货物 装载问题。 本文首先阐述了单元装载的体系并提出了几点改进单元装载设计的策略,然 后重点研究了安多集装箱装载问题。安多集装箱既是一种典型的集装器具又兼具了载运工 具的功能,提高安多集装箱的空间利用率,无疑会节约大量的运输费用。因此,集装 箱装载问题受到业界与学术界的重视。安多集装箱装载的关键是根据某种算法生成一 个科学合理的装载

　　,然而目前还没有一种装载算法堪称完美。本文在深入讨 论了集装箱装载问题的渊源、分类和国内外研究现状的基础上,针对单集装箱装 载情况提出了有限树搜索启发式

　　。该方法采用了砌墙式层构建机制,将问题 分解为沿集装箱深度方向构造一系列的“层”,每个“层”又可分解为许多垂直的 “带”,对于“带”的装载转化为背包问题求解。层的厚度和带的宽度选择采用了 分支定界和.策略,对于每个节点只考虑一部分分支,同时为了得到较平整的 层面,将货物按一定规则组对匹配以减少空间浪费。根据测试结果表明,该方法 适用于弱异类和强异类的货物装载情形,既有良好的运算性能又能得到很理想的 优化解,对于实际装载作业具有较强的指导性,也为今后该问题的进一步研究提 供了借鉴。 最后本文探讨了物流电子商务环境下货物信息配载的实现途径,提出了几种 交易方式,并介绍了佳怡物流管理系统的开发过程。 关键词:单元装载:集装箱装载:树搜索;启发式;背包装载山东大学硕士学位 论文, ? , ,【. ’ . . . ,, .. ,, ., , . ,. , . . , . , ?, .. . ,.; ; ;; 原创性声明 本人郑重声明:所星交的学位论文,是本人在导师的指导下,独 立进行研究所取得的成果。除文中已经注明引用的内容外,本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体,均已在文中以明确方式标明。本声明 的法律责任由本人承担。 彰勉必 日 论文作者签名: 期: 坐盘盟:目 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定,同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版,允许论 文被查阅和借阅;本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索,可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 保密论文在解密后应遵守此规定 日 论文作者签名:恤: 导师签名:荔签绉 期:鲨绰望:塑山东大学硕士学位论文 第章绪论 .课题的背景 运输是物流活动的一个重要内容,在整个物流成本中占有很大的比例,是影 响 物流成本一项重要因素。在美国,运输费占的比重大约为%,大于库存费 用%的比重】。日本曾经对一部分企业进行调查,在商品从产品到消费者手中 所 花费的物流费用中,运输费占的比例为%.我国商业部早在年代对商品流通费 和物流费也进行了一些调查和分析,商品流通费占商品销售额的.%,其中:物 流费用??运输、保管、包装费三项占%,商品损耗占.%,合计为.%.【】 由此可见,应当努力采取各种措施降低运输费用,从而降低物流活动的整体 成本。 当前,一些与运输相关问题的运筹方法研究,比如配送中心的选址、运输车辆的 路线规划、集装器具或运载工具的装载优化等等,已经成为业界和学术界的热点。 集装单元可以使的物流各环节可以有效地联合为一个整体,使整个物流系统 实现合理化。物流的现代进展是离不开集装的,可以说集装是物流现代化的重要 标志。 充分发挥集装器具和载运工具的装载能力,可以降低货物运输的单位成本, 节约可观的物流费用。集装箱不仅是一种

　　化的集装器具而且兼具了载运工具 的特点,在货物运输中有着广泛的应用,有利于货物单元化运输和机械作业和组 织多式联运。据报道,目前的集装箱内部空间利用率平均仅为%,集 装箱仅为%,可见空间利用率不是很理想【】。而且我们在济南集装箱国际分流中 心以及佳怡物流等企业调研过程中也发现:装箱的运筹作业基本上依赖人工经验, 调度员凭经验估计出要装箱的货物数量或所需的集装箱数量,然后开具装箱单, 装箱工人作业也靠经验而且带有随机性,这就造成了集装箱空间的浪费,甚 至会 因为需要修改装箱单而干扰业务。因此提高集装箱内部空间利用率,是提高集装 箱运输效益的重要途径。另外,托盘以及厢式货车的装载情形比如目标函数、 约束条件与集装箱装载类似,集装箱装载的优化方法可以为前两者借鉴。因此, 以集装箱为对象研究货物的装载优化问题不仅具有行业典型性,还有着很好的经 济可行性,这也是本课题的出发点和着眼点。山东大学硕士学位论文 .剪裁与装填问题 集装箱装载问题,从本质上讲属于剪裁与装填问题 的一个分支。 剪裁问题是指在一种材料上寻找各种形状的最佳布局以使材料的浪费率最小。 装填问题则是指若干小的物体已最佳方式组合并装入一个大的空间从而使空间的 利用率最大。装填问题有人也称为布局问题。从本质而言,剪裁问题与装填问题 有着天然的内在联系,是一个互逆的过程,很难有一个严格的界定将它们区分开 来。例如:对于装填问题,我们可以认为将小物体装入空间的过程看作是将空间 分割成若干小空间这些小空间对应与各个物体的过程;对于剪裁问题,可以 认为将若干剪成的小物体材料以最大材料利用率的为目标回填到原来大材料中的 过程。 翦裁问题按物理空间可以分为一维、二维、三维形式。装填问题同样也存在一 维、二维、三维的形式。三维的装填问题又可以进~步细分为装柜问题 、托盘装载问题 、集装箱装载问题 【,引. 由于具有很好的实用价值,剪裁与装填问题近年来在国际上备受关注。其中剪 裁问题主要应用于木材加工业、纺织皮革业、钣金加工业等的板料的切割或下料, 装填问题主要应用于半导体加工行业、机械行业等的布局设计、企业的车辆装载、 托盘装载等等。此类闻题涉及面广、潜在价值巨大,同时又具有很高的复杂度, 吸引了很多管理科学、计算机科学、数学与运筹学等研究领域的人士进行不断的 研究。 针对剪裁与装填的问题的研究最早出现在大约五十年代。剪裁与装填问题被认 为是难问题,难于精确求解,目前对于此类问题的解决算法分为确定性和启发 性两种。确定性算法主要包括线性规划、整数规划、动态规划等传统算法,这类 算法只适合求解问题规模比较小的情况,因为随着问题规模增加,解空间呈指数 倍地扩大,不能在合理的时间内给出最优解。于是人们将目光转向现代算法如模 拟退货算法、禁忌算法、基因算法等等。这些算法涉及生物进化、人工智能、神 经系统和统计学等知识,都是以一定的直观基础而构造的算法,我们称之为启发 式算法。启发式方法未必能够给出最优解,但一般可以满足实际问题的需要。山东大学硕士学位论文 .集装箱装载问题 ..概述 ,指如何将一些长方体盒子 所谓集装箱装载问题 货物按某种方式装入集装箱,从而最大限度地提高集装箱的空间能力。 是货物运输过程中普遍存在的一个重要的也很典型的环节,托盘装载以及卡车等 运输车辆的装载与集装箱装载具有类似性。在装载的稳定性、容积限制、载 重限 制等约束条件下,使集装箱的空间利用率最大,是这类问题的主要目标。 集装箱装载问题可以划分为不同的分支,在文献】中提出将集装箱 装载问题分为//和厂/,也即单集装箱和多集装箱的装载。则根据 货物的差异,将装载的盒子货物分为同类、弱异类 ,同类是指盒子都相同的情况,弱 、强异类 异类指盒子的种类比较少的情况,而强异类指盒子的种类很多的情况?】。根据目 标函数和约束条件的差异,将集装箱装载问题概括为几种变化形式:条状 装载 ,其目标函数为货物装载后占用集装箱的长度为最小;背包形式 ,其目标函数为集装箱的空间利用率最大:同箱型多箱装载 装载 ,其目标函数为所用的集装箱数量最少:多箱型多箱装载 . ,其目标函数为集装箱的运输成本最小【“。 由于集装箱装载工作到目前为止大多还停留在人工阶段,所以结合计算机技 术设计出实用的算法来指导装箱,意义重大。集装箱装载问题已经被证明是完 全问题,求解时具有时间复杂性和空间复杂性,目前求解这类问题通常采用启发 式算法。启发式方法借助于有效的优化策略缩小搜索空间,尽可能在可以接 受的 时间内给出最优解或近似最优解。 国际上针对集装箱装载问题的研究最早可以追溯上个世纪六十年代,此后相 继出现了一批经典的算法,这些方法各有特点和侧重,但都不能保证是最优、最 完善的算法,这也为我们进一步研究此类问题留下了空间,其实这正是集装箱装 载问题的魅力所在。就国内研究情况来说,对于该问题的研究比较少、也不够丰 富。本文以集装箱空间利用率最大为目标,力图推陈出新,探讨一种更有效的方 法。山东大学硕士学位论文 ..相关问题 在装填问题中,有如下几类问题与集装箱装载很相似。 背包问题 在经典的背包问题中,有个体积为 ,?,的小物体要装入背包中,每个小物体都联系一定的利润,?,,背 包的容量为,问如何装载便装入背包的小物体的利润之和最大。如果假设小物体 的利润等于它们的体积,该问题即是一个空间利用率最大化的问题。 原指单元装柜问题,常见于一维和二维情 装柜问题 形,指如何将个尺寸不超过的小物体装入箱子,使所用的箱子最小。 原指将同一规格的长方体箱子按某 托盘装载问题 种方式放在一个矩形托盘或货架上,从而使码放货物的体积最大。现在对货物的 要求不再有同一规格限制。托盘装载的最大特点在于托盘一般没有侧面支撑.从 货物码放的稳定性考虑需要保证货物不会从堆码上掉下来,而集装箱装载则不必 考虑此约束。 .课题的潜在意义 随着单元装载技术 的推广和应用,集装箱在运输中地位和作用 日益受到人们重视。提高集装箱的装载利用率,将会降低运输成本,为制造企业 和物流企业尽可能多地挖掘利润。因此对于该问题的研究具有重要的现实意义。 从理论角度上说,集装箱的装载问题研究也会影响到其他领域的优化策略。 从广义上讲,剪裁和装填问题不仅仅物理空问才存在,如果我们将问题抽象匕, 会发现此类问题的研究方法也适用于计算机的多处理器并行处理、内存分配等等 领域。这使的剪裁和装填问题的研究有更深远的意义。 .课题的主要研究内容和方法 本文在参考国内外大量文献的基础上,通过分析和比较集装箱装载问题的各 种研究方法的优缺点,提出了一种有限树搜索的宿发式方法,经过实验分析具有 很好的效果。另外根据当前货物信息配载业的发展特点,本文针对货运信息配载 电子商务系统的体系进行了研究,提出了比较可行的交易模式。

　　共分六章,各章内容如下; 第一章绪论:介绍了问题的背景、剪裁与装填问题、集装箱装载问题及相关 山东大学硕士学位论文 问题、国内外的研究以及该研究的潜在意义等等。 第二章单元装载技术:比较详细地介绍了集装单元等知识的基本概念、集装 单元的模式和改善策略。 第三章集装箱装载问题研究综述详尽地介绍集装箱装载问题的分类、一般 性描述、国内外研究状况,分析和比较它们的异同和优缺点,提出了本课题研究 方法的思路。 第四章有限树搜索启发式方法详细给出了本问题的数学模型和算法,并对 数据进行了实验,通过与其他方法比较得出本算法的理论价值和实际意义。 第五章基于网络环境的货运信息配载实现本章介绍了当前货运信息配载行 业的特点和现状,提出了基于物流电子商务的货运信息配载模式,并介绍了佳怡 物流管理应用系统。 最后是总结,在本章对于课题的研究作了总结,指出了课题研究的意义、存 在的问题和有待于改善的地方。山东大学硕士学位论文 第章货物集装单元化技术 .集装单元和集装系统概述 ..基本概念 集装单元是指采用各种不同的方法和器具,把具有包装或无包装的物品,整 齐地汇集成为一个扩大的、便于装卸并在整个物流过程中保持~定形状的作业单 元。 集装化是指采用集装器具或捆扎方法,把物品组成标准规格的单元货件,以 加快装卸、搬运、储存及运输等物流活动。它既是一种包装形式,又远远超出包 装的范畴:既是一种运输或储存形式,又不完全只起运输或储存的作用。集装贯 穿了物流的全过程,在全过程中发挥作用。 集装系统是由货物单元、集装器具、装卸搬运设备和输送设备等组成的高效、 快速地进行物流作业服务的人工系统。集装系统是“把许多件运输物品集中成一 个单位,以这种状态进行一系列的运输、保管、装卸,从而能在多方面取得效果 的体制”。 集装有效地将分散的物流各项活动联结成一个整体,是物流系统化中的核心 内容和主要方式。集装系统能在多方面起作用,因而许多人已将其看成是干线物 流发展方向。 被输送的物品分成有形固体的物品和粉粒、液体、气体等流体两种,狭义 的集装仅以前者为对象,广义的集装也包括后者。 集中状态有三种:不使用托盘、集装箱等类集装设备而将包装货按原有形态捆 扎等集中的狭义“集合包装”;使用托盘类的“托盘集装托盘货物”;使用集装 箱类的集装箱集装集装箱货物。在这三种形态中,属于“进行一系列的输送、 保管、装卸”的系统,有以托盘集装状态和集装箱状态为代表的两种集装系统。 ..集装化的方式和种类 集装有若干种典型的方式,在各类典型方式的交叉领域还有许多非此非彼的山东大学硕士学位论文 集装方式,因而集装的种类方式很多,主要有集装箱和托盘集装方式。 各种典型的集装方式和它们之间的变形方式如下: 托盘最典型的是平托盘,其变形体有柱式托盘;架式托盘集装架、笼 式托盘集装笼、箱式托盘、折叠式托盘、轮式托盘台车式托盘、薄板托盘滑 板等: 集装箱最典型的是普通集装箱,其变形体有:笼式集装箱、罐式集装箱、 台架式集装箱、平台集装箱、折叠式集装箱等,许多类集装箱和相应的托盘 在形 态上区别并不大,但规模相差较大; 集装容器典型集装容器是集装袋,其变形体有集装网络、集装罐、集装 筒等; 集装货捆集装网也是货捆的一种变形体; ..集装的特点与效果 集装的主要特点是集小为大,而这种集小为大是按标准化、通用化要求而进 行的,这就使中、小件散杂货以一定规模进入市场、进入流通领域,形成了规模 优势。集装的效果实际上是这种规模优势的效果。主要有以下几方面: 促使装卸合理化。和单个物品的逐一装卸处理比较,集装效果主要表现在: 首先可以缩短装卸时间,这是由于多次装卸转为集装一次装卸而带来的效果;其次 可以降低装卸作业劳动强度。采用集装后不但减轻了装卸劳动强度,而且集装货物 的保护作用,可以更有效防止装卸时的碰撞损坏及散失丢失。 使包装合理化。采用集装后,物品的单体包装及小包装要求可降低甚至 可以去掉小包装从而在包装材料上有很大节约,包装强度由于集装的大型化和防 护能力有增强,也大大提高,有利于保护货物。 由于集装整体进行运输和保管,大大方便了运输及保管作业,便于管理, 也能有效利用运输工具和保管场地的空间,大大改善环境。 有利于组织货物多式联运,加速物资周转,实现“门”运输。 集装的晟大效果,还是以其为核心所形成的集装系统,将原来分立的物 流各环节可以有效地联合为一个整体,使整个物流系统实现合理化。 ..集装单元技术的应用 物流系统是由储存、运输、包装、装卸搬运等环节组成的。各环节之间是相互山东大学硕士学位论文 联系、相互影响、相互制约的,各个环节之间不能随意变化改动。在物流活动过 程中应利用系统理论的系统工程思想把物流系统当成一个完整的整体来对待。集 装单元化技术是物流管理硬技术如物流设备、器具及辅助器具与软技术运 筹方法、程序和制度的有机结合,是在系统分析的基础上产生的应用于现代物 流的科学技术,是进行综合规划和改进物流机能的有效技术,它在物流系统中具 有重要的应用价值。 集装单元化技术在装卸搬运中的应用 在整个物流过程中,装卸搬运出现的频率大于其他环节,因而物流装卸搬运所 需的时间和劳动力占整个过程的比重较大,所需要的费用占整个物流成本的比例 也很高。采用集装单元化技术可以改善这一情况。将多种物品组成一个大小 相当、 适合现有装卸搬运设备作业,便于现有设施作业的货物集装单元。单元化集装器 具可以采用托盘、集装箱或其他形式。单元物资在装卸搬运中通常般保持不变的 形式。应用集装单元化技术可以使作业快速、高效,促进装卸搬运的机械化与自 动化实现。 集装单元化技术在运输中的应用 把物资按~定单位集中,并保持集装形式不变的直达运输,称为集装单元化直 达运输。集装单元化直达运输主要有托盘、集装箱两种直达运输形式。采用集装 单元化技术,便于组织和实现铁路、公路、水运多种形式的联合运输以及“门到 门”运输,具有良好的经济效果。 集装单元化技术在储存中的应用 随着物流业的发展,出现了很多仓储新技术,仓库的功能也有了很大的变化。 仓库已从过去的静态管理物资储存时间长转向动态管理货物进出库频繁, 功能上由单纯保管物资的场所演进为分拣、配送、加工、信息处理的配送中心。 集装单元化技术就是一种使货物由静态变为动态的技术方法,而托盘、集装箱等 单元化器具就是实现这种转变的媒介物。集装单元化技术可以使仓储作业省力、 省时、低成本、实现绿色环保。 ..托盘与集装箱的发展 ...托盘的出现和发展 托盘的概念 托盘是目前被普遍采用的一种搬运物资的工具,是;特殊的包装形式。托山东大学硕士学位论文 盘具有和集装箱类似的作用,即能把零散的物资组成一个较大的整体,以利于物 资的装卸和运输。托盘在承托物品时,实际起到的是托起物品的作用,故而称为 托盘,见图所示。可见,托盘即是为了便于装卸、运输、保管等而使用的由 可以承载单位数量物品的负荷面和叉车插口构成的装卸用垫板。 单面四向型 单面二向型 图托盘 托盘的基本结构和分类 托盘是方形或长方形扁平垫板。垫板下有“脚”,形成插口,以供叉车、铲车 等设备进行装卸、运送和堆放。托盘基本上是由横梁、托板和垫块三个主要部分 组成。 托板??构成托盘面的叫托板,位于托盘两端的板叫边缘板。 垫块??代替起梁作用的长方形体的脚叫垫块。 横梁??把托板互相连接起来的构件称之为梁。 托板、横梁和垫块三者在结构上必须遵守三者相邻的面互相成直角的原则。 只有将三者紧密而牢固地结合起来,才能保证托盘的方正、平稳、牢固、使 用面 平滑、装卸方便等。 按托盘叉车操方式作分为两向通路托盘和四向通路托盘见图。托盘按 材质可分为木托盘、胶合板托盘、塑料托盘、复合材料托盘等。按负载重量 可分 为.吨托盘、吨托盘、吨托盘等。 托盘的规格 托盘的规格是指托盘的长与宽,通常用宽长来表示。国际标准化组织先后 三次提出建议规格×、×、×、×、、 ×?、×和×注:单位均为。根据实际计算, 、 和 三种规格的托盘对集装箱底面积的利用率最高。 国际上主要国家使用率最高的三种规格是:×、×、×。 我国托盘数量虽少,但规格比较繁杂。年颁布国家标准是:×、 ×和 这三种。机械工业系统使用规定:平托盘规山东大学硕士学位论文 格为,×、×两种规格;箱式托盘和柱式托盘为, 和 、 ×。我国铁路使用的托盘规格主要有: 、 和 四种规格。 托盘堆码方式 从货物托盘上堆码时的行列配置来看,有如图表?所示的四种基本堆积模 型。 .多层不交错堆码是以最简单的排列形式,在托盘上将包装箱向一个方向并 列,而且从最下层到最上层是完全一致的堆码模型。这种模型的堆码,由于各层 间的货物未能啮合,会引起垛间分离,安稳性较差。 .层间纵横交错堆码是奇数层的货物之间成度交叉堆码的模型。在正 方形托盘一边长度为货物的长、宽尺寸的公倍数的情况下,可以采用这种堆码模 型。 .砖砌体堆码是将货物纵横排列,组合成一层,而奇数层和偶数层之间相对 度进行堆码的模型。这个模式多用于长方型托盘装运袋包装货物的堆码。 .中心留孔堆码是用风车型的堆码形式,在各层中改变货物的方向进行维 码。可以来用这种堆码模型的范围有:正方形托盘中,象图中所示一层诽放四个 货物,且货物的长度与宽度尺寸之和和托盘的一个边长吻合时,可采用这种模型, 其特点是适于这种模型的货物尺寸无穷无尽,但是,在长度和宽度尺寸相差 过大 时,中央部分的无效空间也过大,致使托盘的表面利用率降低。 此外,在这些模型中,、、三种模型是上下咬合堆码,所以总称为联锁堆 码。但是,最近从瓦楞纸箱的耐压强度方面着眼,为减少最下层箱的破损,也 采 用下面三层不交错堆码,上部层纵横交错堆码和中心留孔堆码的方法。 多层可交错堆码 .纵横交错堆码 国 田田田圈 奇数瑶 偶数培 奇数层 偶数层山东大学硕士学位论文 .砖砌体堆码 .中心留孔堆码 固’国 凹田园回 奇数居 偶数层 奇数层 偶数层 图托盘堆码方式 托盘的优点 ?可以有效地保护商品,减少物资的破损,在物资的运输、装卸、保管过 程中具有特别的效用。 ?可以加快物资装卸、运输话动,减轻工人的劳动强度,从而加速商品的 流转。 ?可以节省包装材料,降低包装成本。 ?可阻促进装卸、运输作业的机械化和包装的标准化、系列化、规格化。 国内外托盘集装发展概况 本世纪年代,由于叉车在市场上的出现和使用,托盘首先在工业部门使用, 成为与叉车相配合的一种附属装卸搬运工具。第二次世界大战期间,为解决军用 物资快速装卸问题,托盘得到了进~步发展。战后,随着经济的复苏和发展,伴 随着叉车产量的增长。托盘在社会各行业中得到普及。托盘在方便装卸作业的基 础上,进一步成为方便储存的工具。许多工业发达国家纷纷采用货物带托盘储存 的方法,以提高物资出入库效率和仓库利用率,实现储存作业的机械化。从年 代起,美国、瑞典等国家为了消除转载时码盘拆盘的繁重体力劳动,实现包件货 物搬运作业机械化,开始了托盘流通和联营。由此至年代。在各主要工业发达 国家都实现了托盘流通与联营。 托盘既是装卸工具,储存工具,同时还是一种运输工具。托盘从企业内,车 站内,港口内的使用发展到随船运输。托盘交流与联营业务组织好的国家,如北 美和北欧诸国还直接将托盘运至商店,陈列在柜台上直接售货,又使托盘发展成 售货工具。 从上述国外托盘发展的历史,可以看到托盘从装卸搬运到储存、运输,直到 售货工具,已深入到生产、流通、消费诸领域。从生产终点将货物码上托盘开始,山东大学硕士学位论文 到货物售给消费者或供给新的生产线使用为止,它经过了包装、装卸搬运、储存、 运输等环节,贯穿于物流的全过程。在物流发达国家托盘的保有量如今数以亿计, 可见托盘集装在世界的发展水平。 我国托盘在年代中期开始使用托盘进行装卸作业。但是,多年来由于对托 盘流通的体制、组织和管理方法缺乏有组织的深入研究和实践,对开展托盘流通 所必须的成套设备和设施缺乏统筹规划,再加上其它因素的干忧,致使本来与其 它工业国几乎同时起步的托盘集装技术没能取得应有的水平。现在,我国托盘的 运用基本还是以在企业内、车站内、港口内使用为主,托盘的功能也基本上停留 在装卸搬运和储存工具的阶段。即使是铁路这样庞大的物流体系,托盘的保有量 估计也就在百万左右。 ...集装箱的产生和发展 定义 集装箱是集合包装容器中最主要的形式。根据国际标准化组织 对集装箱所下的定义与技术要求,我国年颁发的国家标准 《集装箱名词、术语》中,对集装箱的定义,集装箱应具有如下特点和技术要 求: ?材质坚固耐久,具有足够的强度,能长期反复使用; ?适用于各种运输形式,便于货物运送,用一种或多种运输方式运输时,途 中转运,不动容器内货物,可以直接换装: ?各有便于装卸和搬运的专门装置,可以进行快速的装卸搬运,并可以从一 种运输工具直接方便池换装到另一种运输工具上: ?要求形状整齐划一,便于货物的装满和卸空; ?具有立方米和立方米以上的内容积。 集装箱的分类 国际标准化组织技术委员将集装箱按规格分为个系列,种箱型。 它的外部尺寸和总重量如附录卜所示。现在国际问常用的规格是、、比、 、和等种箱型。附录卜所示的是上述种箱型的长度比例关系。我国 现已制定了集装箱标准?,其外部尺寸和重量如附录卜所示。 按用途可以分为通用集装箱和专用集装箱。通用集装箱适于装载运输条件无 特殊要求的各种不同规格的干杂货,进行成箱、成件集装运输。专用集装箱 是根 据某些商品对运输条件的特殊要求而专门设计的集装箱。箱内可设有通风、 空调 或货架等设备,可用于装载鲜活、易腐、怕热、怕冻或形体较大的商品等。山东大学硕士学位论文 还有根据结构、材质等差异进行分类的方式,这里不再赘述。 集装箱的发展 纵观世界集装箱发展的历史,大体上可分为三个阶段: 第一阶段,即年代以陆运,中、小型集装箱为主; 第二阶段,即年代以海运.大型集装箱,国际标准集装箱迅速发展: 第三阶段,即年代后,以水路、公路、铁路联合运输成为件杂货运输的主 导形式。 我国集装箱发展始于年代中期,开端于铁路运输业,此后陆续发展了集装 箱海运、公路运输以及国际联运多种运输形式。随着我国经济贸易的稳步发展, 以及大量跨国公司涌进我国市场,从而使得我国集装箱运输业连续多年出现高速 发展的势头。我国集装箱港口吞吐量以每年递增%的速度持续发展。中国集装 箱船队巳跻身世界四强,而且我国也是当今世界上最大的集装箱生产国。 .单元化包装技术 ..包装的概念 包装指在流通过程中保护产品、方便储运、促进销售,按一定技术方法雨采 用的容器、材料及辅助物等的总体名称。也指为了达到上述目的而采用容器、材 料及辅助物的过程中施加一定技术方法的操作活动。包装是单元化装载系统的一 部分,也是物流系统的构成要素之一,与运输、保管、搬运、流通加工均有十分 密切的关系。 .。包装种类和作用 包装种类按功能对包装进行分类,又可分为工业包装和商业包装。限于本课题 的研究范围,这里我们只讨论工业包装。工业包装是以运输、保管为主要目的的 包装,也就是从物流需要出发的包装,亦称运输包装,是部包装包含内 部包装。 工业包装主要作用是有保护功能、定量单位化功能、便利功能和效率功 能。 保护功能。避免搬运过程中的脱落,运输过程中的振动或冲击,保管中的由 于承受物重所造成的破损;避免异物的混入和污染:防湿、防水、防锈、遮光,山东大学硕士学位论文 防止因为化学或细菌的污染而出现的腐烂变质;防霉变、防虫害。 定量功能。整理成为适合搬动、运输的单元;整理成适合使用托盘、集装箱、 货架或载重汽车、货运列车等运载的单元。 便利动能。形状便于运输、搬动或保管:便于实施运输、搬动或保管等物流 作业;便于生产;便于废弃物的处理。 效率功能。有利于提高生产、搬运、销售、输配送、保管等效率。 ..包装方法 从物流环境讲,被包装的货物在流通过程中受到的环境影响因素,分成气象 环境、物理环境及生物环境三种。 在~般的流通环境中,必须考虑的环境因素是物理环境方面的堆码负荷以下 称堆压、振动、冲击和气象环境方面的温湿度。在生物环境因素方面,有发霉、 虫害、动物危害等因素。 其中的堆压多发生在保管和运输时,一般’隋况下,保管时堆码的层数较多, 特别是近来由于普及托盘保管,常采用高层堆码。因此,根据叉车的举升高度, 必须考虑仓库内最高堆码高度为.?.米时的堆压集装箱问题。另外,在运输时,货车、 卡车、集装箱的最高堆码高度为.米,船中的堆码高度取决于船型,按?米 确定堆压条件。 其次是振动、冲击。人力装卸时产生冲击,机械装卸及运输时产生振动和冲 击。在运输过程中振动、冲击的大小,也可以由卡车、货车、集装箱等设备的设 计及强度标准反映出来。例如,卡车运输时,在汽车负荷计算标准中规定,上下 方向为.标度,前后方向为.标度,左右方向为.标度。另外,包装货 物在卡车货台上如不用绳子捆扎而呈自由放置状态时,要特别注意发生的弹上冲 击自由落下高度为厘米左右。 ..包装注意的问题及发展趋势 改进包装应注意的一些问题: 采用单元装载尺寸和运输包装系列尺寸 包装单元的尺寸与单元装载尺寸一致,规定为 以及.将包装单元尺寸作为基准尺度.进行模数分割就可以得到系列 化的包装尺寸。在剔除了互换性差的尺寸后,进行长宽、大小匹配就可得到所需山东大学硕士学位论文 包装尺寸系列。 采用这种运输包装系列尺寸,可以使货物恰好不多不少地码放在托盘上,既 不致溢出,也不留有空隙。卡车的车箱规格,也最好按单元装载尺寸的要求制造, 使装载货物时既不致超出也不致空余。 包装大型化 随着交易单位的大型化和物流过程中搬运的机械化,单个包装亦趋大型化。 如作为工业原料的粉粒状货物,就使用以吨为单位的柔性容器进行包装。大批量 出售日用杂货或食品的商店因为销售量大,只要不是人力搬运,也无需用千克 的小单位包装。包装单位大型化可以节省劳力,降低包装成本。与包装大型化同 步的是最近在有的批发商店里,直接将工业包装的货物摆在柜台上,可见对 这种 大型化包装应给予足够的重视,由此也可以看出包装的趋势。 包装机械化 包装过去主要是依靠人力作业的人海战术,进入大量生产、大量消费时代以 后,包装的机械化也就应运而生。包装机械化从逐个包装机械化开始,直到装箱、 封口、捆扎等外包装作业完成。此外,还有使用托盘堆码机进行的自动单元化包 装,以及用塑料薄膜加固托盘的包装等。 在超级市场,预先包装原包装业已普及,就是从保证卫生出发,食品包 装机械化也是非常必要的。 如上所述,包装机械化对于节省劳力,货物单元化,提高销售效率,以及采 取无人售货方式等均是必要的,不可缺少的。 节省资源的包装与拆装后的废弃物处理必须和社会系统相适应 包装的寿命很短,多数到达目的地后便废弃了.但随着物流量的增大,垃圾公害 问题提上议事日程。随着对”资源有限”认识的加深,包装材料的回收利用和再生利 用受到了重视。今后应尽可能地积极推行包装容器的循环使用,并尽可能地回收 废弃的包装容器予以再生利用。这是非常重要的,特别是近来过大包装、过分包 装、包装废弃物问题,回收再生利用等等包装与社会机制协调的问题将日益突出。 单元装载物料搬运与物流标准化 单元装载物料搬运系统由三部分组成:包装、托盘以及物料搬运设备。其核 心是自始至终采用托盘运输,即从发货至到货后的装卸,全部使用托盘运输方式。 这三者的相互影响和它们与产品的相互影响共同决定了单元装载物料搬运系统的 效率。物流系统效率化的关键在于使单元装载系统化,也即把货物归整成一定数山东大学硕士学位论文 量的单件进行动输。为此,在物流过程中所有的设施、装置、机具均应引进物流 标准概念。 物流标准是指为实现标准化,提高物流效率,将物流系统各要素的基准尺寸体 系化。其基础就是单元装载尺寸。单元装载尺寸是运输车辆、仓库、集装箱等能 够有效利用的尺寸。包装单元是指在运输、装卸、仓储等流通过程中,把多个包 装组件组合成可用机械作业的单元体和符合有关条件的单元包装件。托盘是使用 最广泛的单元化装载工具,在货物流通中的相关尺寸调节中,托盘尺寸起着 主导 作用。对于集装箱、汽车车厢、船舱、火车车厢等都可以托盘尺寸为组合模数。 物流托盘标准化的思想就是把运输包装系列尺寸、单件装载尺寸、车箱尺寸和 一系列的规格尺寸作为一个整体联系起来。做好包装中的标准化工作,可以使物 品的包装与托盘系列、集装箱、货车等承载器具相互配套、相互匹配,能够充分 利用车辆的装载容积、承载能力,提高物流作业连续性基础工作的水平。 集装单元器具的标准化的意义:便于互换、流通,减少重复搬运,提高流 通效率:标准器具可以保证使用性能;节省原材料。便于大量生产、维 修和管理。 标准化要考虑的因素:适合国内常用的运输工具尺寸:各类集装箱的 尺寸:国家标准化政策以及标准:国际标准,以及与我国贸易有往 来的国家的标准,以便于国际流通。 .改善单元装载的策略和途径 。.产品设计与包装设计的一体化 产品的包装设计提前到产品设计阶段,与产品设计同步考虑。产品与包装一体 化的设计过程为:首先,明确产品的流通环境:第二,设定产品/包装的设计目标; 第三,产品/包装设计:第四,目标检验:第五,包装产品检验;第六,可持续包 装工程。产品包装设计采用由外到内的策略,即包装尺寸结合集装器具托盘、集 装箱的标准模数设计。 ..改变托盘设计降低单元装载成本 在美国大约有%的家用产品用托盘运输,花在托盘以及包装上的费用会是相 当大的。大多数公司在包装开发上投入了大量资源,却很少给予托盘设计同等的 山东大学硕士学位论文 重要性。弗吉尼亚工学院单元装载设计中心研究了包装、托盘及物料搬运设备的 关系,认为托盘与包装作为一个整体系统决定了单元装载的总体性能。有许多方 法可以改进托盘设计以节省单元装载的总费用。 廉价的托盘不等于最节约成本的托盘。使用低价位的托盘经常导致其他因素 的出现,比如产品容易损坏,从而需要额外的保护包装和搬运劳动。 最方便、快捷、可靠和经济的设计本托盘的方法是使用计算机辅助设计即托 盘设计系统。使用者输入托盘规格、负荷类别及支撑条件,就能估计托 盘的强度、刚度、耐用性以及使用成本。 改进设计的途径有:提高钉子的质量:使用有翼托盘;重新部署托板;增加 托板厚度;增大托板面积;比较平的托板;使用四梁托盘;去掉粱的凹口两向 即可;调换侧梁与托板的尺寸;使用干燥的木材:考虑可回收托盘设计。 ..推广可重复使用托盘 可重用托盘即可以保护环境又能节约费用。无疑,一个可使用次的耐用托 盘比个一次性的塑料托盘使用更少的材料,对自然资源的利用更有效。尽管可 重用托盘自身成本高于一次性托盘,但可以多次使用,从它带来的经济效益看是 物超所值。它的经济性主要有四个方面。 减轻由于运输过程中震动引起的货物破损 卡车或铁路货车在运输中的震动频率为~赫兹,而载货托盘则会产生谐振 现象。托盘的刚度与共振频率有正比关系,低刚度托盘的共振频率小于赫兹, 可重用托盘一般有较大的刚度。与一次性托盘相比,可重用托盘传递的运输震动 比较弱,可以减轻货物因为震动导致的破损。 减轻载荷集中造成的破损 柔性的低刚度的托板可以将很大一部分载荷传递给侧梁和支撑块,托盘与紧 固装置相邻的地方容易出现破损情况,而刚度大的托板则将货物重量较多地分布 在承载面相应传递给侧梁和支撑块的载荷较少,这样就可以降低货物破损程度。 根据弗吉尼亚单元装载设计中心对五种托盘的实验显示,大刚度托盘可以为客户 节省大约%的费用。可重用托盘与一次性托盘相比能够更均匀地分布载荷。 可重用托盘具有较大的承载能力 通常可重用托盘具有比较大的侧梁与支撑块,因此具有很强的承载能力。 与自动化的物料搬运设备的匹配性好山东大学硕士学位论文 本章小结 本章系统地阐述了单元化装载系统的理念。探讨了包装、集装器具以及物料搬 运设备之间的相互关系以及物流标准化的意义,提出了改进单元装载的策略和途 径。山东大学硕士学位论文 ;曼璺皇皇置寰苎毫曼鼍皇曼皇寰 一 第章集装箱装载方法概述 .引言 集装箱装载问题以下正文中简称是一个非常具有实用价值的研究课题, 在学术上是属于相当复杂的组合最佳化问题,在实务上亦属于物流管理相当重要 之课题。的研究盛早发端于对剪裁和装填问题的研究,根据文献早在 年和就在 ~文中对进行了研究。在二十世纪八十年代以来,对于的研 究日益展开,出现了很多启发式算法。年和给出了一 个非常经典的启发式算法【刖,对此后该问题的研究影响很大。这些算法在不同的 角度展现了自己的特点和优点,然而迄今为止,还没有~种算法能在各个方面 超 越其他方法,所以也吸引很多人对进行研究。就国内的研究和应用’隋况看, 我们还处在比较滞后的境地。基于此,分析和比较现有的研究方法,探索出 一种更有效的方法,对于的研究和应用无疑有重要的意义。 .集装箱装载问题的分类 提出了一种比较经典的分类方式,将分为//和//也 即单集装箱装载和多集装箱装载情况,单集装箱装载以集装箱空闻利用率最 大为 目标,多集装箱装载以所需集装箱数量最少为目标。 另一种很重要的分类是提出的.根据货物的情形将分为同类 、弱异类 、强异类 ,同 类是指盒子都相同的情形,弱异类指盒子的种类比较少的情形。雨强异类指 盒子 的种类很多的情形。 根据目标函数和约束条件的差异,将集装箱装载阅题概括为几种变化 形式: 最、长度配装 它假设集装箱的高度和宽度为确定尺 寸但长度无限大,目标是使装载货物后长度利用最小: 背包装载 该种情形认为,每个货物都会产生一定 的利润,因此目标为利润的最大化,如果假定利润与货物体积相当,那么目标 转山东大学硕士学位论文 化为集装箱空间浪费最低也即容积利用率最高: 同箱型多箱装载?该情形为所有集装箱规格统一,目标 为所用集装箱数量最少; 多箱型多箱装载? 它的特点在于集装箱可 以有多种规格,每种集装箱都有一定的运输成本,目标为运输成本最小。 .集装箱装载问题的一般描述及装载方式 为了便于研究而又不失一般性,通常对有如下假设: 集装箱的长、宽、高分别代表笛卡尔坐标系的、、轴方向,坐标原点 位于前端左下角集装箱门在后部,如图一所示无特别说明,本文均参照此 坐标系; 货物装在长方体的盒子内,盒子本身的挤压变形可以忽略: 货物放置方向必须与坐标轴平行或正交,货物不能与其他货物交迭放置, 货物不得悬置于集装箱的尺寸范围,不同类型货物可以相邻摆放。 图集装褥坐标糸 货物的装填方式可以归纳为:砌墙方式?,堆叠方式 ,立体排列 。 。剪裁方式 砌墙方式由和提出,以后的很多算法也都采用了“层” 的装填方式,该方式就是把集装箱的装填看作一层一层进行的,层有水平平 选择非常 行于平面和竖直平行于平面之分。层的厚度 重要。对于层的厚度选择,和方法是从剩余盒子中选择盒子的最 小边最大的一个作为层厚。以后陆续有人提出根据盒子的最大体积、最长棱边、山东大学硕士学位论文 最大底面积、相同类型盒子的数量等标准来选择层厚。 堆叠方式指盒子在集装箱的水平面组成一系列合适的“塔”】。 切割方式是指将集装箱分割为许多小空间】。 立体排列方式是指以同种类型的盒子组成规则的立方体装填集装箱的方式‘“。 .集装箱装载的实际制约因素 在配装过程中,除了对货物和集装箱自身的尺寸、重量及利润的考虑外,还 有一些因素需要引起注意: ?方向限制有时货物的摆放方向有明确要求,因此装载必须按照此要求执行: ?承载能力限制货物的承载能力由包装盒的结构和货物本身的性质决定; ?稳定性货物在集装箱内不能窜动,需要用泡沫塑料填充空余空间或用包装 带捆束以固定货物,以免相互间磕碰引起损坏,另外尽可能使集装箱重心和其 几何中心一致,以有利于运输和机械装卸作业; ?货物编组属于同一接受人的货物或货物类型相近的变成一组,便于装卸作 业: ?配装隔离限制某些货物不宜于其它货物混装,如食品与化工产品等: ?某类货物整体运输对于像机床等设备,有时需拆借成各个部件运输,因此 尽量组织一起装车发运; ?配装优先级按照货物的运到期限或者保质期等情况确定装箱货物的优先 次 序。 当然并不是每种因素在任何情况下都很重要,但相当一部分情况下某些因素 直接影响到了运输的质量,需要引起足够的重视.】。 . 的研究方法 研究方法有线性规划、整数规划、动态规划等传统方法、构造型启发式方 法及严谨启发式方法包括模拟退火算法、禁忌算法、基因算法等等【。 传统方法 针对单集装箱装载问题给出了基于动态规划前向策略的近似算法, 货物在件左右时运算时间是可以接受的【?。 对于多集装箱装载问题,给出了整数线性规划模型,考虑了货物和集装 箱的不同规格、货物的方向、放置等因素【。等人则给出了基于整数规划山 东大学硕士学位论文 的三维装箱启发式算法,对于每个集装箱依次配装直至所有货物装完为止, 但是 这种方法仅适用于同种规格的集装箱配装,而且由于变量以及约束条件随货 物数 量增加而迅速增多,从而使问题难于求解。 传统方法由于随着问题的规模增大,解空间呈指数倍增长,从而使问题难于 求解,因此结合优化的搜索策略降低搜索空间,才是该类方法的生命力所在。 构造型启发式方法 这类方法以经验为基础,具有直观实用的特点。和以下称 &首先采用构造型启发式方法来解决集装箱装载问题,并提出了层的概念,此 后~些有影响的方法也都采用了“层”这种装填方式,只是层的方向以及层厚的 选择有所差异。 方法的特点:适用于弱异类情形;货物可以任意放置:层垂直于平面; 层的厚度选择有两种情况:首先是选择剩余数量最多的某类盒子已部分装入 作为新层开始。二是从其余类别的盒子中按照三级标准即盒子最小边最大、盒子 数量、盒子最大边最大选择层厚:空间遍历顺序为先向上、再向右、最后再向前, 也即层可以看作由竖直的“条”组成。该方法考虑了层与层之间的空隙融合。该 方法的缺点在于每个盒子都需要分析和处理,时效较低,另外同一层相邻两个盒 子之间可能存有空隙。 针对同类货物进行了装载研究,针对弱异类货物进行了研究?。。 等人在年提出了另外一种层的构建方式,与方法不同之处 在于:层由水平的“条”组成;盒子的优先级按照体积大小来决定;盒子在层之 间不允许跨骑;通过改变第一层确定层厚的盒子的位置,来产生多种装箱方案. 为解的优化提供更大的保证。该方法适合于强异类的盒子情形,不足之处在于: 水平“条”的表面由于盒子高度的差异而呈现方齿状,盒子不允许层间跨骑,造 成空间的浪费。 和提出,尽量用同一类的盒子构成完整层,如果剩余类型的 不能构成完整层,再用方法进行装填。该方法的可取之处在于,将三维装填 转化为二维装填。 针对同类盒子的装载采纳完整层的概念,给出了装填方法,该方法改 善之处在于可以旋转集装箱,从而使层可以调整码放方向比如沿宽度或高度方向。 宫佩珊针对同类产品且无摆放限制的装填提出了~种递归方法,与的方法 非常相似【,。 与则是构建水平层,为了使层表面趋于平坦按照盒子的高度设置优 先级别,并且定义移动边界分隔己装填和未装填空间。该算法给出的组数据被山东大学硕士学位论文 当作标准测试数据使用【】。 等人提出一种简明新颖的算法,该算法舍弃了层的概念,用一种特殊的 空间描述方法表示空闲空间和已装填空间。但是该算法缺点就是耗费内存较多, 增加了时间复杂度,而且盒柱之间有空隙【。 和提出一种算法也没有采用层的装填方式,而是采用了 等人的空间描述方法,算法独到之处在于尽量使相同的盒子组成盒柱,并且对于 盒子的优先级制定了四个标准即空间利用率、深度方向尺寸、盒子体积、剩余空 间坐标最小吲。 王亚英针对托盘装载问题的研究提出拟单一物品的策略即将不够一层的同类 物品拼成一个新的物品,另外高度接近的不同物品之间可以组合。阎威武针对 集装箱装载问题则进一步提出空间合并策略”。段国林则将托盘分为对称的三个 区域,采用先边后中间的装填策略。 姜义东提出了用三叉树结构表达三维矩形物体布局状态空间分解的方法,采 用体积定序、占角策略【?。 杨传民采用全面枚举搜索研究同类货物的装箱优化,该方法只适合小规模问 题‘叭。 严谨启发式方法 严谨启发式方法是近年来解决复杂优化问题备受关注的一类方法。该类方法 以寻找全局最优解为目标,一般具有严密的理论依据。用于装箱问题的这类方法 有模拟退火算法 , ,简称、基因算法 简称、禁忌算法 ,简称。 到目前为止,关于模拟退火算法、禁忌算法用于三维装箱问题的研究比较罕 见,因此不做讨论。 基因算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全 局优化概率搜索算法。其基本步骤是首先产生一组初始个体,然后进行编码,再 通过复制、交叉、变异操作,最后输出搜索结果。用基因算法解决集装箱装载问 题是一种可行思路,但基因算法本身还存在一些不足,尤其在解群分布不均匀十 易于出现不成熟收敛、陷入局部极优。如果能有一种算法以为基础,保留全局 搜索能力,又能提高算法的群体多样性,则此算法一定可以获得良好的结果,

　　本文档为【集装箱装载问题启发式算法研究及应用】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑， 图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。

　　[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件，我们尽快处理。

　　本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。