Full Text:   <2418>

CLC number: TP301.6

On-line Access: 

Received: 2004-06-11

Revision Accepted: 2004-10-20

Crosschecked: 0000-00-00

Cited: 0

Clicked: 5600

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2005 Vol.6 No.6 P.565-570

http://doi.org/10.1631/jzus.2005.A0565


A heuristic method for solving triangle packing problem


Author(s):  CHEN Chuan-bo, HE Da-hua

Affiliation(s):  College of Computer Science & Technology, Huazhong University of Science & Technology, Wuhan 430074, China

Corresponding email(s):   chuanboc@163.com, hedahua@xinhuanet.com

Key Words:  Triangle packing problem, Rigid placement, Flexibility, Destruction, Least-Destruction-First (LDF) strategy, Backtracking


CHEN Chuan-bo, HE Da-hua. A heuristic method for solving triangle packing problem[J]. Journal of Zhejiang University Science A, 2005, 6(6): 565-570.

@article{title="A heuristic method for solving triangle packing problem",
author="CHEN Chuan-bo, HE Da-hua",
journal="Journal of Zhejiang University Science A",
volume="6",
number="6",
pages="565-570",
year="2005",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2005.A0565"
}

%0 Journal Article
%T A heuristic method for solving triangle packing problem
%A CHEN Chuan-bo
%A HE Da-hua
%J Journal of Zhejiang University SCIENCE A
%V 6
%N 6
%P 565-570
%@ 1673-565X
%D 2005
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2005.A0565

TY - JOUR
T1 - A heuristic method for solving triangle packing problem
A1 - CHEN Chuan-bo
A1 - HE Da-hua
J0 - Journal of Zhejiang University Science A
VL - 6
IS - 6
SP - 565
EP - 570
%@ 1673-565X
Y1 - 2005
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2005.A0565


Abstract: 
Given a set of triangles and a rectangle container, the triangle packing problem is to determine if these triangles can be placed into the container without overlapping. triangle packing problem is a special case of polygon packing problem and also NP-hard, so it is unlikely that an efficient and exact algorithm can be developed to solve this problem. In this paper, a new concept of rigid placement is proposed, based on which a discrete solution space called rigid solution space is constructed. Each solution in the rigid solution space can be built by continuously applying legal rigid placements one by one until all the triangles are placed into the rectangle container without overlapping. The proposed Least-destruction-First (LDF) strategy determines which rigid placement has the privilege to go into the rectangle container. Based on this, a heuristic algorithm is proposed to solve the problem. Combining Least-destruction-First strategy with backtracking, the corresponding backtracking algorithm is proposed. Computational results show that our proposed algorithms are efficient and robust. With slight modification, these techniques can be conveniently used for solving polygon packing problem.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article

Reference

[1] Dowsland, K.A., Dowsland, W.B., 1992. Packing problems. European Journal of Operational Research, 56(1):2-14.

[2] Garey, M.R., Johnson, D.S., 1979. Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, New York.

[3] Li, Z., Milenkovic, V.J., 1995. Compaction and separation algorithms for non-convex polygons and their applications. European Journal of Operational Research, 84:539-561.

[4] Liang, K.H., Yao, X., Newton, C., Hoffman, D., 2002. A new evolutionary approach to cutting stock problems with and without contiguity. Computers and Operations Research, 29(12):1641-1659.

[5] Lipnitskii, A.A., 2002. Use of genetic algorithms for solution of the rectangle packing problem. Cybernetics and Systems Analysis, 38(6):943-946.

[6] Milenkovic, V.J., Daniels, K.M., 1996. Translational Polygon Containment and Minimal Enclosure Using Mathematical Programming. Proceedings of the Annual ACM Symposium on Theory of Computing, p.109-118.

[7] Milenkovic, V.J., Daniels, K.M., Li, Z., 1991. Automatic Marker Making. Proceedings of the Third Canadian Conference on Computational Geometry, p.243-246.

[8] Osogami, T., Okano, H., 2003. Local search algorithms for the bin packing problem and their relationships to various construction heuristics. Journal of Heuristics, 9(1):29-49.

[9] Wang, H.Q., 2002. An improved algorithm for the packing of unequal circles within a larger containing circle. European Journal of Operational Research, 141(2):440-453.

Open peer comments: Debate/Discuss/Question/Opinion

<1>

gabriel@godoy<gabrgodoy@outlook.com>

2014-05-01 12:02:48

thanks for sharing

Please provide your name, email address and a comment





Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2022 Journal of Zhejiang University-SCIENCE