Iterated Tabu Search and Variable Neighborhood Descent for packing unequal circles into a circular container

• Published in: European journal of operational research 2016-04, Vol.250 (2), p.615-627
• Main Authors: Zeng, Zhizhong, Yu, Xinguo, He, Kun, Huang, Wenqi, Fu, Zhanghua
• Format: Article
• Language: English
• Subjects: Algorithms; Benchmarks; Iterated Local Search; Iterative methods; Job shops; Mathematical functions; Neighborhoods; Packing; Packing problem; Studies; Tabu Search; Variable Neighborhood Descent
• ISSN: 0377-2217; 1872-6860
• DOI: 10.1016/j.ejor.2015.09.001

•A high performance algorithm for packing unequal circles into a circular container.•A new insert neighborhood is designed to supplement traditional swap neighborhood.•An efficient mechanism to employ the insert neighborhood.•The algorithm improves or matches all but one records of three benchmark sets.•Analyses on which key new features are important and how they work. This paper presents an Iterated Tabu Search and Variable Neighborhood Descent (ITS-VND) algorithm for packing unequal circles into a circular container (PUCC). The algorithm adapts the Tabu Search procedure of Iterated Tabu Search algorithms and proposes a Tabu Search and Variable Neighborhood Descent (TS-VND) procedure. We observe there are strong complementarities between the small circles and the large vacant places, and propose the insert neighborhood to match up the small circles with the large vacant places. Although the insert neighborhood is inefficient and time-consuming, it is an important supplement to the classic swap neighborhood as it could arrange the small circles properly. Predicated on these features, we employ the insert neighborhood only at chosen local minima of the swap neighborhood that shows promise for an improvement. The traditional Tabu Search procedure is then transformed into a hybrid procedure composed of two alternative parts, namely Variable Neighborhood Descent and Tabu Search respectively. Besides this reformed procedure, ITS-VND also incorporates other new features, such as an adaptive evaluation function, a novel method for accelerating the neighborhood exploration, and the “collision accidents” criterion for evaluating how intensively the area near the current solution has been explored. The computational results on three well established benchmark sets show that the proposed algorithm not only has a good discovery capability but also can provide good results within a reasonable time. For a total of 84 benchmark instances, the proposed algorithm improves the best-known results on 23 instances, matches 60, and only misses one.