One of the well-known combinatorial optimization problems is travelling salesman problem (TSP). This problem is in the fields of logistics, transportation, and distribution. TSP is among the NP-hard problems, and many different metaheuristics are used to solve this problem in an acceptable time especially when the number of cities is high. In this paper, a new meta-heuristic is proposed to solve TSP which is based on new insight into network routing problems. 1. Introduction Although there are various classic methods for solving optimization problems, but they are not always able to solve real and applied optimization problems. It is generally believed that these problems are known as difficult and complicated problems. TSP is a typical example of a very hard combinatorial optimization problem. TSP can be modelled as an undirected weighted graph, such that cities are the graph’s vertices, paths are the graph’s edges, and a path’s distance is the edge’s length. It is a minimization problem starting and finishing at a specified vertex after having visited each other’s vertex exactly once. Metaheuristics can solve high-dimensional problems quickly. Heuristics may be classified into two families: specific heuristics and metaheuristics. Specific heuristics are tailored and designed to solve a specific problem and/or instance. Metaheuristics are general-purpose algorithms that can be applied to solve almost any optimization problem. They may be viewed as upper level general methodologies that can be used as a guiding strategy in designing underlying heuristics to solve specific optimization problems [1]. The word metaheuristic was first used by Glover [2] during introducing tabu search concepts. Metaheuristics gained more popularity in few recent decades, and various algorithms are proposed to solve the problem such as Genetic Algorithm [3–5], Ant Colony [6–10], Particle Swarm [11], and Simulated Annealing [12, 13]. In this paper, a novel metaheuristic is proposed for solving TSP. This algorithm is used to foresee the best next city so as to gain shorter rout. The 2-Opt and 3-Opt algorithms are also used in local search. They are probably the most basic local search heuristics for the TSP. The paper is organized as follows: Section 2 illustrates the background theory of suggested algorithm. In Section 3, formulating algorithms are presented. Algorithm improvement by using k-Opt is discussed in Section 4. The algorithm is employed into several standard TSP instances in the next section and the results are reported. According to the obtained results, it is
References
[1]
T. El-ghazali, Meta-Heuristic from Design to Implementation, Wiley, 2009.
[2]
F. Glover, “Future paths for integer programming and links to artificial intelligence,” Computers and Operations Research, vol. 13, no. 5, pp. 533–549, 1986.
[3]
S. Yuan, B. Skinner, S. Huang, and D. Liu, “A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms,” European Journal of Operational Research, vol. 228, no. 1, pp. 72–82, 2013.
[4]
Y. Nagata and D. Soler, “A new genetic algorithm for the asymmetric traveling salesman problem,” Expert Systems with Applications, vol. 39, no. 10, pp. 8947–8953, 2012.
[5]
W. Hui, “Comparison of several intelligent algorithms for solving TSP problem in industrial engineering,” Systems Engineering Procedia, vol. 4, pp. 226–2235, 2012.
[6]
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.
[7]
J. Yang, X. Shi, M. Marchese, and Y. Liang, “Ant colony optimization method for generalized TSP problem,” Progress in Natural Science, vol. 18, no. 11, pp. 1417–1422, 2008.
[8]
M. Dorigo and L. M. Gambardella, “Ant colonies for the travelling salesman problem,” BioSystems, vol. 43, no. 2, pp. 73–81, 1997.
[9]
J. Bai, G. K. Yang, Y. W. Chen, L. S. Hu, and C. C. Pan, “A model induced max-min ant colony optimization for asymmetric traveling salesman problem,” Applied Soft Computing, vol. 13, no. 3, pp. 1365–1375, 2013.
[10]
A. Colorni, M. Dorigo, F. Maffioli, V. Maniezzo, G. Righini, and M. Trubian, “Heuristics from nature for hard combinatorial optimization problems,” International Transactions in Operational Research, vol. 3, no. 1, pp. 1–21, 1996.
[11]
X. H. Shi, Y. C. Liang, H. P. Lee, C. Lu, and Q. X. Wang, “Particle swarm optimization-based algorithms for TSP and generalized TSP,” Information Processing Letters, vol. 103, no. 5, pp. 169–176, 2007.
[12]
K. Meer, “Simulated annealing versus metropolis for a TSP instance,” Information Processing Letters, vol. 104, no. 6, pp. 216–219, 2007.
[13]
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.
[14]
C. Engels and B. Manthey, “Average-case approximation ratio of the 2-opt algorithm for the TSP,” Operations Research Letters, vol. 37, no. 2, pp. 83–84, 2009.
[15]
K. H. Hsieh, “Fourier descriptors for 2-Opt and 3-Opt heuristics for traveling salesman problem,” Journal of the Chinese Institute of Industrial Engineers, vol. 28, no. 3, pp. 237–246, 2011.
