sTSP: Let V = be a set of cities, E = be the edge set, and drs = dsr be a cost measure associated with edge ∈ E. aTSP: If drs ≠ dsr for at least one then the sTSP becomes an aTSP. The aTSP and sTSP are defined on different graphs – complete directed and undirected. sTSP can be considered, in many cases, as a subproblem of the aTSP. mTSP: The mTSP is defined as: In a given set of nodes, let there be m salesmen located at a single depot node. The remaining nodes that are to be visited are intermediate nodes. Then, the mTSP consists of finding tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized.
Algorithm
Description
Below is the dynamic programming procedure: There is an optimization property for TSP: Every subpath of a path of minimum distance is itself of minimum distance. Compute the solutions of all subproblems starting with the smallest. Whenever computing a solution requires solutions for smaller problems using the above recursive equations, look up these solutions which are already computed. To compute a minimum distance tour, use the final equation to generate the 1st node, and repeat for the other nodes. For this problem, we cannot know which subproblems we need to solve, so we solve them all.
Recursive formulation
Number the cities 1, 2,..., N and assume we start at city 1, and the distance between city i and city j is di,j. Consider subsets S ⊆ of cities and, for c ∈ S, let D be the minimum distance, starting at city 1, visiting all cities in S and finishing at city c. First phase: if S =, then D = d1,c. Otherwise: D = minx∈S−c. Second phase: the minimum distance for a complete tour of all cities is M = minc∈ A tour n1,..., nN is of minimum distance just when it satisfies M = D + dnN,1.
g - starting from 1, path min cost ends at vertex x, passing vertices in set S exactly once
cxy - edge cost ends at x from y
p - the second-to-last vertex to x from set S. Used for constructing the TSP path back at the end.
k = 0, null set: Set ∅: g = c21 = 1 g = c31 = 15 g = c41 = 6 k = 1, consider sets of 1 element: Set : g = c32 + g = c32 + c21 = 7 + 1 = 8 p = 2 g = c42 + g = c42 + c21 = 3 + 1 = 4 p = 2 Set : g = c23 + g = c23 + c31 = 6 + 15 = 21 p = 3 g = c43 + g = c43 + c31 = 12 + 15 = 27 p = 3 Set : g = c24 + g = c24 + c41 = 4 + 6 = 10 p = 4 g = c34 + g = c34 + c41 = 8 + 6 = 14 p = 4 k = 2, consider sets of 2 elements: Set : g = min = min = min = 20 p = 3 Set : g = min = min = min = 12 p = 4 Set : g = min = min = min = 20 p = 3 Length of an optimal tour: f = g = min = min = min = 21 Predecessor of node 1: p = 3 Predecessor of node 3: p = 4 Predecessor of node 4: p = 2 Predecessor of node 2: p = 1 Hence, an optimal TSP tour is given by 1 → 2 → 4 → 3 → 1.
function algorithm TSP is for k := 2 to n do C := d1,k end for for s := 2 to n−1 do for all S ⊆, |S| = s do for all k ∈ S do C := minm≠k,m∈S end for end for end for opt := mink≠1 return end function
Complexity
Exhaustive enumeration
This brute-force method starting at any city, enumerate all possible permutations of cities to visit, and find the distance of each permutation and choose one of minimum distance. The total number of possible routes covering all N cities can be given as ! and !/2 in aTSP and sTSP respectively. Stirling's approximation:
Dynamic programming approach
This algorithm offers faster execution than exhaustive enumeration, with the disadvantage using a lot of space: the worst-case time complexity of this algorithm is and the space. Time: the fundamental operations employed in the computation are additions and comparisons. The number of each in the first phase is given by and the number of occurrence of each in the second phase is Space: The space complexity can be slightly improved by noticing that the calculation of minimum costs for subsets of size s only requires subsets of size s-1. By storing only subsets of size s-1 and s at any point of the algorithm, the space complexity reduces to:
Related algorithms
Precise algorithm for solving the TSP
Besides Dynamic Programming, Linear programming and Branch-bound algorithm are precise algorithms that can solve TSP. Linear programming applies to the cutting plane method in the integer programming, i.e. solving the LP formed by two constraints in the model and then seeking the cutting plane by adding inequality constraint to gradually converge at an optimal solution. When people apply this method to find a cutting plane, they often depend on experience. So this method is seldom deemed as a general method. Branch-bound algorithm is a search algorithm widely used, although it's not good for solving the large-scale problem. It controls the searching process through effective restrictive boundary so that it can search for the optimal solution branch from the space state tree to find an optimal solution as soon as possible. The key point of this algorithm is the choice of the restrictive boundary. Different restrictive boundaries may form different branch-bound algorithms.
Approximate algorithm for solving the TSP
As the application of precise algorithm to solve problem is very limited, we often use approximate algorithm or heuristic algorithm. The result of the algorithm can be assessed by C / C* ≤ ε. C is the total travelling distance generated from approximate algorithm; C* is the optimal travelling distance; ε is the upper limit for the ratio of the total travelling distance of approximate solution to optimal solution under the worst condition. The value of ε >1.0. The more it closes to 1.0, the better the algorithm is. These algorithms include: Interpolation algorithm, Nearest neighbour algorithm, Clark & Wright algorithm, Double spanning tree algorithm, Christofides algorithm, Hybrid algorithm, Probabilistic algorithm.
