A Hybrid Algorithm with Modified Inver-Over Operator and Genetic Algorithm Search for Traveling Salesman Problem
In this article, we develop a novel hybrid approach to solve the traveling salesman problem (TSP). In this approach, we first initialize suboptimal solution using Nearest Neighbor (NN) tour construction method, followed modified Inver-over operator and th
- PDF / 833,619 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 19 Downloads / 197 Views
Abstract In this article, we develop a novel hybrid approach to solve the traveling salesman problem (TSP). In this approach, we first initialize suboptimal solution using Nearest Neighbor (NN) tour construction method, followed modified Inver-over operator and then proposed crossover with 2-opt mutation applied to improve for optimal solution. We use 14 TSP data sets from TSPLIB to evaluate the performance of proposed hybrid method. The proposed hybrid method gives better results in terms of best and average error. In experimental results of the tests we show that the proposed hybrid method is superior to available algorithm in literature.
Keywords Traveling salesman problem Basic inver-over operator inver-over operator 2-opt mutation Crossover operator
Modified
1 Introduction 1.1
Traveling Salesman Problem
Combinatorial optimization problem contains a broad study of the traveling salesman problem (TSP) [1]. Given a set of n cities and distance between each pair of cities, the traveling salesman visit all cities only once and return back to starting city with minimum distances. This type problem is modeled in graph theory with D.R. Singh (&) M.K. Singh DST-Centre for Interdisciplinary Mathematical Sciences (DST-CIMS), Banaras Hindu University, Varanasi 221005, India e-mail: [email protected] M.K. Singh e-mail: [email protected] T. Singh Department of Mathematics, Birla Institute of Technology and Science Pilani, K K Birla Goa Campus, Zuarinagar 403726, Goa, India e-mail: [email protected] © Springer Science+Business Media Singapore 2016 R.K. Choudhary et al. (eds.), Advanced Computing and Communication Technologies, Advances in Intelligent Systems and Computing 452, DOI 10.1007/978-981-10-1023-1_14
141
142
D.R. Singh et al.
help of vertices and edges. Vertices represent cities and edges represent roads between the two cities and the weight of an edge represents distance between two adjacent cities. Thus, we have a weighted graph G = (V, E, w), where w: E → Z and Z is a set of nonnegative integer. A closed C = (u = u0, u1, u2, …, un = u) tour in which all the vertices are distinct which is known as Hamiltonian cycle. Finding Hamiltonian cycle with minimum travel cost w(C) = ∑w(ei), where summation is taken over all edges in C in the weighted graph is the desired solution. The matrix representation of weighted graph is known as cost matrix which is denoted by C = (cij), i, j = 1, 2, …, n. An entry of cost matrix cij represents the cost between ith vertex to jth vertex. The total cost of Hamiltonian cycle is the sum of cost of each edge in Hamiltonian cycle. In general; this problem is NP-hard. The Euclidean distance (cost) between two adjacent vertices is calculated as fallow: cij ¼
qffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi 2 2ffi xi xj þ yi yj ;
ð1Þ
where (xi, yi) and (xj, yj) are coordinates of two adjacent vertices.
1.2
Literature Review
According to Arora [2], TSP is NP-hard combinational optimization problem. The most commonly used heuristic and meta-h
Data Loading...
