论文部分内容阅读
随着电子商务的飞速发展,电商平台每天处理的订单数以亿计,订单包装箱的成本日益不可忽视。包装箱的规格尺寸对于订单包装成本具有根本性的影响,对其进行科学决策具有巨大的经济价值。本文将其归结为一种箱型设计及装箱问题(Bin design and packing problem,BDPP)。该问题为根据待装载物品来设计规定数量种类的箱型,每种箱型的成本为其长宽高的函数,求装载完所有物品时所用箱子总成本最小的箱型设计方案和对应的装箱方案。BDPP问题本质上是一种开放维度问题(ODP),但由于涉及多箱型三维装箱问题(3D-MBSBPP),而且每种箱型的三个维度尺寸全部开放,其复杂度在这类问题中是最高的,目前尚未查到针对此问题的研究,因此本文也具有很大的理论研究价值。首先,本文阐述了与BDPP关联紧密的ODP、3D-MBSBPP的研究现状。其次,本文建立了BDPP的数学模型,并对目标函数进行了线性化处理,用于模型验证。然后对BDPP进行了分解,将BDPP分为六个层级的决策问题,并以此为基础提出了四种启发式算法:针对BDPP的子问题3D-MBSBPP分别提出了一种确定性启发式算法(DCHA)和一种禁忌搜索变邻域搜索混合启发式算法(TSVNSHHA);针对BDPP主流程则分别设计了一种混合遗传算法(HGA)和一种混合差分进化算法(HDEA)。DCHA是建立在本文提出的点面结合的复合空间结构基础上的求解3D-MBSBPP的启发式算法。DCHA既可以为TSVNSHHA提供初始解,还作为内层算法被HGA和HDEA调用。以上算法都可以求解物品可旋转及不可旋转两种情况下的问题,并且还可以考虑物品的易碎性约束。在数值实验中,采用前人提出的3D-MBSBPP算例,先对DCHA的8种策略组合进行了测试,选择表现好的策略组合2和8分别为物品不能旋转和可旋转时的默认策略组合。在3D-MBSBPP的实验中,通过与GRASP*算法进行对比,证明在相同时间内本文提出的TSVNSHHA算法可以得到更好的解:物品不允许旋转时,TSVNSHHA比GRASP*算法成本下降3.34%;允许旋转时,下降达到了10.71%。在BDPP的实验中,针对前人算例及其给出的箱型,采用HDEA算法优化箱型后可使成本下降16.47%,HGA算法则可使成本下降多达27.28%。在国内某电商实际数据上测试的结果则是HDEA可使装箱成本下降37.56%,而HGA可下降35.7%。以上实验说明,基于本文设计的BDPP算法重新设计箱型可以大幅降低装箱成本。