Abstract: Cable reel packing problem widely exists in practical production of cable enterprise,which is essentially a weighed-rotated variable-sized two-dimension bin packing problem.To handle with the cable reel packing problem,a mixed integer programming model with the objective of minimizing the packing cost was established and a Hybrid Monte Carlo Tree Search (HMCTS) algorithm was proposed.Under the framework of Monte Carlo tree search,an effective local search strategy was incorporated into the HMCTS to find optimal pin selection solution,as well as to determine the packing position for each item in a bin.Further,a relaxation model was introduced to effectively reduce the computation cost.By using sixdifferent sized benchmark sets generated from practical production of cable enterprise,experimental simulations and comparative analysis were conducted,and the results demonstrated the effectiveness and robustness of the proposed HMCTS algorithm in solving the cable reel packing problem.

Key words: Monte Carlo tree search, mixed integer programming model, relaxation model, cable reel packing problem, variable-sized

摘要： 电缆盘装箱问题广泛存在于线缆企业的生产实际中,本质上属于带载重约束和正交旋转的多箱型二维装箱问题。针对电缆盘装箱问题,建立以装箱成本最小化为目标的混合整数规划模型,提出一种混合蒙特卡洛树搜索(HMCTS)算法。在蒙特卡洛树搜索框架下,通过融入高效邻域搜索策略,寻找得到较优的箱子选择方案,并确定每个箱子中货物的装箱位置和方式。在此基础上,构建电缆盘装箱问题的松弛模型,有效降低算法的计算成本。基于线缆企业生产实际中6种不同规模的数据集,对HMCTS算法进行仿真实验和对比分析,结果表明所提算法在求解电缆盘装箱问题中具有较高的有效性和鲁棒性。

关键词: 蒙特卡洛树搜索, 混合整数规划模型, 松弛模型, 电缆盘装箱问题, 多箱型