Travelling Salesman Problem
(using SA and GA)
Authors : IIT2015508, ITM2015006, IIT2015507, IIT2015131, IIT2015138
Under Guidance of : Dr. Vrijendra Singh
Abstract — TSP is an NP complete problem, presently there is no polynomial solution available. In this paper we try to solve this very hard problem using various heuristics such as Simulated Annealing, Genetic Algorithm to find a near optimal solution as fast as possible. We try to escape the local optimum, using these advanced heuristic techniques.
Keywords - Genetic Algorithm; Simulated Annealing; heuristic;
1. Introduction
Travelling salesman problem can be formulated as “For given list of nodes determine the shortest tour covering all nodes and …show more content…
It is hard to solve since the number of possible solutions increases exponentially with the size of input. Even the naive solution which goes through all possible arrangements of nodes has a Ō(n!) complexity.
This Problem has many variations like Symmetric Travelling Salesman Problem and Asymmetric travelling Salesman Problem. In Symmetric TSP , the distances between two nodes is same forwards and backwards, while in Asymmetric TSP the distances between two nodes may not be same in either direction. Available deterministic methods like dynamic programming, branch and bound …show more content…
Literature Survey
According to wikipedia, the origins of TSP is yet not known. It was first found in a handbook in 1832 without any prior mathematical statements . It was later formulated by mathematician W.R Hamilton and Thomas Kirkman. The general form of TSP was first studied by Karl Menger in the 30’s.
We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route. [3]
V. PLAN OF WORK We studied various papers on solving Travelling Salesman Problem using Simulated Annealing and Genetic Algorithm with minor modifications to improve the results. Designed a Graphical User Interface, which can takes input from file in TSPLIB data format,
(using SA and GA)
Authors : IIT2015508, ITM2015006, IIT2015507, IIT2015131, IIT2015138
Under Guidance of : Dr. Vrijendra Singh
Abstract — TSP is an NP complete problem, presently there is no polynomial solution available. In this paper we try to solve this very hard problem using various heuristics such as Simulated Annealing, Genetic Algorithm to find a near optimal solution as fast as possible. We try to escape the local optimum, using these advanced heuristic techniques.
Keywords - Genetic Algorithm; Simulated Annealing; heuristic;
1. Introduction
Travelling salesman problem can be formulated as “For given list of nodes determine the shortest tour covering all nodes and …show more content…
It is hard to solve since the number of possible solutions increases exponentially with the size of input. Even the naive solution which goes through all possible arrangements of nodes has a Ō(n!) complexity.
This Problem has many variations like Symmetric Travelling Salesman Problem and Asymmetric travelling Salesman Problem. In Symmetric TSP , the distances between two nodes is same forwards and backwards, while in Asymmetric TSP the distances between two nodes may not be same in either direction. Available deterministic methods like dynamic programming, branch and bound …show more content…
Literature Survey
According to wikipedia, the origins of TSP is yet not known. It was first found in a handbook in 1832 without any prior mathematical statements . It was later formulated by mathematician W.R Hamilton and Thomas Kirkman. The general form of TSP was first studied by Karl Menger in the 30’s.
We denote by messenger problem (since in practice this question should be solved by each postman, anyway also by many travelers) the task to find, for finitely many points whose pairwise distances are known, the shortest route connecting the points. Of course, this problem is solvable by finitely many trials. Rules which would push the number of trials below the number of permutations of the given points, are not known. The rule that one first should go from the starting point to the closest point, then to the point closest to this, etc., in general does not yield the shortest route. [3]
V. PLAN OF WORK We studied various papers on solving Travelling Salesman Problem using Simulated Annealing and Genetic Algorithm with minor modifications to improve the results. Designed a Graphical User Interface, which can takes input from file in TSPLIB data format,