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–4]. The types of metaheuristics like genetic algorithms (GA) [5–7], 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
References
[1]
K. Helsgaun, “General k-opt submoves for the Lin–Kernighan TSP heuristic,” Mathematical Programming Computation, vol. 1, no. 2-3, pp. 119–163, 2009.
[2]
H. D. Nguyen, I. Yoshihara, K. Yamamori, and M. Yasunaga, “Implementation of an effective hybrid GA for large-scale traveling salesman problems,” IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics, vol. 37, no. 1, pp. 92–99, 2007.
[3]
O. Martin, S. W. Otto, and E. W. Felten, “Large-step Markov chains for the traveling salesman problem,” Complex Systems, vol. 5, no. 3, pp. 299–326, 1991.
[4]
Y. Nagata and S. Kobayashi, “A powerful genetic algorithm using edge assembly crossover for the traveling salesman problem,” Informs Journal on Computing, vol. 25, no. 2, pp. 346–363, 2013.
[5]
H. Ismkhan and K. Zamanifar, “Developing improved greedy crossover to solve symmetric traveling salesman problem,” International Journal of Computer Science Issues, vol. 9, no. 4, pp. 121–126, 2012.
[6]
M. Albayrak and N. Allahverdi, “Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithms,” Expert Systems with Applications, vol. 38, no. 3, pp. 1313–1320, 2011.
[7]
A. Chowdhury, A. Ghosh, S. Sinha, S. Das, and A. Ghosh, “A novel genetic algorithm to solve travelling salesman problem and blocking flow shop scheduling problem,” International Journal of Bio-Inspired Computation, vol. 5, no. 5, pp. 303–314, 2013.
[8]
X. Geng, Z. Chen, W. Yang, D. Shi, and K. Zhao, “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search,” Applied Soft Computing Journal, vol. 11, no. 4, pp. 3680–3689, 2011.
[9]
S. M. Chen and C. Y. Chien, “Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques,” Expert Systems with Applications, vol. 38, no. 12, pp. 14439–14450, 2011.
[10]
D. Karaboga and B. G？rkemli, “A combinatorial Artificial Bee Colony algorithm for traveling salesman problem,” in Proceedings of the International Symposium on Innovations in Intelligent Systems and Applications (INISTA '11), pp. 50–53, Istanbul, Turkey, June 2011.
[11]
M. Dorigo and L. M. Gambardella, “Ant colony system: a cooperative learning approach to the traveling salesman problem,” IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, 1997.
[12]
J. B. Escario, J. F. Jimenez, and J. M. Giron-Sierra, “Ant colony extended: experiments on the travelling salesman problem,” Expert Systems with Applications, vol. 42, no. 1, pp. 390–410, 2015.
[13]
G. Dong, W. W. Guo, and K. Tickle, “Solving the traveling salesman problem using cooperative genetic ant systems,” Expert Systems with Applications, vol. 39, no. 5, pp. 5006–5011, 2012.
[14]
D. Whitley, D. Hains, and A. Howe, “A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover,” in Proceedings of the 11th International Conference on Parallel Problem Solving from Nature, 2010.
[15]
K. Helsgaun, “An effective implementation of the Lin-Kernighan traveling salesman heuristic,” European Journal of Operational Research, vol. 126, no. 1, pp. 106–130, 2000.
[16]
B. Freisleben and P. Merz, “Genetic local search algorithm for solving symmetric and asymmetric traveling salesman problems,” in Proceedings of the IEEE International Conference on Evolutionary Computation (ICEC '96), pp. 616–621, May 1996.
[17]
S. Lin and B. W. Kernighan, “An effective heuristic algorithm for the traveling-salesman problem,” Operations Research, vol. 21, pp. 498–516, 1973.
[18]
K. Helsgaun, “LKH source codes,” 2009, http://www.akira.ruc.dk/～keld/research/LKH.
[19]
P. Larra？aga, C. M. H. Kuijpers, R. H. Murga, I. Inza, and S. Dizdarevic, “Genetic algorithms for the travelling salesman problem: a review of representations and operators,” Artificial Intelligence Review, vol. 13, no. 2, pp. 129–170, 1999.
[20]
Z. Tao, “TSP problem solution based on improved genetic algorithm,” in Proceedings of the 4th International Conference on Natural Computation (ICNC '08), pp. 686–690, October 2008.
[21]
B. A. Julstrom, “Very greedy crossover in a genetic algorithm for the traveling salesman problem,” in Proceedings of the ACM Symposium on Applied Computing, pp. 324–328, February 1995.
[22]
H. Ismkhan and K. Zamanifar, “Study of some recent crossovers effects on speed and accuracy of genetic algorithm, using symmetric travelling salesman problem,” International Journal of Computer Applications, vol. 80, no. 6, pp. 1–6, 2013.
[23]
S. S. Ray, S. Bandyopadhyay, and S. K. Pal, “Genetic operators for combinatorial optimization in TSP and microarray gene ordering,” Applied Intelligence, vol. 26, no. 3, pp. 183–195, 2007.
[24]
A. Takeda, S. Yamada, K. Sugawara, I. Yoshihara, and K. Abe, “Optimization of delivery route in a city area using genetic algorithm,” in Proceedings of the 4th International Symposium on Artificial Life and Robotics, 1999.
[25]
J. L. Bentley, “K-d trees for semidynamic point sets,” in Proceedings of the 6th Annual Symposium on Computational Geometry, pp. 187–197, June 1990.
[26]
J. L. Bentley, “Experiments on traveling salesman heuristics,” in Proceedings of the 1st Annual ACM-SIAM Symposium on Discrete Algorithms, 1990.
[27]
H. Ismkhan and K. Zamanifar, “Using ants as a genetic crossover operator in GLS to solve STSP,” in Proceedings of the International Conference of Soft Computing and Pattern Recognition (SoCPaR '10), pp. 344–348, Paris, France, December 2010.
[28]
B. M. Ombuki and M. Ventresca, “Local search genetic algorithms for the job shop scheduling problem,” Applied Intelligence, vol. 21, no. 1, pp. 99–109, 2004.
[29]
Y. M. Wang, H. L. Yin, and J. Wang, “Genetic algorithm with new encoding scheme for job shop scheduling,” The International Journal of Advanced Manufacturing Technology, vol. 44, no. 9-10, pp. 977–984, 2009.
[30]
F. T. Hanshar and B. M. Ombuki-Berman, “Dynamic vehicle routing using genetic algorithms,” Applied Intelligence, vol. 27, no. 1, pp. 89–99, 2007.
[31]
N. Yalaoui, H. Mahdi, L. Amodeo, and F. Yalaoui, “A new approach for workshop design,” Journal of Intelligent Manufacturing, vol. 22, no. 6, pp. 933–951, 2011.
[32]
A. S. Ramkumar, S. G. Ponnambalam, N. Jawahar, and R. K. Suresh, “Iterated fast local search algorithm for solving quadratic assignment problems,” Robotics and Computer-Integrated Manufacturing, vol. 24, no. 3, pp. 392–401, 2008.
[33]
K. S. Goh, A. Lim, and B. Rodrigues, “Sexual selection for genetic algorithms,” Artificial Intelligence Review, vol. 19, no. 2, pp. 123–152, 2003.
[34]
D. Whitley, “The genitor algorithm and selective pressure: why rank-based allocation of reproductive trials is best,” in Proceedings of the 3rd International Conference on Genetic Algorithm, 1989.
[35]
S. Hiroaki and I. Yoshihara, “A fast TSP solver using GA on java,” in Proceedings of the 3rd International Symposium on Artificial Life and Robotics, 1999.
[36]
N. H. Dinh, Y. Ikuo, Y. Kunihito, and Y. Moritoshi, “Greedy genetic algorithms for symmetric and asymmetric TSPs,” Information Processing Society of Japan, Transactions on Mathematical Modeling and Its Applications, vol. 43, no. 10, pp. 165–175, 2002.
[37]
J. Majumdar and A. K. Bhunia, “Genetic algorithm for asymmetric traveling salesman problem with imprecise travel times,” Journal of Computational and Applied Mathematics, vol. 235, no. 9, pp. 3063–3078, 2011.
