论文研究-求解三维装箱问题的混合遗传模拟退火算法.pdf

所需积分/C币:10 2019-09-11 21:50:06 795KB .PDF
58
收藏 收藏
举报

集装箱装载是货物运输过程中重要的一步,其属于NP-hard问题。为了提高效率,降低成本,提出了以集装箱体积利用率最大化为目标建立三维装载模型,同时考虑体积约束、重量约束、重心约束、方向约束。利用混合遗传、模拟退火与三空间分割启发式装载算法求解模型,算法中融入局部最优解保存策略来避免局部较好解在后续的算法过程中出现适应度降低的情况。通过强异类算例与弱异类算例对算法进行性能测试,并结合具体的货物装载数据,得出三维装载图与目标函数值。结果表明,该算法应用于集装箱装载有着较好的效果。
计算机工程与应用 ()方向约束 在确定货物装载顺序时,还需考虑特定类型货物的 摆放方向,如果客户没有提出任何方向限制,那么可以 根据装载需求进行装载,以提高装载效率 ()载约束 在进行分层装载时,要充分考虑货物的最大承载压 力,否则下面的货物会因为承载压力不够而导致损坏, 因此装载层数以及装载顺序都需要被限制 ()装载顺序约東 Z 不同订单的货物应按照不同的装载优先级进行处理 模型假设 本文主要针对集装箱装载布局进行研究,将体积约公式()()中,X,Y1,乙为货物的重心坐标,[D 東、重量约東、重量平衡约束、方向约束作为约束条件。[Q,aO.a为重心安全区间。 为了提高集装箱的利川效率,将集装箱体积利用率最大 作为目标函数。现将模型做如卜假设 求解算法 ()集装箱形状假设为卡长方体。 三空间分割启发式算法 ()集装箱内货物的位置没有区域限制。 三维装箱问题本身具有定的复杂性,同时为了满 ()货物均为长方体且质量分布均匀 足实际应用中的需求,必须使用启发式算法来生成有效 ()货物可以保持其形状和尺寸,不会由于堆叠而的装载方案。优秀的启发式算法应具备在较短的时间 变形,不是危险品等特殊货物 内生成高质量的解,同时还应具有适应不同需求的灵活 ()不考虑途中货物的加载与卸载。 性。本文主要采用三空间分割的启发式算法来制定 模型建立 装载方案,下面介绍启发式算法的内容 基于以上內容分忻,现将数学模型的目标函数和装 )定序规则 箱约東条件建立如下。 货物装载顺序将会影响集装箱空间布局的质量,在 ()H标函数为集装箱体积利用率最优 设计装载方案的过程中,为了确定货物放入集装箱中的 先后顺序,较多地采用定序规则 在此规则屮常用的有体积递减、重量递减、最长边 Z=max 递减等规则。以货物最长边递减规则为例,首先比较货 其中,Z为集装箱体积利用率,为货物的序号,物最长边,如果最长边相同则比较次长边,然后沿着集 1-1,2,…,n,v为第件货物的休积.V为集装箱的装箱的长度方向进行装载;如果货物的最长边和次长边 体积。 都相同,则依次考虑货物的重量,依照降序的规则进行 ()货物总重量约東: 装填。 ∑m≤M )定位规则 在待装载货物遵循一定的先后次序逐个装箱的过 其中,m为第件货物的重量,M为集装箱的最大载程中,需要相应的定位规则确定其摆放位置。 重量。 定位规则包含多种方法,首先将货物放置在集装箱 ()货物总体积约束 的一角,然后沿着边依次装载,最后再填满中心的占角 ()策略应川较多。本文采用占角策略开展装载研究。 ()空间分割规则 ()货物装载一维尺寸约束: 集装箱的剩余空间指装载定的货物以后,集装箱 0≤x7+l1≤L 内部剩余的还可以利用的空间。在后续不断添加货物 0≤y+ve;<W ()的过程中,剩余空间的形状变得相对复杂,很难进行整 0≤x;+h;≤H 体描述。为了使货物的待装载空间表述清楚,采用三空 其中,x1,y1,x为货物摆放位置参考坐标,l,n,h为货间分割规则来对集装箱空间进行划分。 物的长宽高,L,W,H为集装箱的长宽高。 当集装箱中装入一个货物时,此时集装箱中的空间 ()集装箱装满货物后的重心范围约東 结构发生了变化,除去货物所占有的休积外,将剩余空 张钧,等:求解三维裝箱问题的混合遗传模拟退火算法 间划分成前、右、上三个部分。在不断添加货物时,陆续物基准面选取的不同,会产生不同的空间划分方式,除 生成上述子空间,直至装满集装箱或者没有待装货物为图所表示的划分方式以外还有其他多科划分方式。 止。如图即为集装箱三空间分割布局与三维坐标系集装箱未满载前,会不断生成剩余空间,因此必须搜索 对应关系示意图。 y 出可利用的剩余空间。如图所示,在搜索剩余空间的 过程中,对空间的高度进行升序排列,规定待装载空间 的优先级,进而保货物由下至上进行装载。 开始 la. b.cls 搜索空间 ,W,H) 还有刺余空间吗 剩余空间划分 剔除含有零坐标的空间 启发式算法具体编码序列形式如下 将空间按Z坐标升序排列 y,2 在上述编码序列中,表示集装箱序号,x2,y,z 结束 表示这一空间可放置参考点的三维坐标,即空间的左后 图搜索剩余空间流程图 下顶点坐标。当可放置参考点的三维坐标为原点时,该 ()空间合并规则 空间的长宽高为xn,y4,z;当可放置参考点的三维坐标 启发式算法的空间分割为货物的装载寻找出可利 不是原点时,空间的长度表示为: L=max(xb- 3s -y) )用的剩余空间。然而在实际编写算法的过程中,会存在 些无法利用的零散空间,所以要以一定的方法进行整 宽度表示为 合。空间合并是为了充分利用零散空间而形成更大的 W=min(b-o, y,-ya) 待装载空间。这样不但可以提高集装箱的空间利川率 高度表示为: 同时也将收善货物的装载效果。下面对剩余空间的合 H=y.-2 () 由以上编码规则可知,集装箱长为L、宽为W、高并进行介绍。 定义K()=(x,y,x,x,y,x表示集合K()的零 为H,则该集装箱初始可用空间表示为: 散空间厅号,则闲置的剩余空间碎片的长度为 V=(i,0.0.0.L,W,H) Ly=max(; -ci,yi-yi 例如将一件长为a,宽为b,高为c的货物按照如 图所示的方法装入集装箱后,新生成的三个剩余空间宽度为 V(m)的编码及尺寸为: Wi=min(r-i,y;y )=(a,0,0,1,WF) 高度为 XL-a. w W.=min(l-a, w) 在设计算法的过程中,将集装箱置于三维坐标系 H 中,所以空间合并包括一种方向的合并。图图展示 V(m+1)的编码及尺寸为 了集装箱中部分货物装载空间合并示意图 V(m+1)=(0b.0,a,W,Ⅰ max(a, w-b Wn+l=min(a, W-6 V(m+2)的编码及尺寸为 图前后合并示意图 V(m+2)=(i,0,0.c,a,b,H) I m+=max(a, b) =min H 集装箱剩余空间划分是继续装入货物的前提,对货 图左看合并示意图 计算机工程与应用 开始装载 导入货物与集装箱信息 初始化空间 图上:下合并示意图 搜索空间 ()三空间分割启发式算法步骒 根据三空间分割启发式算法的设计理念,结合定序 待装货物可否装入当前空间 选用下一个集装箱 规则定位规则、空间分割规则以及空间合并则,使货 物的装载过程有序可控算法具体步骤如下: 放置待装货物 步骤导入集箱与货物基本数据通过函数变量O 定义货物种类数、货物数量总数集装箱序号,根据空间 空间分割 编码规则,初始化集装箱剩余空间。 空间合并 步骤对货物的摆放位置进行编码 否 货物装载完毕 其中,为集装箱的箱号,为货物的种类号,x,y,为 ↓是 货物放置的起始坐标点,,,h为货物的长、宽、高。 结装载 步骤对待放入集装箱货物的尺寸与集装箱最人 图三空间分割启发式算法流程图 承载量进行判断,货物的长、宽、高小于集装箱剩余空间 编码与解码 的长、宽、高,货物重量之和小于集装箱的最大承载量 本文算法编码由货物装载顺序和货物放置状态两 步骤当货物满足上述装载要求时,按照上述的编部分组成即采川两段式编码。 码方式进行装载。装载完毕后,根据空间分割规则产生 ①货物装载顺序编码 三个了空间,分别为前空间、右空间和上空间。每次生 利川自然数对k种货物进行编号,然后生成货物的 成剩余空间集合后,都要根据空间合并规则对空间进行装载顺序 合并操作。 ②货物放置状态编码 步骤对剩余空间中的z坐标进行排序,进而确 放置状态通常分为任意旋转、絷止旋转、水平旋转 定空间的高低,确保货物是从下往上进行装载。 三种。任意旋转的货物有种摆放方式,编码值用自然 步返川步骤,依次加载后续货物,直至货物数,, 表示;禁止旋转的货物只有一种摆放方 序列集合为空。 式,编码值用自然数表示;水平旋转的货物有两种摆 步骤当集装箱剩余空间不能满足货物装载,就要放方式,编码值用,表示 用下一个集装箱。 编表示如下 步骤最后得出装载结果和剩余空间的数据。 P={S1,S2…,S,S+1,S2-2…,S2 根据以上步骤说明,三空间分割启发式算法流程图 解码过程在三空间分割启发式算法中进行,此过程 如图所示 确定了某种货物在对应集装箱中的摆放数量以及摆放 混合遗传模拟退火算法 位置。解码的表示方法在三空间分割算法中有着详细 根据相关研究,遗传算法在求解 问题中有的介绍。 着较好的全局搜索能力,但在局部搜索与收敛速度方面 )选择算了 效果不是很明显,而模拟退火算法则在局部搜索中展现 本文算法利用轮盘赌方法进行个体选择。 出较好的能力。因此本文采用二者结合的方法来解决 ①染色体适应度: 三维装箱问题,并且算法中融入了最优解保存策略来提 高性能。 算法在求得新解的过程中包含两个阶段第一阶 ②选择概率: 段是利用三空间分割启发式算法来构造货物的装载空 Uk k= 间,为后续寻优过程提供较为良好的初始解;第二阶段 ③累计概率: 是采用混合遗传模拟退火算法对装载方案进行寻优 下面将详细介绍算法理论及步骤。 9=∑p,k=1,2 张钧,等:求解三维裝箱问题的混合遗传模拟退火算法 ④通过多次旋转轮盘,选出相应的染色体。 按照目标函数值确定混合遗传模拟退火算法后续的搜 ()交叉算子 索空间和搜索方向。 根掂两段式编码,货物装载顺序部分采用部分映射 在两种算法结合的过程中,采取最优解保存策略, 交叉,根据第一部分交叉点的位置,货物放置状态部分这样避免产生的局部较好解在后续的选择、交乂和变异 的编码值在其对应的位置上进行交换。 的过程中出现适应度降低的情况,同时也保证了遗传算 设编码宇符串长度为2k,根据交叉概率确定交叉法的全局收敛性。在最优解保存策略中,通过设置最优 方法是否进行。若进行交叉,在口,之间随机牛成两解保留比例g≠%来俯定直接进入下一代的群体 个不同的整数作为交叉点,通过部分映射的关系来交叉假设上一代群体数量为,通过计算每个个体的适应 前一部分编码值:根据第一部分交叉点位置,第二部分度值,根据相应的排列方式将适应度值排名前名的 的编码值在与其对应的位置F进行交换。交叉示例如个体直接复制到下一代中,不进行后续的交叉、变异等 图所示 橾作环节,降低当前群体中最优解被破坏的可能性。 算法步骤如下所示: 步骤将集装箱与货物的详细数据载入主程序。 步驟设置遗传算法与模拟退火算法参数 装载序 放置状态 步骤根据两段式编码规则随机生成初始种群 P P(m)。 交叉后 步骤根据三空间分割启发式算法进行解码操作, [「「即实现货物的有效装载。 步骤计算每个个体的适应度值。 P 步骤进行遗传算法的选择操作,选取适应度值前 图交叉小意图 的个体直接复制到下一代中,记为Pl(m),未被选 ()变异算子 中的个体进行下一步交叉操作,记为P2(m)。 在种群进化过程中,变异是保持染色体多样性的重 步骤进行交叉操作:P2(m)→P2"(m)。 要环节。为了避免算法过早收敛,装载顺序采用顺序逆 步骤进行变异操作:P2m)→、P2"(m)。 转变异。根据货物摆放方向约束的限制,放置状态变异 步骤进行模拟退火操作,记为P2mm)→P(n)。 范围要在相应的取值范围内进行基本位变异,如图所示。 步骤将最优解保存策略P1m)和混合遗传模 拟退火产生的解P)结合起来,形成新一代种群 步骤终止条件判断,若符合,输出最优解,若不 符合返回步骤。 装载顺序 变异后 放置状态 基亍混合遗传模拟退火算法求解集装箱三维装载 流程图如图所示。 图变异示意图 ()遗传算法与模拟退火算法集成 实验方案 混合算法的起止由模拟退火算法的初始温度和终 本文所研究的集装箱三维装载算法采用 编 止温度控制。由于本文应用三空间分割启发式算法与程语言实现。为了测试算法的有效性,先后采用弱异类 混合遗传模拟退火算法相结合求解集装箱三维装载结测试算例和强异类测试算例对本文算法进行性能测试, 果,可以相应扩大初始种群的数量,在寻优过程中增大并结合其体的货物装载数据,得出三维装载图与目标函 全局搜索范围。所以根据某种特定的定序规则定义初值。 始种样的产生,会导致寻优结果产生局限,囚此采用随 参数设置 机生成初始种群的方式对装载结果进行寻优。 在 的环境下,所使用的计算机配 按照三空间分割启发式算法的相关规则进行集装置数据为: 箱装载,判断每个个体的适应度值,然后进行遗传算法存操作系统为 专业版。在实现算法 的选择操作,进行下一步的适应度评价,并在算法设置之前,确定遗传算法与模拟退火算法的具体参数为:种 的起止范围内进行重复迭代,最终输出最优解。针对集群规模Pe-20,交又概率pros0.9,变异概率 装箱三维装载的具体特点,本文将优化模型中的目标函 simulation-0.05,最优解保留比例-10%,初始湿度 数直接作为混合遗传模拟退火算法的适应度函数,可以T=100,终止温度7=103,降温速率q=0.97 计算机工程与应用 表弱异类货物测试对比 算法 本文方法 开妗 通过 仿真灾验,空间利用率达到 结 果明显优于许光泞应用的遗传算法解决装箱问题 建立箱体及货物数据库,后续读入 的优化结果,算例对比结果如表所示 设置遗传算法及模拟退火算法的相关参数 表强异类算例 算法 利用函数产生初始种群 体积利用率 许光泞 空间分割启发式算法产生装载方案 本文方法 选择操作 货物装载结果如表所示,根据以上实验证明,本 文的混合遗传模拟退火算法与三空间分割启发式算法 判断个体是否直接成为下一代 在求解强异类货物装载中,得到了较为理想的装载方 案,以上结果充分证明了本文算法适用于解决三维装箱 交叉、变异与模拟退火操作 最优解保留 山题。 表货物装载结果 组合成为下一代种群 箱号货物序号 放置起始坐标 货物尺寸 模拟退火算法降温 心 长 否 判断是否满足终止条件 翰出当前解作为最优解 图混合遗传模拟退火算法流程 算例分析与比较 在弱异类测试中,使用 提出的算例,测 试目标是将一组尺寸不同的货物分配到一个已知的集 装箱内并且使得集装箱的体积利用率最大。同时本文 还将同样应用此算例进行求解的的研究结果进行 对比,结果如表所示,表中数据为集装箱体积利用率。 通过表可以看出,在种弱异类算例中,有种 算例均可实现全部装载,实现最优结果。经过本文算法 进行装载优化后,较难算例 也 得到了较高的体积利用率,分别为 集装箱体积利用率高于的装载结果。 针对 的组经典弱异类问题测试,木 文采川的混合遗传模拟退火算法与三空间分割启发式 实例验证 算法相结合的方法,具有较好的优化效果,允分证明本 通过上节算例分析与比较可知,本文算法在求解集 文算法在求解弱异类货物装载过程屮具有明显的优装箱-维装载问题中有一定的优越性。现将本文模型 势。由于弱异类货物装载具有组算例,不能一一将中考虑到的体积约束重量约束以及重心约束应用于实 装载结果体现。 际集装箱装载,所采用的集装箱为,具体属性如 在强异类测试中,选取国内学者许光泞应用的货物表所示 装载算例:算例中包含种尺寸大小不一的货物,符 表集装箱属性 合强异类货物装载问题数据类型,待装载集装箱的规格集装箱类型代码长宽高载重量 为 张钧,等:求解三维裝箱问题的混合遗传模拟退火算法 货物数据来源丁吉林大学赵雨霏硕上论文《我国快 递企业航空货运飞机装载优化研究》,货物数据详情 如表所示。 表货物数据详情 序号长 数量重量 图集装箱装载三维图 结東语 针对集装箱一维装载过程,建立了多目标约束模 以上数据为快递公司提供的部分待装载货物,货物型采用混合遗传模拟退火算法与三空间分割启发式算 的儿何中心为重心且叮混合装载,符合模型中假设规法结合求解。经过弱异类、强异类以及实际货物装载算 定。重心约束规定为X轴方向偏差为,),Y轴方例的测试,取得了理想的装箱效果,正明了算法的有效 向偏差为(,),Z轴方向偏差为(、)。 性和可行性。本文算法中的三空间分割启发式算法,模 将上述数据进行测试,本文算法得出用个集拟了人工装箱的思路,通过空间分割与合并等规则进 裝箱将上述件货物全部装完,其中装载量最大的集步提高了装箱利用率,釆用遗传算法和模找退火算法技 装箱体积利用率为 ,具体结果如表所示。 术集成,利用两段式编码方式确定了货物装填顺序和摆 表体积利用率及重心结果 放方向,解除了对货物装填过程单一规则的限制,为优 箱号体积利用率重心(x)重心(y)重心(x 化空间利用率提供更好的选择。通过具体的编程方法, 得出了集装箱三维装载图示,为装载过程提供了智能的 通过上述结果可以看出本文算法在求解集装箱 决策方案。根据集装箱三维装载自身的复杂性和特殊 维装载的过程中集装箱取得了较高的体积利用率重性,不规则货物与不规则集装箱装载更多目标与约東 心偏差范围较小,且在规定范围内。同时将本文设计的等问题有待进步研究。 混合遗传模拟退火算法( )与标准遗传算法() 和模拟退火算法()进行对比,结果如图所示 参考文献 迭代次数 图算法优化性能比较 根据对比图可知,本文所设计的 算法能够 在较快的时间内搜索到全局最优解,收敛速度明显优 算法与算法,从而证明 算法具有很强的 收敛性。 由于第二个集装箱是在第一个集装箱满载后才进 行装载,因此其装载结果不能对本文算法说明问题,如 果考虑更多货物数据情况下,能够满足第二个集装箱全 部装满,可能会得到一个较好的体积利用率。本文将货 物的摆放位置进行了可视化展示,图即为本次算例 得出的最大三维装载图示。 下转第页)

...展开详情
试读 8P 论文研究-求解三维装箱问题的混合遗传模拟退火算法.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_38743968 你的留言是对我莫大的支持
2019-09-11
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 至尊王者

    成功上传501个资源即可获取
关注 私信
上传资源赚积分or赚钱
    最新推荐
    论文研究-求解三维装箱问题的混合遗传模拟退火算法.pdf 10积分/C币 立即下载
    1/8
    论文研究-求解三维装箱问题的混合遗传模拟退火算法.pdf第1页
    论文研究-求解三维装箱问题的混合遗传模拟退火算法.pdf第2页

    试读结束, 可继续读1页

    10积分/C币 立即下载 >