An Adaptive Tabu Search (ATS) and Other Metaheuristics for a Class of Optimal Allocation Problems
Shigeyuki Takahara* and Sadaaki Miyamoto*
*Kagawa Prefectural Industrial Technology Center
587-1 Goto-cho Takamatsu Kagawa 761-8031, Japan
**Institute of Information Sciences and Electronics, University of Tsukuba Ibaraki 305-8573, Japan
We propose an ATS, for a class of optimal allocation problems, that uses various types of memory to make the search effective. To improve efficiency, our tabu search (TS) uses a combination of objects, rather than moves, as memory elements, simplifying search constraints and improving search efficiency. The ATS is applied to optimal allocation of irregular shapes on a sheet to minimize waste. The effectiveness of the proposed method is compared to other metaheuristics in a simulation whose results show the ATS to be superior.