求解集装箱装载问题的混合蚁群模拟退火算法

Hybrid Ant Colony Simulated Annealing Algorithm for Solving Container Loading Problems

中文关键词: 三维装箱  大规模集装箱装载  启发式算法  蚁群算法  模拟退火算法

英文关键词: three-dimensional container loading  large scale container loading  heuristic algorithm  ant colony  simulated annealing algorithm

中文摘要:

      目的 针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题，提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法 首先，采用塔装载启发式算法将三维待装箱装载成塔集，即将三维装箱问题降为二维装箱问题，有效降低集装箱的装载规模;其次，蚁群算法通过融入信息素选择更新策略，并利用自适应信息素挥发系数来提升算法整体的收敛速度，同时结合模拟退火算法对每代优秀路径集进行局部搜索，避免算法因收敛过快而陷入局部最优;最后，将蚁群模拟退火算法与二维装载点启发式算法相结合，优化每座塔的装载顺序和放置姿态，寻找最优的装载方案。结果 实验证明，在250组算例中，采用混合算法后，集装箱的平均空间利用率为90.92%，优于其他3种对比算法。结论 设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。

英文摘要:

      The work aims to propose a hybrid algorithm of tower loading heuristic algorithm, two-dimensional loading point heuristic algorithm, and ant colony simulated annealing algorithm to address the container loading problem of large-scale and complex multi specification goods in the logistics industry. Firstly, the three-dimensional container was loaded into towers through the tower loading heuristic algorithm to reduce the three-dimensional packing problem to a two-dimensional packing problem, effectively reducing the loading scale of large-scale containers. Secondly, the ant colony algorithm incorporates a pheromone selection and update strategy and an adaptive pheromone evaporation coefficient to improve the overall convergence speed of the algorithm. At the same time, it combines with simulated annealing algorithm to perform local search on the set of excellent paths in each generation, avoiding the algorithm from falling into local optima due to too fast convergence. Finally, the ant colony simulated annealing algorithm was combined with a two-dimensional loading point heuristic algorithm to optimize the loading sequence and placement posture of each tower to find the optimal loading plan. The experiment showed that in 250 sets of examples, the average space utilization rate of the container in this algorithm was 90.92%, which was better than that of the three comparative algorithms. In conclusion, the hybrid ant colony simulated annealing algorithm designed in this article is very suitable for solving large-scale container packing problems.