Problems that often arise in finding the shortest distance or the fastest route in any area is the lack of information itself. It has also happened in the tourism activity, when people, in this case, tourists, need to find a path to get tourist attractions place or to know the level of a street crowded and the volume of the path. Due to their limited time, the shortest route search is important (Fard & Akbari, 2013). Searching the shortest route is to determine the most optimal path, that is the path with the shortest route and the smallest fee. This can be applied by searching all routes altogether through a connected network (Chelouah & Siarry, 2000). In some applications, it is also helpful to know the shortest paths with two or three additional alternatives, for example, in order to improve the effectiveness of travel information, a driver can get some choices as s/he like based on the need.

Determining routes can use metaheuristic process. It is the method for finding a solution by combining interaction between local searching procedures and higher strategies, in order to create a process that is able to get the local optimal spots, and do a search on space solutions for finding global solutions (Kusumadewi & Purnomo, 2005). Metaheuristic variants are Simulated Annealing, Genetic Algorithms, Cross Entropy, Particle Swarm Optimation and Tabu Search (Bajeh & Abolarinwa, 2011). Searching fastest distance and the shortest route, in this research we choose the tourist attraction places at Rote Ndao Regency-Indonesia is applied using Tabu Search since it has shown good performance with functions more than 10 variables (Sarmady, 2012). This algorithm can optimize costs and can produce minimum cost. In the case of our research, Tabu Search algorithm is able to increase the initial solutions through improving procedures. As have been stated, we applied the system by examining tourism attraction places in Rote Island, Indonesia. Geographically, it is located between 10 degrees 25–11 degrees south latitude, and 121 degrees 26 49–123 degrees East longitude. It has a wide choice of tour destinations such as Nemberala Beach, Bo'a Beach, Mando's Beach, Oeseli Beach, Laviti Beach, the Lake of the Dead Sea, Termanu stone, etc. There are many tourists have visited this island. To help tourism development in Indonesia, especially in Rote Island, as well as to examine the application built in finding the shortest route, we conducted this research.