A parallel algorithm of polygons packing based on ant colony

Author

Peng, Wen ; Tong, Ruofeng ; Tang, Min ; Dong, Jinxiang

Author_Institution

Inst. of Artificial Intelligence, Zhejiang Univ., China

Volume

2

fYear

2005

fDate

24-26 May 2005

Firstpage

846

Abstract

This paper presents a novel algorithm for optimal packing problem by combining ant colony algorithm with BLF (bottom-left-fill) heuristic approach. The proposed algorithm not only automatically looks for the best sequence of the polygons and each polygon´s optimum rotation by ant colony algorithm but also implements the exact layout with the BLF heuristic algorithm. Moreover, the algorithm supports the parallel computation and facilitates quick convergence to the optimal solution. The experimental results show the effectiveness of our algorithm comparing with the other methods.

Keywords

bin packing; genetic algorithms; heuristic programming; parallel algorithms; BLF heuristic algorithm; BLF heuristic approach; ant colony algorithm; bottom-left-fill; optimal packing problem; optimal solution; parallel algorithm; parallel computation; polygon optimum rotation; polygon packing; Ant colony optimization; Computational complexity; Computational modeling; Concurrent computing; Genetic algorithms; Heuristic algorithms; Manufacturing; Parallel algorithms; Shape; Simulated annealing;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Supported Cooperative Work in Design, 2005. Proceedings of the Ninth International Conference on

Print_ISBN

1-84600-002-5

Type

conf

DOI

10.1109/CSCWD.2005.194296

Filename

1504203