详情

原文传递三维装箱与选箱算法研究

论文题名：	三维装箱与选箱算法研究
关键词：	物流运输;装箱问题;选箱问题;多约束条件;启发式算法;布局类型;空间分割
摘要：	进入新世纪以来，电商平台和物流企业得到了飞速的发展，其中物流运输涉及到货物的装箱以及货箱的选择问题，合理的装箱方案和合适的货箱箱型不仅可以有效提高货箱的空间利用率，还能减少不必要的纸箱浪费，从而降低货物的运输成本和材料成本。此外还可以大大地提高工人的装箱效率，避免频繁地进行货物摆放位置的调整，节约大量的时间，因此研究三维装箱问题和选箱问题有着极大的理论价值和实践价值。　　首先现有的装箱算法大多缺乏对实际约束条件的考虑，降低了算法在实际生产中的可行性和实用性。因此，本文针对沿托盘边缘摆放货物这一关键约束条件以及其它10种现实约束的单箱型强异构货物装箱问题进行了研究，提出了一种两阶段启发式装箱算法，在第一阶段将三维装箱问题转为二维装箱问题，即先将货物摆放成层，设计了三种符合约束条件的二维布局类型，针对剩余零散货物提出了稳定支撑算法和插缝算法来构造货物层，最后将层在托盘高度方向上进行摆放。算法在苛刻的约束条件下仍达到了平均近80%的空间利用率，达到了实际生产中的要求。　　其次，货箱的规格尺寸对订单成本有着极大的影响，本文将优化货箱箱型的问题归结为三维装箱与选箱问题（BinPackingandSelectingProblem，BPSP）。该问题主要是根据过去的订单信息并结合三维装箱算法设计指定数量的不同规格的货箱，每种货箱的成本包括运费成本、箱体材料成本、填充物材料成本，分别与货箱的三边和、表面积以及空间利用率有关。针对BPSP的子问题，即多箱型强异构货物装箱问题提出了一种基于预先打包策略和底面平铺策略的空间分割算法，并对货物摆放顺序、子空间选择进行了针对性优化，在实际算例的测试种达到了平均85.6%的空间利用率，为下一步的选箱算法提供了基础。　　最后，针对BPSP中的选箱问题，提出了货箱箱型优化的启发式算法，其中货箱的生成结合了聚类算法，货箱尺寸的优化则是根据订单中的货物信息，并结合三维装箱算法，选出货箱规格尺寸最为合适的货箱箱型。在实际案例的测试中，该算法使运费和材料成本合计下降多达17.84%，实验证明该算法可有效降低物流成本。
作者：	智阳光
专业：	计算机科学与技术
导师：	王书振
授予学位：	硕士
授予学位单位：	西安电子科技大学
学位年度：	2021