%0 Journal Article
%T A Novel Metaheuristic for Travelling Salesman Problem
%A Vahid Zharfi
%A Abolfazl Mirzazadeh
%J Journal of Industrial Engineering
%D 2013
%I Hindawi Publishing Corporation
%R 10.1155/2013/347825
%X 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¨C5], Ant Colony [6¨C10], 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
%U http://www.hindawi.com/journals/jie/2013/347825/