在冷链物流企业装箱作业中, 不仅需要满足传统装箱问题中所涉及的空间约束, 同时也需要满足不同商品存放时的温度要求. 在实际作业中, 不同的商品具有不同的装箱温层区间, 温层区间不相交的商品不能被装入同一个箱子. 为维持运输中温度的稳定, 需在箱内装入一定数量的冷媒, 而这又会影响到箱内可装载的空间, 对成本产生不利影响. 为解决这一挑战, 本文研究带有温层和冷媒装载约束的冷链商品三维多箱型装箱问题, 综合考虑了冷媒、 箱子、 运输三项成本并给出其数学规划模型, 同时设计了三种用于求解该问题的启发式算法. 本文基于一大型电商物流企业的真实订单数据, 改造生成了不同规模的测试算例以检验各算法的表现. 数值实验结果表明, 所提出的三种算法都能在合理的时间内给出该问题的较优解. 通过与各算例最优解的下界比较, 发现基于物品分组的启发式算法求得的平均成本距下界最近, 但求解速度较慢. 求解速度最快的为结合模拟退火的基于极端点法的构造型启发式算法, 但其在大规模测试算例上的表现要差于其他两种算法. 通过进一步对比分析三种算法的适用场景, 能够为企业提供管理见解与启示, 有望改善冷链物流企业的实际装箱操作流程.
Abstract
In the bin-packing operations in cold chain logistics companie, it is essential to meet not only the spatial constraints involved in traditional packaging problems but also the temperature requirements for storing different goods. Different goods have distinct temperature layer for packaging, and goods with non-overlapping temperature layers cannot be packed into the same boxes (bins). In this work, we study the 3D multiple bin-size bin packing problem with temperature layer and refrigerant loading constraints (3DMBSBPP-TLRL) that focuses on packing a list of perishable goods into insulated boxes (bins) of different types that are loaded with refrigerant packs in different quantities. Our objective is to minimize the total material and shipping costs. Since the insulated bins require special packing materials and refrigerant that are expensive, inefficient planning during the setup or packing, however small, can adversely affect costs. We first develop a set of geometric constraints as well as two temperature-related constraints for this problem. The temperature layers and refrigerant loads are considered. Then, we propose a mathematical programming model which in essence is a nonlinear programming model. We find that it is infeasible to solve this model directly. Next, we develop three different heuristic algorithms. Two of them are constructive heuristics based on extreme point and empty space generation. The third one is a two-stage heuristic algorithm based on item grouping. To test the proposed three algorithms, we conduct computation experiments based on real transaction data from a cold chain logistics company. The effectiveness of the algorithm in terms of run time and solution quality is verified compared with the solutions obtained from the relaxed mathematical programming model. Numerical experimental results show that while all three proposed three algorithms are able to provide reasonably good solutions to 3DMBSBPP-TLRL within a limited time, the two-stage heuristic algorithm based on items grouping performs best, achieving the lowest average cost in all the instance sets of different scale. The fastest algorithm is the extreme point-based constructive heuristic algorithm, but it fails to perform well in terms of solution quality on large-scale test instances. The business scenarios of the three proposed algorithms are discussed and analyzed at the end of the paper, further providing managerial insights that hopefully will facilitate real bin-packing operations in cold chain logistics companies.
关键词
三维多箱型装箱问题 /
冷链物流 /
温度敏感商品 /
构造型启发式算法
{{custom_keyword}} /
Key words
three-dimensional multiple bin-size bin packing problem /
cold chain logistics /
temperature-sensitive product /
constructive heuristic algorithm
{{custom_keyword}} /
中图分类号：
F224.3
U169.42
{{custom_clc.code}}
({{custom_clc.text}})
{{custom_sec.title}}
{{custom_sec.title}}
{{custom_sec.content}}
参考文献
[1] 国家发展和改革委员会. 2022年"十四五"冷链物流发展规划[EB/OL]. [2023-08-03]. https://www.ndrc.gov.cn/fggz/fzzlgh/gjjzxgh/202203/t20220325_1320204.html. National Development and Reform Commission. The 14th five-year plan for cold-chain logistics[EB/OL]. [2023-08-03]. https://www.ndrc.gov.cn/fggz/fzzlgh/gjjzxgh/202203/t20220325_1320204.html.
[2] 牟进进, 陈莒伟, 王淑云. 蓄冷式多温集配路径优化模型[J]. 中国管理科学, 2022, 30(10): 236-246. Mou J J, Chen J W, Wang S Y. Optimization model of cold accumulated multi-temperature joint pickup and distribution[J]. Chinese Journal of Management Science, 2022, 30(10): 236-246.
[3] Ostermeier M, Hübner A. Vehicle selection for a multi-compartment vehicle routing problem[J]. European Journal of Operational Research, 2018, 269(2): 682-694.
[4] 王淑云, 孙虹. 随机需求下冷链品多温共配路径优化研究[J]. 工业工程与管理, 2016, 21(2): 49-58. Wang S Y, Sun H. Optimization of multi-temperature joint distribution with stochastic demands[J]. Industrial Engineering and Management, 2016, 21(2): 49-58.
[5] 戴夏静, 梁承姬. 带时间窗的蓄冷式多温共配冷链配送问题研究[J]. 重庆师范大学学报(自然科学版), 2017, 34(5): 18-25. Dai X J, Liang C J. Cold storage type of multi-temperature distribution problem with the soft time windows[J]. Journal of Chongqing Normal University (Natural Science), 2017, 34(5): 18-25.
[6] 丁秋雷, 胡祥培, 姜洋, 等. 考虑新鲜度的农产品冷链物流配送受扰恢复模型[J]. 系统工程理论与实践, 2021, 41(3): 667-677. Ding Q L, Hu X P, Jiang Y, et al. A recovery model for cold chain delivery of agricultural products by considering freshness[J]. Systems Engineering—Theory & Practice, 2021, 41(3): 667-677.
[7] Martello S, Pisinger D, Vigo D. The three-dimensional bin packing problem[J]. Operations Research, 2000, 48(2): 256-267.
[8] Faroe O, Pisinger D, Zachariasen M. Guided local search for the three-dimensional bin packing problem[J]. INFORMS Journal on Computing, 2003, 15(3): 267-283.
[9] Moura A, Oliveira J F. A GRASP approach to the container-loading problem[J]. Intelligent Systems, 2005, 20(4): 50-57.
[10] George J A, Robinson D F. A heuristic for packing boxes into a container[J]. Computers & Operations Research, 1980, 7(3): 147-156.
[11] Crainic T G, Perboli G, Tadei R. TS2PACK: A two-level tabu search for the three-dimensional bin packing problem[J]. European Journal of Operational Research, 2009, 195(3): 744-760.
[12] Fekete S P, Schepers J. A combinatorial characterization of higher dimensional orthogonal packing[J]. Mathematics of Operations Research, 2004, 29(2): 353-368.
[13] Chen C S, Lee S M, Shen Q S. An analytical model for the container loading problem[J]. European Journal of Operational Research, 1995, 80(1): 68-76.
[14] Eley M. A bottleneck assignment approach to the multiple container loading problem[J]. OR Spectrum, 2003, 25(1): 45-60.
[15] Ertek G, Kilic K. Decision support for packing in warehouses[J]. Lecture Notes in Computer Science, 2006: 115-124.
[16] Li Y, Chen M Z, Huo J Z. A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem[J]. Expert Systems with Applications, 2022, 189: 115909.
[17] Lau H C, Chan T M, Tsui W T, et al. An AI approach for optimizing multi-pallet loading operations[J]. Expert Systems with Applications, 2009, 36(3): 4296-4312.
[18] 何大勇, 查建中, 姜义东. 遗传算法求解复杂集装箱装载问题方法研究[J]. 软件学报, 2001, 12(9): 1380-1385 He D Y, Zha J Z, Jiang Y D. Research on genetic algorithm for solving complex container loading problems[J]. Journal of Software, 2001, 12(9): 1380-1385.
[19] Bortfeldt A, Wäscher G. Constraints in container loading—A state-of-the-art review[J]. European Journal of Operational Research, 2013, 229(1): 1-20.
[20] Ren J, Tian Y, Sawaragi T. A tree search method for the container loading problem with shipment priority[J]. European Journal of Operational Research, 2011, 214(3): 526-535.
[21] He K, Huang W. An efficient placement heuristic for three-dimensional rectangular packing[J]. Computer & Operations Research, 2011, 38(1): 227-233.
[22] Bortfeldt A, Gehring H. A hybrid genetic algorithm for the container loading problem[J]. European Journal of Operational Research, 2001, 131(1): 143-161.
[23] Paquay C, Schyns M, Limbourg S. A mixed integer programming formulation for the three-dimensional bin packing problem deriving from an air cargo application[J]. International Transactions in Operational Research, 2016, 23(1-2): 187-213.
[24] Crainic T G, Perboli G, Tadei R. Extreme point-based heuristics for three-dimensional bin packing[J]. INFORMS Journal on Computing, 2008, 20(3): 368-384.
[25] Lim A, Rodrigues B, Wang Y. A multi-faced buildup algorithm for three-dimensional packing problems[J]. Omega, 2003, 31(6): 471-481.
[26] Eglese R W. Simulated annealing: A tool for operational research[J]. European Journal of Operational Research, 1990, 46(3): 271-281.
[27] Gzara F, Elhedhli S, Yildiz B C. The pallet loading problem: Three-dimensional bin packing with practical constraints[J]. European Journal of Operational Research, 2020, 287(3): 1062-1074.
[28] Do Nascimento O X, De Queiroz T A, Junqueira L. Practical constraints in the container loading problem: Comprehensive formulations and exact algorithm[J]. Computers & Operations Research, 2021, 128: 105186.
{{custom_fnGroup.title_cn}}
脚注
{{custom_fn.content}}
基金
国家自然科学基金(71821002,71201141)
{{custom_fund}}
PDF(730 KB)
