考虑时间窗约束的装箱问题研究

发布时间：2020-07-12 04:26

【摘要】：本文介绍和研究了考虑时间窗约束的装箱问题(BPPTW),该问题是物流行业中普遍存在的实际问题。快递公司每天需要将待配送的货物从配送中心交付到各个客户手上,在配送之前,就涉及到怎样装箱的问题,当待配送的物品含有到达时间窗限制时,由于时间窗没有交集的两个物品不能装入同一个车厢中,此时不能再按照传统的装箱方案来装载物品,必须为考虑时间窗约束的装箱问题设计一个合理的装箱方案。合理的装箱方案不仅能为企业节省运输费用、提高配送效率,还能进一步地提高客户满意度。假设配送中心有若干待配送的物品以及足够的车厢,且这些物品具有不同的重量和配送时间窗,目的是选择一组具有最低成本或最少数量的箱子来装载所有物品。装载在同一箱子中物品的总重量不得超过该箱子的重量约束,且同一箱子中所有物品的时间窗之间必须有一个共同的时间点。BPPTW是装箱问题的一个扩展,由于装箱问题是NP难问题,所以BPPTW也是NP难问题,对其进行研究能够丰富组合优化领域的内容,为以后学者研究该类问题提供一个基准;同时,研究BPPTW还能提高物流的配送效率,从而为企业降低运输成本和提高客户满意度。因此,研究该问题具有重要的理论价值和实践价值。本文首先将时间窗约束考虑到一维装箱问题中,从而形成了考虑时间窗约束的一维装箱问题(1DBPP-TW)这一新问题,在综合考虑装箱问题和带时间窗约束的车辆路径问题的数学模型之后,为1DBPP-TW建立了数学模型。首先,针对该模型,本文采用了IBM公司开发的CPLEX对其进行求解;接着,提出了基于时间范围的贪心启发式算法(GTR)来快速生成该问题的初始可行解;最后,开发了一种迭代局部搜索算法(ILS)来进一步提高解的质量。本文对CPLEX、GTR算法、ILS算法进行了大量的实例测试,结果表明,CPLEX仅能求解规模较小的实例,GTR算法能在很短的时间内为1DBPP-TW找到较好的初始解,ILS算法能进一步地提高初始解的质量。本文继续将时间窗约束考虑到变尺寸装箱问题中,从而形成了考虑时间窗约束的变尺寸装箱问题(VSBPPTW)这一新问题。首先,本文在1DBPP-TW模型的基础上为VSBPPTW建立了数学模型并采用CPLEX求解该模型;然后,采用著名的最佳适应启发式算法(BF)为VSBPPTW产生初始可行解;最后,开发了一种最短路径解码器,并在最短路径解码器的基础上开发了ILS算法来进一步地提高解的质量。为了检验ILS算法的有效性,本文采用了文献中变尺寸装箱问题(VSBPP)的例子(实例集Set1和Set2)来进行实验,实验结果表明:ILS算法在求解实例集Set1时,其计算结果都劣于文献中求解VSBPP最好的变领域搜索算法(VNS),但与VNS计算结果的差距很小;ILS算法在求解实例集Set2时,部分测试实例的计算结果要优于VNS算法,但平均结果微劣于VNS算法。ILS算法是针对VSBPPTW提出的算法,但其在求解VSBPP问题时也表现出较高的性能,与求解VSBPP最好的VNS算法之间的差异很小,可以证明ILS算法的有效性。同样,本文继续使用CPLEX、BF算法、ILS算法求解VSBPPTW实例。结果表明,CPLEX仅能求解规模较小的实例,BF算法能在很短的时间内为VSBPPTW找到较好的初始解,ILS算法能进一步地提高初始解的质量。因此,本文得出的结论为:GTR算法和BF算法能为1DBPP-TW和VSBPPTW快速生成问题的初始可行解,ILS算法能进一步地提高初始解的质量。虽然ILS算法是针对1DBPP-TW和VSBPPTW提出的高效启发式算法,但其在求解VSBPP时,也表现出较高的性能。
【学位授予单位】：江西财经大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：TP301.6;F253
【图文】：

考虑时间窗约束的装箱问题

研究思路图

NF算法装箱过程

【参考文献】

相关期刊论文 前1条

1 张铁山;郭晓薇;;社会物流总费用变化趋势与影响因素分析[J];物流工程与管理;2014年09期

本文编号：2751417