Please wait a minute...
ZJUS-A
Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering)  2011, Vol. 12 Issue (11): 860-872    DOI: 10.1631/jzus.A1100038
Industrial Engineering     
Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems
Xiao Liu, Jia-wei Ye
School of Civil and Transportation Engineering, South China University of Technology, Guangzhou 510640, China
Download:     PDF (0 KB)     
Export: BibTeX | EndNote (RIS)      

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.

Key words： Packing      Cutting      Nesting      Irregular      Heuristic algorithm      Minimum total potential energy     
Received: 18 February 2011      Published: 28 October 2011
CLC:  TH16  
Service
E-mail this article
Add to my bookshelf
Add to citation manager
E-mail Alert
RSS
Articles by authors
Xiao Liu
Jia-wei Ye
Cite this article:

Xiao Liu, Jia-wei Ye. Heuristic algorithm based on the principle of minimum total potential energy (HAPE): a new algorithm for nesting problems. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(11): 860-872.

URL:

http://www.zjujournals.com/xueshu/zjus-a/10.1631/jzus.A1100038     OR     http://www.zjujournals.com/xueshu/zjus-a/Y2011/V12/I11/860

[1] Pui-Lam Ng, Albert Kwok-Hung Kwan, Leo Gu Li. Packing and film thickness theories for the mix design of high-performance concrete[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2016, 17(10): 759-781.
[2] Jin Shi, Wen-shan Fang, Ying-jie Wang, Yang Zhao. Measurements and analysis of track irregularities on high speed maglev lines[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2014, 15(6): 385-394.
[3] Shuo-qiao Zhong, Jia-yang Xiong, Xin-biao Xiao, Ze-feng Wen, Xue-song Jin. Effect of the first two wheelset bending modes on wheel-rail contact behavior[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2014, 15(12): 984-1001.
[4] David Poto?nik, Bojan Dol?ak, Miran Ulbin. GAJA: 3D CAD methodology for developing a parametric system for the automatic (re)modeling of the cutting components of compound washer dies[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2013, 14(5): 327-340.
[5] Nikola Stosic, Ian K. Smith, Ahmed Kovacevic, Elvedin Mujic. Geometry of screw compressor rotors and their tools[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(4): 310-326.
[6] Xue-cheng Bian, Chang Chao, Wan-feng Jin, Yun-min Chen. A 2.5D finite element approach for predicting ground vibrations generated by vertical track irregularities[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(12): 885-894.
[7] Peng Liu, Jiu-hua Xu, Yu-can Fu. Cutting force and its frequency spectrum characteristics in high speed milling of titanium alloy with a polycrystalline diamond tool[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2011, 12(1): 56-62.
[8] Raviraj SHETTY, Raghuvir PAI, Vasanth KAMATH, Shrikanth S. RAO. Steam as coolant and lubricant in turning of metal matrix composites[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(9): 1245-1250.
[9] Yin-jun WANG, Cheng ZHUO, Jun-yong DENG, Jin-fang ZHOU, Kang-sheng CHEN. In-package P/G planes analysis and optimization based on transmission matrix method[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2008, 9(6): 849-857.
[10] WANG Zhou-jing, LI Kevin W.. Layer-layout-based heuristics for loading homogeneous items into a single container[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2007, 8(12): 1944-1952.
[11] Liu Hu-yao, He Yuan-jun. Algorithm for 2D irregular-shaped nesting problem based on the NFP algorithm and lowest-gravity-center principle[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(4): 570-576.
[12] AUDY J.. An appraisal of techniques and equipment for cutting force measurement[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(11): 1781-1789.
[13] KHAN M.M.A., DHAR N.R.. Performance evaluation of minimum quantity lubrication by vegetable oil in terms of cutting force, cutting zone temperature, tool wear, job dimension and surface finish in turning AISI-1060 steel[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2006, 7(11): 1790-1799.
[14] XIAN Jun. Reconstruction algorithm in lattice-invariant signal spaces[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(7): 760-763.
[15] LIU Yi-jian, ZHANG Jian-ming, WANG Shu-qing. Parameter estimation of cutting tool temperature nonlinear model using PSO algorithm[J]. Journal of Zhejiang University-SCIENCE A (Applied Physics & Engineering), 2005, 6(10): 4-.