The Traveling Salesman Problem

Linear Optimization
Final Submission
April 10th, 2021
1 Draft/Abstract.
The Traveling salesman problem (TSP) is a problem that can be seen as if a salesman is going to sell products to several cities, he starts from the first city, and he has to visit every city once and get back to the starting city. This requires considering what route he should schedule to be most optimal. The problem is an NP-hard problem, and the search is NP-complete. If we make a graph, it will be a weighted and undirected graph. By increasing the vertices, the different combinations of the vertices will increase. 
Background 
The Traveling Salesman Problem is an adaptation of the Assignment Problem that considers additional restrictions that guarantee the exclusion of subcircuits in the optimal solution. A circuit represents visits for each vertex once with no repeats. The set of constraints define a traditional allocation model. However, the mapping problem will produce subcircuit solutions rather than complete circuits spanning all n cities. Different computer programs make it possible to deal with the traveling salesperson problem's difficulties.
The complexity of calculating the Traveling Salesman Problem has resulted in multiple attempts to improve route calculation efficiency. The most basic method is brute force, which consists of calculating all possible routes, which is highly inefficient and almost impossible in large networks. There are also heuristics developed due to the complexity in calculating optimal solutions in robust networks, which is why there are methods such as the nearest neighbor. There are also algorithms that provide optimal solutions, and this is mainly the assignment algorithm methods. Some of the earliest attempts to solve TSP focused on a triangular distance matrix (c ij = 0 if i > j) where polynomial algorithms were used. Linear programming and dynamic programming are some of the precise methods that have been useful to solve the TSP and are considered in this paper.
In linear programming models with two decision variables and graphical methods, they approaches are used to solve a linear programming model graphically. However, since there are more variables, the linear programming solvers are helpful to solve the TSP. Dynamic programming solves the problem in stages where an optimization variable is involved in each stage. Calculations of the different stages are recursively linked to generating the optimal solution. Thus, this requires solving optimization problem by combining various sub-problem solutions. The objective is to find the best route and minimize total costs.
There are various variants of the TSP, and they all focus on routing problems to find the optimal route in cities where there are nodes and or customers (Kara et al., 2013). The branch and bound procedure in dynamic programming was adopted and helped to solve problems that had up to 50 nodes for optimality (Kara et al., 2013). Additionally, the approach has been used to solve problems with up to solve 200 nodes. Different approaches have been adopted (Kara et al., 2013). There has been a focus on dealing with optimal solution, and the complexity since getting high-quality solutions requires algorithms that solve large sets of data.
Human solution
“An initial experiment by N. I. Polivanova in 1974 compared human performance on geometrically represented problems versus performance on problems where the travel costs are given explicitly for each pair of cities. The small examples used in this test (having at most 10 cities) allowed for easy look-up in the explicit lists, but the participants performed distinctly better on the geometric instances. This result is not surprising, given the geometric appeal of the TSP discussed in the previous section. It does, however, indicate that people may rely on perceptual skills in approximately solving the TSP, rather than purely cognitive skills” (Applegate et al., 2017)
Tour Construction
1 Nearest Neighbor Procedure.
Starting from the first city, always look for the nearest city as the next target of route, and follow this procedure recursively. The nearest neighbor procedure is a heuristic algorithm designed to solve the traveling salesman problem, but it does not ensure an optimal solution. However, the method provides good solutions, and is efficient.
2 Clark and Wright Savings
According to the property that the sum of the two sides of the triangle inequality is greater than the third side, the initial condition is that salesman should return to last city after visiting a city, and then the calculate the cost difference between routes, and the sort the cities in descending order and merge them.
3 Insertion Procedure
Between two consecutive cities i and j, insert a city k so that d (i , k) + d (k , j) = d (i , j) is minimized. When c ij is the distance from the city i to the city j, then the TSP is similar to the allocation problem.
Application of the problem
The traveling salesman must visit all cities in a, where the distances between all cit...