The travelling salesman problem sets up a benchmark for comparison test for different computational methods. Even though the problem is easily expressed, its solution is computationally difficult. A salesperson has a task to take a closed round tour of a mentioned number of cities. All these mentioned cities are connected to each other by means of roads and a criterion of Hamilton is that, each city can be visited only once. The main aim of program is to obtain minimum optimal tour length by the optimization of given problem. In order to do this, once can change the order in which cities are being traversed. N is the total number of given cities, and every city is assigned with an ordinal number from 1 to N.
Brief history: This travelling …show more content…
This applies also in each and every opposite direction, thus leading to formation of a graph which is undirected in nature. Due to this symmetry, the number of solutions possible is halved making life of a user easy!
- Asymmetric TSP: Here, in contrast to the above, the distances may not be same as well as the paths may not exist in both directions, which leads to formation of a graph which is directed in nature.
Applications of TSP:
Even in its own purest form, TSP has many applications. Following are few such examples manufacturing of the microchips, planning of different processes like travelling, field of logistics handling. It appears as an application of sequencing of DNA in its modified form.
In these applications:
- The concept in application field of cities can be represented, to give some examples, customers, DNA fragments etc, points of soldering.
- The concept that is – distance, represents say costs or duration of time involved in …show more content…
This helps a lot during travelling to unknown destinations with the complete reliance on the virtual GPS system being employed in the vehicle: Figure 3: Google Maps fastest roundtrip solver Courtesy: www.heuristicswiki.wikispaces.com
The travelling salesman problem in its generalized form, also has been termed as the "travelling politician problem", wherein conceptually a politician deals with "states" which comprises within of one/more "cities" and further the politician is obliged to visit exactly one "city" from each one of the "state", that politician is dealing with.
Ways to solve Travelling Salesman Problem:
There are many methods that are being employed to solve TSP problems, which vary as per their respective path formulation techniques and also time-span required for computation completion. Some of those methods are as mentioned: Heuristics, Genetic Search, Greedy, Hill Climbing, Simulated Annealing, Ant Colony, Random search
Brief history: This travelling …show more content…
This applies also in each and every opposite direction, thus leading to formation of a graph which is undirected in nature. Due to this symmetry, the number of solutions possible is halved making life of a user easy!
- Asymmetric TSP: Here, in contrast to the above, the distances may not be same as well as the paths may not exist in both directions, which leads to formation of a graph which is directed in nature.
Applications of TSP:
Even in its own purest form, TSP has many applications. Following are few such examples manufacturing of the microchips, planning of different processes like travelling, field of logistics handling. It appears as an application of sequencing of DNA in its modified form.
In these applications:
- The concept in application field of cities can be represented, to give some examples, customers, DNA fragments etc, points of soldering.
- The concept that is – distance, represents say costs or duration of time involved in …show more content…
This helps a lot during travelling to unknown destinations with the complete reliance on the virtual GPS system being employed in the vehicle: Figure 3: Google Maps fastest roundtrip solver Courtesy: www.heuristicswiki.wikispaces.com
The travelling salesman problem in its generalized form, also has been termed as the "travelling politician problem", wherein conceptually a politician deals with "states" which comprises within of one/more "cities" and further the politician is obliged to visit exactly one "city" from each one of the "state", that politician is dealing with.
Ways to solve Travelling Salesman Problem:
There are many methods that are being employed to solve TSP problems, which vary as per their respective path formulation techniques and also time-span required for computation completion. Some of those methods are as mentioned: Heuristics, Genetic Search, Greedy, Hill Climbing, Simulated Annealing, Ant Colony, Random search