A bee colony optimisation algorithm with a sequential-pattern-mining-based pruning strategy for the travelling salesman problem

The unique foraging behaviour of bees via waggle dance has been computationally realised as an algorithm named bee colony optimisation (BCO) to solve different types of combinatorial optimisation problems such as travelling salesman problem (TSP). In order to enhance the performance of BCO, local optimisation can be integrated. However, local optimisation incurs high processing overhead especially when all solutions are allowed to undergo the local optimisation. This paper proposes a pruning strategy based on the top-k sequential patterns (TKS) mining algorithm. Specifically, TKS is employed to identify the frequent building blocks along the optimisation process. A total of 19 TSP benchmark problem instances ranging from 318 cities to 1,291 cities were used as the test bed. The proposed pruning strategy shows a significant reduction in terms of the computational time to yield TSP solutions with similar tour length as compared with two state-of-the-art approaches.