Quasi-Monte-Carlo Tree Search for 3D Bin Packing
The three-dimensional bin packing problem(3D-BPP)is a classic NP-hard combinatorial optimization problem,which is difficult to be solved with an exact solution,so lots of heuristic approaches have been proposed to generate approximated solutions to this problem.In this paper,we present a novel heuristic search algorithm,named Quasi-Monte-Carlo Tree Search(QMCTS),where efficiency and effectiveness are balanced via clipping off the search space in both the breadth and depth range.Furthermore,the QMCTS scheme can be sped up in parallel processing mode,which can theoretically outperform the depth-first search(DFS)and breadth-first search(BFS)based algorithms.Experiments on the benchmark datasets show that the proposed QMCTS approach can consistently outperform state-of-the-art algorithms.
3D bin packing problem Monte-Carlo tree search Combinatorial optimization problem
Hailiang Li Yan Wang DanPeng Ma Yang Fang Zhibin Lei
Hong Kong Applied Science and Technology Research Institute Company Limited,Sha Tin,Hong Kong Anji Technology Company Limited,Shanghai,China
国际会议
广州
英文
384-396
2018-11-23（万方平台首次上网日期，不代表论文的发表时间）