英语原文共 10 页，剩余内容已隐藏，支付完成后下载完整资料
基于混合遗传算法，利用三维非均匀装箱模型的多约束问题
摘要：这项工作提出了使用遗传算法的不同方法，将任意尺寸的三维装箱优化为棱柱型集装箱，同时考虑主要装箱实时装箱约束（包括承载约束、放置空间约束、稳定性约束、重叠性约束、方向约束、重量约束等），本研究的主要目标是在遵循上述装载约束的前提下，将任意尺寸的非标准箱优化为标准的棱柱形集装箱，采用不同的遗传算法（诸如二进制算法、带或不带惩罚适应度函数的十进制算法、带最大化或最小化适应度函数的约束遗传算法、启发式遗传算法和混合遗传算法），在任意尺寸装箱以及各种装箱约束的前提下，遗传算法被用于最小化集装箱内部未使用的空位空间，调整算法是启发式算法在本研究中的应用，旨在通过填充容器内未使用的空闲空间来提高遗传输出，调整算法亦提高了将获取的输出转化为表格式或图标格式的可读装载箱序列的能力。总的说，遗传算法和启发式算法的联合应用被认为与启发式箱体装载技术相当。
1.介绍
进化算法基于生物进化原理（hopper and turton，1997），遗传算法是一类用于在较短时间内优化各种复杂约束问题的进化算法。工业和物流企业面对的一个复杂问题就是：如何在更短的时间内，以更低的成本在全球范围内包装和分销他们的产品。一般情况下，货物装在箱子里，箱子装在集装箱里，以便安全、可靠和紧凑地分发。使用集装箱地运费也包括在产品成本中，但不增加任何额外的费用。因此，充分利用可利用的集装箱空间，将非增值的成本降到最低成为企业的当务之急。这一问题在本研究中已通过遗传算法实现。Artside等人在2018年开发算法，重点是装载过程中箱体的重叠问题，在计算集装箱的占用率时也考虑了同样的问题。Ranga等人在2018年的研究中考虑了集装箱内部箱子的旋转以实现最佳装载，取代自由旋转，并通过超载变异操作实现正交旋转。Fabrizio和Andrea在2018年进行二维装载问题启发式规则研究，但本次研究重点在3D装载和多或少的广义算法上。Martinez等人在2017年开发了具有不规则箱自由旋转的装箱算法，在此研究中，考虑四种不同形状的任意大小物品。Xueping和Kaike在18年应用车间算法于二维物品的装载，但本次研究使用三维装载。Celia等人在2018年尝试通过考虑运输约束以解决装载问题，同时本研究也考虑了惩罚函数。Gorge和Robinson在1980年引入将物品逐层装载至标准集装箱的方法。Hopper和Turton在1997年将遗传算法的概念应用到箱式装载的问题中，并证明遗传算法的性能是令人满意的。Bortfeldt和Gehring在2001年基于逐层装载的概念，且含装载约束的集装箱装载问题，提出了混合遗传算法，并证明该算法可提供满足装载约束的可行解。Lodi等人在2002年采用禁忌搜索的启发式算法，在三维多集装箱装载问题中加深的纸箱的方向性考量，并证明纸箱的方向性在优化装载中也起着重要作用。Martine Labbe等人在2003年提出一个在最少时间内将最大数量的物品装入集装箱的计数算法和边界。Nihat和Anurag在2004年完成了一种改进的人工神经网络算法，用于求解结合迭带试验学习法和优先逻辑方法的经典物品装载数据集。Zhou和li开发了一种将不同尺寸的物品装载至集装箱的第三树方法。Wenqi和kun在2009年将一种新的崩落算法应用于解决三维单集装箱装载问题。Leonardo等人在2010年建立了一种数学模型（在考虑货物稳定性和承载约束前提下，将矩形物品装入集装箱）。Rajesh等人在2017年使用萤火虫算法试验了装载优化。Allen等人在2011年引入空间策略（在3d条形型装载问题中），其中考略了一套标准的长方体，放入一个宽度、高度固定和长度无约束的容器中。Rajesh等人在2012年开发了遗传算法，将二维矩形物体装载至更大的矩形内。Rajesh和Saravanna在2012年遗传算法运用于动态装箱问题。尽管有许多启发式和混合方法应用于3D装箱，但这些方法大都将三维问题简化为二维问题，甚至简化为一维问题来求解。也有一些方法没有考虑主要的装箱约束。根据文献调查，显然有必要对三维装箱问题进行优化，在满足装载约束前提下，装载n个任意大小的物体。
在本次研究中，我们将规则尺寸的矩形棱柱形容器放在一边，以试验n个不同形状棱柱形容器的装载（在相应的填料约束下，考虑不同尺寸的方形、矩形、圆柱形和球形物体）。装载约束有：承载约束、放置约束、稳定性约束、重叠约束、方向约束和重量约束。对用户定义的装箱数据进行编码，并输入到遗传算法中进行优化，所开发的遗传算法模块在不违背约束的情况下，识别出最优可行的装载模式，从而获得最大的集装箱利用率。
许多研究者并没有考虑主要的装载约束，本研究中得到的最优可行解可供工人直接用于装载过程。因为其他研究者没有尝试过突变超载，研究者们同样对突变遗传算子进行了超负荷敏感度分析。另外，为了提高基因在装载中的效果，本文将如此组织。、
研究者的背景研究工作已经在文献第二节讨论过。第三节描述了不同的实验实现和所获结果。最后，给出结论和未来的方向。
2.装箱问题
装箱问题是指在满足装箱约束条件的前提下，在最大箱容的条件下确定物品组合的问题。输入为集装箱规格、物品数、物品规格及相关的约束条件。用户定义的数据应检查其完整性，并根据权重值按降序排序。不正确的装箱和任意的不规则箱会导致容器内部形成一些空的未使用空间。容器内部形成的这种空隙是主要问题，这回导致箱子不稳定，使用额外的集装箱，使用额外的安全气囊/减震器/填塞器和插管，增加货物/运输成本和整体零售成本，而不会增加装载附件的任何附加值，为解决装箱问题，开发了各种模型，并用二阶数学方程对开发的模块进行了验证。
3.遗传算法-二进制编码
在二进制编码的遗传算法中，用户定义的盒子数据已经被编码成了二进制元素。盒子的编码格式应该包含盒子的尺寸、容器内的位置及其约束条件。图1给出了两个双亲（每个双亲含4个盒子）的样本。
图一中，前九个二进制数字表示三维盒子尺寸，后3位数字表示容器内盒子的位置。盒子位置可以是最近装载的盒子的左右上下前后。盒子的方向占据后两位数字，表示垂直或水平位置。最后1至2位数字是识别箱子的辅助数据。其他装载约束在最后阶段检查，以使解决方案可行。这些二进制元素将作为输入元素输入到开发的混合遗传模块中，进而确定集装箱内装载模式的最优序列，遗传算法模块的各个阶段是初始父公式、父交叉、子变异和适应度函数计算，适应度函数用于最大化集装箱容积利用率，遗传算法输出的这些箱子将随着问题的位置和方向进行装载。这些输出已经检查了装载约束，并且认为满足装载约束的模式是可行的解决方案。即便模块给出了更好的结果，计算时间和内存使用也会随着问题大小的增加而增加。因此，更好的开发模式已改为十进制编码方式。
4.十进制编码遗传算法
编码遗传算法模块中，使用十进制编码代替二进制编码减少了计算时间和内存使用2给出了一组十进制编码的父代样本。
十进制数1、2、3、4分别代表立方体、矩形棱柱体、圆柱体、球体。在图2中，起始数据2、4、2、1、3分别表示矩形棱柱体数据库中的盒子、球形数据库中的第一个盒子、矩形棱柱形数据库中的第二个盒子、来自长方体数据库中的第一个盒子、来自圆柱体数据库中的第一个盒子等等。这些父代被遗传算子允许操作以识别最佳装载模式。这些约束需要被检查以从DCGA输出可行的盒子装载模式。在某些情况下，最优GA解通过约束检查消除，从而浪费了从不可行的模式集中识别最优解的计算时间，通过使用带有惩罚适应度函数的十进制编码来增强DCGA模块，避免了这种情况。
5.带惩罚适应度函数的十进制编码遗传算法
在该DCGAP模块中，在计算适应度函数值的阶段检查约束。违反约束的约束将具有较小的适应度值并从生成中消除，罚适应度如下：
Fobj（x）是最大化适应度函数的目标函数，它计算集装箱内装载箱所占的总体积，plc（x）是位置（边界交叉）约束，惩罚值为0.25。ovr（x）、stb（x）、weg（x）、ori（x）、lber（x）分别表示集装箱及其内部物品的重叠约束、稳定性约束、重量承受能力约束、物品方向约束，以及容器的最大承载能力，罚值为0.1。尽管DCGAP在较短的时间和内存使用量下产生了最优可行的装载模式，但对于较大规模的问题，其性能可能并不让人满意。本研究通过修改遗传算子以获得更好的性能来解决这一问题。
6.启发式遗传算法
在启发式遗传算法模块中，交叉算子和变异算子分别增强为两点双交叉和重载变异算子。图3解释了这一过程。
在图3中，“亲本-x”是从一组随机配置的人群中随机产生的样本亲本。对于交叉而言，在本研究中，交叉位点也是随机产生的，样本点位为07，22，51，68。因此，第58位到102位之间的字符串在第一和第二双亲之间交换，以生成由“temp offspring”表示的临时子代，该子代又与第三代双亲交换从第30位到第75位的字符串，以生成由“offspring I”表示的新子代，它继承了三个双亲的性质，从而通过生成新的参数组合来增加解空间。为了避免在局部最优点出现停滞，已经允许产生的后代在突变遗传算子上操作。
在这项研究中，作为一个特定于应用的启发式，两点遗传变异在方向满足约束下被超载，通过超载而不是改变盒子的类型，盒子的方向通过随机交换盒子的长度、宽度和高度等尺寸参数而改变。随机产生的变异点位为9和65。对第65位和第4位进行解码，得到矩形棱柱体数据库中的第4个物体和圆柱体数据库中的第12个物体。通过应用突变操作，突变后代结构保持不变，但考虑到在用户定义的方向约束下，这些箱子的尺寸值被互换，如图4所示。这样就避免了停滞，通过超载操作也检查了不同的方向。基于多次迭代结果，研究发现，即使经过多代，种群中父代起始位置的字符串仍然保持不变。这可以通过交换操作来避免。
本研究采用单点随机交换的方法，如图5所示，随机产生的交换点为82，然后将超出位置的字符串交换到前面，形成“交换缓冲区”。这样，同一组存储箱将保留不同的包装顺序。
HGA在标准基准问题上取得了较好的效果，但在真实情况下，物流企业将接受到多种不同尺寸的物品。这将导致边界附近形成空位，同时HGA的输出应为装载可读格式。因此，本研究中开发了一种特殊的启发式算法，即调整算法。
7.混合遗传调整算法
基于首次适应算法的概念，将遗传算法与优化算法即混合遗传优化算法相结合，对集装箱内有或没有空位的物品进行装载，并以装载可读表格和图表格式生成输出。一个样本箱装载输出如表1所示，表示物品的类型、尺寸、集装箱内的放置位置以及体积数据。
为了便于用户和装载工人理解，该表格数据已经转化为图表格式。图6显示了给定数据集的示例图表格式和第一个底层的俯视图/平面图。图6中的每个方框及其数值分别表示一个箱子及其序列号。
8.结果
表2比较了不同方法对bischoff和ratcliff（1995）试验实例的装载集装箱利用率，HGTA数据是连续10次试验的最佳值。
表2说明，与带惩罚适应度函数的遗传算法相比，应用混合遗传算法，集装箱装载的有效性从67.35%提高到92.57%，因此，应用HGTA明显提高了遗传算法的有效性。
9.结论
本研究提出一种较好的混合遗传算法，藉由整合即使装载限制约束，来处理不同大小、不同形状集装箱的三维装载问题。实验结果显示，启发式的遗传改良，如双点双交叉、定位变异和交换操作增加了求解空间，通过满足装箱约束得到了可行的装箱模式，TA进一步提高遗传输出的有效性，并考虑了非棱柱形物体装载的进一步改进措施。
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[239228]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
