The Scatter Search is one of the population-based metaheuristics, which can be used to solve a wide range of problems including Traveling Salesman Problem (TSP), Routing Protocol, and End-to-End QoS , while Bees Algorithm can be applied to optimize the solution of these problems. In this paper, an improved Scatter Search algorithm based on Bees Algorithm has been presented. The improvement provides Scatter Search with random exploration for search space of problem and more of intensification for promising solutions. The original and improved Scatter Search has been tested on Traveling Salesman Problem. A computational experiment with benchmark instances is reported. The results demonstrate that the improved Scatter Search algorithm produces better performance than original Scatter Search algorithm. The developed algorithm has been compared with other algorithms for the same problem, and the result was competitive with some algorithm and insufficient with another.