TRAVELLING SALESPERSON PROBLEM

50 %
50 %
Education

Published on March 6, 2009

Author: ankush85

Source: authorstream.com

TRAVELLING SALESPERSON PROBLEM : 1 TRAVELLING SALESPERSON PROBLEM Let G = (V,E) be a directed graph defining an instance of travelling Sales Person Problem Le Cij = cost of edge (i,j), Cij = ? if (i,j) ? E and let ?v ? = n. Assumption : Every tour starts & ends at vertex 1. So, the solution space S = { 1, ?, 1 ? ? is a permutation of (2,3,…..n)}; ?S ? = (n-1) ! TRAVELLING SALESPERSON PROBLEM (Contd..) : 2 TRAVELLING SALESPERSON PROBLEM (Contd..) The size of S may be reduced by restricting S so that (1,i1,i2, ….in-1, 1) ? S iff <ij, ij+1 > ?E, 0 ? j ? n – 1, i0 = in =1. S can be organised into a state space tree. For complete graph with ?V ? = 4, state space tree is as in Figure 1 each leaf node (L) is a solution node & defines a path from root to L. TRAVELLING SALESPERSON PROBLEM (Contd..) : 3 TRAVELLING SALESPERSON PROBLEM (Contd..) 1 2 3 4 2 3 4 3 4 2 4 2 3 5 6 7 8 9 10 4 3 4 2 3 2 11 12 13 14 15 16 Figure 1 TRAVELLING SALESPERSON PROBLEM (Contd..) : 4 TRAVELLING SALESPERSON PROBLEM (Contd..) Node (14) represents tour i0 = 1, i1 = 3, i2 = 4, i3 =2. To use LCBB to search travelling salesperson state space tree, we need to define a cost function c(.) and two other functions c(.) and u(.) such that c(R) ? c(R) ? u(R) ?nodes R. TRAVELLING SALESPERSON PROBLEM (Contd..) : 5 TRAVELLING SALESPERSON PROBLEM (Contd..) The cost c(.) is such that the solution node with least c(.) corresponds to a shortest path/tour in G one choice for c(.) is : C(A) = { length of tour defined by path from root to A, if A is a leaf. Cost of minimum-cost leaf in the sub tree A, if A is not a leaf. c(.) can be obtained by using the reduced cost matrix corresponding to G. TRAVELLING SALESPERSON PROBLEM (Contd..) : 6 TRAVELLING SALESPERSON PROBLEM (Contd..) A row (column) is said to be reduced iff it contains at-least one zero and all remaining entries as non-negative. A Matrix is reduced iff every row and column is reduced. TRAVELLING SALESPERSON PROBLEM - Example : 7 TRAVELLING SALESPERSON PROBLEM - Example Example : Graph with 5 vertices ? 20 30 10 11 15 ? 16 4 2 3 5 ? 2 4 19 6 18 ? 3 16 4 7 16 ? TRAVELLING SALESPERSON PROBLEM (Contd..) : 8 TRAVELLING SALESPERSON PROBLEM (Contd..) Since every tour on this graph includes exactly one edge (i,j) with i = k, 1? k ? 5, and exactly one edge (i,j) with j = k, 1? k ? 5, subtracting a constant t from every entry in one row or one column of the cost matrix reduces the length of every tour by exactly t A minimum-cost tour remains a minimum cost tour following this subtraction operation. TRAVELLING SALESPERSON PROBLEM (Contd..) : 9 TRAVELLING SALESPERSON PROBLEM (Contd..) If t is chosen to be the minimum entry in row i (column j), then subtracting it from all entries in row i (column j) introduces a zero into row i (column j). Repeating this as often as needed, the cost matrix can be reduced. The total amount subtracted from the columns & rows is a lower bound on the length of a minimum-cost tour and can be used as the c value for the root of state space tree. TRAVELLING SALESPERSON PROBLEM (Contd..) : 10 TRAVELLING SALESPERSON PROBLEM (Contd..) ? 10 20 0 1 ? 10 17 0 1 13 ? 14 2 0 12 ? 11 2 0 1 3 ? 0 2 0 3 ? 0 2 16 3 15 ? 0 15 3 12 ? 0 12 0 3 12 ? 5x5 11 0 0 12 ? Subtracting 10,2,2,3,4 from Reduced cost matrix the rows 1,2,3,4,5 Subtracting 1,3 from column 1, column 3. Total amount subtracted = 10+2+2+3+4+1+3 = 25 Hence, all tours in original graph have a length at-least 25. TRAVELLING SALESPERSON PROBLEM (Contd..) : 11 TRAVELLING SALESPERSON PROBLEM (Contd..) Let A be reduced cost matrix for node R. Let S be a child of R such that the tree edge (R,S) corresponds to including edge <i,j> in the tour. If S is not a leaf, then the reduced cost matrix for S may be obtained as follows : 1) Change all entries in row i and column j of A to ?. 2) Set A(j,i) to ?. [This prevents the use of edge < j,i >] TRAVELLING SALESPERSON PROBLEM (Contd..) : 12 TRAVELLING SALESPERSON PROBLEM (Contd..) Reduce all rows & columns in the resulting matrix except for rows & columns containing only ?. Let the resulting matrix be B If r is the total amount subtracted in step (3), then c(S) = c(R) + A (i,j) + r. For leaf nodes, c(.) = c(), as each leaf defines a unique tour For upper bound function U, we can use u(R) = ? for all nodes R. For S not leaf, reduced cost matrix will be TRAVELLING SALESPERSON PROBLEM (Contd..) : 13 TRAVELLING SALESPERSON PROBLEM (Contd..) ? ? ? ? ? ? ? ? ? ? 12 ? 11 2 0 ? ? 11 2 0 0 ? ? 0 2 0 ? ? 0 2 15 ? 12 ? 0 15 ? 12 ? 0 11 ? 0 12 ? 11 ? 0 12 ? (i) (ii) iii) No further reduction required as each row & column has a zero. TRAVELLING SALESPERSON PROBLEM (Contd..) : 14 TRAVELLING SALESPERSON PROBLEM (Contd..) c(S) = c(R) + A (i,j) + r = 25 + 10 + 0 = 35 Similarly finding other reduced cost matrices, we obtain the tour length for solution node 11 is c(11) = 28 & U is updated to 28. For the next node 5, c(S) = 31 > U. Hence LCBB terminates with 1,4,2,5,3,1 as the shortest length tour. TRAVELLING SALESPERSON PROBLEM (Contd..) : 15 TRAVELLING SALESPERSON PROBLEM (Contd..) 25 1 2 3 4 5 35 2 53 3 25 4 5 31 2 3 5 28 6 50 7 8 36 3 5 52 9 10 28 3 11 28 Fig. 4 DYNAMIC STATE SPACE TREE ORGANISATION : 16 DYNAMIC STATE SPACE TREE ORGANISATION If G = (V,E) has e edges then every tour contains exactly ‘n’ of the ‘e’ edges. For each i, 1 ? i ? n there is exactly one edge of the form (i,j) and one of the form (k,i) in every tour. A possible organisation for the state space tree is a binary tree. - a left branch represents the inclusion of a particular edge while the right branch represents the exclusion of that edge. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 17 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) If edge <i,j> is used then the left sub-tree of the root will represent all tours including edge <i,j> & the right sub tree will represent all tours that do not include edge <i,j>. If an optimal tour is included in the left sub tree then only (n-1) edges need to be selected. If all optimal tours lie in the right sub tree then we have still to select n edges. DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) : 18 DYNAMIC STATE SPACE TREE ORGANISATION (Contd..) Since the left sub tree selects fewer edges, it should be easier to find an optimal solution in it than to find one in the right sub tree. Selection Rule for edges : Select that edge which results in a right sub tree that has highest c value. Dynamic State Space Tree Organisation - example : 19 Dynamic State Space Tree Organisation - example Consider the reduced cost matrix. The fact, that all tours have a length at-least 25, is represented by the root of state space tree. At the root node, we have to determine an edge <i,j> that will maximize the c value of the right sub tree. If we select an edge <i,j> whose cost in reduced matrix is positive, then the c value of the right sub tree will remain 25 Dynamic State Space Tree Organisation – example (Contd..) : 20 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 ? 10 17 0 1 12 ? 11 2 0 0 3 ? 0 2 15 3 12 ? 0 11 0 0 12 ? Dynamic State Space Tree Organisation – example (Contd..) : 21 Dynamic State Space Tree Organisation – example (Contd..) This is because the reduced matrix for right sub-tree will have cost (i, j) = ? & all other entries are identical. Hence, B will be reduced and c cannot increase. So, we must choose an edge with reduced cost 0. Once this is chosen, the cost of the edge will be set to ? and the matrix may not be reduced. To reduce the matrix again some amount is to be subtracted and it is to be added to the c value. Thus the c value may increase Dynamic State Space Tree Organisation – example (Contd..) : 22 Dynamic State Space Tree Organisation – example (Contd..) If A is the reduced cost matrix for node R, then the selection of edge <i,j> (A(i,j) = 0) as the next partitioning edge will increase the c of the right sub-tree by ? = min k?j { A (i,k) } + min k?i{ A(k,j) } as this much needs to be subtracted from row i & column j to introduce a zero into both. Dynamic State Space Tree Organisation – example (Contd..) : 23 Dynamic State Space Tree Organisation – example (Contd..) For edges <1,4), <2,5>, <3,1>, <3,4>, <4,5>, <5,2>, & <5,3>. ? = 1, 2, 11, 0, 3, 3 & 11 So, either of edges <3,1> or <5,3> can be used. Let us assume that LCBB selects edge <3,1> c(2) can be computed in a manner similar to static state space tree. The reduced matrices are : Dynamic State Space Tree Organisation – example (Contd..) : 24 Dynamic State Space Tree Organisation – example (Contd..) 1 2 3 4 5 1 ? 10 ? 0 1 ? 10 17 0 1 2 ? ? 11 2 0 1 12-11=1 ? 11 2 0 3 ? ? ? ? ? ? 3 ? 0 2 4 ? 3 12 ? 0 4 15-11=4 3 12 ? 0 5 ? 0 0 12 ? 0 11-11=0 0 0 12 ? (i) node 2 (ii) node 3 iii) No further reduction required as each row & column has a zero. Dynamic State Space Tree Organisation – example (Contd..) : 25 Dynamic State Space Tree Organisation – example (Contd..) 25 1 include <3,1> exclude <3,1> 25 2 3 36 Same as include <5,3> exclude <5,3> 28 4 5 36 include <1,4> exclude <1,4> 28 6 7 37 Dynamic State Space Tree Organisation – example : 26 Dynamic State Space Tree Organisation – example The edge selection at node 6 is { <3,1>, <5,3>, (1,4>} This corresponds to path 5,3,1,4. At this point 3 of 5 edges have been selected. The remaining 2 may be selected directly. The only possibility is {<4,2>, <2,5> }. This gives the path 5,3,1,4,2,5 with length 28. So u = 28. Next node 3 has c(3) > u. So, LCBB terminates. Computed cost (Node 4) = 25+0+3 = 28.

 User name: Comment:

July 23, 2017

July 23, 2017

July 23, 2017

July 23, 2017

July 23, 2017

July 23, 2017

Related pages

Travelling salesman problem - Wikipedia, the free encyclopedia

The travelling salesman problem (TSP) ... The problem is sometimes, especially in newer publications, referred to as Travelling Salesperson Problem.

Problem des Handlungsreisenden – Wikipedia

Das Problem des Handlungsreisenden (auch Rundreiseproblem, engl. Traveling Salesman Problem oder Traveling Salesperson Problem (TSP)) ist ein ...

Traveling Salesman Problem -- from Wolfram MathWorld

The traveling salesman problem is a problem in graph theory requiring the most efficient (i.e., least total distance) Hamiltonian cycle a salesman can take ...

The Travelling Salesperson problem - Free maths help and ...

D1 Discrete Mathematics The Travelling Salesperson problem The Nearest Neighbour Algorithm The Lower Bound Algorithm The Tour Improvement Algorithm

Traveling Salesman Problem - University of Waterloo

The Traveling Salesman Problem is one of the most intensively studied problems in computational mathematics. These pages are devoted to the history ...

The Traveling Salesperson Problem - Carnegie Mellon University

Nonadditive Recursions Up: A Tutorial on Dynamic Previous: Equipment Replacement. The Traveling Salesperson Problem. We have seen that we can solve one ...

Travelling salesman problem - Simple English Wikipedia ...

The Travelling Salesman Problem (often called TSP) is a classic algorithmic problem in the field of computer science. It is focused on optimization.