考虑货物冲突关系的二维装箱问题研究
PDF下载 (491)孙宝凤,王 帅,郑黎黎,乔 海.考虑货物冲突关系的二维装箱问题研究[J].宁波大学学报(理工版),2020,33(2):79-85.DOI:
SUN Baofeng,WANG Shuai,ZHENG Lili,QIAO Hai.Research on two-dimensional packing problem with cargo conflicts[J].Journal of Ningbo University(Natural Science & Engineering Edition),2020,33(2):79-85.DOI:
| Title: | Research on two-dimensional packing problem with cargo conflicts |
| 作者: | 孙宝凤, 王 帅, 郑黎黎, 乔 海 |
| Author(s): | SUN Baofeng, WANG Shuai, ZHENG Lili, QIAO Hai |
| 关键词: | 二维装箱问题; 货物冲突; 改进的模拟退火算法 |
| Keywords: | two-dimensional packing problem; cargo with conflicts; improved simulated annealing algorithm |
| 分类号: | O221.4; TB114.1 |
| 文献标识码: | A |
| 摘要: | 货物冲突及其处理方式直接影响货箱消耗量和货物装载成效, 通过构建冲突矩阵和“冲突货物不能放置同一货箱内”处理方式, 同时考虑负载安全因素, 建立了考虑货物冲突关系的二维装箱优化模型. 设计了改进的模拟退火算法, 其运用贪心算法对货物冲突预处理, 确保初始装箱序列为可行解; 提出了兼顾当前温度和适应度影响的动态随机扰动率 方程, 增强了邻域解的搜索能力, 改善了算法整体性能. 算例分析表明模型和算法有效. 120种货物冲突稀疏度[0.1,0.9]情景下, 货箱面积利用率均值为[0.342,0.732], 降低了装载单元使用数量, 提高了资源利用率. 不同样本量情景下, 改进算法的求解质量和运行效率表现良好. |
| Abstract: | Cargo conflicts and their handling methods directly affect the efficiency of the cargo loading and unloading. A two-dimensional packing optimization model solving the cargo conflict is established in this paper. The conflict matrix and the rule “conflicting goods cannot be placed in the same container” are applied. Improved simulated annealing algorithm is designed for the model, in which the greedy algorithm is employed to preprocess the cargo conflicts to ensure that the initial packing sequence guarantees a feasible solution. Its neighborhood solution search ability and calculation speed are strengthened by dynamic random perturbation equation which takes into consideration the current temperature and fitness for improvement of the overall algorithm performance. Simulation tests show that the model proposed and algorithm improved can achieve the satisfying results. For example, under the context of 120 cargo with the conflict sparsity range being [0.1,0.9], the average utilization rate of container area is [0.342,0.732]. These readings show the capability of reducing the number of loading units and improving the resource utilization. Other simulations with varying cargo samplings also demonstrate promising results. |
| 参考文献 /References: | [1] Liao C S, Hsu C H. New lower bounds for the three-dimensional orthogonal bin packing problem[J]. European Journal of Operational Research, 2013, 225(2):244-252. [2] Elhedhli S, Li L, Gzara M, et al. A branch-and-price algorithm for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2011, 23(3):404-415. [3] Maiza M, Radjef M S, Sais L. Efficient lower bounds for packing problems in heterogeneous bins with conflicts constraint[J] Intelligent Mathematics II: Applied Mathematics and Approximation Theory, 2016, 441:263- 270. [4] Galinier P, Hertz A. A survey of local search methods for graph coloring[J]. Computers & Operations Research, 2006, 33(9):2547-2562. [5] Jansen K. An approximation scheme for bin packing with conflicts[J]. Journal of Combinatorial Optimization, 1999, 3(4):363-377. [6] Gendreau M, Laporte G, Semet F. Heuristics and lower bounds for the bin packing problem with conflicts[J]. Computers & Operations Research, 2004, 31(3):347-358. [7] 元野. 基于图着色模型的零担物流调度优化问题研究[D]. 哈尔滨: 哈尔滨工业大学, 2015. [8] Trivella A, Pisinger D. The load-balanced multi- dimensional bin-packing problem[J]. Computers & Operations Research, 2016, 74:152-164. [9] Khanafer A, Clautiaux F, Talbi E G. Tree decomposition based heuristics for the two-dimensional bin packing problem with conflicts[J]. Computers & Operations Research, 2012, 39:54-63. [10] Muritiba A E F, Iori M, Malaguti E. Algorithms for the bin packing problem with conflicts[J]. INFORMS Journal on Computing, 2010, 22(3):281-288. [11] Khanafer A, Clautiaux F, Hanafi S, et al. The min-conflict packing problem[J]. Computers & Operations Research, 2012, 39(9):2122-2132. [12] Pereira J. Procedures for the bin packing problem with precedence constraints[J]. European Journal of Operational Research, 2016, 250(3):794-806. [13] 卢宇婷, 林禹攸, 彭乔姿. 模拟退火算法改进综述及参数探究[J]. 大学数学, 2015, 31(6):96-103. [14] 孙宝凤, 史俊妍, 杨雪, 等. 基于实时信息的取送货动态车辆路径问题研究[J]. 宁波大学学报(理工版), 2019, 32(3):93-100. [15] Bengtsson B E. Packing rectangular pieces--A heuristic approach[J]. The Computer Journal, 1982, 25(3):353-357. |
| 备注/Memo: | 收稿日期: 2019－09－30. 宁波大学学报（理工版）网址: http://journallg.nbu.edu.cn/ 基金项目: 博士学科点专项科研基金（20130061110008）; 吉林省交通科技发展计划（2019012）; 国家自然科学基金（51308249）. 宁波大学学报（理工版）网址：http://journallg.nbu.edu.cn/第一作者: 孙宝凤（1970－）, 女, 吉林长春人, 博导/教授, 主要研究方向: 物流系统规划与仿真优化. E-mail: sunbf@jlu.edu.cn *通信作者: 郑黎黎（1975－）, 女, 吉林长春人, 副教授, 主要研究方向: 道路交通网络动态分析. E-mail: zlldtq1024@163.com |
