Full Text:
<3965>
CLC number: TH16
On-line Access: 2011-10-28
Received: 2011-02-18
Revision Accepted: 2011-08-29
Crosschecked: 2011-09-28
Cited: 4
Clicked: 16265
Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems
| |||||||||||||
Xiao Liu, Jia-wei Ye. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems[J]. Journal of Zhejiang University Science A, 2011, 12(11): 860-872.
@article{title="Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems",
author="Xiao Liu, Jia-wei Ye",
journal="Journal of Zhejiang University Science A",
volume="12",
number="11",
pages="860-872",
year="2011",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.A1100038"
}
%0 Journal Article
%T Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems
%A Xiao Liu
%A Jia-wei Ye
%J Journal of Zhejiang University SCIENCE A
%V 12
%N 11
%P 860-872
%@ 1673-565X
%D 2011
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.A1100038
TY - JOUR
T1 - Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems
A1 - Xiao Liu
A1 - Jia-wei Ye
J0 - Journal of Zhejiang University Science A
VL - 12
IS - 11
SP - 860
EP - 872
%@ 1673-565X
Y1 - 2011
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.A1100038
Abstract: We present a new algorithm for nesting problems. Many equally spaced points are set on a sheet, and a piece is moved to one of the points and rotated by an angle. Both the point and the rotation angle constitute the packing attitude of the piece. We propose a new algorithm named HAPE (heuristic algorithm based on the principle of minimum total potential energy) to find the optimal packing attitude at which the piece has the lowest center of gravity. In addition, a new technique for polygon overlap testing is proposed which avoids the time-consuming calculation of no-fit-polygon (NFP). The detailed implementation of HAPE is presented and two computational experiments are described. The first experiment is based on a real industrial problem and the second on 11 published benchmark problems. Using a hill-climbing (HC) search method, the proposed algorithm performs well in comparison with other published solutions.
[1]Albano, A., Sapuppo, G., 1980. Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Transactions on Systems, Man and Cybernetics, 10(5):242-248.
[2]Art, J.R.C., 1966. An Approach to the Two Dimensional Irregular Cutting Stock Problem. Technical Report No. 36.Y08, IBM Cambridge Scientific Center, Massachusetts, USA.
[3]Bennell, J.A., Dowsland, K.A., Dowsland, W.B., 2001. The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon. Computers & Operations Research, 28(3):271-287.
[4]Błażewicz, J., Hawryluk, P., Walkowiak, R., 1993. Using a tabu search approach for solving the two-dimensional irregular cutting problem. Annals of Operations Research, 41(4):313-325.
[5]Burke, E., Hellier, R., Kendall, G., Whitwell, G., 2006. A new bottom-left-fill heuristic algorithm for the two-dimensional irregular packing problem. Operations Research, 54(3):587-601.
[6]Burke, E.K., Hellier, R.S.R., Kendall, G., Whitwell, G., 2007. Complete and robust no-fit polygon generation for the irregular stock cutting problem. European Journal of Operational Research, 179(1):27-49.
[7]Dowsland, K.A., Dowsland, W.B., 1993. Heuristic Approaches to Irregular Cutting Problems. Technical Report, University College of Swansea, Swansea, UK.
[8]Dowsland, K.A., Dowsland, W.B., Bennell, J.A., 1998. Jostling for position: local improvement for irregular cutting patterns. Journal of the Operational Research Society, 49(6):647-658.
[9]Dowsland, K.A., Vaid, S., Dowsland, W.B., 2002. An algorithm for polygon placement using a bottom-left strategy. European Journal of Operational Research, 141(2):371-381.
[10]Fujita, K., Akagji, S., Kirokawa, N., 1993. Hybrid Approach for Optimal Nesting Using a Genetic Algorithm and a Local Minimisation Algorithm. Proceedings 19th Annual ASME Design Automation Conference, Part 1, 65:477-484.
[11]Gomes, A.M., Oliveira, J.F., 2002. A 2-exchange heuristic for nesting problems. European Journal of Operational Research, 141(2):359-370.
[12]Gomes, A.M., Oliveira, J.F., 2006. Solving irregular strip packing problems by hybridising simulated annealing and linear programming. European Journal of Operational Research, 171(3):811-829.
[13]Hibbeler, R.C., 2011. Statics and Mechanics of Materials. Prentice Hall, New Jersey, USA, p.261-272.
[14]Hopper, E., 2000. Two-Dimensional Packing Utilising Evolutionary Algorithm and Other Meta-Heuristic Methods. PhD Thesis, University of Wales, Cardiff, UK.
[15]Jakobs, S., 1996. On genetic algorithms for the packing of polygons. European Journal of Operational Research, 88(1):165-181.
[16]Marques, V.M.M., Bispo, C.F.G., Sentieiro, J.J.S., 1991. A System for the Compaction of Two-Dimensional Irregular Shapes Based on Simulated Annealing. Proceedings International Conference on Industrial Electronics, Control and Instrumentation, p.1911-1916.
[17]Oliveira, J.F., Gomes, A.M., Ferreira, J.S., 2000. TOPOS—a new constructive algorithm for nesting problems. OR Spectrum, 22(2):263-284.
[18]Ratanapan, K., Dagli, C.H., 1997. An Object-Based Evolutionary Algorithm for Solving Irregular Nesting Problems. Proceedings Artificial Neural Networks in Engineering Conference, p.383-388.
[19]Sun, J., Yang, C., 1995. Computer Graphics. Tsinghua University Press, Beijing, China, p.390-391 (in Chinese).
Open peer comments: Debate/Discuss/Question/Opinion
<1>