粒子群自进化算法求解物流装箱问题  

Logistics Loading Problem Based on Particle Swarm Auto-evolving Algorithm

作　　者：赵崟 王小平[1] 臧铁钢[1] 金将 姜世阔 ZHAO Yin;WANG Xiaoping;ZANG Tiegang;JIN Jiang;JIANG Shikuo(College of Mechanical&Electrical Engineering,Nanjing University of Aeronautics&Astronautics,Nanjing 210016,China)

机构地区：[1]南京航空航天大学机电学院,江苏南京210016

出　　处：《物流技术》2024年第3期52-69,共18页Logistics Technology

摘　　要：为了解决当今物流行业中装载货物类型为强异构的情况,提高装载填充率和效率,提出了一种求解三维装箱问题的元启发式算法——粒子群自进化算法。算法包含两部分:极限点构造启发式算法和粒子群自进化规则。极限点构造启发式算法引入了极限点的概念,利用新的极值点思想推导出了三维装箱问题的启发式算法。粒子群自进化规则提出了在货物装载序列中表示粒子的方法,推导了粒子间交叉、变异算子,在极限点构造启发式算法的基础上不断迭代进化完成货物的装载。通过不同结果的比对,证明该算法显著提高了物流装载的空间利用率,强异构货物的平均装载率达到了85%,验证了算法在强异构货物下的有效性与优越性,并给出了货物装载的三维模型。由于实际测试集的缺少,分别为机腹仓装载类和集装板类模型提出了实例生成器,通过生成器的测试集验证了算法在实际应用中的紧凑性、实用性和快捷性。In order to deal with the strong cargo heterogeneity in logistics loading process nowadays and im⁃prove filling rate and loading efficiency,we proposed a meta-heuristic algorithm,namely particle swarm autoevolving algorithm,for solving the three-dimensional loading problem.Firstly,we established a mathematical model satisfying multiple constraints for the three-dimensional load⁃ing problem which is a core academic concept in logistics and freight transportation,and constructed a fitness function for obtaining the filling rate of the cargo to provide evaluation criteria for the proposed algorithm.Said algorithm consists of two main modules,respectively the limit point construction-based heuristic algo⁃rithm and the particle swarm auto-evolving rule.Therein,the limit point construction-based heuristic algo⁃rithm is responsible for decoding the particle swarm sequence,generating the solution,and evaluating its fit⁃ness.The concept of limit point is introduced as the basis of the heuristic algorithm,and three cargo placement strategies are designed there upon to derive a new heuristic method to effectively solve the three-dimensional pallet loading problem.Moreover,the particle swarm auto-evolving rule is responsible for the evolution of the coding solution(particle swarm sequence)so as to provide the optimal solution for the limit point construc⁃tion-based heuristic algorithm.Said rule proposes the method of representing the particles in the cargo loading sequence,deduces the partial uniform crossover operator and self-mutation operator,obtains the next genera⁃tion through the crossover and mutation of the particles,and updates the loading sequence,which provides par⁃ticle swarm sequence input for the limit point construction-based heuristic algorithm thus to optimize cargo loading.The comparison result shows that the proposed algorithm significantly improves the space utilization rate in the logistics loading process(raising the average loading rate of strong heterogeneity cargo to 85%),which veri�

关 键 词：三维装箱问题 强异构装载 物流运输 极点法 粒子群算法 启发式算法 

分 类 号：F252.13[经济管理—国民经济]