.png){kind=icon}
返回
Exact algorithms for unconstrained three-dimensional cutting problems: a comparative study
.png){kind=icon}
PRE
AI
DOI：10.1016/S0305-0548(03)00019-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In this paper we propose two exact algorithms for solving the three-dimensional cutting (3DC) problem. We study the two cases of the unconstrained 3DC problem: (i) only one large pallet is considered, denoted U_3DC, and (ii) the general version, denoted U_G3DC, in which different large pallets are considered. For both cases of the problem, we consider that there is unlimited quantity of each type of pieces to cut, and that all cuts are of guillotine type. We propose a first exact algorithm for the U_3DC problem. The algorithm is an adaptation of Gilmore and Gomory's approach (Oper. Res. 14 (1966) 1045) initially proposed for solving the unconstrained two-dimensional guillotine cutting problem. We then present a second algorithm for the same problem. This algorithm is mainly based upon a graph search procedure using a depth-first search strategy. This algorithm is a straightforward extension of the two-dimensional guillotine cutting approach proposed in (Eur. J. Oper. Res. 91 (1996) 553). We later show how we can extend the dynamic programming based algorithm for exactly solving the U_G3DC problem. Finally, we undertake an extensive experimental study with a large number of problem instances extracted from the literature and compare the performances of both algorithms.
Keyword:
combinatorial optimization
cutting problems
exact algorithms
knapsack function
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
暂无机构信息
引用论文
.png){kind=icon}
分享收藏分享收藏分享收藏分享收藏
查看更多内容