A General Parallel Tabu Search Algorithm For Combinatorial Optimisation Problems

摘要

Tabu Search (TS) is a meta-heuristic search algorithm that is easy to parallelise. Efficient parallelisation of TS can represent a significant saving in the real-time required to solve a problem over an equivalent sequential algorithm. In this study, a general parallel TS algorithm for solving combinatorial optimisation problems (COPs) is presented. The unique feature of our approach is that the TS solves a wide range of COPs expressed in a high level syntax. The benefit of this general code is that it can be used in real-time applications due to its parallel scalability and the fact that it can accept changing problem definitions. After reviewing a number of suitable parallelisation strategies, results are presented that show that good parallel speedup is achieved while efficient solutions to hard COPs are obtained.