计算机科学

计算机科学 ›› 2023, Vol. 50 ›› Issue (11A): 221200091-10.doi: 10.11896/jsjkx.221200091

• 人工智能 • 上一篇    下一篇

复杂约束下单集装箱装载问题的改进元启发式算法

刘日鑫, 秦威, 许鸿伟   

  1. 上海交通大学机械与动力工程学院工业工程与管理系 上海 200240
  • 发布日期:2023-11-09
  • 通讯作者: 秦威(wqin@sjtu.edu.cn)
  • 作者简介:(jerryliurixin0812@sjtu.edu.cn)
  • 基金资助:
    国家重点研发计划(2019YFB1704401)

Improved Metaheuristics for Single Container Loading Problem with Complex Constraints

LIU Rixin, QIN Wei, XU Hongwei   

  1. Department of Industrial Engineering and Management,School of Mechanical Engineering,Shanghai Jiao Tong University,Shanghai 200240,China
  • Published:2023-11-09
  • About author:LIU Rixin,born in 1996,postgraduate,is a member of China Computer Federation.His main research interests include operation research and intelligent manufacture.
    QIN Wei,born in 1982,Ph.D,professor,Ph.D supervisor,is a member of China Computer Federation.His main research interests include complex system modeling and control and optimization.
  • Supported by:
    National Key Research and Development Program of China(2019YFB1704401).

PDF (PC)

555

摘要： 三维单集装箱装载问题(Three-dimensional Single Container Loading Problem,3D-SCLP)因其在制造业和物流业中有着广泛的应用,已成为最优化领域中最经典的工程问题之一。然而,目前的优化方案主要从算法优化改进与局部约束调整等角度考虑,没有充分考虑实际装载过程中的复杂约束需求,如重量限制、负载平衡、货物稳定性、堆叠约束以及人因工程因素,导致现有方法理论装载率虽高,但实用性低。在充分考虑实际多重复杂约束的基础上,提出了一种基于天鹰座优化器的改进元启发式算法。该算法基于种群优化策略,并将差分变异和高斯扰动与潜在点策略相结合,实现复杂约束情况下的快速收敛。在中等规模工业实例数据上进行了算法验证,与传统启发式优化方法相比,所提方法能够解决中等规模复杂约束下的三维装箱优化问题,在实际空间利用率、生成效率等方面优于现有的解决方案。对物流运输行业减少人工成本,实现装箱标准化与智能化具有重要意义。

关键词: 三维单集装箱装载问题, 复杂约束, 天鹰座优化器, 高斯扰动, 差分变异

Abstract: Three-dimensional single container loading problem(3D-SCLP) has become one of the most classic engineering problems in the field of optimization because of its wide application in manufacturing and logistics.However,the current optimization scheme mainly considers the optimization and improvement of algorithm and local constraints,but fails to fully consider the actual complex constraints,such as weight limit,load balance,cargo stability,stacking constraints and human factors,which leads to the problem that the theoretical loading rate of the existing methods is high,but the practicality is low.In order to solve this problem,this paper proposes an improved meta-heuristic algorithm based on the Aquila optimizer on the basis of fully considering the complex constraints of multiple realities.It is based on population optimization strategy,and combines differential mutation and Gaussian disturbance with potential point strategy to achieve rapid convergence under complex constraints,and it is verified on the data of a medium-scale industrial example.Compared with the traditional heuristic optimization method,the proposed method can solve the three-dimensional packing optimization problem under complex constraints,and is superior to the existing solutions in terms of actual space utilization and generation efficiency,thus embodies intelligent packing,realizes standardization and intelligence of packing,and reduces manual participation.

Key words: Single container loading problem, Complex constraints, Aquila Optimizer, Gaussian disturbance, Differential mutation

中图分类号: 

  • TP301
[1]HA C T,NGUYEN T T,BUI L T,et al.An online packing heuristic for the three-dimensional container loading problem in dynamic environments and the Physical Internet[C]//European Conference on the Applications of Evolutionary Computation.Cham:Springer,2017:140-155.
[2]BORTFELDT A,WÄSCHER G.Constraints in container loa-ding-a state-of-the-art review[J].European Journal of Operational Research,2013,229(1):1-20.
[3]TLILI T,FAIZ S,KRICHEN S.A particle swarm optimization for solving the one dimensional container loading problem[C]//2013 5th International Conference on Modeling,Simulation and Applied Optimization(ICMSAO).IEEE,2013:1-4.
[4]LODI A,MARTELLO S,VIGO D.Heuristic and metaheuristic approaches for a class of two-dimensional bin packing problems[J].INFORMS Journal on Computing,1999,11(4):345-357.
[5]CRAINIC T G,PERBOLI G,TADEI R.Extreme point-basedheuristics for three-dimensional bin packing[J].Informs Journal on computing,2008,20(3):368-384.
[6]BAYRAKTAR T,ERSÖZ F,KUBAT C.Effects of memory andgenetic operators on Artificial Bee Colony algorithm for Single Container Loading problem[J].Applied Soft Computing,2021,108:107462.
[7]ALONSO M T,ALVAREZ-VALDÉS R,IORI M,et al.Mathematical models for multi container loading problems with practical constraints[J].Computers & Industrial Engineering,2019,127:722-733.
[8]SUN H L,WANG Z J.Heuristic algorithm for containers loading homogeneous goods[J].Computer Applications and Software,2011,28(4):193-195,204.
[9]ZHANG C Y,WU Z B,WANG Y F.Fast Container Loading Algorithm for Airline Luggage Registration Based on K-means Clustering [J].Packaging and food machinery,2019(3):37.
[10]HUANG W,HE K.A New Quasi-Human Algorithm for the Strongly Heterogeneous Container Loading Problem[C]//2007 Japan-China Joint Workshop on Frontier of Computer Science and Technology(FCST 2007).IEEE,2007:119-124.
[11]ZHU W,HUANG W,LIM A.A prototype column generation strategy for the multiple container loading problem[J].Euro-pean Journal of Operational Research,2012,223(1):27-39.
[12]DO NASCIMENTO O X,DE QUEIROZ L.Practical constraints in the container loading problem:Comprehensive formulations and exact algorithm[J].Computers & Operations Research,2021,128:105186.
[13]GONÇALVES J F,RESENDE M G C.A biased random key genetic algorithm for 2D and 3D bin packing problems[J].International Journal of Production Economics,2013,145(2):500-510.
[14]LI Y,CHEN M,HUO J.A hybrid adaptive large neighborhood search algorithm for the large-scale heterogeneous container loading problem[J].Expert Systems with Applications,2022,189:115909.
[15]ZHANG D F,WEI L J,CHEN Q S,et al.A combinational heuristic algorithm for the three-dimensional packing problem[J].Journal of Software,2007,18(9):2083-2089.
[16]ABUALIGAH L,YOUSRI D,ABD ELAZIZ M,et al.Aquilaoptimizer:a novel meta-heuristic optimization algorithm[J].Computers & Industrial Engineering,2021,157:107250.
[17]JUNQUEIRA L,MORABITO R,YAMASHITA D S.Three-dimensional container loading models with cargo stability and load bearing constraints[J].Computers & Operations Research,2012,39(1):74-85.
[18]RAMOS A G,SILVA E,OLIVEIRA J F.A new load balance methodology for container loading problem in road transportation[J].European Journal of Operational Research,2018,266(3):1140-1152.
[19]BISCHOFF E E,RATCLIFF M S W.Issues in the development of approaches to container loading[J].Omega,1995,23(4):377-390.
[20]STORN R,PRICE K.Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces[J].Journal of gGobal Optimization,1997,11(4):341-359.
[21]ZHENG J N,CHIEN C F,GEN M.Multi-objective multi-population biased random-key genetic algorithm for the 3-D container loading problem[J].Computers & Industrial Engineering,2015,89:80-87.
[22]KANG K,MOON I,WANG H.A hybrid genetic algorithm with a new packing strategy for the three-dimensional bin packing problem[J].Applied Mathematics and Computation,2012,219(3):1287-1299.
[23]KOONSINTANANAN S,KIMPAN W.Applied particle swarm optimization in solving container loading problem for logistics[C]//2019 11th International Conference on Knowledge and Smart Technology(KST).IEEE,2019:88-93.
[24]JAMRUS T,CHIEN C F.Extended priority-based hybrid genetic algorithm for the less-than-container loading problem[J].Computers & Industrial Engineering,2016,96:227-236.
[25]ARAYA I,MOYANO M,SANCHEZ C.A beam search algorithm for the biobjective container loading problem[J].European Journal of Operational Research,2020,286(2):417-431.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
渝ICP备16013121号-4
地址：重庆市渝北区洪湖西路18号    邮编：401121  
电话：023-63500828（编辑部） 023-67039612（会议/专题） 023-67039623（财务/发票）
E-mail：jsjkx12@163.com
本系统由北京玛格泰克科技发展有限公司设计开发