Notices
Results 1 to 1 of 1

Thread: Travelling Salesman Problem - Part 1

  1. #1 Travelling Salesman Problem - Part 1 
    Forum Freshman
    Join Date
    Nov 2012
    Posts
    9
    I have found a new solution to the Travelling Salesman Problem. I have tried the solution on all the "complete" graphs of the examples in the 2 textbooks given in the reference section in the post given below. The solution is as follows :-

    I have split the solution in parts, because the solution is not fitting in one single post. So I have given the solution as parts in different posts. For eg: This post is "Travelling Salesman Problem - Part 1". So the solution is continued in "Part 2" ,"Part 3" etc.. until it is written "End of posting".


    The solution is as follows:-


    Starter Edge method for an improved solution for the Travelling Salesman Problem


    Abstract
    This paper is mainly about a solution to the graph problem of Figure 5.23 given in the book ‘Elements of Discrete Mathematics’ by C.L.Liu.


    General note
    In the starter edge method, the edge with the least weight in a graph is selected as the beginning edge to be taken to be processed. Then from the starter edge, a starter vertex is selected. Then from the starter vertex, the ‘nearest neighbour method’ ( This method is the same method that is mentioned in the book ‘Elements of Discrete Mathematics’ by C.L.Liu in Section 5.8 of Chapter 5 ) is applied. A hamilton circuit is obtained. Collect all the edges with lesser weights which are skipped when the process for obtaining the hamilton circuit is carried out. If any lesser weight edges are not skipped when obtaining the hamilton circuit, then this hamilton circuit is the minimum weight hamilton circuit. Collect all these edges for processing in the next stage. After the hamilton circuit is obtained, then the second starter vertex from the starter edge is selected. Then from the second starter vertex, the nearest neighbour method is applied. Then during the process of obtaining the hamilton circuit, if any lesser weight edges are skipped, they are collected to be processed in the next stage. Then in the next stage, sort all the skipped edges according to their weights. Then from the least weight skipped edge, select the skipped edge as the starter edge and start the same type of process that was done at the beginning. Proceed to process all the skipped edges to obtain hamilton circuits ( If there is any hamilton circuit which did not have any skipped edges, then stop the process immediately because the possibly minimum hamilton circuit has been found.). So the process continues ( if there are more skipped edges to be processed ) in further stages until a hamilton circuit with no skipped edges is obtained or until all the skipped edges have been processed. When all the skipped edges have been processed, collect all the hamilton circuits together and find the hamilton circuit with the least weight among them. This hamilton circuit is the possibly best minimum hamilton circuit.


    Notations

    [n1,n2]
    :- It denotes the edge joining the vertices n1 and n2 in a graph where n1 and n2 are alphabets or integers. Also n1 < n2 in order to avoid duplication of edges. ‘n1’ is called the left vertex of the edge [n1,n2] and ‘n2’ is called the right vertex of the edge [n1,n2]. For eg:- [b,c] and [c,b] represent the same edge, so the edge is only represented as [b,c] where b is alphabetically less than c. Also for eg:- in the edge [b,c], ‘b’ is called the left vertex and ‘c’ is called the right vertex.

    w[n1,n2]
    :- It denotes the weight of the edge connecting the vertices n1 and n2.

    {n1}
    :- It denotes the vertex n1 of a graph where n1 is an alphabet or an integer.

    sv{n1}
    :- It denotes the ‘starter vertex’ ie:- the vertex ‘n1’ from which the construction of the hamilton circuit begins. n1 is an alphabet or integer.

    se[n1,n2]
    :- It denotes the ‘starter edge’ ie:- an edge which joins the vertices ‘n1’ and ‘n2’. n1 and n2 are alphabets or integers. The starter edge is the starting edge from which the construction of the hamilton circuit begins and is the edge which must be included in the hamilton circuit that is being formed. For the sake of convention, the first starter vertex is always taken from the left vertex of the starter edge and the second starter vertex is always taken from the right vertex of the starter edge. For eg:- in ‘se[b,c]’, sv{b} is always taken first for processing the first hamilton circuit and sv{c} is always taken second for processing the second hamilton circuit ie:- the numerically or alphabetically lesser vertex is taken first for constructing the hamilton circuit, for the purpose of convention. Also in the notation ‘se[n1,n2]’, ‘n1’ is called the left starter vertex and ‘n2’ is called the right starter vertex.

    PCm
    :- It denotes the mth partial circuit where m is an integer.

    w(PCm)
    :- It denotes the total weight of the mth partial circuit where m is an integer.

    pc(se[n1,n2],sv{n2}) = PCm
    :- ‘pc(se[n1,n2],sv{n2})’ denotes the partial circuit which has starter edge of [n1,n2] and a starter vertex of ‘n2’. Also to make the notation into shortform, this notation can also be equated to PCm (ie:- the mth partial circuit ). Also to denote the vertices present in the partial circuit, the vertices can also be represented as for eg:- ‘pc(se[n1,n2],sv{n2}) = PCm = (n1,n2,n3)’ denotes the mth partial circuit containing the vertices n1,n2 and n3. Here {n1} is connected to {n2} to form an edge [n1,n2] and {n2} is connected to {n3} to form an edge [n2,n3]. Also the above notation can be written as ‘pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm’ which also has the same meaning.

    HCm
    :- It denotes the mth hamilton circuit where m is an integer.

    w(HCm)
    :- It denotes the weight of the mth hamilton circuit where m is an integer.

    pc(se[n1,n2],sv{n2}) = PCm(HCz)
    :- It denotes the mth partial circuit of the zth hamilton circuit. Here the zth hamilton circuit is not fully formed yet, but is going to be formed later when all the vertices of the graph has been added to the partial circuit in order to form the hamilton circuit. For eg:- ‘pc(se[n1,n2],sv{n2}) = PCm(HCz) = (n1,n2,n3)’ means the mth partial circuit of the zth hamilton circuit (the zth hamilton circuit is the hamilton circuit which is going to be formed later) and consists of the vertices n1,n2 and n3. Also the above notation can be written as ‘pc(se[n1,n2],sv{n2}) = (n1,n2,n3) = PCm(HCz)’ which also has the same meaning.

    w(PCm(HCz))
    :- It denotes the weight of the mth partial circuit ( where m is an integer ) of the zth hamilton cirucit. ( The hamilton circuit will be formed later when all the vertices of the graph has been included in the partial circuit.)

    hc(se[n1,n2],sv{n2}) = HCm
    :- ‘hc(se[n1,n2],sv{n2})’ denotes the hamilton circuit which has starter edge of [n1,n2] and a starter vertex of ‘n2’. Also to make the notation into shortform, this notation can also be equated to HCm (ie:- the mth hamilton circuit ). Also to denote the vertices present in the hamilton circuit, the vertices can also be represented as, for eg:- ‘hc(se[n1,n2],sv{n2}) = HCm = (n1,n2,n3,n4)’ which denotes the mth hamilton circuit containing the vertices n1,n2,n3 and n4. Here {n1} is connected to {n2} to form the edge [n1,n2] , {n2} is connected to {n3} to form the edge [n2,n3] , {n3} is connected to {n4} to form the edge [n3,n4] and {n4} is connected to {n1} to form the edge [n1,n4]. Also the above notation can be written as ‘hc(se[n1,n2],sv{n2}) = (n1,n2,n3,n4) = HCm’ which also has the same meaning.

    w(HCm)
    :- It denotes the total weight of the mth hamilton circuit .

    Skipped edge
    :- ‘Skipped edge’ means an edge which was considered for forming a part of the hamilton circuit because of its lesser weight, but is not taken because taking this edge will not form a hamilton circuit, since addition of this edge causes more than 2 edges to be attached to a single vertex, since in a hamilton circuit, only 2 edges are allowed to be attached to a single vertex.

    Stage r
    :- It denotes the processing stage where all the skipped edges are sorted according to their weights and are taken one by one (beginning with the least weight edge) with each edge considered as a starter edge. Also the process for obtaining the hamilton circuits from the skipped edges take place in a particular stage. ‘r’ is an integer.

    Step 1
    :- It denotes the step where the first starter vertex ( ie:- the left starter vertex ) of the starter edge is taken. For eg :- in step 1 for se[b,c], sv{b} is taken, ie:- vertex b is taken as the first starter vertex. Also taking the left starter vertex as the first starter vertex for ‘step 1’ is for the purpose of convention.


    Continued in the posting Travelling Salesman Problem - Part 2.


    Reply With Quote  
     

  2.  
     

Similar Threads

  1. Deep-Space travelling, is it even possible?
    By Pendragon in forum Astronomy & Cosmology
    Replies: 90
    Last Post: August 30th, 2011, 09:52 AM
  2. Travelling into the future
    By couchSports in forum Physics
    Replies: 9
    Last Post: May 6th, 2010, 10:38 AM
  3. Travelling hotspots or travelling plates?
    By Pong in forum Earth Sciences
    Replies: 32
    Last Post: December 26th, 2009, 03:28 PM
  4. Complexity of Traveling Salesman Problem
    By diogenes in forum Mathematics
    Replies: 1
    Last Post: May 30th, 2008, 09:27 PM
  5. Complexity of Traveling Salesman Problem
    By diogenes in forum Computer Science
    Replies: 0
    Last Post: May 30th, 2008, 03:27 PM
Tags for this Thread

View Tag Cloud

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •