针对某型多载具自动化存取系统优化分配问题，分析该自动化存取系统的运行特点，建立了该自动化存取系统优化问题的马尔科夫决策过程模型，并提出了求解模型的基于改进蒙特卡罗树搜索算法。首先，以总搬运量和同类型货箱距离最小为目标建立货位优化模型，为了更好控制蒙特卡罗树搜索分支合理性，对算法节点选择部分进行优化。最后，对改进的蒙特卡罗树搜索算法进行货位优化及对比测试。实验结果表明：改进的蒙特卡罗树搜索算法较采用贪心思想、采用魔方还原思想以及基于传统蒙特卡罗树搜索的算法在货位优化运行效果上更优。
To optimize the distribution of the multi vehicle automatic access system storage space, the operation characteristics of a multi vehicle automatic access system are analyzed, the Markov decision process model of the multi vehicle automatic access system optimization problem is established, and an improved Monte Carlo tree search algorithm is proposed to solve the model. Firstly, the cargo location optimization model is established aiming at the minimum total handling capacity and the distance between the same type of containers. Then, in order to better control the rationality of Monte Carlo tree search branch, the node selection part of the algorithm is optimized. Finally, the improved Monte Carlo tree search algorithm is optimized and tested. The experimental results show that the improved Monte Carlo tree search algorithm is better than the greedy algorithm, the cube reduction algorithm and the traditional Monte Carlo tree search algorithm.
2022,44(8): 169-173 收稿日期：2021-09-06
DOI：10.3404/j.issn.1672-7649.2022.08.036
分类号：U671.99
基金项目：航空科学基金资助项目（2018ZC41002）
作者简介：陈俭新(1990-),男,硕士,工程师,研究方向为强化学习、船用特种物资调度
参考文献：
[1] 李越. 集装箱装载配置优化算法研究[D]. 上海:上海交通大学, 2002.
[2] 张延华, 姜雄文. 基于改进遗传算法的电气设备仓库库位优化[J/OL]. 控制工程:1-9[2022-04-06].
[3] 柏乐. 仓储货位优化及调度模型的研究与实现[D]. 北京:北京邮电大学, 2020.
[4] 邓爱民, 蔡佳, 毛浪. 基于时间的自动化存取系统货位优化模型研究[J]. 中国管理科学, 2013, 21(6):107-112
[5] YUE L, GUAN Z, HE C, et al. Slotting optimization of automated storage and retrieval system (AS/RS) for efficient delivery of parts in an assembly shop using genetic algorithm:a case study[J]. Iop Conference, 2017, 215:012002
[6] GIU J D, JIANG Z Y, TANG M A, et al. Research on slotting optimization of AS/RS based on cyclical virus evolutionary genetic algorithm[J]. Journal of Lanzhou Jiaotong University, 2013.
[7] WU J H, QIN T D, CHEN J, et al. Slotting optimization algorithm of the stereo warehouse[J]. Advanced Materials Research, 2012, 756-759:1371-1376
[8] 张贵军, 姚俊, 周晓根, 等. 基于精英多策略的货位分配优化方法[J]. 计算机科学, 2018, 45(1):273-279
[9] 陈月婷, 何芳. 基于改进粒子群算法的自动化存取系统货位分配优化[J]. 计算机工程与应用, 2008, 44(11):229-231,236
[10] WALEDZIK K, MANDZIUK J. Applying hybrid monte carlo tree search methods to risk-awareproject scheduling problem[J]. Information Sciences, 2017.
[11] 封佳祥, 江坤颐, 周彬, 等. 多任务约束条件下基于强化学习的水面无人艇路径规划算法[J]. 舰船科学技术, 2019, 41(12):140-146
[12] PAN C H, WU M H. A study of storage assignment problem for an order picking line in a pick-and-pass warehousing system[J]. Computers & Industrial Engineering, 2009, 57(1):261-268
