%0 Journal Article
%T Developing Programming Tools to Handle Traveling Salesman Problem by the Three Object-Oriented Languages
%A Hassan Ismkhan
%A Kamran Zamanifar
%J Applied Computational Intelligence and Soft Computing
%D 2014
%I Hindawi Publishing Corporation
%R 10.1155/2014/137928
%X The traveling salesman problem (TSP) is one of the most famous problems. Many applications and programming tools have been developed to handle TSP. However, it seems to be essential to provide easy programming tools according to state-of-the-art algorithms. Therefore, we have collected and programmed new easy tools by the three object-oriented languages. In this paper, we present ADT (abstract data type) of developed tools at first; then we analyze their performance by experiments. We also design a hybrid genetic algorithm (HGA) by developed tools. Experimental results show that the proposed HGA is comparable with the recent state-of-the-art applications. 1. Introduction The objective of TSP is to find the shortest tour among a set of cites. Given the distance matrix where stands for distance between the city and , the problem is called symmetric TSP (STSP) when and, otherwise, it is named asymmetric TSP (ATSP). Since TSP is NP-Complete, there is no exact algorithm with time complexity better than an exponential time. It means that exact algorithms are not practical for the large-scale instances in reasonable running times, so we have to use approximate algorithms to find the semioptimal solutions in acceptable running times. Recently, many approximate algorithms have been developed to handle TSP instances [1¨C4]. The types of metaheuristics like genetic algorithms (GA) [5¨C7], simulated annealing [8], swarm based algorithm [9], artificial bee colony algorithm [10], ant colony algorithms [11, 12], and combination of these algorithms have been applied to the TSP [13, 14]. However, if we consider the experiment sections of these references, we observe that almost all of these algorithms have not been applied to the instances with size of more than 1000. Among these metaheuristics, surly, Lin-Kernighan (LK) which is a type of local search algorithms (LSAs) (in this paper, LS points to the local search) is one of the best algorithms in which its extended types have been successfully applied to the large-scale instances with size of more than 85000 nodes [3, 15]. In addition, in many cases, these algorithms have been used in other metaheuristics and have increased their performance [2, 11, 16]. LSAs include 2- and 3-opt and Lin-Kernighan (LK) algorithms have been based on edges exchange process [1, 3, 15, 17]. GAs are population-based and their efficiency depends on their operators [4]. To easily use these algorithms, we have programmed objective tools by three object-oriented languages which include C++, C#, and Java. These tools allow the researchers or
%U http://www.hindawi.com/journals/acisc/2014/137928/